Pólya计数理论

1 群

群$(G, \cdot)$: 闭合, 结合律, 幺元, 逆

1.1 置换群

置换为双射$\pi:[n]\to [n]$, 置换之间的操作符 $\cdot$ 定义为函数的复合, 即$(\pi \cdot \sigma)(i)=\pi(\sigma(i))$

对称群$S_n$

$S_n$表示$[n]$的所有置换的集合. 容易验证$S_n$和函数复合操作 $\cdot$ 构成一个群, 称为$n$元对称群.
$S_n$的子群称为置换群.

循环群$C_n$

定义特殊的置换$\sigma$满足$\forall i, ~\sigma(i)=(i+1)\mod n$, $C_n=\{\sigma^t|t\ge 0\}$, $C_n$称为$n$阶循环群, 生成元为$\sigma$, 是$n$边正多边形的旋转对称.

Dihedral群$D_n$

定义特殊置换$\rho$满足$\forall i\in [n], ~\rho(i)=n-i-1$. 把$\rho$加入$C_n$则得到Dihedral群$D_n$. 为正$n$边形翻转和旋转操作的对称群

Cycle decomposition

将置换等价表示为cycle的复合

1.2 群操作

群操作

例子: 项链上色

问题: $n$个珠子的项链, 珠子每个是$m$种颜色之一. 形式化的为$x:[n]\to[m]$, 即把$m$个颜色分配给$n$个位置. $X=\{x:[n]\to[m]\}$为这样的分配的集合.

考虑两种对称操作:

旋转: 循环群$C_n$
旋转和翻转: dihedral群$D_n$

项链的操作被描述为$X$上的群操作. 对于置换群$G$, 任意$\pi \in G$和$x\in X$, 群操作$\pi\circ x$定义为$(\pi \circ x)(i)=x(\pi(i))$

2 Burnside’s Lemma

2.1 轨道(Orbits)

定义和性质如下:

可以把轨道理解为一个等价类, 同一等价类中的元素可以通过$G$中的操作相互转换.

2.2 invariant set and stabilizer

$G$: 作用于集合$X$上的置换群. $\pi\in G$, $x\in X$.

$\pi$的invariant set: $X_\pi =\{x\in X|\pi\circ x=x\}$
$x$的stabilizer: $G_x=\{\pi\in G|\pi \circ x=x\}$

引理:

$|G_x||Gx|=|G|$

证明:

$Gx=\{x_1,x_2,\cdots, x_t\}$, $P=\{\pi_1,\pi_2,\cdots, \pi_t\}$, 其中$\pi_i\circ x=x_i, ~ i = 1,2,\cdots, t$
构造一个$G$和$P\times G_x$的双射:
- 对于任意$\pi\in G$, 对于某个$x_i$有$\pi\circ x=x_i$
- 因为$\pi_i\circ x=x_i$, 所以$\pi_i\circ x=\pi\circ x$, 故$(\pi_i^{-1}\cdot \pi)\circ x=x$
- 记$\sigma=\pi_i^{-1}\pi$, 则$\pi_i\cdot \sigma =\pi$, $\sigma \circ x=x$, 即$\sigma \in G_x$.
- 因此每个$\pi\in G$对应一个不同的pair$(\pi_i, \sigma)\in P\times G_x$
- 对于每个$\pi_i\in P$和$\sigma\in G_x$, 有$\pi=\pi_i\cdot \sigma\in G$
- 对于$\pi_i\sigma=\pi_j\tau$, 有$(\pi_i\cdot \sigma)\circ x=x_i$, $(\pi_j\cdot \tau)\circ x=x_j$, 所以$x_i=x_j$, $\pi_i=\pi_j$, $\tau =\sigma$
- 因此是双射, 得证.

2.3 轨道计数

Burnside’s Lemma: 轨道的个数(记做$|X/G|$) 为

$|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|$

证明:

记$A(\pi, x)=\begin{cases}1 & \pi\circ x=x,\\0& ~ otherwise. \end{cases}$
$\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi, x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi, x)=\sum_{x\in X}|G_x|$.
定义轨道为$X_1,\cdots, X_{|X/G|}, 则$
$|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|X_i|}=|G||X/G|$
使用上面的引理, 有
$\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G||X/G|$

3 Pólya’s Theory of Counting

3.1 The cycle index

对于某种上色$x$, 如果$x$在$\pi\in G$下是不变的, 那么在$\pi$的每个circle中的所有位置必须有相同颜色. 即如果$\pi$被分解为$k$个circle, 那么$|X_\pi|=m^k$.

定义一个置换群$G$中的cycle index:

对任意$\pi\in G$, 如果$\pi$是$k$个cycle的乘积, 且第$i$个cycle的长度为$l_i$,令

$M_\pi(x_1,x_2,\cdots, x_n)=\prod_{i=1}^k x_{l_i}.$

$G$的cycle index为

$P_G(x_1,x_2,\cdots,x_n)=\frac{1}{|G|}\sum_{\pi\in G}M_\pi(x_1,x_2,\cdots, x_n)$

3.2 Pólya’s enumeration formula

对于任意tuple $v=(n_1,n_2,\cdots, n_m)$满足$n_1+n_2+\cdots+n_m=n$和$n_i\ge 0, ~ 1\le i\le m$, 表示第$i$个颜色的珠子有$n_i$个.

pattern inventory:

$a_v$的多元生成函数

$F_G(y_1,y_2,\cdots, y_m)=\sum_va_vy_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}$

Pólya’s enumeration formula:

非等价的$n$个物体的$m$色上色的pattern inventory为

$F_G(y_1,y_2,\cdots, y_m)=P_G(\sum_{i=1}^my_i,\sum_{i=1}^my_i^2,\cdots,\sum_{i=1}^my_i^n)$

证明思路如下:

$X^v=\{x:[n]\to[m]|\forall i\in [m], x^{-1}(i)=n_i\}$表示第$i$个颜色出现$n_i$的着色方案集合(所有都算, 对称的也算)
$X_\pi^v=\{x\in X^v|\pi\circ x=x\}$
先(用Burnside’s lemma)证明
$a_v=\frac{1}{G}\sum_{x\in G}|X_\pi^v|$
再证明
$M_\pi(\sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2,\cdots,\sum_{i=1}^m y_i^n)=\sum_{v=(n_1,\cdots,n_m)\\n_1+\cdots+n_m=n}|X_\pi^v|y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}$
考虑中间值$(y_1^{l_1}+y_2^{l_1}+\cdots,y_m^{l_1})y_1^{l_2}+y_2^{l_2}+\cdots,y_m^{l_2})\cdots (y_1^{l_m}+y_2^{l_m}+\cdots,y_m^{l_m})$, 和等式左右都相等.
合起来即证毕.