Pólyaの数え上げ定理

同義語：Pólya enumeration theoremPólya–Redfieldの定理

概要

前提知識: 群の作用, 置換, 巡回置換, 母関数

正方形の 4 つの頂点を赤と白で塗る方法は $2^4=16$ 通りあるが、回して重なるものを同じとみなすと 6 通りになる。このような「対称性で移り合うものを同一視した塗り分け」の個数は、群の作用の記事の命題「軌道の個数の公式」（Burnside の補題）で求められる。Pólya の数え上げ定理 は、これをさらに進めて、「赤を $2$ 個、白を $2$ 個使う塗り分けは何通りか」のように色の使われ方ごとの個数を、1 つの多項式（母関数）にまとめて与える。
その多項式は、群の各元が塗られる場所をどのような長さの巡回に分けるかを記録した 巡回指数 に、$z_k\mapsto r^k+w^k$（色の重みの $k$ 乗和）を代入するだけで得られる（thm-pet-main）。首飾りの数え上げ、立方体の面の塗り分け、同型を除いたグラフの数え上げなどが、この 1 つの定理から統一的に導かれる。

設定と定義

以下、$X$ を $n$ 元の有限集合（塗られる場所）、$G$ を $X$ に作用する有限群、$C$ を空でない有限集合（色の集合）とする。$X$ から $C$ への写像 $f$ を 塗り分け といい、その全体を $C^X$ と書く（$\lvert C^X\rvert=\lvert C\rvert^n$）。

塗り分けへの作用と模様

$g\in G$ と $f\in C^X$ について
$$ (g\cdot f)(x):=f(g^{-1}x)\qquad(x\in X) $$
と定める。これは $G$ の $C^X$ への作用である。この作用の軌道を模様（pattern）という。2 つの塗り分けが同じ模様に属することは、$G$ の元で一方を他方に移せることである。

作用であることは $(g\cdot(h\cdot f))(x)=(h\cdot f)(g^{-1}x)=f(h^{-1}g^{-1}x)=((gh)\cdot f)(x)$ から分かる。$g\cdot f$ は「場所 $x$ の色を $gx$ に運んだ」塗り分けである（$(g\cdot f)(gx)=f(x)$）。
$g\in G$ の作用で定まる $X$ の置換を、置換の記事の定理「互いに素な巡回置換の積への分解」で巡回置換の積に分け、不動点を長さ $1$ の巡回として数える。長さ $k$ の巡回の個数を $c_k(g)$、巡回の総数を $c(g):=\sum_kc_k(g)$ と書く。巡回は、$g$ で生成される部分群 $\langle g\rangle$ の $X$ への作用の軌道 $\{x,gx,g^2x,\dots\}$ のことである。

巡回指数

$G$ の $X$ への作用の 巡回指数（cycle index）を、変数 $z_1,\dots,z_n$ の多項式
$$ Z_G(z_1,\dots,z_n):=\frac1{\lvert G\rvert}\sum_{g\in G}z_1^{c_1(g)}z_2^{c_2(g)}\cdots z_n^{c_n(g)} $$
と定める。

$\sum_kk\,c_k(g)=n$ なので、各項は $z_k$ に重み $k$ を付けた $n$ 次の単項式である。巡回指数は群 $G$ だけでなく、$G$ の $X$ への作用によって決まる（ex-pet-action-dependence）。

重みと模様の目録

$R$ を有理数体 $\mathbb{Q}$ を含む可換環（たとえば有理数係数の多項式環 $\mathbb{Q}[r_1,\dots,r_m]$）とし、各色 $c\in C$ に重み $w(c)\in R$ を与える。塗り分け $f$ の重みを $W(f):=\prod_{x\in X}w(f(x))$ と定める。$W(g\cdot f)=W(f)$ なので、模様 $O$ の重み $W(O)$ が $O$ の元の重みとして定まる。和
$$ F_G:=\sum_{O\in C^X/G}W(O) $$
を 模様の目録（pattern inventory）という。

