对称群、群作用与 Pólya 定理
Gorenstein
·
·
算法·理论
- 群作用
- 对称群及其计数
- 对称群作用
- 对称群的一些例子
- 轮换与循环分解
- 对同型号置换的计数：Cauchy 公式
- 轮换指标及其 OGF
- Pólya 计数定理
- 染色集上的作用
- Pólya 定理及其证明
- Pólya 定理的一些例子
- 带权的 Pólya 定理
- 定理的证明
- 有限制的染色同构计数
- 组合类的 Cycle 构造
群作用
先来定义幺半群作用的概念，这是之后讨论对称群的计数的基础。
$$
a:M\times X\to X,
$$
满足以下条件：
- $\forall m,m'\in M,\,x\in X$，满足 $a(m',a(m,x))=a(m'm,x)$（结合律）。
- $\forall x\in X,\;a(1,x)=x$。
将带有 $M$ 作用的集合称为 $M\text-$集。另将 $\forall m\in M,x\in X$ 都有 $a(m,x)=x$ 的作用称为**平凡作用**。
习惯上亦将 $a(m,x)$ 记作 $m\cdot x$ 或 $mx$。此时上述条件简写作
$$
\begin{aligned}
m'(mx)&=(m'm)x,\\
1\cdot x&=x,\\
f(mx)&=mf(x).
\end{aligned}
$$
以上关于左作用的定义可逐条改写得到右作用。事实上，所谓右有作用无非就是 $M^{\operatorname{op}}$ 对其的左作用。
接下来定义 $M\text-$集同构的概念。
$\bf Definition\;2.\quad$设 $M\text-$集间的映射 $f:X\to Y$ 满足
$$
f(a(m,x))=a(m,f(x)),\quad m\in M,\,x\in X,
$$
则称该映射为 $\bf{M\text-}$**等变映射**；若等变映射 $M_1\xleftrightarrow[g]{f}M_2$ 满足
$$
fg=\operatorname{id}_{M2},\,gf=\operatorname{id}_{M1},
$$
则称 $f,g$ 互为**同构**。
$\bf Example.\quad$显然 $M_n(\mathbb R)$ 成一幺半群。若视 $\mathbb R^n$ 中的元素为一列向量，则 $M_n(\mathbb R)$ 在 $\mathbb R^n$ 上的作用 $(\boldsymbol A,\boldsymbol x)\mapsto \boldsymbol A\boldsymbol x$ 无非是矩阵乘法。
$\bf Proposition\;3.\quad$设群 $G$ 左作用于 $X$，设 $Y$ 是任意集合。则群 $G$ 对于集合 $\{f:X\to Y\}$ 有自然的左作用 $a(g,f)=[x\mapsto f(g^{-1}x)]$。
${Proof.}\quad$显然有 $a(1,f)=[x\mapsto f(1\cdot x)]=f$。对于 $g,h\in G$，有
$$
\begin{aligned}
\;\;\qquad\;\;\qquad a(h,a(g,x))&=\left[x\mapsto a(g,x)(h^{-1}x)\right]=\left[x\mapsto f(g^{-1}h^{-1}x)\right]=a(hg,x).\qquad\qquad\quad\square
\end{aligned}
$$
我们给出以下一项性质作为对群作用的笼统介绍的收尾。
$\bf Proposition\;4.\quad$对于一个群 $M$，全体 ${M\text-}$集连同等变映射构成一范畴，记作 $M\text-\mathsf{Set}$。
## 群作用的轨道空间
### 不动点、轨道与稳定化子
兹给出不动点、轨道和稳定化子的定义。
$\bf Definition\;5.\quad$设幺半群 $M$ 作用于 $X$。以下定义
- **不动点集** $X^M:=\{x\in X:\forall m\in M,\,mx=x\}$。
- $\boldsymbol{m\text-}$**不动点** $\psi(m):=\{x\in X:mx=x\}$。
- $x$ 的**轨道** $Mx:=\{mx:m\in M\}$。它是 $X$ 的 $M\text -$子集。
- $x$ 的**稳定化子** $\operatorname{Stab}_M(x):=\{m\in M:mx=x\}$。不难验证它是 $M$ 的子幺半群。
对于群 $G$ 作用于 $X$ 上，$x$ 的稳定化子亦记作 $G_x$。它是 $G$ 的一个子群。
### 等价类的划分
群 $G$ 的作用的基本组成是形如 $G/H$ 的陪集空间。考虑以下引理。
$\bf Lemma.\quad$设群 $G$ 作用于 $X$，则
- 对每个轨道选定代表元 $x$，就有轨道分解
$$X=\bigsqcup_x Gx\,.$$
- $\forall x\in X$，以下映射乃同构：
$$
\begin{aligned}
G/\operatorname{Stab}_G(x)&\longrightarrow Gx,\\
g\cdot\operatorname{Stab}_G(x)&\longmapsto gx.
\end{aligned}
$$
- 对所有 $x\in X,\,g\in G$，有
$$
\operatorname{Stab}_G(gx)=g\operatorname{Stab}_{G}(x)g^{-1}.
$$
- 存在基数的恒等式
$$|X|=\sum_x[G:\operatorname{Stab}_G(x)].$$
这给出了一个划分方式；它在下文会被略加解释。
$Proof.\quad$前两条的意义是明显的。对于第三条，设 $hx=x$，直接验证得 $ghg^{-1}gx=gx$。对于第四条，考察其轨道分解以及第二条引理给出的同构。$\square
由此可以看出 x,y 是否属于同一轨道可作为等价类划分的依据。相应的商集记作 G\backslash X，称为轨道空间。对于右作用，轨道空间对称地记作 X/G。
Burnside 引理
接下来给出我们熟知的 Burnside 引理。它给出了这样一个事实：轨道个数 = 所有 g\text-不动点数目的均值。
$$
\frac{1}{|G|}\sum_{g\in G}|\psi(g)|.
$$
$Proof.\quad$考察有序对 $(g,x)$ 的个数，满足 $gx=x$。一方面，它是 ${\large\sum\limits_{\tiny g\!\!\!\!\in\!\!\!\!G}\normalsize|\psi(g)|}$；另一方面，它是
$$
\sum_{x\in X}\operatorname{Stab}_G(x)=\sum_{x\in X}|G|/|Gx|,
$$
这是因为存在同构 $G/\operatorname{Stab}_G(x)\rightarrow Gx$。由此可得
$$
\frac{1}{|G|}\sum_{g\in G}|\psi(g)|=\sum_{x\in X}\frac{1}{|Gx|}=\sum_{Gx}\sum_{y\in Gx}\frac{1}{|Gy|}.
$$
结合轨道分解的原理可知上式右端正是轨道数。$\square
对称群及其计数
对于集合 X，其上的对称群是指全体双射 X\xleftrightarrow{1:1}X 对映射合成构成的群，记作 \mathfrak S_X。双射 \sigma\in\mathfrak S_X 称置换。
习惯上，我们常将 X 等同于 [n]:=\{1,2,\cdots,n\}，记 \mathfrak S_{n}:=\mathfrak S_{[n]}。
对称群的子群称为置换群。
对称群作用
对任意集合 X，显然有 \mathfrak S_X 作用于 X 上：a:(\sigma,x)\mapsto\sigma(x)。
另当留意到给定群 G 在 X 上的作用相当于给出了同态 G\to\mathfrak S_X，映 g 为 [x\mapsto gx]。
对称群的一些例子
二面体群
$$
\begin{aligned}
\sigma_i(a)&=a+i&\pmod n,\\
\tau_j(a)&=-a+j&\pmod n,
\end{aligned}
$$
并记
$$
D_n=\{\sigma_i,\tau_j:i,j=1,2,\cdots,n\},
$$
则 $D_n$ 是 $\mathfrak S_n$ 的一个子群，称其为 $[n]$ 上的**二面体群**。
$\bf Note.\quad$留意 $\{\sigma_i:i=1,2,\cdots,n\}$ 也是 $[n]$ 上的一个置换群，它是 $\sigma_1$ 生成的循环群。
### 自同构群
设 $G=(V,E)$ 是一个图，其上的一个自同构 $\sigma$ 是这样一个置换，满足
$$
(x,y)\in V\iff(\sigma(x),\sigma(y))\in V,\quad\forall x,y\in V.
$$
图的所有自同构在映射合成下构成群，称其为**自同构群** $\operatorname{Aut}(G)$。
## 轮换与循环分解
为了更好地叙述对称群的性质，考虑如下引理。
$\bf Lemma.\quad$对 $X,Y$，存在自然嵌入
$$
\mathfrak S_X\times\mathfrak S_Y\hookrightarrow \mathfrak S_{X\sqcup Y},
$$
即 $\mathfrak S_n\times\mathfrak S_m\hookrightarrow \mathfrak S_{n+m}$。这是由置换挪动的元素的不交决定的。$\square
以下给出轮换的定义。
$$
\begin{aligned}
\sigma(a_{i})&=a_{i+1},&i\in\mathbb Z/m\mathbb Z,\,\\
\sigma(x)&=x,&x\notin\{a_1,\cdots,a_m\}.
\end{aligned}
$$
称两个轮换 $(a_1 \cdots a_m),(b_1 \cdots b_n)$ 不交，如果 $\{a_1,\cdots,a_m\}\cap\{b_1,\cdots,b_n\}=\varnothing$。
接下来给出著名的循环分解定理。
$\bf Theorem\;7.$**（循环分解）**$\quad$每个 $\sigma\in\mathfrak S_X$ 都能被唯一表成不交的循环之积
$$
\sigma=(a_1a_2\cdots)(b_1b_2\cdots)\cdots
$$
$Proof.\quad$这无非是 $\sigma$ 生成的有限循环群 $\langle\sigma\rangle$ 下的轨道分解。$\square
不难看到，以上的一个循环分解可对应于整数的一种分拆方式。我们藉此引入轮换型号的概念。
## 对同型号置换的计数：Cauchy 公式
$\bf Theorem\;9.\;(Cauchy)\quad$对称群 $\mathfrak S_n$ 中型号为 $(l_1,\cdots,l_n)$ 的置换个数为
$$
\frac{n!}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}.
$$
### 公式的证明
今有不交的集族满足：
- 由 $l_1$ 个 $1\text-$集，$l_2$ 个 $2\text-$集，$\cdots$，$l_n$ 个 $n\text-$集共同组成。
- 集族所有元素之交为 $[n]$。
- 集合大小单调不降，但相同大小的集合间无顺序。
- 集合内的元素有标号但无顺序。
设此般集族的组合类为 $\mathcal U$。
显然，两个集族 $S,T\in\mathcal U$ 是不同的，当且仅当存在至少一对数不在相同集合内的数，交换 $S$ 中这两个数可以得到 $T$；交换相同大小集合的位置和一个集合内部的元素后，$S$ 仍然是 $S$。
考虑将一个集族 $S\in\mathcal U$ 从左到右读出其中每个元素，如此可以得到 $n$ 的一个排列。
集合内任意交换元素的方案数为 $(1!)^{l_1}\cdots(n!)^{l_n}$，相同大小的集合间交换元素的方案数为 $l_1!\cdots l_n!$。因此按上述方法规则，对于单个集族 $S\in\mathcal U$，它能够生成的排列数量是
$$
l_1!l_2!\cdots l_n!(1!)^{l_1}(2!)^{l_2}\cdots(n!)^{l_n}.
$$
记这样生成的排列为 $\mathcal C_S$。根据上述讨论，不同的 $\mathcal C_S$ 是不交的。由此设组合类
$$
\mathcal A:=\bigcup_{S\in\mathcal U}\mathcal C_S.
$$
注意到存在如下双射：
- $\mathcal A$ 中每一个元素可单射到 $\mathfrak S_n$。
- 对任意 $\sigma\in\mathfrak S_n$，考察序列 $\{\sigma(i)\}_{1}^n$将其从左到右分出个 $l_1$ 段长度为 $1$ 的子区间，$l_2$ 个长度为 $2$ 的子区间，$\cdots$，$l_n$ 个长度为 $n$ 的子区间。将每个子区间都作为一个集合，这样能够唯一形成一个 $\mathcal U$ 中的集族。
由此可得
$$
|\mathcal A|=|\mathfrak S_n|=n!\,.
$$
故而将 $[n]$ 分为 $l_1$ 个 $1\text-$子集，$l_2$ 个 $2\text-$子集，$\cdots$，$l_n$ 个 $n\text-$子集的方案数为
$$
\frac{n!}{l_1!l_2!\cdots l_n!(1!)^{l_1}(2!)^{l_2}\cdots(n!)^{l_n}}.
$$
而每个 $t\text-$子集能够形成 $(t-1)!$ 个轮换。因此得到型号为 $(l_1,\cdots,l_n)$ 的置换个数为
$$
\frac{n!}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}.
$$
$\square
轮换指标及其 OGF
接下来引入轮换指标的概念。
$$
P_G(x_1,\cdots,x_n)=\frac{1}{|G|}\sum_{\sigma\in G}x_1^{l_1(\sigma)}x_2^{l_2(\sigma)}\cdots x_n^{l_n(\sigma)}
$$
以下给出轮换指标的一个例子。
### $n$ 阶循环群的轮换指标
设 $\sigma=(12\cdots n)$，考察 $\sigma$ 生成的 $n$ 阶循环群 $\langle\sigma\rangle$ 的轮换指标。
若 $k\mid n$，则 $\sigma^k$ 是 $k$ 个 $\dfrac{n}{k}\text-$轮换之积。否则，若 $\gcd(k,n)=1$，则它是一个 $n\text-$轮换。
对于一般情形，设 $d=\gcd(k,n)$，则 $\sigma^k=\left(\sigma^d\right)^{\frac{k}{d}}$。显然 $\sigma^d$ 是 $d$ 个$\dfrac{n}{d}\text-$轮换之积；而 $\gcd\!\left(\frac{n}{d},\frac{k}{d}\right)=1$，从而 $\sigma^k$ 就是 $d$ 个$\dfrac{n}{d}\text-$轮换之积。故而
$$
l_i\!\left(\sigma^k\right)=\begin{cases}
0,&i\neq \dfrac{n}{\gcd(k,n)},\\
\gcd(k,n),&i=\dfrac{n}{\gcd(k,n)}.
\end{cases}
$$
于是
$$
\,\quad\qquad\qquad\begin{aligned}
\quad\quad P_{\langle\sigma\rangle}(x_1,\cdots,x_n)&=\frac{1}{n}\sum_{k=1}^n\left(x_{n/\gcd(k,n)}\right)^{\gcd(k,n)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)x_{d}^{n/d}.\qquad\qquad\qquad\blacksquare
\end{aligned}
$$
### 对称群轮换指标的 OGF
现在我们考察对称群轮换指标的 OGF，即 $\sum_{n\geqslant 0}P_{\mathfrak S_n}(x_1,\cdots,x_n)z^n$。
$\bf Theorem\;11.\quad$对称群轮换指标的 OGF 为
$$
\sum_{n=0}^{\infty}P_{\mathfrak S_n}(x_1,\cdots,x_n)z^n=\prod_{t=0}^{\infty}\exp\!\left(\frac{x_t}{t}z^t\right)=e^{\frac{x_1}{1}z+\frac{x_2}{2}z^2+\cdots+\frac{x^n}{n}z^n+\cdots}.
$$
$Proof.
\begin{aligned}
\;\qquad\,\;\quad\qquad\qquad\sum_{n=0}^{\infty}P_{\mathfrak S_n}&(x_1,\cdots,x_n)z^n\\&=\sum_{n=0}^{\infty}\left(\sum_{l_1+2l_2+\cdots+nl_n=n}\frac{x_1^{l_1}x_{2}^{l_2}\cdots x_{n}^{l_n}}{l_1!l_2!\cdots l_n!1^{l_1}2^{l_2}\cdots n^{l_n}}\right)z^n\\
&=\sum_{n=0}^{\infty}\sum_{l_1+2l_2+\cdots+nl_n=n}\prod_{t=0}^{n}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}\\
&=\sum_{l_1,l_2,\cdots,l_n,\cdots}\prod_{t=0}^{\infty}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}=\prod_{t=0}^{\infty}\sum_{l_t=0}^{\infty}\frac{1}{l_{t}!}\left(\frac{x_t}{t}z\right)^{l_t}\\
&=\prod_{t=0}^{\infty}\exp\!\left(\frac{x_t}{t}z^t\right)=e^{\frac{x_1}{1}z+\frac{x_2}{2}z^2+\cdots+\frac{x^n}{n}z^n+\cdots}.\qquad\quad\qquad\qquad\qquad\quad\;\square
\end{aligned}
Pólya 计数定理
染色集上的作用
下面给出染色集的概念。
下面构造积集 $C^A$ 上的群作用。设 $G$ 是 $A$ 上的一个置换群，它可以诱导出一个 $G$ 在 $C^A$ 上的作用。考察
$$
a(g,f)=f\circ g^{-1},\qquad g\in G,\,f\in C^A.
$$
容易验证这般构造的确实是一个作用。在这个作用下，同属于一个轨道的染色 $f$ 被认为是等价的。因此，轨道个数就是互不等价的染色方案的数目。
## Pólya 定理及其证明
$\bf\;Theorem\;13.\;(Pólya)\quad$设 $A,C$ 为 $n\text-$集合和 $m\text-$集合，设 $G$ 是 $A$ 上的置换群，设 $\mathcal F$ 为 $G$ 作用在 $C^A$ 上的轨道集合，则
$$
|\mathcal F|=P_{G}(m,m,\cdots,m).
$$
### 定理的证明
首先来看下面这个引理。
$\bf Lemma.\quad$设 $\operatorname{type}(g)=(l_1(g),\cdots,l_n(g))$ 为 $g$ 的轮换型号，则
$$
\varphi(g)=|C|^{l_1(g)+\cdots+l_n(g)}.
$$
$Proof.\quad$不动点 $f\in C^A$ 要在 $g$ 的每一个轮换内部分别取相同值，而每一个轮换的取值都有 $|C|$ 种。$\square
从而由 Burnside 引理可得
\begin{aligned}
|\mathcal F|&=\frac{1}{|G|}\sum_{g\in G}|\psi(g)|\\
&=\frac{1}{|G|}\sum_{g\in G}|C|^{l_1(g)}|C|^{l_2(g)}\cdots|C|^{l_n(g)}\\
&=P_{G}(m,m,\cdots,m).
\end{aligned}
\square
Pólya 定理的一些例子
此处的置换群是二面体群 $D_6$。经计算得
$$
P_{D_6}(x_1,x_2,\cdots,x_n)=\frac{1}{12}\!\left(x_1^6+3x_1^2x_2^2+4x_2^3+2x_3^2+x_6^1\right),
$$
从而结果是 $P_{D_6}(2,2,\cdots,2)=2$。$\blacksquare
$$
P_{C_4}(2,2,2,2)=\frac{1}{2}\big(2^4+2^2+2\cdot 2\big)=6.
$$
$\bf Example.\quad$求用 $m$ 种颜色给长度为 $n$ 的圆周染色得到的不同可重圆周排列的方案数 $C_m(n)$。（[P4980](https://www.luogu.com.cn/problem/P4980)）
置换群 $G$ 就是由 $n\text-$轮换 $(12\cdots n)$ 生成的 $n$ 阶循环群，从而
$$
\begin{aligned}
C_m(n)&=P_{\langle(12\cdots n)\rangle}(m,m,\cdots,m)=\frac{1}{n}\sum_{d\mid n}\varphi(d)x_{m}^{m/d}.
\end{aligned}
$$
$\bf Example.\quad$第一类斯特林数的幂转换公式（[P5408](https://www.luogu.com.cn/problem/P5408)）与可重集组合问题。
设可重集 $S$ 有 $x$ 种元素，每种元素皆有无限个。则其间不同的 $n\text-$子集个数可视作一个集合 $A\to B$ 的映射，其中 $A$ 中元素全部相同，$B$ 中元素各自不同，$|A|=n,|B|=x$。经典地，它是
$$
\binom{n+x-1}{n}.
$$
考虑
$$
B^{[n]}:=\{f\mid f:[n]\to B\},
$$
则一个映射恰对应 $\mathfrak S_n$ 作用于积集 $B^{[n]}$ 的一条轨道。从而映射个数是
$$
P_{\mathfrak S_n}(x,x,\cdots,x)=\frac{1}{n!}\sum_{\sigma\in\mathfrak S_n}x^{k(\sigma)}=\frac{1}{n!}\sum_{k=0}^n{n\brack k}x^k，
$$
从而
$$
\begin{aligned}
\binom{n+x-1}{n}&=\frac{1}{n!}\sum_{k=0}^n{n\brack k}x^k，\\
\Longrightarrow\qquad x^{\overline n}&=\sum_{k=0}^n{n\brack k}x^k.
\end{aligned}
$$
# 带权的 Pólya 定理
设 $G$ 作用于 $X$，对于 $x\in X$，定义 $w(x)$ 为其**权函数**。当 $\forall y\in Gx$ 有 $w(y)=w(x)$ 时，又可将权函数记作 $w(Gx)$，视作对于一个轨道的权函数。
对于染色集上的作用，我们做一些额外的补充。设 $G$ 作用于 $A$，我们上面已经说明由此可诱导一个 $G$ 在 $C^A$ 上的作用。下面我们将说明 $C$ 上的一个权函数也可顺势诱导出 $C^A$ 上的权函数。
对于 $f\in C^A$，定义
$$
w(f)=\prod_{a\in A}w(f(a)).
$$
注意到当映射 $f_1,f_2$ 等价时，存在 $g\in G$ 使得 $f_2=f_1\circ g^{-1}$，从而
$$
w(f_2)=\prod_{a\in A}w(f_2(a))=\prod_{a\in A}w\big(f_1\big(g^{-1}(a)\big)\big)=w(f_1),
$$
故此般定义对于轨道而言是良好的：它在同一轨道上取相同的常数值。设 $\mathcal F$ 为 $G$ 作用于积集 $C^A$ 的轨道之集合，下面给出著名的带权 Pólya 定理。
$\bf Theorem\;14.\;(Pólya)\quad$设 $w$ 是 $C$ 上的一个权函数，并按如上方法得到 $C^A$ 上的权函数。则它也是 $\mathcal F$ 上的权函数，且有
$$
\sum_{F\in\mathcal F}w(F)=P_G\left(\sum_{c\in C}w(c),\sum_{c\in C}w(c)^2,\cdots,\sum_{c\in C}w(c)^n\right).
$$
## 定理的证明
我们先来看 Burnside 定理的带权形式；然后利用该引理，我们将证明 Pólya 定理。
### 带权 Burnside 定理
下面给出对轨道的权之和计数的**带权 Burnside 引理。**
$\bf Theorem\;15.\;(Burnside)\quad$设 $O_1,\cdots,O_N$ 是群 $G$ 作用于 $X$ 的全部轨道；设 $w$ 为其上的一个权函数，它对于同一轨道具有相同的常数值。则
$$
\sum_{i=1}^Nw(O_i)=\frac{1}{|G|}\sum_{g\in G}\sum_{x\in\varphi(g)}w(x).
$$
$Proof.
\begin{aligned}
\qquad\qquad\qquad\qquad\qquad\quad\;\sum_{i=1}^Nw(O_i)&=\sum_{x\in X}\frac{w(x)}{|O_x|}=\frac{1}{|G|}\sum_{x\in X}|G_x|w(x)\\
&=\frac{1}{|G|}\sum_{x\in X}|G_x|\sum_{g\in G_x}1\\
&=\frac{1}{|G|}\sum_{g\in G}\sum_{x\in\varphi(g)}w(x).\qquad\qquad\qquad\qquad\qquad\qquad\quad\qquad\square
\end{aligned}
余下的工作
设 k=l_1(g)+l_2(g)+\cdots+l_n(g)。对任意 (c_1,\cdots,c_k)\in C^k，设 f_{c_1,\cdots,c_k} 为 C^A 中在符号集 A_i 中取常数值 c_i 的映射。则
w(f_{c_1,\cdots,c_k})=\prod_{a\in A}w(f_{c_1,\cdots,c_k}(a))=\prod_{i=1}^kw(c_i)^{|A_i|},
从而
\begin{aligned}
\sum_{f\in\psi(g)}w(f)&=\sum_{(c_1,\cdots,c_k)\in C^k}w(f_{c_1,\cdots,c_k})=\sum_{(c_1,\cdots,c_k)\in C^k}\prod_{i=1}^kw(c_i)^{|A_i|}\\
&=\prod_{i=1}^k\sum_{c\in C}w(c)^{|A_i|}=\prod_{j=1}^n\left(\sum_{c\in C}w(c)^j\right)^{l_j(g)},
\end{aligned}
其中最后一个等号是由于 |A_1|,\cdots,|A_k| 中等于 l_j(g) 的恰有 j 个。故运用带权的 Burnside 引理，得
\begin{aligned}
\sum_{F\in\mathcal F}w(F)&=\frac{1}{|G|}\sum_{g\in G}\sum_{f\in\varphi(g)}w(f)\\
&=\frac{1}{|G|}\sum_{g\in G}\prod_{j=1}^n\left(\sum_{c\in C}w(c)^j\right)^{l_j(g)}\\
&=P_G\left(\sum_{c\in C}w(c),\sum_{c\in C}w(c)^2,\cdots,\sum_{c\in C}w(c)^n\right).
\end{aligned}
有限制的染色同构计数
有时我们会遇到这样一类染色问题，即不仅有置换群作用于染色的对象上，而且还要求每种颜色 c_i 恰好给 k_i 个元素染色。这就需要以下定理。
$$
P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right)=\sum_{k_1+\cdots+k_m=n}N(k_1,\cdots,k_m)x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},
$$
换言之，限制为 $(k_1,\cdots,k_m)$ 的映射轨道 $N(k_1,\cdots,k_m)$ 的数量由下式决定：
$$
N(k_1,\cdots,k_m)=\left[x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}}\right]P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right).
$$
$Proof.\quad$设 $\mathcal X:=\{x_1,x_2,\cdots,x_k\}$ 为形式变元集，定义权函数 $w(c_i)=x_i$。则 $f$ 恰把 $A$ 中的 $k_i$ 个元素映成 $c_i$ 的充要条件是
$$
w(f)=x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},
$$
故 $N(k_1,\cdots,k_m)$ 就是这样的轨道条数。一方面
$$
\sum_{F\in\mathcal F}w(F)=\sum_{k_1+\cdots+k_m=n}N(k_1,\cdots,k_m)x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}},
$$
另一方面
$$
\sum_{F\in\mathcal F}w(F)=P_G\left(\sum_{i=1}^mx_i,\sum_{i=1}^mx_i^2,\cdots,\sum_{i=1}^mx_i^n\right),
$$
由此就得到 $N(k_1,\cdots,k_m)=\left[x_1^{k_1}x_2^{k_2}\cdots x_m^{k_{m}}\right]P_G\left(\sum\limits_{i=1}^mx_i,\sum\limits_{i=1}^mx_i^2,\cdots,\sum\limits_{i=1}^mx_i^n\right)$。$\square
我们已经知晓置换群是 $D_6$。运用带权的 Pólya 定理得其结果是
$$
\begin{aligned}
\left[x_1^2x_2^4\right]P_{D_6}(x_1+x_2,x_1^2+x_2^2,\cdots,x_1^6+x_2^6)=3.
\end{aligned}
$$
### 无标号简单图计数（图同构计数，[P4727](https://www.luogu.com.cn/problem/P4727)）
一张图是一个集合对 $([n],E)$，其中边集 $E\subseteq D$，且
$$
D=\binom{[n]}{2}.
$$
有标号的简单图被定义为映射
$$
\begin{aligned}
f_E:\quad\; D&\longrightarrow\{0,1\},\\
\{i,j\}&\longmapsto\begin{cases}
1,&\{i,j\}\in E,\\
0,&\{i,j\}\notin E.
\end{cases}
\end{aligned}
$$
对于 $g\in\mathfrak S_n$，其诱导出 $D$ 上的置换是
$$
\pi_g(\{i,j\})=\{g(i),g(j)\}.
$$
记 $G_n=\{\pi_g:g\in\mathfrak S_n\}$，由 Pólya 定理，$n$ 个点的无标号简单图数量是
$$
P_G(2,2,\cdots,2).
$$
${\bf Theorem\;17.\quad}n$ 阶无标号简单图的个数是
$$
\sum_{l_!+2l_2+\cdots+nl_n=n}\frac{2^{N(l_1,\cdots,l_n)}}{l_1!\cdots l_n!2^{l_1}\cdots2^{l_n}},
$$
其中
$$
N(l_1,\cdots,l_n)=\frac{1}{2}\left(\sum_{s,t}l_sl_t\gcd(s,t)-\sum_{2\nmid s}l_s\right).
$$
## 组合类的 Cycle 构造
下面我们运用带权的 Burnside 引理证明
$$
\begin{aligned}
\mathcal A=\text{C}{\small\text{YC}}(\mathcal B)&:=\text{S}{\small\text{EQ}}(\mathcal B)/\mathbf S\\&\Longrightarrow A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}.
\end{aligned}
$$
### 证明
设 $\mathcal A=\text{C}{\small\text{YC}}(\mathcal B)$，那么
$$
\mathcal A\cong\sum_{n\geq1}\mathcal B^n/\mathbf S,
$$
其中 $\mathbf S$ 是 $\langle\sigma\rangle$ 轨道等价类。我们要证明
$$
A(z)=\sum_{k=1}^{\infty}\frac{\varphi(k)}{k}\log\frac{1}{1-B(z^k)}.
$$
求 $\sum_{i=1}^Nw(O_i)$，其中 $\langle\sigma\rangle$ 作用于 $\mathcal B^n$ 上。运用带权 Burnside 引理
$$
\sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^n\sum_{(\beta_i)_{i\leq n}\in\psi(\sigma^k)}w((\beta_i)_{i\leq n}),
$$
而 $\sigma^k$ 是 $(k,n)$ 个 $n/(k,n)\text -$轮换之积，所以就有
$$
\sum_{i=1}^Nw(O_i)=\frac{1}{n}\sum_{k=1}^nB\big(z^{n/(k,n)}\big)^{(k,n)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}.
$$
于是
$$
\begin{aligned}
A(z)&=\sum_{n=1}^{\infty}\frac{1}{n}\sum_{d\mid n}\varphi(d)B\big(z^d\big)^{n/d}\\
&=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\sum_{n\geq 1}\frac{B\big(z^d\big)^{n}}{n}\\
&=\sum_{d=1}^{\infty}\frac{\varphi(d)}{d}\log\frac{1}{1-B(z^d)}.
\end{aligned}
$$