【组合数学】Pólya 计数理论

1. 引言

Pólya 计数理论是数学中的一个分支，主要研究的是对称性在组合计数问题中的应用。该理论以匈牙利数学家乔治·波利亚（George Pólya）的名字命名，他在20世纪初提出了许多关于对称性和组合计数的重要思想。

该理论主要用于解决组合计数问题，即计算对象的数量，但通常存在对称性质。例如计算不同颜色的珠子串成的项链有多少种不同的排列方式，考虑到项链旋转对称性，这个问题就可以用 Pólya 计数理论来解决。

Pólya 计数理论涉及的基础知识主要包括:

1. 对称群：学习群论中的对称群及其性质，对于理解对称性在计数中的作用至关重要。
2. 循环指标定理（Cycle Index Theorem）：这是 Pólya 计数理论的核心定理，用于计算具有对称性的结构的计数问题。
3. 组合学：熟悉组合学的基础概念和技巧，如排列、组合、置换等。

Pólya定理通常更专注于处理置换群的计数问题，强调对称性对对象计数的影响。
Burnside引理则更侧重于计算群作用下不同轨道（等价类）的数量，它提供了一种更通用的方法来计算群作用的结果。

---

2. 置换群

“群” 的定义：
给定集合 G 和 G 上的二元运算 “?” ，如果满足以下 4 个条件，则称代数结构 $(G,?)$为群：

• 封闭性：“?” 运算在 G 上是封闭的，即对任意 , $a,b\in G$，都有 $a?b\in G$
• 结合律：“?” 运算满足结合律，即对任意 , $a,b,c\in G$ ，都有 $a?(b?c)=(a?b)?c$
• 存在单位元：存在 $e\in G$ ，对任意 $a\in G$ ，满足 $e?a=a?e=a$ 称为 G 的单位元
• 存在逆元：对任意 $a\in G$ ，存在 $a^{?1}\in G$ ，满足 $a^{?1}?a=a?a^{?1}=e$ 称为 a 的逆元

置换群 （Permutation Group）
是指由一组置换（即一种对象到另一种对象的一一映射）组成的群。这个群包含了所有可能的置换，并且满足群的性质，比如封闭性、结合律、单位元和逆元。

对称群（Symmetric Group）
是一个特定类型的置换群，表示某个集合上所有可能的置换组成的群。具体而言，对称群是由集合上的所有元素的全排列所构成的置换群。如果集合有n个元素，那么其对称群的阶（群的大小）就是 n! ，记作 S? 。

对称群是置换群的一种特殊情况，它描述了一个特定集合上的所有置换的全集。同时，置换群可以表示更一般性的情况，不仅仅局限于描述集合上的置换。

置换可以表示为不相交的轮换之积，比如$$\sigma =\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 3& 2& 1& 6& 5& 7& 8& 4\end{array}\right)=(13)(2)(5)(4678)$$σ 写成 2 个长为 1、1 个长为 2、1 个长为 4 的轮换之积，称它为 $1^2{2}^1{4}^1$ 型的置换
若σ 有 $b_i$ 个长为 $i(1\le i\le n)$ 的不相交轮换因子，则称 σ 是 $1^{b_1}{2}^{b_2}...n^{b_n}$ 型的置换。对于 $b_i=0$ 的那些因子(即不存在长为 i 的轮换因子)，则不必写出

习题1、 求正四面体关于顶点集合{1，2，3，4}的置换群

---

3. Burnside 引理

共轭类

定义 3.1：设 D,R 是有限集合，从 D 到 R 的映射全体记为 F = { f ∣ f : D → R } F=\{f|f:D\rightarrow R\} F={f∣f:D→R}
G 是 D 上的一个置换群，对 任 意 $f_1,f_2\in F$ ， 若 存 在 σ ∈ G ， 使 得 对 任 意 d ∈ D ， 等 式 $f_1(d)=f_2(\sigma (d))$ 均成立，则称 $f_1$ 和 $f_2$ 是 G 等价的。

G 等价关系是 F 上的等价关系，满足三个条件：自反、对称、传递。

定义 3.2：对任意 s,t ∈ G ，若存在 g ∈ G ，使得 $s=g^{?1}tg$ ，则称 s 与 t 是G 共轭的

引理 3.1：两个置换 s,t ∈ Sn 关于 Sn 是共轭的，当且仅当它们是同型的

引理 3.2：Sn 中属于 $1^{b_1}{2}^{b_2}...n^{b_n}$ 型的元素个数为 $\frac{n!}{b_1!b_2!...b_n!?1^{b_1}{2}^{b_2}...n^{b_n}}$
其中 $b_1+2b_2+...+n{b}_n=n$ 。
分母中：