$W(g\cdot f)=\prod_xw(f(g^{-1}x))$ は、$x\mapsto g^{-1}x$ が $X$ の全単射なので積の順序を入れ替えただけで $W(f)$ に等しい。色を $C=\{c_1,\dots,c_m\}$ とし $w(c_i):=r_i$（変数）とおくと、$W(f)=r_1^{i_1}\cdots r_m^{i_m}$ の $i_j$ は色 $c_j$ を塗った場所の個数なので、$F_G$ の $r_1^{i_1}\cdots r_m^{i_m}$ の係数は 色 $c_j$ をちょうど $i_j$ 個ずつ使う模様の個数 である。すべての重みを $1$ にすれば $F_G$ は模様の総数になる。

Pólya の数え上げ定理

証明は 2 つの補題に分かれる。1 つ目は、$g$ で動かない塗り分けの重みの和を巡回の長さで表す。

動かない塗り分けの重みの和

$g\in G$ について、$g\cdot f=f$ であることと、$f$ が $g$ の各巡回の上で一定であることは同値である。したがって、$p_k:=\sum_{c\in C}w(c)^k$（色の重みの $k$ 乗和）とおくと
$$ \sum_{f\in C^X,\ g\cdot f=f}W(f)=p_1^{c_1(g)}p_2^{c_2(g)}\cdots p_n^{c_n(g)} $$
であり、とくに $g$ で動かない塗り分けは $\lvert C\rvert^{c(g)}$ 個ある。

$g\cdot f=f$ は、すべての $x$ で $f(g^{-1}x)=f(x)$ が成り立つことであり、$x$ を $gx$ に置き換えると、すべての $x$ で $f(x)=f(gx)$ が成り立つことと同値である。これを繰り返すと $f(x)=f(g^kx)$（$k\ge0$）なので $f$ は各巡回 $\{x,gx,g^2x,\dots\}$ の上で一定であり、逆に各巡回の上で一定なら $f(gx)=f(x)$ である。
よって動かない塗り分けは、$c(g)$ 個の巡回のそれぞれに色を 1 つずつ選ぶことと一対一に対応する。長さ $k$ の巡回に色 $c$ を選ぶと、その巡回の $k$ 個の場所が重み $w(c)^k$ を寄与する。巡回ごとの選び方は独立なので、重みの和は各巡回についての和 $\sum_cw(c)^k=p_k$ の積 $\prod_kp_k^{c_k(g)}$ になる（積を展開すると、各巡回に色を 1 つずつ選んだ組の重みの和になる）。重みをすべて $1$ にすると $p_k=\lvert C\rvert$ で、個数 $\lvert C\rvert^{c(g)}$ を得る。$\square$

2 つ目は、Burnside の補題（群の作用の記事の命題「軌道の個数の公式」）の重みつき版である。

重みつきの Burnside の補題

有限群 $G$ が有限集合 $Y$ に作用し、$W\colon Y\to R$ が各軌道の上で一定であるとする（$R$ は $\mathbb{Q}$ を含む可換環）。$Y^g:=\{y\in Y\mid gy=y\}$ とおくと
$$ \sum_{O\in Y/G}W(O)=\frac1{\lvert G\rvert}\sum_{g\in G}\ \sum_{y\in Y^g}W(y) $$
である。ここで $W(O)$ は軌道 $O$ の元での $W$ の値である。

右辺の二重和を、組 $(g,y)$（$gy=y$）にわたる和と見て、$y$ ごとにまとめると $\sum_{y\in Y}\lvert G_y\rvert\,W(y)$ である（$G_y$ は $y$ の安定化群）。群の作用の記事の定理「軌道・安定化群定理」により、$y$ の軌道を $O$ とすると $\lvert G_y\rvert=\lvert G\rvert/\lvert O\rvert$ である。1 つの軌道 $O$ に属する $\lvert O\rvert$ 個の $y$ はどれも $W(y)=W(O)$ なので、その寄与の和は $\lvert O\rvert\cdot\frac{\lvert G\rvert}{\lvert O\rvert}W(O)=\lvert G\rvert\,W(O)$ である。$Y$ は軌道に交わりなく分かれるので、二重和は $\lvert G\rvert\sum_OW(O)$ に等しい。$\square$

$W\equiv1$ のときが Burnside の補題である。

Pólya の数え上げ定理

