Burnside引理 与Polya定理

『组合数学』4. Burnside引理 与Polya定理

群的概念

• 定义：给定集合$G=\{a,b,c,d\}$和集合$G$的二元运算 $\cdot$ 并满足下面四个条件：
  • 封闭性：若$a,b\in G$, 则存在$c\in G$, 使得$a \cdot b = c$
  • 结合律成立：对于任意$a,b,c\in G,$有$(a\cdot b)\cdot c =a\cdot( b\cdot c)$
  • 存在单位元素：存在$e\in G, \forall a \in G. \quad a\cdot e=e \cdot a = a$
  • 存在逆元素： $\forall a \in G, \exist b \in G, a\cdot b = b\cdot a = e,b = a^{-1}$

下面举一些群的例子

• $G=\{-1,1\}$在普通乘法下是群
• $G = {0,1,...,n-1}$在 $mod \ n$的加法下是群
• 二维欧式空间所有缸体旋转$T=\{T_\alpha\}$构成群，其中$T_\alpha = \begin{pmatrix} cos\alpha && sin\alpha\\ -sin\alpha && cos\alpha \end{pmatrix}$
• 有限群：有有限元素的群，其元素个数成为阶，记做$|G|$
• $Abel$群/交换群，若群内任意二元素$a,b$恒满足$ab=ba$，
• 子群：$G$是群$H$是$G$的子集，$H$在$G$的原有运算下也是群，则称$H$是$G$的子群

群的基本性质

• 群的单位元唯一

  $e_1e_2 = e_1=e_2$

• 消去律成立：$ab=ac \Leftrightarrow b=c$,$\qquad ba = ca\Leftrightarrow b=c$

  同理证明一侧即可$\because ab=ac \therefore a^{-1}(ab)=a^{-1}(ac),结合律：b=c$

• 逆元唯一

  反证有两个逆元$b,c$, $ab=e, \ ac=e\$ 左边同时乘$a^{-1}$，唯一

• $(abc\cdots z)^{-1} = z^{-1}\cdots c^{-1} b^{-1}a^{-1}$

• $G$是有限群，$g=|G|$设$G=\{a_1,a_2,..,a_g \}$, 对$G$的任意元素$a$, 则比存在一个最小常数$r(a)$使得$a^{r(a)} = e$，进一步$a^{-1} = a^{r(a)-1}$

  设有限群$|G$$|$的阶为$k$，构造一个有$k+1$个元素的序列：$\{a,a^2,...,a^{k+1}\}$，由封闭性这些元素都在群中，由鸽巢原理知这$k+1$个元素至少有两个相同，于是有$a^l = a^m\Rightarrow a^{l-m}=e$

  对于有限群，总能找到最小的整数$r(a)$ 。 $QED$

置换群

所有的有限群都能被它表示

$n$阶置换：

$\begin{pmatrix} 1&2\cdots n\\ a_1&a_2\cdots a_n\end{pmatrix}$

易知$n$阶置换有$n!$个

置换群是群

• 封闭性：

  $\begin{pmatrix} 1&2\cdots n\\ a_1&a_2\cdots a_n \end{pmatrix}\begin{pmatrix} a_1&a_2\cdots a_n\\ b_1&b_2\cdots b_n \end{pmatrix}=\begin{pmatrix} 1&2\cdots n\\ b_1&b_2\cdots b_n \end{pmatrix}$

• 结合性：易证

• 单位元：

  $\begin{pmatrix} 1&2\cdots n\\ 1&2\cdots n \end{pmatrix}$

• 逆元素：

  $\begin{pmatrix} 1&2\cdots n\\ a_1&a_2\cdots a_n \end{pmatrix}*\begin{pmatrix} a_1&a_2\cdots a_n\\ 1&2\cdots n \end{pmatrix}=\begin{pmatrix} 1&2\cdots n\\ 1&2\cdots n \end{pmatrix}$

