C3,3を考える。
例えば、
0 0 0 1 1 1
など、順列は6個の中から0を3個選ぶから、
6C3個ある。
が、これを回したもの、
0 0 1 1 1 0
なども円順列としては同じである。
円順列としては同じでも別の順列になるのは、
基本的に6種類ある。
しかし、
0 1 0 1 0 1
は2つ移動すれば同じになるので、
周期2で重複は2種類である。
周期は6の約数になるが、
奇数の周期はありえない、
例えば周期3だと、
0 1 1 0 1 1
などと0と1の数が違ってしまうから。
というわけで、この場合の周期は2と6のみである。
というわけで、
全ての順列は6C3=20個、
周期が2のものは、2C1個だが、
周期2だから2つダブっているから、
2C1/2個
周期6だけど周期2でないものは、
6C3-2C1個だが、
周期6だから6つずつダブっているから、
(6C3-2C1)/6個、
合わせて、4個となる。
この考え方は、nが素数のときに適用できる。
Cp,p = (2pCp - 2) / 2p + 1
具体的には、
C19,19 = 930138522
C23,23 = 178987624514
C29,29 = 518401146543812
C31,31 = 7506908923471954
一般の場合については、月曜日くらいに。