有限群 $G$ が $n$ 元の有限集合 $X$ に作用し、色の集合 $C$ の各色に重み $w(c)$ が与えられているとする。$p_k:=\sum_{c\in C}w(c)^k$ とおくと、模様の目録は
$$ F_G=Z_G(p_1,p_2,\dots,p_n) $$
である。とくに $C=\{c_1,\dots,c_m\}$、$w(c_i)=r_i$ とすると、色 $c_j$ をちょうど $i_j$ 個ずつ使う模様の個数は、
$$ Z_G\Bigl(\sum_ir_i,\ \sum_ir_i^2,\ \dots,\ \sum_ir_i^n\Bigr) $$
を展開したときの $r_1^{i_1}\cdots r_m^{i_m}$ の係数に等しい。

lem-pet-weighted-burnside を $Y=C^X$ と塗り分けの重み $W$（模様の上で一定）に当てると
$$ F_G=\sum_{O\in C^X/G}W(O)=\frac1{\lvert G\rvert}\sum_{g\in G}\ \sum_{g\cdot f=f}W(f) $$
である。lem-pet-fixed により内側の和は $p_1^{c_1(g)}\cdots p_n^{c_n(g)}$ なので、右辺は巡回指数の定義により $Z_G(p_1,\dots,p_n)$ である。後半は、$F_G$ の係数の意味（def-pet-inventory の後の段落）から従う。$\square$

模様の総数

$m$ 色で塗る模様の総数は
$$ Z_G(m,m,\dots,m)=\frac1{\lvert G\rvert}\sum_{g\in G}m^{c(g)} $$
である。

thm-pet-main で重みをすべて $1$ にすると $p_k=m$ であり、$F_G$ は模様の総数になる。$\square$

正方形の頂点の 2 色の塗り分け

正方形の頂点を順に $1,2,3,4$ とし、$90^\circ$ の回転 $\rho=(1\,2\,3\,4)$ が生成する位数 $4$ の群 $C_4$ を考える。$\rho^0$ は長さ $1$ の巡回 4 個、$\rho,\rho^3$ は長さ $4$ の巡回 1 個、$\rho^2=(1\,3)(2\,4)$ は長さ $2$ の巡回 2 個なので
$$ Z_{C_4}=\tfrac14\bigl(z_1^4+z_2^2+2z_4\bigr) $$
である。赤と白の重みを $r,w$ として $z_k=r^k+w^k$ を代入すると
$$ \tfrac14\bigl((r+w)^4+(r^2+w^2)^2+2(r^4+w^4)\bigr)=r^4+r^3w+2r^2w^2+rw^3+w^4 $$
となる。赤 $2$ 個・白 $2$ 個の模様は $2$ 通り（隣り合う 2 頂点が赤か、向かい合う 2 頂点が赤か）で、総数は $1+1+2+1+1=6$ である。
裏返しも許すと群は位数 $8$ の二面体群 $D_4$ になり、増えた 4 つの裏返しは、対角線についての 2 つが $z_1^2z_2$、向かい合う辺の中点を結ぶ直線についての 2 つが $z_2^2$ を与えるので、$Z_{D_4}=\frac18(z_1^4+2z_1^2z_2+3z_2^2+2z_4)$ である。2 色ではこの場合も同じ多項式 $r^4+r^3w+2r^2w^2+rw^3+w^4$ になる（2 色の正方形では、裏返して初めて重なる模様がない）。

首飾りと腕輪

円周上に等間隔に並んだ $n$ 個の玉の位置を $\mathbb{Z}/n\mathbb{Z}=\{0,1,\dots,n-1\}$ とし、回転 $\rho(i)=i+1$ が生成する位数 $n$ の巡回群 $C_n$ を考える。$C_n$ の模様を 首飾り（necklace）という。$\varphi(d)$ は Euler関数、和 $\sum_{d\mid n}$ は $n$ の正の約数にわたる。

巡回群の巡回指数

$C_n$ の $\mathbb{Z}/n\mathbb{Z}$ への作用の巡回指数は
$$ Z_{C_n}=\frac1n\sum_{d\mid n}\varphi(d)\,z_d^{\,n/d} $$
である。