• 任意$n$阶有限群同构与一个$n$个文字的置换群

  要点：

  • 元素一一对应:双射

    即$n$阶有限群$G$与一$n$个文字的置换群同构,

    首先有限群内做运算得到的结果相当于一个排列，即对于某一元素$a_i$,对$n$个不同元素做运算$a_1a_i,...a_na_i$后仍然是不同元素（易证：否则：反证：右乘逆元就相等矛盾了。于是元素运算的结果对应与某个排列。便可进行下面的运算了

  • 运算保持：

    $p_ip_j=\begin{pmatrix} a_1&a_2\cdots a_n \\a_1a_i&a_2a_i\cdots a_na_i \end{pmatrix}\begin{pmatrix} a_1&a_2\cdots a_n\\ a_1a_j&a_2a_j\cdots a_na_j \end{pmatrix}$

    $$

    $=\begin{pmatrix} a_1&a_2\cdots a_n\\ a_1a_i&a_2a_i\cdots a_na_i \end{pmatrix}\begin{pmatrix} a_1a_i&a_2a_i\cdots a_na_i\\ a_1a_ia_j&a_2a_ia_j\cdots a_na_ia_j \end{pmatrix}$

    $=\begin{pmatrix} a_1&a_2\cdots a_n\\ a_1a_ia_j&a_2a_ia_j\cdots a_na_ia_j \end{pmatrix} \leftrightarrow a_ia_j$

循环、奇循环、偶循环

$m$阶循环：

$\begin{pmatrix} a_1&a_2\cdots a_m\\ a_2&a_2\cdots a_1 \end{pmatrix} = (a_1,a_2,...,a_m)$

注意：

• 令$p=$$n$阶循环, 易知$p^n = (1)(2)...(n) = e$

4-1任何一个置换都可以表示成若干循环的乘积

不断出入循环搜索即可，

定义： 2阶循环$(i,j)$叫作$i$和$j$对换或换位

4-2 任一循环都可以表示成对换的积

给出其中一种分解方法：

$(1,2,3,\cdots,n) = (1,2)(1,3)\cdots(1,n)$

数学归纳法证明即可, 注：别忘记忽略不写的自循环

当然分解不唯一，换位的数目也可不同，但是换位的奇偶性不变

定义4-2：若置换可分解为奇数个换位之积，奇置换。同理偶置换

可知数字华容道问题做换位：必定是偶置换

4-3 $S_n$中的偶置换的全体构成$\frac 12(n!)$子群$A_n$，称为交代群

• 封闭性：若$p_1,p_2$是偶置换$p_1p_2$当然也是偶置换
• 结合律：易证
• 单位元，包含原置换群的单位元$e$，（所以奇置换不成群，单位元是偶置换
• ）
• 逆元：$(i,j)$的逆元是$(i,j)$

再证阶数为$\frac 12(n!)$：即奇置换的个数$|B_n|$等于偶置换的个数$|A_n|$

• 任一偶置换加上置换$(i,j)$都是奇置换，有$|B_n|\ge |A_n|$

• 同理，于是个数相等

• 终于的实质内容与下节课揭晓.jpg…

4.4Burnside 引理

若干概念。。

1. 共轭类

   $p = (a_1...a_{k_1})(b_1...b_{k_2})...(h_1...h_{k_l})$

   其中$k_1+...+k_l = n$

   假设其中$k$阶循环出现的次数为$c_k$,$k$阶循环出现的次数用$(k)^{c_k}$表示

   于是易得$\sum kc_k=n$

   其中格式相同的称为共轭类

   定理4.4 $S_n$中属于$(1)^{c_1}...(n)^{c_n}$共轭类中元素个数为$\frac{n!}{c_1!..c_n! \ 1^{c_1}...n^{c_n}}$

   证明：左下元素表示去掉相同元素的排列，右下表示循环群为圆周排列

   （科普：圆周排列 排列n个不同元素的种数为$\frac{n!}{n}$）

2. $k$不动置换类

   设$G$是$\{1,2,3,...,n \}$的置换群，$G$中使$k$保持不变的置换全体: $Z_k$ 成为使 $k$不动的置换类

   可知群$G$关于$k$的不动置换类$Z_k$是$G$的子群

   • 封闭性：若两个置换是$k$不动，其乘积显然不动
   • 结合律、单位元：继承自群$G$
   • 逆元：群$G$中逆元含有因子$k$的