• $b_1!b_2!...b_n!$ 表示互不相交的轮换乘积可以交换：$b_k$ 个长为 k 的轮换因子在全排列中是不同的全排列
• $1^{b_1}{2}^{b_2}...n^{b_n}$ 表示轮换因子的书写方式：长为 k 的轮换可以写成 k 种形式，而长为k的轮换因子有$b_k$个

例如，S3 中有 3 个共轭类，分别是 $1^3$ 型 1 个，$3^1$ 型 2 个，$1^1{2}^1$ 型 3 个。

---

k 不动置换类

定义 3.3：设 G 是 {1,2, …,n} 上的置换群，令 Z k = { σ ∣ σ ∈ G , σ ( k ) = k } Z_k=\{\sigma|\sigma\in G,\sigma (k)=k\} Zk?={σ∣σ∈G,σ(k)=k} 是 G 中使元素 k 保持不动的置换全体

例如 G = { σ I , ( 1 , 2 ) , ( 3 , 4 ) , ( 1 , 2 ) ( 3 , 4 ) } G=\{\sigma_I,(1,2),(3,4),(1,2)(3,4)\} G={σI?,(1,2),(3,4),(1,2)(3,4)}，则 Z 1 = Z 2 = { σ I , ( 3 , 4 ) } Z_1=Z_2=\{\sigma_I,(3,4)\} Z1?=Z2?={σI?,(3,4)}； Z 3 = Z 4 = { σ I , ( 1 , 2 ) } Z_3=Z_4=\{\sigma_I,(1,2)\} Z3?=Z4?={σI?,(1,2)}。 即 1 不动置换类和 2 不动置换类为(34)，3 不动置换类和 4 不动置换类为(12)。

Burnside 引理

引理 3.3：设 G = { a 1 , a 2 , . . . , a n } G = \{a_1,a_2, ...,a_n\} G={a1?,a2?,...,an?} 是 D={1,2, …, n} 上的置换群，则 G 诱导出来的等价类个数为$$l=\frac{1}{|G|}\sum _{i=1}^{g}c(a_i)$$其中，$c(a_i)$ 表示在置换 $a_i$ 作用下保持不变的元素个数

习题2、 G = { σ I , ( 14 ) ( 23 ) , ( 12 ) ( 34 ) ( 56 ) , ( 13 ) ( 24 ) ( 56 ) } G=\{\sigma_I,(14)(23),(12)(34)(56),(13)(24)(56)\} G={σI?,(14)(23),(12)(34)(56),(13)(24)(56)} 是D = {1，2，3，4，5，6} 上的置换群。求G在D上的等价类个数

习题3、一个正方形均分成 4 个格子，用两种颜色对 4 个格子着色，能得到多少种方案？经过旋转吻合的两种方案属于同一种方案

解：因为每格有两种颜色可供选择，故有如图所示的 16 种可能方案
每个图都绕过中心的轴逆时针方向旋转 90°，180°，270°时，得到 16 种图像的一种排列，可以看作是原 16 种图像的一种置换。

1. 不动置换：$p_1=(c_1)(c_2)(c_3)(c_4)(c_5)(c_6)(c_7)(c_8)(c_9)(c_{10})(c_{11})(c_{12})(c_{13})(c_{14})(c_{15})(c_{16})$
2. 旋转 90°：$p_2=(c_1)(c_2)(c_3{c}_4{c}_5{c}_6)(c_7{c}_8{c}_9{c}_{10})(c_{11}{c}_{12})(c_{13}{c}_{14}{c}_{15}{c}_{16})$
3. 旋转 180°：$p_3=(c_1)(c_2)(c_3{c}_5)(c_4{c}_6)(c_7{c}_9)(c_8{c}_{10})(c_{11})(c_{12})(c_{13}{c}_{15})(c_{14}{c}_{16})$
4. 旋转 270°：$p_4=(c_1)(c_2)(c_6{c}_4{c}_5{c}_3)(c_{10}{c}_8{c}_9{c}_7)(c_{11}{c}_{12})(c_{16}{c}_{14}{c}_{15}{c}_{13})$

由Burnside 引理，不同等价类的个数为 $l=\frac{1}{4}(16+2+4+2)=6$，其 $c(p_1)=16,c(p_2)=2,c(p_3)=4,c(p_4)=2$。不同的图像如图所示：

---

4. Pólya 计数定理

等价类集合中所有等价类权的和通常称为该等价类集合的模式表（pattern inventory）。

模式表用于描述一组对象在某种等价关系下的分类情况，这些对象根据特定的性质或规则被分成不同的等价类。

一个直观的例子是将一组物体按照颜色进行分类。假设有一些球，有红色、蓝色和绿色三种颜色的球。现在要按照颜色来分组，但是每个等价类（颜色）的大小（球的数量）可以不同。例如，可能有3个红球、4个蓝球和2个绿球。

