スターリング数

 投稿者:山中和義  投稿日:2013年12月 1日(日)10時20分19秒
  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


 

戻る