3. 等价类

   $R$：若$\exist p\in G$使得$kRj$

   关系$R$满足自反、对称、传递性，则称为等价关系

   由等价关系将$[1, n]$划分类若干等价类，元素$k$所属的等价类称为$E_k$

呜呜呜这节课全都是基本概念。。下节课可能才会和之前的主函数关联起来

（还有21天期末有点慌…）

1. 由等价关系将$[1, n]$划分类若干等价类，元素$k$所属的等价类称为$E_k$

重要定理4-11：$|E_k||Z_k| = |G|$

证明：$|E_k|$表示等价类的个数，$|Z_k|$则表示$k$不置换类的个数

若任意一个左边的都属于等式右侧，任意一个右侧的元素都属于等式左侧

假设等价类$|E_k| = l,$令$E_k = {a_1(=k),\cdots,a_l}$，其中为各不相同的元素

充分：

有置换$p\in Z_k$, 以及置换$p_i \ s.t. \quad k\mathop{\to}\limits^{p_i}a_i$变为等价类中的$a_i \quad i=1,2,\cdots,l$

于是有$k \mathop{\to}\limits^{p}k\mathop{\to}\limits^{p_i}a_i$ 即是$k\mathop{\to}\limits^{pp_i}a_i$

于是集合$Z_kp_j = G_j \subseteq G$, 并且集合间当$i\not=j \to G_i\cap G_j = \varnothing$

有$Z_kp_1 \mathop+\limits^.Z_kp_2 \mathop+\limits^. \cdots \mathop+\limits^.Z_kp_l \subseteq G$ 其中 $\mathop+\limits^.$表示不相交集合的并，

而直和的原因：如果相交集合不为空，必定有相同得的元素，即$k\mathop{\to}\limits^{pp_i}a_i =And\ k\mathop{\to}\limits^{pp_j}a_i$然而是不可能的，对于不同的置换

必要：

对于任一一个$G$中的置换$p$，都有其逆置换$p^{-1}$,使得$k\mathop{\to}\limits^{pp^{-1}}k$

则$pp^{-1}$属于$Z_k$, 于是任一一个置换$p$：$p \in Z_kp^{-1}$ 于是$G \subseteq Z_kp_1 \mathop+\limits^.Z_kp_2 \mathop+\limits^. \cdots \mathop+\limits^.Z_kp_l$

于是相等得证

$Burnside$引理：$G$$=\{a_1\cdots a_g\}$,其中$a_1 = e$
记$c_1(a_j)$中保持不变的元素个数 ，不同的等价类的个数为$l$
则$l = \frac{1}{|G|}[c_1{a_1}+c_1{a_1}+c_1{a_2}+\cdots+c_1{a_g}]$

证明：

略一下（画表有点麻烦）

$Polya$定理，设$\overline{G}$为$n$个对象的置换群，用$m$种颜色涂$n$个对象，每个对象一种颜色，不同的染色方案为
$l = \frac{1}{\overline G}[m^{C(\overline a_1)}+\cdots+m^{C(\overline a_g)}]$,其中 ${C(\overline a_k)}$是置换$a_k$的循环节数

证明：只需$m^{C(\overline p)} = c_1(\overline p)$,即转化为$Burnside$引理($p$为$G$的一个置换)即：对于$p_i$作用下不变的图像，也即是$p_i$中的循环节染一种染色：作为一种等价类 的图像

说了这么多干的举个例子感受威力：

例：对于正方体的八个顶点用红蓝二着色，求方案数

上顶面四个顶点称为1234，下面5678

所谓方案数也就是等价类的种数，此正方体对于三种旋转的方式可看做一样，

1. 对面中心作为旋转轴

   旋转90/270度时候

   此时八个顶点上下四个顶点为同一等价类：置换为（1,2,3,4）(5,6,7,8)此类情况对于三个轴，两种角度便是六个共轭类：$(4)^2$ 表示有两个4阶循环（下面都简写了）

   旋转180度时

   此时置换为$(1,3)(2,4)(5,7)(6,8)$ 三个轴每个为：$(2)^4$

