波利亚计数定理（Pólya enumeration theorem），也称为波利亚 - 伯恩赛德定理，是组合数学中用于解决在对称操作下的计数问题的重要工具，它结合了群论和生成函数的思想。下面从基本概念、定理内容、定理证明思路和应用举例几个方面详细介绍：

基本概念

• 置换群：设 (X={1,2,\cdots,n}) 是一个有限集合，(X) 上的一个置换 (\sigma) 是从 (X) 到 (X) 的一个双射。所有 (X) 上的置换构成的集合 (S_n) 在置换的复合运算下构成一个群，称为 (n) 次对称群。(S_n) 的任意一个子群 (G) 称为 (X) 上的一个置换群。
• 循环分解：任何一个置换 (\sigma\in S_n) 都可以分解为不相交的循环的乘积。例如，置换 (\sigma=\begin{pmatrix}1&2&3&4&5\2&3&1&5&4\end{pmatrix}) 可以分解为 ((123)(45))，其中 ((123)) 和 ((45)) 是不相交的循环。循环 ((a_1a_2\cdots a_k)) 表示 (a_1\to a_2,a_2\to a_3,\cdots,a_k\to a_1)。
• 循环指标：设 (G) 是 (X={1,2,\cdots,n}) 上的一个置换群，对于 (\sigma\in G)，设 (\sigma) 分解为 (j_1) 个 1 - 循环，(j_2) 个 2 - 循环，(\cdots)，(j_n) 个 (n) - 循环，则定义 (\sigma) 的循环类型为 ((j_1,j_2,\cdots,j_n))，满足 (\sum_{i = 1}^{n}ij_i=n)。群 (G) 的循环指标 (Z(G)) 定义为 (Z(G)=\frac{1}{\vert G\vert}\sum_{\sigma\in G}x_1^{j_1}x_2^{j_2}\cdots x_n^{j_n})，其中 (\vert G\vert) 是群 (G) 的阶。

定理内容

设 (X={1,2,\cdots,n}) 是一个有限集合，(G) 是 (X) 上的一个置换群，(C) 是 (m) 种颜色的集合。用 (C) 中的颜色对 (X) 中的元素进行染色，两个染色方案被认为是等价的当且仅当存在 (G) 中的一个置换 (\sigma) 使得一个染色方案通过 (\sigma) 的作用可以变成另一个染色方案。

设 (P(x_1,x_2,\cdots,x_n)) 是群 (G) 的循环指标 (Z(G))，将 (x_i) 替换为 (m^i)（(i = 1,2,\cdots,n)），则不同的染色方案数 (N) 为 (N = Z(G)(m,m^2,\cdots,m^n))。

更一般地，如果考虑带权的染色问题，设 (w(c)) 是颜色 (c\in C) 的权，对于一个染色方案 (f:X\to C)，其权 (W(f)=\prod_{x\in X}w(f(x)))。令 (P(x_1,x_2,\cdots,x_n)) 是 (G) 的循环指标，将 (x_i) 替换为 (\sum_{c\in C}w(c)^i)（(i = 1,2,\cdots,n)），则所有不同染色方案的权的和 (S) 为 (S = Z(G)(\sum_{c\in C}w(c),\sum_{c\in C}w(c)^2,\cdots,\sum_{c\in C}w(c)^n))。

定理证明思路

波利亚计数定理的证明主要基于伯恩赛德引理（Burnside's lemma）。伯恩赛德引理指出，设 (G) 是一个有限群，(X) 是一个有限集合，(G) 作用在 (X) 上，不同的轨道数（在 (G) 的作用下元素的等价类的个数）(N) 为 (N=\frac{1}{\vert G\vert}\sum_{g\in G}\vert X^g\vert)，其中 (X^g={x\in X:g(x)=x}) 是在 (g) 作用下不动的元素的集合。

在染色问题中，将染色方案的集合看作 (X)，置换群 (G) 作用在染色方案上。对于每个置换 (\sigma\in G)，计算在 (\sigma) 作用下不动的染色方案的个数，通过分析置换的循环分解，得到其与循环指标的关系，从而推导出波利亚计数定理。

应用举例

• 项链染色问题：假设有一个由 (n) 颗珠子组成的项链，用 (m) 种颜色对珠子进行染色。项链可以旋转，因此旋转后相同的染色方案被认为是等价的。这里的置换群 (G) 是由 (n) 个旋转置换组成的循环群 (C_n)。对于 (C_n) 中的旋转 (r^k)（旋转 (k) 个位置，(k = 0,1,\cdots,n - 1)），其循环分解中的循环个数 (d=\gcd(k,n))，每个循环的长度为 (\frac{n}{d})。(C_n) 的循环指标 (Z(C_n)=\frac{1}{n}\sum_{k = 0}^{n - 1}x_{\frac{n}{\gcd(k,n)}}^{\gcd(k,n)})。根据波利亚计数定理，不同的染色方案数 (N=\frac{1}{n}\sum_{k = 0}^{n - 1}m^{\gcd(k,n)})。
• 立方体染色问题：考虑用 (m) 种颜色对立方体的 6 个面进行染色，立方体可以通过旋转操作变换。立方体的旋转群 (G) 包含 24 个元素，分别是恒等旋转、绕对面中心连线旋转、绕对棱中点连线旋转和绕对角线旋转。通过计算每个旋转的循环分解，得到循环指标 (Z(G))，再将 (x_i) 替换为 (m^i) 就可以得到不同的染色方案数。