ポリアの数え上げ定理

(x1, x2, .., xn) にそれぞれ1..kの値を割り振る。

(x1, x2, .., xn) -> (x2, x3, .., xn, x1)のようにrotate出来て、その動作によって同じくなるものは同じと考える

これの数え上げをどうするかという話。

これは、 (x1, x2, .., xn) = (x1, x2, .., xn)となるもの (x1, x2, .., xn) = (x2, x3, .., xn+1)となるもの (x1, x2, .., xn) = (x3, x4, .., xn+2)となるもの .. (x1, x2, .., xn) = (xn, x1, x2, .., xn-1)となるもの を全部足してnで割ればいい。

任意の要素について(x1, x2, .., xn) = (x1+a, x2+a, .., xn+a)となる最小のaを求める。

するとb = ka(kは整数)について (x1, x2, .., xn) = (x1+b, x2+b, .., xn+b)となるので、n/a回出てくる。 さらにそれらそれぞれについて、0,1,..,a-1回rotateしたものも出てくるため結局n回出てくる。

これができると何がいいのかというと、 全部のiについて x1 = x1+i = x1+2i = x1+3i .. x2 = x2+i = x2+2i = x2+3i .. x3 = x2+i = x3+2i = x3+3i .. .. という条件のもとでの数え上げさえ出来ればよくて回転して一致という条件を消せるから。