4. Burnside 引理和Polya定理

用六种不同颜色涂一正方体，一面一色，且每个面颜色不同，会有多少种涂法？？

这是会转的物体，记数方式会有点不同？？？？怎么考虑这种旋转类的物体呢？？

这个时候就需要引入置换等一系列的公式了

4.0 考点+例题

4.1 群相关概念

4.1.1 群的定义

群就是它将数学的运算进行归类

定义 给定集合和上的二元运算,满足下列条件称为群

满足一下条件

• 封闭性

  若,则存在，使得

• 结合律

  任意,有

• 有单位元

  存在，任意

• 有逆元

  任意，存在,记为

例子

在普通乘法下是群，因为其满足4个条件

在普通乘法下是群，

在mod n的加法下是群

例子

二维欧式空间所有刚体旋转构成群。其中

4.1.2 相关概念

群元素的个数是有限的，是有限群

群元素的个数是无限的，是无限群

有限群的元素个数叫做群的阶，记作.

设是群，是的子集，若在原有的运算之下也是一个群，则称为的一个子群

单位元唯一

消去律成立

4.2 置换群

参考资料

https://zhuanlan.zhihu.com/p/35428113

4.2.1 前期数学准备

置换群是最重要的有限群，所有的有限群都可以用之表示

1) 置换概念

有限集上的双射函数称为上的置换或排列

置换就是把n个元素做一个全排列，比如1，2，3，4分别变成3，1，2，4，或者分别变成4，3，2，1。

一般地，1变,2变,...的置换记为

，即时，称为上的置换为次置换，上的次置换可表示为

性质

n阶置换共有个，同一置换用这样的表示可有个表示法,

如时

一般的时，记上所有置换的集合为

---

左合成运算，先进行运算，在进行运算

右合成运算，先进行运算，在进行运算

例子

啥意思呢？？？

就是1变成了3,2变成了1 ，3变成2,4还是4

啥意思呢？是把1变成了3 ，在中呢是把3变成了2,所以呢，他们相乘结果就是1变成了2

可以推断出置换不满足结合律

2) 循环概念

Rotate(1->4->3->2->1)

其实可以用循环进行表示

例子

若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换

任一置换可表示成若干不相交循环的乘积

3) 共轭类

设为置换群

对于，存在一种分解方法使得置换分解为若干不相交的循环乘积

其中,

设阶循环出现的次数为,用表示

则中置换的格式为

则

例子

比如的形式

的形式都是为

在置换群中具有相同形式的置换全体，叫做该形式相应的

注意点

在中属于形式的元素个数为

循环在洗牌中应用

54张牌去掉大小王，一共52张牌，然后一分为二，每次洗牌，从左边放一张牌，右边放一张牌。直到两边牌没有，请问这样子的牌洗多少次就可以恢复原样？

答案一共是 8次

4) 对换概念

任一循环都可以表示为对换的积

4.2.2 置换群概念

1) 置换分解

中任意元素可以分解为对换之积

任一循环都可以表示为对换的积，每个置换的分解形式不是唯一的

任一置换表示成对换的个数的奇偶是唯一的

对换是一种做出来的带有符号的东西。

2) 置换群定义

给定n个元素组成的集合

上的若干置换所构成的群称为次置换群

上的所有置换构成的群称为次对称群

次对称群的子群即为次置换群

置换分成两大类：奇置换与偶置换

,3个换位，奇置换

，0个换位，偶置换

中所有偶置换构成一阶为的子群称为交错群，记作

4.2.3 应用

1) 多面体群

正凸多边形

凸多边形中，如果各边相等且各角也相等，这样的多边形叫做正多边形

欧拉定理

任何凸多面体的顶点数与面数的和都较棱数多2，即。

由欧拉定理推出：凸正多面体只有5种，即正四面体，正八面体，正二十面体，正六面体(正方体)，正十二面体

正八面体群或正六面体群由24个运动构成群，它与四次对称群同构，所以正八面体群与正六面体群是一致的，都是4次对称群.有时把四次对称群称为正八面体群或正六面体群

2) 着色问题的等价类

例子1

给2×2方格中涂黑白两色，有几种方法？16种

如果规定逆时针旋转90度，180度，270度后相同的方案算一种，那么答案就变成6种

这样的问题称为等价计数问题。也就是说题目会定义一种等价关系，满足等价关系的元素看成同一类，只统计一次。

自反性：每个元素和他自身等价

对称性：如果A和B等价，则B和A等价

传递性：如果A和B等价，B和C等价，则A和C等价

例子二

旋转0度的情况

旋转90度状况

旋转180度

旋转270度

如果某个置换使得图像变成，称和属于同一个等价类

还有一些置换对一些图根本不起作用，比如旋转180度这种置换对于图6不起作用，这种类就叫做不动置换类

