円順列（1）

数学 プログラミング

数え上げ組合せ論入門 (日評数学選書)

より。
例えば、0を3つと1を3つの順列は、



 0 0 0 1 1 1

 0 0 1 0 1 1

  ...

などあり、6C3個あるわけだが、
これを円状に配置したものを円順列という。



   0       1

 1   1   0   0

 1   0   1   0

   0       1

この2つは、回せば同じなので同じとみなす。
これを一般円順列とここでは呼び、
この個数を数える。
一般的な公式はないらしい。
上の例だと、



   0       0       0       0

 1   1   1   0   1   1   0   1

 1   0   1   0   0   1   1   0

   0       1       0       1

この4つしかない。
これを、C3,3と表すことにする。


プログラムを作って色々数えてみよう。
順列を生成するプログラムを作って、
回してみて一致したらアウト、とか。

結果

C1,1 = 1
C2,2 = 2
C3,3 = 4
C4,4 = 10
C5,5 = 26
C6,6 = 80
C7,7 = 246
C8,8 = 810
C9,9 = 2704
C10,10 = 9252
C11,11 = 32066
C12,12 = 112720
C13,13 = 400024
C14,14 = 1432860

雑に作ったのでメモリがここで厳しい。
少し工夫してメモリを減らしてみた。

C15,15 = 5170604