Skip to content

4. Burnside 引理和Polya定理

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

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

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

4.0 考点+例题

4.1 群相关概念

4.1.1 群的定义

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

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

满足一下条件

  • 封闭性

    ,则存在,使得

  • 结合律

    任意,有

  • 有单位元

    存在,任意

  • 有逆元

    任意,存在,记为

例子

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

在普通乘法下是群,

在mod n的加法下是群

例子

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

4.1.2 相关概念

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

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

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

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

单位元唯一

消去律成立

4.2 置换群

参考资料

bash
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阶置换共有个,同一置换用这样的表示可有个表示法,

image-20220105194724562

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


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

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

例子

啥意思呢???

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

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

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

2) 循环概念

image-20220105170010569

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

其实可以用循环进行表示

例子

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

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

3) 共轭类

为置换群

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

其中,

循环出现的次数,用表示

中置换的格式为

例子

比如的形式

的形式都是为

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

注意点

中属于形式的元素个数为

image-20220105172557836

循环在洗牌中应用

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

image-20220105174734749

image-20220105174747036

答案一共是 8次

4) 对换概念

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

4.2.2 置换群概念

1) 置换分解

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

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

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

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

2) 置换群定义

给定n个元素组成的集合

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

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

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

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

,3个换位,奇置换

,0个换位,偶置换

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

4.2.3 应用

1) 多面体群

正凸多边形

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

欧拉定理

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

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

image-20220105190928900

image-20220105191001252

image-20220105191115044

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

2) 着色问题的等价类

例子1

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

img

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

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

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

对称性:如果A和B等价,则B和A等价

传递性:如果A和B等价,B和C等价,则A和C等价

例子二

image-20220105202124957

旋转0度的情况

旋转90度状况

旋转180度

旋转270度

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

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

image-20220105202053302

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着色,有多少种方案??

image-20220106091558036

解;在3维空间考虑,3顶点的置换群

转120度,

对称轴翻转

不动

结果就是

例子

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

image-20220106093726958

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

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

不动,1个

一共4个置换,方案数

4.3.2 正四面体总结

正四面体-顶点的转动群

例子

甲烷的4个键任意用

链接,有多少种方案?

image-20220106092447207

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

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

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

4.3.3 正六面体总结

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

image-20220106100712885

对于正六面体转动群

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

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

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

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

正六面体转动群的阶数为

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

整理一下的

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

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

image-20220106102900772

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

正六面体转动群的阶数为

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

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

4.4 母函数型的Polya定理

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

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

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

image-20220106110551568

一共8个置换

方案数为

4.4.1 概念

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

4.4.2 例子

例子

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

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

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

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

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

一共是6个不同的置换

的系数为

的系数

例子二

image-20220106111835450

所以的系数为

image-20220106112814819

例子三

image-20220106113032811

image-20220106113140936

例子四

正四面体点4着色,面3着色,棱2着色,求方案数??

例子五

image-20220106114352409

4.4.3 图的计数

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

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

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

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

完全图的边数

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