$\rho$ は長さ $n$ の巡回置換 $(0\,1\,\cdots\,n-1)$ である。巡回置換の記事の命題「巡回置換の冪」により、$0\le k< n$ について $\rho^k$ は長さ $n/\gcd(k,n)$ の巡回 $\gcd(k,n)$ 個に分かれる（$k=0$ では長さ $1$ の巡回 $n$ 個）。$d\mid n$ を固定し、巡回の長さが $d$、すなわち $\gcd(k,n)=n/d$ となる $k$ を数える。そのような $k$ は $n/d$ の倍数なので $k=\frac ndj$（$0\le j< d$）と書け、$\gcd(\frac ndj,n)=\frac nd\gcd(j,d)$ なので、条件は $\gcd(j,d)=1$ と同値である。よってその個数は $\varphi(d)$ であり、各 $\rho^k$ は単項式 $z_d^{n/d}$ を与える。$\square$

首飾りの個数

$m$ 色の玉で作る長さ $n$ の首飾りの個数は
$$ N(n,m)=\frac1n\sum_{d\mid n}\varphi(d)\,m^{n/d} $$
である。とくに $\sum_{d\mid n}\varphi(d)\,m^{n/d}$ は $n$ で割り切れ、$n=p$ が素数なら $m^p\equiv m\pmod p$（Fermatの小定理）が成り立つ。

最初の式は cor-pet-count と prop-pet-cyclic から従う。$N(n,m)$ は個数なので整数であり、$nN(n,m)=\sum_{d\mid n}\varphi(d)m^{n/d}$ は $n$ の倍数である。$n=p$ なら約数は $1,p$ で、$\varphi(1)=1$、$\varphi(p)=p-1$ なので $m^p+(p-1)m=m^p-m+pm$ が $p$ の倍数、すなわち $m^p\equiv m\pmod p$ である。$\square$

裏返しも許すと、群は $\rho$ と鏡映 $\sigma(i)=-i$ が生成する位数 $2n$ の二面体群 $D_n$（$n\ge3$）になり、その模様を腕輪（bracelet）という。円順列とじゅず順列の記事の「じゅず順列」は、各色の玉の個数を指定した腕輪のことである。

二面体群の巡回指数

$n\ge3$ とする。$D_n$ の $\mathbb{Z}/n\mathbb{Z}$ への作用の巡回指数は
$$ Z_{D_n}=\frac12Z_{C_n}+\begin{cases}\dfrac12\,z_1z_2^{(n-1)/2}&(n\text{ が奇数})\\[2mm]\dfrac14\bigl(z_1^2z_2^{(n-2)/2}+z_2^{n/2}\bigr)&(n\text{ が偶数})\end{cases} $$
である。

$D_n$ の元は回転 $\rho^k$ と鏡映 $\sigma_j(i):=j-i$（$0\le j< n$）の $2n$ 個である。回転からの寄与の和は $nZ_{C_n}$ である。$\sigma_j(\sigma_j(i))=j-(j-i)=i$ なので $\sigma_j$ は対合であり、巡回の長さは $1$ か $2$ である。不動点は $2i\equiv j\pmod n$ の解である。$n$ が奇数なら $2$ は法 $n$ で可逆なので解はちょうど 1 つで、$\sigma_j$ は $z_1z_2^{(n-1)/2}$ を与える。$n$ が偶数なら、$j$ が偶数のとき解は $i\equiv j/2$ と $j/2+n/2$ の 2 つ、$j$ が奇数のとき解はない。よって $n/2$ 個の鏡映が $z_1^2z_2^{(n-2)/2}$、$n/2$ 個が $z_2^{n/2}$ を与える。全体を $2n$ で割ればよい。$\square$

$n$	1	2	3	4	5	6	7	8
2 色の首飾り $N(n,2)$	2	3	4	6	8	14	20	36
2 色の腕輪	2	3	4	6	8	13	18	30
3 色の首飾り $N(n,3)$	3	6	11	24	51	130	315	834
3 色の腕輪	3	6	10	21	39	92	198	498

$n=1,2$ の腕輪の欄は、$\sigma$ がすでに回転であることから首飾りと同じ個数である。2 色の腕輪が首飾りより初めて少なくなるのは $n=6$ で、首飾り $RRWRWW$ と $RRWWRW$ は回転では移り合わないが、裏返すと移り合う。