2. 对边中心作为旋转轴

   只能绕180度点重合，有六个轴

   易知此时也是$(2)^4$, ：$(1,2)(7,8)(3,5)(4,6)$

3. 对角中心作为旋转轴，

   四个轴分别转120、240度的角度，

   置换为$(2)(8)(1,3,6)(4,7,5)$ 格式为$(1)^2(3)^2$

4. 当然还有不转的情况$(1)^8$

开始计算根据$Polya$定理：$m = \frac{1}{24} (2^8+6\times2^2+3\times 2^4+6\times2^6+8\times2^4) = 23$

再解释一下就是幂是颜色种数，分子为循环节的数目

此便可加深理解了：对于染色相同的循环节其经过变换仍然是同一种。

定义4-4 欠角：凸多面体中一个顶点有关的面角之和与360°的差成为该顶点的欠角：（平面是360度，凸起来便小于360度）

定理4-7 凸多面体的各个顶点的欠角之和为720°

证明：$V$$,S,E$分别是顶点集，面集，边集。

有欧拉定理$|V|+|S|-|E| = 2$

设$a_{ij}$为顶点$V_i$与面$S_j$的面角，$e_j$为$S_j$的边数给定$S_j$:

$\sum\limits_{V_i\in V}a_{ij} = (e_j-2)180$:内角和

$\sum\limits_{V_i \in V}(360° - \sum\limits_{S_j \in S}a_{ij}) = |V|360° - \sum\limits_{V_i \in V}\sum\limits_{S_j \in S}a_{ij} = 720°$

例题：足球由正五边形和正六边行组成，求其个数

：每个顶点由两个正六边形与一个正五边形组成，

其欠角为：$(360-120\times2-108) = 12°$,

于是共有60个顶点：$|V| = 60$

并且每个顶点被三条棱，每条棱用两个顶点，

于是有90个棱$|E| = 90$，$|S| = 32$

对于黑五边形：每个顶点仅用一次，于是每五个顶点组成一个五边形，于是有正五边形12个，正六边形20个

母函数形式的$Poyla$定理

包含更多的信息，使用母函数的形式表示出方案数的同时，还能表示每类方案的组成方式。效果可比指数函数的母函数形式

使用四种颜色$b,g,r,y$对三个球进行着色

例：$(b+g+r+y)^3 = \cdots+6bgr+\cdots\cdots$其中系数为方案的个数，文字项表示具体方案

于是对于$Poyla$定理，引入循环指数多项式得

$P(G) = \frac 1G\sum\limits_{i=1}^g\prod\limits_{k=1}^ns_k^{c_k(g_i)}$

引入例子比较容易说明：

骰子的不同方案数：

1. 母函数$Poyla$解法：对应于六种颜色每种用一次来涂正方体：

   $P=\frac 1{24}(x_1+\cdots+x_6)^6$ 并且求的是$x_1x_2\cdots x_6$的系数，可得结果为$\frac{6!}{24} = 30$

2. 直接应用$Burnside$定理

   其中24直接使用了对立方体的面染色的结论：对于立方体刚体的运动置换有24种

   由于六种颜色都不一样，于是除了自身不动的置换，任何置换(旋转)都无法保持不变的

   于是$m = \frac 1{24}\times(6!+0) = 30$

3. 利用容斥原理+$Poyla$定理

   比较麻烦。。

   通过直接计算的$m$种颜色不限使用对正方体的涂色种数为

   $n = \frac{1 }{24} \times (m^6+3m^4+12m^3+8m^2)$ 当$m=6$时计算可得$n=2226$

   (直接应用定理即得）其中$n_i = \{1,10,57,240,800,2226\}$

   而后再容斥原理，分别减去仅使用颜色为$1、2、3、4、5$的情况得到相同结果

   再稍微进一步算一下：以$l_i$表示仅使用$i$种方法的方案数

   $l_2 = n_2 - \tbinom{2}{1}l_1 = 8 \\\vdots\\l_6 = n_6- \tbinom 61 l_1 - \tbinom 62 l_2-\cdots-\tbinom 65l_5 = 30$

   简单解释一下$l_6$：从$6$种颜色中取出$i$种，共有$\tbinom 6i l_i$种方案