这个情况下，对于这组球，等价类集合是按颜色分类的，分为了3个等价类：红色、蓝色和绿色。而模式表就是每个等价类中物体数量的总和，即各颜色球的数量之和：3（红色） + 4（蓝色） + 2（绿色）= 9。

引理 4.1： 设 G 是 D={1,2,…,n } 上的置换群，R = { $r_1,r_2,...,r_m$ }(可理解为m种着色)， F = { f ∣ = f : D → R } F=\{ f | =f: D → R\} F={f∣=f:D→R}则 F 上的全部模式表为 $P_G({\sum }_{r\in R}w(r),{\sum }_{r\in R}{w}^2(r),...,{\sum }_{r\in R}{w}^n(r))$

4.1 对点着色问题

习题4、对图中的顶点进行 m 着色，问有多少种方案?

解：1) 不动置换 ${\sigma }_I$ ，即 $1^9$ 型置换有 1 个
2) 以 $i$ 为中心，旋转 90°，180°，270°，则分别有(aceg) (bdfh)，(ae)(bf)(cg)(dh)，(agec)(hfdb)．这类旋转可以确定 $1^1{4}^2$ 型 2 个，$1^1{2}^4$ 型 1 个
3) 以 bf，hd 为轴翻转 180°，则有(ac)(dh)(eg)，(ag)(bf)(ce)．这类旋转可以确定 $1^3{2}^3$ 型 2 个
4) 以 ae，cg 为轴翻转 180°，则有(cg)(hb)(df)，(ae)(hf)(bd)．这类旋转可以确定 $1^3{2}^3$ 型 2 个
所以，该置换群的轮换指标为 $P_G(x_1,x_2,...,x_9)=\frac{1}{8}(x_1^9+2x_1{x}_4^2+x_1{x}_2^4+4x_1^3{x}_2^3)$
等价类个数即着色方案数为 $l=P_G(m,m,...,m)=\frac{1}{8}(m^9+2m^3+m^5+4m^6)$

习题5、有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案？

解：令 D={a,b,c,d,e,f,g,?,i} , R = { c 1 , c 2 } R=\{c_1,c_2\} R={c1?,c2?} ,6个棋盘格染2种颜色的方法是 F：D→R，由此确定D上的置换为

1. 不动置换 ${\sigma }_I$ ，即 $1^9$ 型置换有 1 个
2. 以 $i$ 为中心，旋转 90°，180°，270°，则分别有(aceg) (bdfh)，(ae)(bf)(cg)(dh)，(agec)(hfdb)．这类旋转可以确定 $1^1{4}^2$ 型 2 个，$1^1{2}^4$ 型 1 个
3. 以 bif，hid 为轴翻转 180°，则有(ac)(dh)(eg)，(ag)(bf)(ce)．这类旋转可以确定 $1^3{2}^3$ 型 2 个
4. 以 aie，cig 为轴翻转 180°，则有(cg)(hb)(df)，(ae)(hf)(bd)．这类旋转可以确定 $1^3{2}^3$ 型 2 个

