概要
これを見てバーンサイドの補題というものが気になったのでいろいろ試してみることにした。
問題
正多面体の各面に対して正の整数を定める方法で、全部の面の和が$S$になる方法は何通りか。ただし回転して一致するものは同じとみなす。
立方体
ABC198-Fは同じことをしている。
立方体[-1,1]^3における回転を考えてみる。回転の構造は群をなしている
24個の回転方法を全て数えるのは面倒だが、共役元に関しては本質的に同じなので、共役類ごとに考えればよい。
具体的には以下の5つとなる。
- x=y,z=0に対して180°回転（6つ）
- x=y=zに対して120°回転（8つ）
- x軸に対して180°回転（3つ）
- x軸に対して90°回転（6つ）
- 回転しない（1つ）
ちなみに立方体の回転の群は4次対称群と同型である。これは4本の対角線を置換する割り当てを考えれば良い。
これについて、数え上げは以下のようになる。
- 2a+2b+2c=S
- 3a+3b=S
- a+2b+2c+d=S
- a+4b+c=S
- a+b+c+d+e+f=S
つまり、
$$\frac{1}{24}\left(\frac{6}{(1-x^2)^3}+\frac{8}{(1-x^3)^2}+\frac{3}{(1-x)^2(1-x^2)^2}+\frac{6}{(1-x)^2(1-x^4)}+\frac{1}{(1-x)^6}\right)$$
の$x^{S-6}$の係数を求めれば良い。
と、Cubeという問題についてはこれでOKなのだが、他の正多面体でも試してみようと思う。
正四面体
正四面体の群は4次の交代群である。4つの頂点に対する置換のうち、光学異性体を除いたものとイメージすればよい。
(1,1,1,),(-1,-1,1),(-1,1,-1),(1,-1,-1)を頂点にもつ正四面体の回転を考えた時、これは立方体の回転のうち、正四面体が不変となるものだけ考えればよい。すると2.3.5.だけが残る。
つまり、
(2) x=y=zに対して120°回転（8つ）
(3) x軸に対して180°回転（3つ）
(5) 回転しない（1つ）
であって、
(2) 3a+b=S,8
(3) 2a+2b=S,3
(5) a+b+c+d=S,1
となるため、最終的な場合の数は
$$\frac{1}{12}\left(\frac{8}{(1-x)(1-x^3)}+\frac{3}{(1-x^2)^2}+\frac{1}{(1-x)^4}\right)$$
の$x^{S-4}$の係数を求めれば良い。
正八面体
正八面体の群は正六面体の群と同型である。よって、|x|+|y|+|z|=1からなる正八面体を考えたとき、
- x=y,z=0に対して180°回転（6つ）
- x=y=zに対して120°回転（8つ）
- x軸に対して180°回転（3つ）
- x軸に対して90°回転（6つ）
- 回転しない（1つ）
となる。これらは、
- 2a+2b+2c+2d=S,6
- a+3b+3c+d=S,8
- 2a+2b+2c+2d=S,3
- 4a+4b=S,6
- a+b+c+d+e+f+g+h=S,1
より、最終的な答えは
$$\frac{1}{24}\left(\frac{6}{(1-x^2)^4}+\frac{8}{(1-x)^2(1-x^3)^2}+\frac{3}{(1-x^2)^4}+\frac{6}{(1-x^4)^2}+\frac{1}{(1-x)^8}\right)$$
の$x^{S-8}$の係数を求めればよい。
正十二面体
正十二面体の群は5次交代群である。位数が60個あって大変そうだが、共役類は4つなので計算はできそう…？
- 正五角形の中心を回転軸として72°回転（24個）
- 反対側の頂点を結んだ直線を回転軸として120°回転（20個）
- 反対側の辺の中点同士を結んだ直線を回転軸として180°回転（15個）
- 回転しない（1個）
これについて、数えてみると
- a+5b+5c+d=S,24
- 3a+3b+3c+3d=S,20
- 2a+2b+2c+2d+2e+2f=S,15
- a+b+...=S,1
よって答えは
$$\frac{1}{60}\left(\frac{24}{(1-x)^2(1-x^5)^2}+\frac{20}{(1-x^3)^4}+\frac{15}{(1-x^2)^6}+\frac{1}{(1-x)^{12}}\right)$$
について、$x^{S-12}$の係数を求めればよい。
正二十面体
正二十面体の群は正十二面体と同型で5次交代群である。これについても共役類で考える。
- 反対側の頂点を結んだ直線を回転軸として72°回転（24個）
- 正三角形の中心と垂直な直線を回転軸として120°回転（20個）
- 反対側の辺の中点同士を結んだ直線を回転軸として180°回転（15個）
- 回転しない（1個）
これについてもおなじように数えると、
- 5a+5b+5c+5d=S,24
- a+3b+3c+3d+3e+3f+3g+h=S,20
- 2a+2b+2c+...=S,15
- a+b+c+...=S,1
よって最終的な答えは
$$\frac{1}{60}\left(\frac{24}{(1-x^5)^4}+\frac{20}{(1-x)^2(1-x^3)^6}+\frac{15}{(1-x^2)^{10}}+\frac{1}{(1-x)^{20}}\right)$$
について、$x^{S-20}$の係数を求めればよい。
最後に
こうして、母関数を有理関数形式で求めることができた場合、漸化式ができるので、行列累乗を使うと$O(\log{S})$で計算することができる。競技プログラミングにおいては$\mod 998244353$みたいな剰余で計算することが多い。
他にも半正多面体でも色々試すことはできそうだけど、大変そうなのでやめておく。