4.2.4 类总结

根据上面的总结

置换群用表示，中每个置换表示为

例子

• 中某个置换的阶循环出现的次数为

1) k不动置换类

若 是中的某一个整数,中使保持不变的置换全体,记作 ，叫做中使元素不动置换类，

比如中的

2) 等价类

在的作用下的“轨迹"形成一个封闭的类，数所属的类成为的等价类，记作

中数所属的等价类记作

3) orbit定理

4.2 Burnside 引理

是根据orbit定理推演出来的

4.2.1 概念

对于一个置换，若一个着色方案经过置换后不变，称为的不动点。

将的不动点数目记为，则可以证明等价类数目为所有的平均值。

分成了个等价类，

可以推断出

等价类的个数=所有置换中一阶循环的个数/所有置换的个数

4.2.2 应用

正方形顶点二着色只考虑旋转的等价类个数是6，一共是4个置换

旋转0度的情况，一阶循环是16

旋转90度状况，一阶循环是2个

旋转180度，一阶循环是4个

旋转270度，一阶循环是2个

所以对应的引理公式为

4.3 Polya定理

用六种不同颜色涂一正方体，一面一色，且每面颜色不同，会有多少种涂法？？

burnside 引理针对着色图像集的转动群来求解的

求解2着色的不同方案，可以用burnside引理

用六种不同颜色涂一正方体一面一色，不同面可以同色，会有多少种涂法？？

4.3.1 概念

设是个对象的一个置换群，是置换的循环的个数，对m种颜色对个对象着色，着色方案数为

二者比较

polya定理中的群是作用在个对象上的置换群

Burnside引理中的群是对这个对象染色后的方案集合上的置换群

4.3.2 平面题目总结

例子

等边三角形的3个顶点用红，蓝，绿3着色，有多少种方案？？

解；在3维空间考虑，3顶点的置换群

转120度，个

对称轴翻转个

不动个

结果就是

例子

有3种不同颜色的珠子串成4颗珠子的项链

绕中心转,为4阶循环,2个

绕中心转,为2阶循环,1个

不动,1个

一共4个置换，方案数

4.3.2 正四面体总结

正四面体-顶点的转动群

例子

甲烷的4个键任意用

链接，有多少种方案？

的结构是一个空间正4面体，原则居于正4面体的中心。正4面体的转动群按转动轴分类：

情况	循环	个数
不动旋转		1
以顶点与对面的中心连线为轴，按反时针方向旋转120度		8
以正四面体的对对边之中点联线为旋转转180度		2

1表示不动循环有1个，表示进行的4着色，上面的4表示有多少个循环，不动旋转中有4个循环，所以写4

4.3.3 正六面体总结

对象不同，对应的置换不同

对于正六面体转动群

• 面的置换 6个面
• 顶点的置换 8个顶点
• 棱的置换 12条棱

1) 正六面体-顶点的转动群

现在研究一下正六面体 顶点的置换

情况	循环情况	个数
不动		1
面面中心旋转度		个
面面中心转180度		3
棱中对棱中转180度		6
对角线为轴转度

正六面体转动群的阶数为个

用2种颜色给正6面体的8个顶点着色，有多少种方案？

整理一下的

2) 正六面体-面的转动群

现在研究一下正六面体的面的置换

情况	循环	个数
面的置换不动		1
面面中心转度		个
面面中新转度		3
棱中对棱中转180度		6
对角线为轴转度

正六面体转动群的阶数为

如果题目变成用6种不同颜色涂一正方体，一面一色，不同面可以同色，会有多少种涂法？？

骰子的6个面分别有点，有多少种不同的方案？？

4.4 母函数型的Polya定理

母函数可以对着色方案进行枚举

比如对3个相同的球用四种颜色(红色，黄色，蓝色，绿色) 涂染，所有可能的颜色组合是？？

有3种不同颜色的珠子，串成4颗珠子的项链，有哪些方案？？、

一共8个置换

方案数为

4.4.1 概念

母函数的Polya定理得出的方案数为

4.4.2 例子

例子

等边三角形的3个顶点用红，蓝，绿3着色，有多少种方案？？

它所对应的置换群很简单，如下

旋转度，,2个。对应的母函数为

按照对称轴翻转，3个,对应的母函数为

不动，1个，对应的母函数为

一共是6个不同的置换

的系数为

的系数

例子二

所以的系数为

例子三

例子四

正四面体点4着色，面3着色，棱2着色，求方案数？？

例子五

4.4.3 图的计数

polya的重要应用就是图的计数

n个顶点的简单图有多少不同的图形？？

简单图：过两个顶点没有多于一条的边，且不存在环的图形

n个无标志顶点的完全图中的边进行二着色，求不同方案数？？

完全图的边数

n个无标志顶点的完全图中的边进行二着色，求不同方案数