所以，该置换群的轮换指标为 $P_G(x_1,x_2,...,x_9)=\frac{1}{8}(x_1^9+2x_1{x}_4^2+x_1{x}_2^4+4x_1^3{x}_2^3)$
F的全部模式表 $$\begin{gathered} P_G(c_1+c_2,c_1^2+c_2^2,...,c_1^9+c_2^9) \\ =\frac{1}{8}[(c_1+c_2{)}^9+2(c_1+c_2)(c_1^4+c_2^4{)}^2+(c_1+c_2)(c_1^2+c_2^2{)}^4+4(c_1+c_2{)}^3(c_1^2+c_2^2{)}^3] \end{gathered}$$根据题意，$c_1^2{c}_2^7$ 系数为 $\frac{1}{8}[(\genfrac{}{}{0ex}{}{9}{2})+4[\left(\genfrac{}{}{0ex}{}{3}{0}\right)\left(\genfrac{}{}{0ex}{}{3}{1}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\left(\genfrac{}{}{0ex}{}{3}{0}\right)]+(\genfrac{}{}{0ex}{}{4}{1})]=\frac{1}{8}(36+24+4)=8$

习题6、对正六角形的6个顶点用5种颜色进行着色。试问有多少种不同的方案,旋转使之重合作为相同处理？

解：令 D={a,b,c,d,e,f} , R = { c 1 , c 2 , c 3 , c 4 , c 5 } R=\{c_1,c_2,c_3,c_4,c_5\} R={c1?,c2?,c3?,c4?,c5?} 6个点染5种颜色的方法是 F：D→R，由此确定D上的置换为

1. 不动置换 ${\sigma }_I$ ，即 $1^6$ 型置换有 1 个
2. 以六边形中点为中心，旋转 60° 和 300°，有(abcdef) 这类旋转可以确定 $6^1$ 型 2 个；旋转 120° 和 240°，有(ace)(bdf) 这类旋转可以确定 $3^2$ 型 2 个；旋转 180°，有(ad)(be)(cf) 这类旋转可以确定 $2^3$ 型 1 个
3. 以绕对角连线旋转180°，则有(a)(d)(be)(cf),(ad)(b)(e)(cf),(ad)(be)( c)(f)．这类旋转可以确定 $1^2{2}^2$ 型 3 个
4. 以对边中点连线为轴翻转 180°，则有(ab)(cf)(de),(af)(be)(cd),(bc)(ad)(fe)．这类旋转可以确定 $2^3$ 型 3 个

所以，该置换群的轮换指标为 $P_G(x_1,x_2,...,x_6)=\frac{1}{12}(x_1^6+2x_6+2x_3^2+3x_1^2{x}_2^2+4x_2^3)$
F的全部模式表

根据题意，$c_1^2{c}_2{c}_3{c}_4{c}_5，c_1{c}_2^2{c}_3{c}_4{c}_5，c_1{c}_2{c}_3^2{c}_4{c}_5，c_1{c}_2{c}_3{c}_4^2{c}_5，c_1{c}_2{c}_3{c}_4{c}_5^2$ 项的系数之和为 $\frac{1}{12}(5?\frac{6!}{2!1!1!1!1!})=150$

---

4.2 对面着色问题

习题7、骰子的 6 个面分别有 1，2，3，4，5，6 个点，问有多少种不同的方案？

解：问题相当于对正六面体的 6 个面用 6 种颜色对之着色，要求各面的颜色都不一样

1. 不旋转，可确定 $1^6$ 型置换 1 个
2. 以相对两面中心连线为轴的旋转．这种轴共有 3 条，对于每条轴可做 ± 90°，180° 旋转．这类旋转可以确定 $1^2{4}^1$ 型置换 6 个，$1^2{2}^2$ 型置换 3 个
3. 以相对两边中点连线为轴的旋转．这种轴共有 6 条，对于每条轴可做 180°旋转．这类旋转可以确定 $2^3$ 型置换 6 个
4. 以正六面体对角线为轴的旋转．这种轴有 4 条，对于每条轴可做 ± 120°旋转．这类旋转可以确定 $3^2$ 型置换 8 个

所以正六面体可产生 24 种置换，该置换群轮换指标为
$P_G(x_1,x_2,...,x_6)=\frac{1}{24}(x^6+6x_1^2{x}_4+3x_1^2{x}_2^2+8x_3^2+6x_2^3)$
用 Pólya 计数定理求解

---

4.3 重复球放盒子

习题8、将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？

解：令 D = { w 1 , w 2 , b 1 , b 2 } , R = { c 1 , c 2 } D=\{w_1,w_2,b_1,b_2\},R=\{c_1,c_2\} D={w1?,w2?,b1?,b2?},R={c1?,c2?}，四个球往两个盒子里放的放法是 F：D→R。
由于$w_1,w_2$是两个相同的白球，$b_1,b_2$是两个相同的黑球，由此确定出D上的置换群为
G = { σ I , ( w 1 w 2 ) , ( b 1 b 2 ) , ( w 1 w 2 ) ( b 1 b 2 ) } G=\{σ_I,(w_1w_2),(b_1b_2),(w_1w_2)(b_1b_2)\} G={σI?,(w1?w2?),(b1?b2?),(w1?w2?)(b1?b2?)}
其轮换指标为 $P_G(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^4+2x_1^2{x}_2+x_2^2)$
F 上的等价类个数由Pólya 计数 可得 $l=P_G(2,2,2,2)=\frac{1}{8}(2^4+2?2^2?2+2^2)=9$
这 9 个不同方案为：$(?,wwbb),(w,wbb),(b,wwb),(ww,bb),(wb,wb),(wwbb,?),(wbb,w),(wwb,b),(bb,ww)$

F的全部模式表$$\begin{gathered} P_G(c_1+c_2,c_1^2+c_2^2,c_1^3+c_2^3,c_1^4+c_2^4) \\ =\frac{1}{4}[(c_1+c_2{)}^4+2(c_1+c_2{)}^2(c_1^2+c_2^2)+(c_1^2+c_2^2{)}^2] \end{gathered}$$盒1与盒2中各放两个球的方案数是 $c_1^2{c}_2^2$项的系数，即为 $\frac{1}{4}[(\genfrac{}{}{0ex}{}{4}{2})+2+2+2]=3$
具体方案为：$(ww,bb),(wb,wb),(bb,ww)$