rotsuka691’s diary

ABC198F-Cubeは、群論と母関数の知識を活かすことができるという意味で典型的な組合せ論の問題です。

結論から書くと、入力 ${S}$ に対して ${n=S-6}$ として、答えは

${\begin{align} c(n):=\frac{1}{24}\Bigg(&\binom{n+5}{5}+6\binom{\lfloor n/2\rfloor+3}{3}+24\binom{\lfloor n/4\rfloor+2}{2}\\ &+3e_2(n)\binom{n/2+2}{2}+8e_3(n)\left(n/3+1\right)-6\big(3-r_4(n)\big)\big(\lfloor n/4\rfloor+1\big)\Bigg)\cdots(\star) \end{align}}$

を ${998244353}$ で割った余りです。ただし、 ${\lfloor x\rfloor}$ は床関数、 ${r_m(n)}$ は ${n}$ を ${m}$ で割った余り、

${\begin{align} e_m(n) := \left\{\begin{array}{cc} 1, & {\rm if}\, m | n\\ 0, & {\rm otherwise} \end{array}\right. \end{align}}$

とします。

C++による解答例：
atcoder.jp

公式の解説にも引用されているOEISのA054473にあるように、 ${c(n)}$ の母関数は

${\begin{align} g(z):=\frac{3z^6+z^5+z^4+1}{(1-z)(1-z^2)^2(1-z^3)^2(1-z^4)}=\sum_{n=0}^\infty c(n) z^n \end{align}}$

です。これを示したのち、上に掲げた ${c(n)}$ の閉じた表式 ${(\star)}$ を導出してみましょう。

固定点を数える

立方体の回転について

立方体（正六面体）を自分自身に移すような回転（向きを変えない=反転を含まない）の全体は、位数24の正六面体群 ${\mathcal{C}}$ をなします。この群は立方体の各面の中心を結んでできる正八面体に対して同時に作用するため、しばしば正八面体群と呼ばれます。

立方体の4本の対角線 ${\alpha, \beta, \gamma, \delta}$ に注目すると、回転と同時にこれらに対して置換として作用していることが分かります。実は立方体の回転によって対角線たちを移し合う全ての置換が可能で、逆にある置換はただ一つの立方体の回転に対応します。すなわち、正六面体群 ${\mathcal{C}}$ は4次対称群 ${{\frak S}_4}$ と同型です。このことを知っていると、あとで回転を列挙するときに見通しが良くなります。

f:id:rotsuka691:20210414001639p:plain — 立方体の4本の対角線は回転によって互いに移り合う

Cauchy-Frobeniusの補題

群論の言葉を使って問題を言い換えましょう。元の問題では和が ${S}$ の正の整数を各面に書くことになっていますが、全ての面から1を引いて和が ${n=S-6}$ の非負整数を書くことを考えても同じことなので、以後これを考えることにします。

和が ${n}$ である6つの非負整数の組からなる集合を $X_n$ とする;

${\begin{align} X_n := \left\{(x_1, x_2, x_3, x_4, x_5, x_6)\in \mathbb{Z}_{\geq 0}^6\, \middle|\, \sum_{i=1}^6 x_i = n\right\} \end{align}}$

${X_n}$ の元の各成分を立方体の各面に割り当てる（「書き込む」）。立方体の回転に伴って ${X_n}$ 上の置換が引き起こされるとき、この作用全体による ${X_n}$ の軌道の個数を求めよ。

一般に、集合 ${X}$ に対して有限群 ${G}$ が作用するとき、軌道（ ${G}$ の作用による ${X}$ の同値類）の個数は ${G}$ の各元の不動点の個数の平均になります。これを Burnsideの補題、あるいは Cauchy-Frobeniusの補題 と呼びます。

${\begin{align} \left|X/G\right| = \frac{1}{|G|}\sum_{g \in G} \left|\left\{x\in X\,\middle|\,gx=x\right\}\right|. \end{align}}$

Burnside's lemma - Wikipedia
Orbit-counting theorem - Groupprops

群の各元に対して不動点を数えるのは、軌道の代表元を漏れなく列挙することに比べれば容易です。実際には全ての元を調べる必要すらなく、共役類の代表元に対して数え上げれば十分です。これは、群のふたつの元が同じ共役類に属していれば、作用する有限集合に引き起こす置換の型が一致するためです（逆は成り立ちません）。

${x_1,\cdots, x_6}$ は下の図に示す特定の割り当てかたを考えることにします。

f:id:rotsuka691:20210414004333p:plain — 各面に変数を割り当てる

f:id:rotsuka691:20210414004403p:plain — 展開図

立方体の回転に応じて各変数がどのように移り合うか調べていきます。

不動点を数える

正六面体群 ${\mathcal{C}}$ のある元 ${g\in \mathcal{C}}$ に対して、 ${g}$ の作用による ${X_n}$ の不動点の集合を ${{\rm Fix}_n(g)}$ で表すことにします。Cauchy-Frobeniusの定理から、

${\begin{align} c(n) = \frac{1}{|\mathcal{C}|}\sum_{g\in \mathcal{C}} \left|{\rm Fix}_n(g)\right| \end{align}}$

です。記号の濫用にはなりますが、共役類 ${{\rm Conj}}$ に対して ${g\in {\rm Conj}}$ の不動点の集合も ${{\rm Fix}_n({\rm Conj})}$ で表すことにします。正六面体群の各共役類に含まれる元に対して不動点を数えましょう。

正六面体群 ${\mathcal{C}}$ は、回転の様子に対応して以下に挙げる5つの共役類（順に ${E, A, B, C, D}$ とします）に分割されます；

${\begin{align} \mathcal{C} = E \sqcup A \sqcup B \sqcup C \sqcup D. \end{align}}$

恒等: 共役類E

恒等写像、すなわち単位元はただひとつです。当然ですが、「何も動かさない」という作用に関する不動点は作用する対象全てです。したがって、

${\begin{align} {\rm Fix}_n(E) = X_n. \end{align}}$

向かい合う面の中心を結ぶ直線に関する1/2回転: 共役類A

このような回転は向かい合う面のペアのそれぞれに対してひとつ存在するため、合わせて3つです。

上下の面 ${x_3, x_4}$ 以外は向かい合う面に移り合います。置換のサイクル表記では ${(x_1 x_6)(x_2 x_5)(x_3)(x_4)}$ です。このとき対角線に対しては ${(\alpha\gamma)(\beta\delta)}$ という置換が引き起こされています。

f:id:rotsuka691:20210414203739p:plain — 向かい合う面の中心を結ぶ直線に関する回転

この作用に対する不動点であるためには ${x_1=x_6}$ かつ ${x_2=x_5}$ であることが必要十分です。したがって、

${\begin{align} {\rm Fix}_n(A) = \left\{(x_1, x_2, x_3, x_4)\in \mathbb{Z}_{\geq 0}^4\, \middle|\, 2x_1+2x_2+x_3+x_4 = n\right\} \subset X_n. \end{align}}$

以下同じ要領で調べられるため、概要のみ書くことにします。

対角線に関する1/3回転: 共役類B

このような回転は4本の各対角線に対して右/左ねじどちらに回すかに応じて存在するため、合わせて8つです。

面に書かれた数の置換： ${(x_1x_2x_3)(x_4x_6x_5)}$
対角線の置換： ${(\alpha)(\beta\delta\gamma)}$

${\begin{align} {\rm Fix}_n(B) = \left\{(x_1, x_4)\in \mathbb{Z}_{\geq 0}^2\, \middle|\, 3x_1+3x_4 = n\right\} \subset X_n. \end{align}}$

f:id:rotsuka691:20210414203808p:plain — 対角線に関する回転

向かい合う辺の中点を結ぶ直線に関する1/2回転: 共役類C

このような回転は向かい合う辺のペアごとに存在するため、合わせて6つです。

面に書かれた数の置換： ${(x_1x_3)(x_2x_5)(x_4x_6)}$
対角線の置換： ${(\alpha\delta)(\beta\gamma)}$

${\begin{align} {\rm Fix}_n(C) = \left\{(x_1, x_2, x_4)\in \mathbb{Z}_{\geq 0}^3\, \middle|\, 2x_1+2x_2+2x_4 = n\right\} \subset X_n. \end{align}}$

f:id:rotsuka691:20210414203836p:plain — 向かい合う辺の中点を結ぶ直線に関する回転

向かい合う面の中心を結ぶ直線に関する1/4回転: 共役類D

回転軸は ${A}$ と同じで、回転角だけが異なります。このような回転は各面に対して右ねじの向きでひとつずつ存在するため、合わせて6つです。

面に書かれた数の置換： ${(x_1x_2x_6x_5)(x_3)(x_4)}$
対角線の置換： ${(\alpha\beta\gamma\delta)}$

${\begin{align} {\rm Fix}_n(D) = \left\{(x_1, x_3, x_4)\in \mathbb{Z}_{\geq 0}^3\, \middle|\, 4x_1+x_3+x_4 = n\right\} \subset X_n. \end{align}}$

以上の観察を表にまとめます。

${\begin{array}{ccccc} \mbox{共役類} & |\mbox{共役類}|\,\, & \mbox{面の置換の型} & \mbox{対角線の置換の型} & {\rm Fix}(\mbox{共役類})\\ \hline E &1&1^6&1^4& X_n \\ A &3&1^22^2&2^2& \left\{(x_1, x_2, x_3, x_4)\in \mathbb{Z}_{\geq 0}^4\, \middle|\, x_1+x_2+2x_3+2x_4 = n\right\}\\ B &8&3^2&1^13^1& \left\{(x_1, x_2)\in \mathbb{Z}_{\geq 0}^2\, \middle|\, 3x_1+3x_2 = n\right\}\\ C &6&2^3&1^22^1& \left\{(x_1, x_2, x_3)\in \mathbb{Z}_{\geq 0}^3\, \middle|\, 2x_1+2x_2+2x_3 = n\right\} \\ D &6&1^24^1&1^22^1&\left\{(x_1, x_2, x_3)\in \mathbb{Z}_{\geq 0}^3\, \middle|\, x_1+x_2+4x_3 = n\right\} \\ \hline \end{array}}$

母関数を展開する

共役類 ${{\rm Conj}}$ に対して、 ${|{\rm Fix}_n({\rm Conj})|}$ の母関数を ${g_{{\rm Conj}}(z)}$ とします。

${\begin{align} g_{{\rm Conj}}(z) := \sum_{n=0}^\infty |{\rm Fix}_n({\rm Conj})|z^n. \end{align}}$

一般に、正整数 ${m}$ と ${(a_1,\cdots,a_m)}$ に対して

${\begin{align} \sum_{n=0}^\infty \left|\left\{(x_1,\cdots,x_m)\in \mathbb{Z}^m_{\geq 0}\,\middle|\, \sum_{i=1}^m a_i x_i=n\right\}\right| z^n = \prod_{i=1}^m \frac{1}{(1-z^{a_i})} \end{align}}$

ですから、上の表より

${\begin{align} g_E(z) &= \frac{1}{(1-z)^6},\\ g_A(z) &= \frac{1}{(1-z)^2(1-z^2)^2},\\ g_B(z) &= \frac{1}{(1-z^3)^2},\\ g_C(z) &= \frac{1}{(1-z^2)^3},\\ g_D(z) &= \frac{1}{(1-z)^2(1-z^4)} \end{align}}$

が分かります。ここにCauchy-Frobeniusの補題を利用すると、所望の ${c(n)}$ の母関数は

${\begin{align} g(z) &= \frac{1}{24} \left(g_E(z) + 3g_A(z) + 8 g_B(z) + 6g_C(z) + 6g_D(z)\right)\\ &=\frac{3z^6+z^5+z^4+1}{(1-z)(1-z^2)^2(1-z^3)^2(1-z^4)} \end{align}}$

と定まります。こうしてひとつにまとまりましたが、展開するにあたっては共役類ごとに見ていくと簡単です。

共役類Eに対する母関数

${ g_E(z)}$ を展開するのはやさしいです。これは重複組合せの母関数です。

${\begin{align} g_E(z) = \sum_{n=0}\binom{n+5}{5} z^n. \end{align}}$

共役類B,Cに対する母関数

これもほぼ重複組合せの母関数ですが、 ${z}$ の冪のみが異なります。

${\begin{align} g_B(z) &= \sum_{n=0}^\infty \binom{n+1}{1} z^{3n} = \sum_{3|n,\, n\geq 0}^\infty \left(n/3+1\right) z^n, \\ g_C(z) &= \sum_{n=0}^\infty \binom{n+2}{2} z^{2n}=\sum_{2|n,\, n\geq 0}^\infty \binom{n/2+2}{2} z^n, \end{align}}$

共役類A,Dに対する母関数

このふたつだけ少し工夫が要ります。あるいはこれくらいなら公式集を持っておくべきなのかもしれません。最初の数項を求めてOEISへ検索しに向かうのも一手（AがA006918、DがA001972）。

手順としては、分母を ${(1-z^k)}$ の冪で表して重複組合せの母関数の線形和に帰着させることになります。

${\begin{align} g_A(z) &= \frac{1}{(1-z)^2(1-z^2)^2}\\ &= \frac{(1+z)^2}{(1-z^2)^4}\\ &= \frac{2+2z-(1-z^2)}{(1-z^2)^4}\\ &= \frac{2(1+z)}{(1-z^2)^4} + \frac{-1}{(1-z^2)^3}\\ &= 2(1+z) \sum_{n=0}^\infty \binom{n+3}{3} z^{2n} - \sum_{n=0}^\infty \binom{n+2}{2} z^{2n}\\ &= 2\sum_{n=0}^\infty \binom{\lfloor n/2\rfloor+3}{3} z^{n} - \sum_{2|n,\,n\geq 0}^\infty \binom{n/2+2}{2} z^{n},\\ g_D(z) &= \frac{1}{(1-z)^2(1-z^4)}\\ &= \frac{(1+z+z^2+z^3)^2}{(1-z^4)^3}\\ &= \frac{4(1+z+z^2+z^3) - (1-z^4)(3+2z+z^2)}{(1-z^4)^3}\\ &= 4(1+z+z^2+z^3) \sum_{n=0}^\infty \binom{z+2}{2} z^{4n} - (3+2z+z^2)\sum_{n=0} \binom{n+1}{1} z^{4n}\\ &= 4\sum_{n=0}^\infty \binom{\lfloor n/4\rfloor+2}{2} z^{n} - \sum_{n=0} \left(3-r_4(n)\right)\left(\lfloor n/4\rfloor+1\right) z^{n}.\\ \end{align}}$

以上から、 ${g(z)}$ の展開が得られ、まとめると式 ${(\star)}$ が導かれます。おつかれさまでした。

おまけ1

上の表から見て取れるように、各共役類は面の置換の型によって6の分割に対応します。ここでは6の分割11通りのうち5つが登場しましたが、残りの6つも示しておきましょう。

1+1+1+1+2

${\begin{align} \frac{1}{(1-z)^4(1-z^2)} &= \frac{8(1+z)}{(1-z^2)^5} + \frac{-4(2+z)}{(1-z^2)^4} + \frac{1}{(1-z^2)^3}\\ &= \sum_{n=0} 8\binom{\lfloor n/2\rfloor + 4}{4} z^n + \sum_{n=0}^\infty 4\left(r_2(n)-2\right) \binom{\lfloor n/2\rfloor+3}{3}z^n + \sum_{2|n,\,n\geq 0} \binom{n/2+2}{2}z^n. \end{align}}$

1+1+1+3

${\begin{align} \frac{1}{(1-z)^3(1-z^3)} &= \frac{1}{(1-z^3)^2} + \frac{-3(1+2z+3z^2)}{(1-z^3)^3} + \frac{9(1+z+z^2)}{(1-z^3)^4}\\ &= \sum_{3|n,\,n\geq 0} (n/3+1)z^n + \sum_{n=0}^\infty 3\left(-r_3(n)-1\right) \binom{\lfloor n/3\rfloor+2}{2} z^n + \sum_{n=0}^\infty 9 \binom{\lfloor n/3\rfloor+3}{3}z^n. \end{align}}$

1+2+3

${\begin{align} \frac{1}{(1-z)(1-z^2)(1-z^3)} &=\frac{6(1+z+z^2+z^3+z^4+z^5)}{(1-z^6)^3} + \frac{-(6+5z+4z^2+3z^3+2z^4+z^5)}{(1-z^6)^2} +\frac{1}{1-z^6} \\ &=\sum_{n=0}^\infty \binom{\lfloor n/6\rfloor+2}{2} z^n +\sum_{n=0}^\infty \left(r_6(n)-6\right)\left(\lfloor n/6\rfloor+1\right) z^n + \sum_{6|n,\,n\geq 0} z^n. \end{align}}$

1+5

${\begin{align} \frac{1}{(1-z)(1-z^5)} &= \frac{1+z+z^2+z^3+z^4}{(1-z^5)^2}\\ &= \sum_{n=0}^\infty \left(\lfloor n/5\rfloor+1\right)z^n \end{align}}$

2+4

${\begin{align} \frac{1}{(1-z^2)(1-z^4)} &=\frac{1+z^2}{(1-z^4)^2}\\ &= \sum_{2|n,\, n\geq 0} \left(\lfloor n/4\rfloor+1\right)z^n \end{align}}$

6

${\begin{align} \frac{1}{1-z^6} &= \sum_{6|n\,n\geq 0} z^n \end{align}}$

おまけ2

今回の問題に比べると、Wikipediaの記事にも例示されている立方体の面の塗分けの問題は母関数を考えなくてよいぶんかなり簡単です。最大 ${n}$ 色で塗り分けるとすると、この中から置換のサイクルごとに色を取ればよいので、

${\begin{align} \frac{1}{24}\left(n^6 + 3n^4 + 8n^2 + 6n^3 + 6n^3\right) = \frac{1}{24}\left(n^6 + 3n^4 + 12n^3 + 8n^2\right) \end{align}}$

通りになります。
A047780 - OEIS "Number of inequivalent ways to color faces of a cube using at most n colors."

まだ取り組んでいませんが、正（四｜六｜八｜十二｜二十）面体の（辺｜面｜頂点）で同様のことを考えると計算の練習になりそうです。

参考文献

成嶋弘『数え上げ組合せ論入門［改訂版］』、日本評論社（2003年）
雪江明彦『代数学1　群論入門』、日本評論社（2010年）