|
|
n文字の置換のうち、m個の巡回置換の積（積の順序は問わない）で表される全体の個数
例 n=5,m=3の場合
(1 2)(3 4)(5)、(1)(2)(3 4 5)など
答え
n文字の置換は、n!通り。
その中から、m個の巡回置換を探す。
便宜上
[1 2 3 4 5] =(1)(2)(3 4 5)
[1 2 4 5 3]
を
[1 2 4 5 3] =(1)(2)(3 4 5)
と表す。
（終り）
PUBLIC NUMERIC n,m
LET n=5
LET m=3
DIM a(n)
FOR i=1 TO n !最初の並び 1,2,3,…,n
LET a(i)=i
NEXT i
PUBLIC NUMERIC c !場合の数
LET c=0
PUBLIC NUMERIC s1(100) !n段目 s1(n,k)
MAT s1=ZER(n)
CALL perm(a,1)
MAT PRINT s1;
END
EXTERNAL SUB perm(a(),k) !辞書順序でn-順列（n!通り）を生成する
IF k=n THEN !すべて並んだなら
PRINT "["; !置換を表示する
FOR i=1 TO n
PRINT a(i);
NEXT i
PRINT "] = ";
LET p=0 !巡回置換の個数
DIM f(n) !篩い
MAT f=ZER
FOR i=1 TO n !n文字
IF f(i)=0 THEN !現れていないなら
LET p=p+1
PRINT "("; !巡回置換を表示する
LET t=i
DO
PRINT t;
LET f(t)=1
LET t=a(t) !次へ
LOOP UNTIL t=i !巡回するまで
PRINT ")";
END IF
NEXT i
IF p=m THEN !m個なら
LET c=c+1
PRINT " ←";c
ELSE
PRINT
END IF
LET s1(p)=s1(p)+1 !n!=Σs1(n,p)
ELSE
FOR i=k TO n
LET t=a(i)
FOR j=i-1 TO k STEP -1
LET a(j+1)=a(j)
NEXT j
LET a(k)=t
CALL perm(a,k+1)
LET t=a(k)
FOR j=k TO i-1
LET a(j)=a(j+1)
NEXT j
LET a(i)=t
NEXT i
END IF
END SUB
実行結果
[ 1 2 3 4 5 ] = ( 1 )( 2 )( 3 )( 4 )( 5 )
[ 1 2 3 5 4 ] = ( 1 )( 2 )( 3 )( 4 5 )
[ 1 2 4 3 5 ] = ( 1 )( 2 )( 3 4 )( 5 )
[ 1 2 4 5 3 ] = ( 1 )( 2 )( 3 4 5 ) ← 1
[ 1 2 5 3 4 ] = ( 1 )( 2 )( 3 5 4 ) ← 2
[ 1 2 5 4 3 ] = ( 1 )( 2 )( 3 5 )( 4 )
[ 1 3 2 4 5 ] = ( 1 )( 2 3 )( 4 )( 5 )
[ 1 3 2 5 4 ] = ( 1 )( 2 3 )( 4 5 ) ← 3
[ 1 3 4 2 5 ] = ( 1 )( 2 3 4 )( 5 ) ← 4
[ 1 3 4 5 2 ] = ( 1 )( 2 3 4 5 )
[ 1 3 5 2 4 ] = ( 1 )( 2 3 5 4 )
[ 1 3 5 4 2 ] = ( 1 )( 2 3 5 )( 4 ) ← 5
[ 1 4 2 3 5 ] = ( 1 )( 2 4 3 )( 5 ) ← 6
[ 1 4 2 5 3 ] = ( 1 )( 2 4 5 3 )
[ 1 4 3 2 5 ] = ( 1 )( 2 4 )( 3 )( 5 )
[ 1 4 3 5 2 ] = ( 1 )( 2 4 5 )( 3 ) ← 7
[ 1 4 5 2 3 ] = ( 1 )( 2 4 )( 3 5 ) ← 8
[ 1 4 5 3 2 ] = ( 1 )( 2 4 3 5 )
[ 1 5 2 3 4 ] = ( 1 )( 2 5 4 3 )
[ 1 5 2 4 3 ] = ( 1 )( 2 5 3 )( 4 ) ← 9
[ 1 5 3 2 4 ] = ( 1 )( 2 5 4 )( 3 ) ← 10
[ 1 5 3 4 2 ] = ( 1 )( 2 5 )( 3 )( 4 )
[ 1 5 4 2 3 ] = ( 1 )( 2 5 3 4 )
[ 1 5 4 3 2 ] = ( 1 )( 2 5 )( 3 4 ) ← 11
[ 2 1 3 4 5 ] = ( 1 2 )( 3 )( 4 )( 5 )
[ 2 1 3 5 4 ] = ( 1 2 )( 3 )( 4 5 ) ← 12
[ 2 1 4 3 5 ] = ( 1 2 )( 3 4 )( 5 ) ← 13
[ 2 1 4 5 3 ] = ( 1 2 )( 3 4 5 )
[ 2 1 5 3 4 ] = ( 1 2 )( 3 5 4 )
[ 2 1 5 4 3 ] = ( 1 2 )( 3 5 )( 4 ) ← 14
[ 2 3 1 4 5 ] = ( 1 2 3 )( 4 )( 5 ) ← 15
[ 2 3 1 5 4 ] = ( 1 2 3 )( 4 5 )
[ 2 3 4 1 5 ] = ( 1 2 3 4 )( 5 )
[ 2 3 4 5 1 ] = ( 1 2 3 4 5 )
[ 2 3 5 1 4 ] = ( 1 2 3 5 4 )
[ 2 3 5 4 1 ] = ( 1 2 3 5 )( 4 )
[ 2 4 1 3 5 ] = ( 1 2 4 3 )( 5 )
[ 2 4 1 5 3 ] = ( 1 2 4 5 3 )
[ 2 4 3 1 5 ] = ( 1 2 4 )( 3 )( 5 ) ← 16
[ 2 4 3 5 1 ] = ( 1 2 4 5 )( 3 )
[ 2 4 5 1 3 ] = ( 1 2 4 )( 3 5 )
[ 2 4 5 3 1 ] = ( 1 2 4 3 5 )
[ 2 5 1 3 4 ] = ( 1 2 5 4 3 )
[ 2 5 1 4 3 ] = ( 1 2 5 3 )( 4 )
[ 2 5 3 1 4 ] = ( 1 2 5 4 )( 3 )
[ 2 5 3 4 1 ] = ( 1 2 5 )( 3 )( 4 ) ← 17
[ 2 5 4 1 3 ] = ( 1 2 5 3 4 )
[ 2 5 4 3 1 ] = ( 1 2 5 )( 3 4 )
[ 3 1 2 4 5 ] = ( 1 3 2 )( 4 )( 5 ) ← 18
[ 3 1 2 5 4 ] = ( 1 3 2 )( 4 5 )
[ 3 1 4 2 5 ] = ( 1 3 4 2 )( 5 )
[ 3 1 4 5 2 ] = ( 1 3 4 5 2 )
[ 3 1 5 2 4 ] = ( 1 3 5 4 2 )
[ 3 1 5 4 2 ] = ( 1 3 5 2 )( 4 )
[ 3 2 1 4 5 ] = ( 1 3 )( 2 )( 4 )( 5 )
[ 3 2 1 5 4 ] = ( 1 3 )( 2 )( 4 5 ) ← 19
[ 3 2 4 1 5 ] = ( 1 3 4 )( 2 )( 5 ) ← 20
[ 3 2 4 5 1 ] = ( 1 3 4 5 )( 2 )
[ 3 2 5 1 4 ] = ( 1 3 5 4 )( 2 )
[ 3 2 5 4 1 ] = ( 1 3 5 )( 2 )( 4 ) ← 21
[ 3 4 1 2 5 ] = ( 1 3 )( 2 4 )( 5 ) ← 22
[ 3 4 1 5 2 ] = ( 1 3 )( 2 4 5 )
[ 3 4 2 1 5 ] = ( 1 3 2 4 )( 5 )
[ 3 4 2 5 1 ] = ( 1 3 2 4 5 )
[ 3 4 5 1 2 ] = ( 1 3 5 2 4 )
[ 3 4 5 2 1 ] = ( 1 3 5 )( 2 4 )
[ 3 5 1 2 4 ] = ( 1 3 )( 2 5 4 )
[ 3 5 1 4 2 ] = ( 1 3 )( 2 5 )( 4 ) ← 23
[ 3 5 2 1 4 ] = ( 1 3 2 5 4 )
[ 3 5 2 4 1 ] = ( 1 3 2 5 )( 4 )
[ 3 5 4 1 2 ] = ( 1 3 4 )( 2 5 )
[ 3 5 4 2 1 ] = ( 1 3 4 2 5 )
[ 4 1 2 3 5 ] = ( 1 4 3 2 )( 5 )
[ 4 1 2 5 3 ] = ( 1 4 5 3 2 )
[ 4 1 3 2 5 ] = ( 1 4 2 )( 3 )( 5 ) ← 24
[ 4 1 3 5 2 ] = ( 1 4 5 2 )( 3 )
[ 4 1 5 2 3 ] = ( 1 4 2 )( 3 5 )
[ 4 1 5 3 2 ] = ( 1 4 3 5 2 )
[ 4 2 1 3 5 ] = ( 1 4 3 )( 2 )( 5 ) ← 25
[ 4 2 1 5 3 ] = ( 1 4 5 3 )( 2 )
[ 4 2 3 1 5 ] = ( 1 4 )( 2 )( 3 )( 5 )
[ 4 2 3 5 1 ] = ( 1 4 5 )( 2 )( 3 ) ← 26
[ 4 2 5 1 3 ] = ( 1 4 )( 2 )( 3 5 ) ← 27
[ 4 2 5 3 1 ] = ( 1 4 3 5 )( 2 )
[ 4 3 1 2 5 ] = ( 1 4 2 3 )( 5 )
[ 4 3 1 5 2 ] = ( 1 4 5 2 3 )
[ 4 3 2 1 5 ] = ( 1 4 )( 2 3 )( 5 ) ← 28
[ 4 3 2 5 1 ] = ( 1 4 5 )( 2 3 )
[ 4 3 5 1 2 ] = ( 1 4 )( 2 3 5 )
[ 4 3 5 2 1 ] = ( 1 4 2 3 5 )
[ 4 5 1 2 3 ] = ( 1 4 2 5 3 )
[ 4 5 1 3 2 ] = ( 1 4 3 )( 2 5 )
[ 4 5 2 1 3 ] = ( 1 4 )( 2 5 3 )
[ 4 5 2 3 1 ] = ( 1 4 3 2 5 )
[ 4 5 3 1 2 ] = ( 1 4 )( 2 5 )( 3 ) ← 29
[ 4 5 3 2 1 ] = ( 1 4 2 5 )( 3 )
[ 5 1 2 3 4 ] = ( 1 5 4 3 2 )
[ 5 1 2 4 3 ] = ( 1 5 3 2 )( 4 )
[ 5 1 3 2 4 ] = ( 1 5 4 2 )( 3 )
[ 5 1 3 4 2 ] = ( 1 5 2 )( 3 )( 4 ) ← 30
[ 5 1 4 2 3 ] = ( 1 5 3 4 2 )
[ 5 1 4 3 2 ] = ( 1 5 2 )( 3 4 )
[ 5 2 1 3 4 ] = ( 1 5 4 3 )( 2 )
[ 5 2 1 4 3 ] = ( 1 5 3 )( 2 )( 4 ) ← 31
[ 5 2 3 1 4 ] = ( 1 5 4 )( 2 )( 3 ) ← 32
[ 5 2 3 4 1 ] = ( 1 5 )( 2 )( 3 )( 4 )
[ 5 2 4 1 3 ] = ( 1 5 3 4 )( 2 )
[ 5 2 4 3 1 ] = ( 1 5 )( 2 )( 3 4 ) ← 33
[ 5 3 1 2 4 ] = ( 1 5 4 2 3 )
[ 5 3 1 4 2 ] = ( 1 5 2 3 )( 4 )
[ 5 3 2 1 4 ] = ( 1 5 4 )( 2 3 )
[ 5 3 2 4 1 ] = ( 1 5 )( 2 3 )( 4 ) ← 34
[ 5 3 4 1 2 ] = ( 1 5 2 3 4 )
[ 5 3 4 2 1 ] = ( 1 5 )( 2 3 4 )
[ 5 4 1 2 3 ] = ( 1 5 3 )( 2 4 )
[ 5 4 1 3 2 ] = ( 1 5 2 4 3 )
[ 5 4 2 1 3 ] = ( 1 5 3 2 4 )
[ 5 4 2 3 1 ] = ( 1 5 )( 2 4 3 )
[ 5 4 3 1 2 ] = ( 1 5 2 4 )( 3 )
[ 5 4 3 2 1 ] = ( 1 5 )( 2 4 )( 3 ) ← 35
24 50 35 10 1
|
|