赤 3 個と白 3 個の首飾り

$n=6$ の約数は $1,2,3,6$ で $\varphi$ の値は $1,1,2,2$ なので
$$ Z_{C_6}=\tfrac16\bigl(z_1^6+z_2^3+2z_3^2+2z_6\bigr) $$
である。$z_k=r^k+w^k$ を代入したときの $r^3w^3$ の係数は、$(r+w)^6$ から $\binom63=20$、$(r^2+w^2)^3$ からは $0$（$r$ の次数が偶数）、$(r^3+w^3)^2$ から $2$ を $2$ 倍した $4$、$(r^6+w^6)$ からは $0$ なので、$(20+4)/6=4$ である。これは円順列とじゅず順列の記事の例「Burnside の補題で数える」で 1 つずつ数えた 4 通りと一致する。

いろいろな例

立方体の面の塗り分け

立方体 $[-1,1]^3$ を自分自身に移す回転は、各行・各列に $\pm1$ がちょうど 1 つある行列式 $1$ の行列 $24$ 個である（特殊直交群の記事の例「立方体を自分自身に移す回転」）。これらを 6 つの面の置換として、回転軸で分けると次のようになる（各元の行列を書き出して確かめられる）。

回転	個数	面の巡回
恒等写像	1	$z_1^6$
向かい合う面の中心を通る軸のまわりの $\pm90^\circ$	6	$z_1^2z_4$
同じ軸のまわりの $180^\circ$	3	$z_1^2z_2^2$
対角線のまわりの $\pm120^\circ$	8	$z_3^2$
向かい合う辺の中点を通る軸のまわりの $180^\circ$	6	$z_2^3$

よって $Z=\frac1{24}(z_1^6+6z_1^2z_4+3z_1^2z_2^2+8z_3^2+6z_2^3)$ であり、$m$ 色で塗る模様は $\frac1{24}(m^6+3m^4+12m^3+8m^2)$ 通り、$m=2$ で $10$ 通り、$m=3$ で $57$ 通りである。3 色をちょうど 2 面ずつ使う模様は、$z_k=r^k+b^k+g^k$ を代入した式の $r^2b^2g^2$ の係数で、$6$ 通りである。

同型を除いた 4 頂点のグラフ

頂点集合 $\{1,2,3,4\}$ の上のグラフは、6 つの 2 元部分集合（辺の候補）を「辺あり」「辺なし」の 2 色で塗ることにあたる。頂点の置換 $\sigma\in S_4$ は 2 元部分集合を $\{a,b\}\mapsto\{\sigma(a),\sigma(b)\}$ で動かし、この作用の模様がグラフの同型類である（グラフ同型）。$\sigma$ の巡回型ごとに 2 元部分集合の巡回を調べると、互換（6 個）と互いに素な互換 2 個の積（3 個）は $z_1^2z_2^2$、長さ $3$ の巡回置換（8 個）は $z_3^2$、長さ $4$ の巡回置換（6 個）は $z_2z_4$ を与える（KT17 §15.5.3, pp. 307–309）。たとえば $(1\,2)$ は $\{1,2\}$ と $\{3,4\}$ を動かさず、$\{1,3\}\leftrightarrow\{2,3\}$、$\{1,4\}\leftrightarrow\{2,4\}$ と入れ替える。よって
$$ Z=\tfrac1{24}\bigl(z_1^6+9z_1^2z_2^2+8z_3^2+6z_2z_4\bigr) $$
であり、「辺あり」の重みを $t$、「辺なし」の重みを $1$ として $z_k=1+t^k$ を代入すると
$$ 1+t+2t^2+3t^3+2t^4+t^5+t^6 $$
を得る。$t^k$ の係数は辺が $k$ 本のグラフの同型類の個数で、総数は $11$ である。これはグラフ同型の記事の例「4 頂点のグラフ」の表と一致する。

対称群と重複組合せ

$S_n$ が $\{1,\dots,n\}$ に自然に作用するとき、各色の個数が同じ 2 つの塗り分けは、一方の色 $c$ の場所を他方の色 $c$ の場所へ写す置換で移り合う。よって模様は色の個数の組 $(i_1,\dots,i_m)$（$i_1+\dots+i_m=n$）と一対一に対応し、$n$ 個の玉と $m-1$ 本の仕切りの並べ方を数えて $\binom{m+n-1}{n}$ 個ある。これを cor-pet-count と比べると、すべての正の整数 $m$ について
$$ \sum_{\sigma\in S_n}m^{c(\sigma)}=n!\binom{m+n-1}{n}=m(m+1)\cdots(m+n-1) $$
であり、両辺は $m$ の多項式なので多項式として一致する。$m^k$ の係数は、巡回がちょうど $k$ 個の $n$ 文字の置換の個数（符号なしの第 1 種 Stirling 数）である（Sta13 Example 7.11 と式 (7.7), pp. 112–114）。

巡回指数が作用によって変わること

$2\times2$ の盤の 4 つのマスを $\begin{matrix}1&2\\3&4\end{matrix}$ と並べる。左右の裏返し $(1\,2)(3\,4)$ が生成する群と、対角線についての裏返し $(2\,3)$ が生成する群は、どちらも位数 $2$ の巡回群と同型だが、巡回指数は $\frac12(z_1^4+z_2^2)$ と $\frac12(z_1^4+z_1^2z_2)$ で異なる。2 色で塗る模様は前者で $(16+4)/2=10$ 通り、後者で $(16+8)/2=12$ 通りである（Sta13 Example 7.1 の $G_2$ と $G_3$、pp. 101–103）。巡回指数を計算するときは、群の抽象的な構造ではなく、場所の集合 $X$ の上の置換を見る必要がある。

条件を外したときの反例

外す条件	反例	成り立たなくなること
平均をとる元の集合が、同一視を与える群全体である	正方形の頂点の 2 色の塗り分けで、操作の集合を「恒等写像と $90^\circ$ の回転」の 2 つだけとして平均をとる	動かない塗り分けの個数の平均 $(16+2)/2=9$ が模様の個数 $6$ に等しい
群は場所だけを動かし、色を動かさない	2 点を 2 色で塗り、場所は動かさず色の入れ替えで同一視する	模様の個数が $Z_G(m,\dots,m)$ に等しい（同一視したものは $\{aa,bb\}$、$\{ab,ba\}$ の 2 個だが、自明な群の $Z_G(2,2)=4$）
恒等元以外の元はどの塗り分けも動かす	正方形の頂点の 2 色の塗り分けと $C_4$（全部同じ色の塗り分けは回転で動かない）	模様の個数が $m^n/\lvert G\rvert$ に等しい（$16/4=4$ だが実際は $6$）

1 行目の 2 つの操作が生成する群は $C_4$ で、同一視の結果は $C_4$ の模様と同じ 6 個になるが、平均をとる集合が群でないので lem-pet-weighted-burnside は使えない。2 行目では色の集合にも群が働いており、場所の置換だけから作った巡回指数では数えられない。3 行目は、各模様の大きさが $\lvert G\rvert$ であることを仮定した割り算で、円順列とじゅず順列の記事の命題「個数が互いに素なら $n$ で割ってよい」はこの割り算が使える場合を述べている。

補足

この定理は 1937 年の Pólya の論文による（Sta13 Theorem 7.7, p. 109）。Redfield も独立に同じ理論を得ており、Pólya–Redfield の理論とも呼ばれる（Bog17 §6.3, p. 125）。証明に使った Burnside の補題は、推移的な場合を Cauchy が、一般の場合を Frobenius が証明していて、Cauchy–Frobenius の補題とも呼ばれる（Sta13 Lemma 7.2 の前, p. 105）。
模様の目録 $F_G$ は、色の重み $r_1,\dots,r_m$ の入れ替えで変わらない対称多項式である。代入する $p_k=r_1^k+\dots+r_m^k$ は冪和対称多項式であり、Pólya の定理は「巡回指数を冪和で書いたものが模様の目録になる」と読める。Pólya 自身は、炭化水素の異性体の数え上げのような化学の問題にこの方法を使った（KT17 §15.5, p. 307）。