Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数学 » , , ,

Burnside引理和Polya定理

组合数学是计算机科学的一门基础学科,本文主要介绍组合数学中非常重要的两个定理:Burnside引理和Polya定理。这两个定理的理解需要有一定的抽象代数的数学基础,但实际应用起来却比较简单,且其对于解决常见的计数问题非常有帮助。

一 基本概念

群:一个集合G,在G上定义了二元运算*满足以下条件:

  1. 封闭性,即任意a∈G,b∈G,有a*b∈G。
  2. 结合律,(a*b)*c=a*(b*c)。
  3. 存在单位元e。对任意a∈G,a*e=e*a=a。
  4. 存在逆元。对任意元素a,存在b,使得a*b=b*a=e。

则称G是对于运算*的群。

置换:有限集到其自身的映射称为一个置换。如以下置换中,把1映射成2,2映射成1,3映射成4,4映射成3,5映射成5。

1 2 3 4 5   1 2 3 4 5   1 2 3 4 5
2 1 4 3 5   3 2 1 5 4   2 3 5 1 4

轮换:如果一个置换把元素a1映射成a2,a2映射成a3,a3映射成a4,…,an映射成a1,而其他元素保持不变,则该置换称为一个轮换,记为(a1,a2,a3,…,an)。
如果两个轮换的没有公共的变动点,称这两个轮换是不相交的。

任何置换都可以唯一表示成不相交轮换的乘积。如上图左边的置换可表示成(1,2)(3,4)(5),一般把映射成自身的元素省略,即写成(1,2)(3,4)。
n次置换f可以表示成c1个长为1的轮换、c2个长为2的轮换、…、cn个长为n的轮换的乘积,称f的类型为(c1, c2, …, cn)。如以上置换类型为(1,2)。

置换的乘积运算即为两个映射的复合,如上图左边两个置换相乘后得到右边置换。
对称群:n元集合G上的所有置换在置换乘法下构成一个群,称为n次对称群。
置换群:对称群的子群称为置换群。
Note:置换群不一定要包含所有置换,但其包含的置换仍应该满足群定义中的性质。

轨道:对n次置换群G,对任意元素k,k在G中的置换下可以取到的值的集合,称为k在G下的轨道,记为G(k)={g(k)|g属于G}
例 4次置换群G={(1), (1 2), (3 4), (1 2)(3 4)}中,G(1)=G(2)={1,2}, G(3)=G(4)={3,4}

稳定子群 对n次置换群G,对任意元素k,G中使k保持不变的置换的全体,称为k在G中的稳定子群,记为Gk。
例 4次置换群G={(1), (1 2), (3 4), (1 2)(3 4)}中,G1=G2={(1), (3 4)}, G3=G4={(1), (1 2)}

定理: G是在有限集合X上的一个置换群,对任意的k属于X,有 |G| = |G(k)| * |Gk|
可化为 |G(k)| = |G| / |Gk|,即要求|G(k)|只需求|Gk|。
例 4次置换群G={(1), (1 2), (3 4), (1 2)(3 4)}中,|G(1)| = |G|/|G1| = 4/2 = 2

不动点:置换a中保持不变的元素称为a的不动点。
若a的类型为(c1, c2, …, cn),则a的不动点个数为c1,记为c1(a)。

二 Burnside引理及简单应用

Burnside引理:G是X={1, 2, …, n}上的置换群,G={a1, a2, …, am},则G在X上的不同轨道的个数为

t = (cl(a1) + cl(a2) + … + cl(am)) / |G|

例1:用2中颜色给2×2棋盘染色,求在旋转等价条件下的不同染色方案数。
先不考虑旋转,共2^4=16中方案,记为X={1, 2, …, 16},编号如下:

2x2染色编号

考虑四种逆时针旋转引起的置换:
旋转0度:p1 = (1)(2)…(16)
旋转90度:p2 = (1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)
旋转180度:p3 = (1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16)
旋转270度:p4 = (1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
则G={p1, p2, p3, p4}组成一个4阶置换群,且G在X上的轨道数目即为不同的染色方案数,
利用burnside引理,有T = (c1(p1)+c1(p2)+c1(p3)+c1(p4)) / |G| = (16+2+4+2) / 4 = 6,不同方案如下

不同方案

G是集合S = {a1, a2, …, an}上的一个置换群,g为G中类型为(c1, c2, …, cn)的一个置换,
将其对应为x1^c1 * x2^c2 * … * xn^cn (x1, x2, …, xn为变量),
定义PG(x1, x2, …, xn) = |G|^(-1) * sum(x1^c1*…xn^cn)(g∈G)为G的轮换指标

例2:用S={a1, a2, a3, a4}表示2×2棋盘的4个格子,旋转置换群G={(a1)(a2)(a3)(a4), (a1 a2 a3 a4), (a1 a3)(a2 a4), (a1 a4 a3 a2)}
则G中置换的类型分别为(4,0,0,0),(0,0,0,1),(0,2,0,0),(0,0,0,1),则轮换指标为
PG(x1,x2,x3,x4) = 1/4 * (x1^4 + x2^2 + 2×4)

三 Polya定理及简单应用

Polya定理:S是n元集合,G是S上的置换群,用集合C中的m种颜色对S中的元素染色,所有染色方案在G作用下互不等价的方案数为

P_G(m,m,…,m) = |G|^(-1) * sum(m^(c(g))) (for g in G)

即G的轮换指标,其中c(g)为置换g中不相交轮换总数(循环节个数),若g类型为(c1, c2, …, cn),则c(g)=c1+c2+…+cn

例3:以上棋盘染色问题中m=2,则t = (2^4+2^2+4) / 4 = 24 / 4 = 6

例4:求等边三角形ABC三个顶点染红绿蓝三种颜色的不同方案数
三角形可以绕中心旋转0、120、240,以及绕3条中线翻转,可用以下置换群表示
G={(A)(B)(C), (A B C), (C B A), (A)(B C), (B)(A C), (C)(A B)}
轮换指标为PG(x1,x2,x3) = 1/6 * (x1^3+3x1x2+2×3)
这里m=3,于是根据Polya定理,不同方案数为PG(3,3,3) = 1/6 * (3^3+3*3*3+2*3)=10

例5(POJ2409):m种颜色染n个珠子串成的项链,旋转和翻转后一样的视为同一种,求不同的染色数。
直接使用Polya定理求解,找出所有的置换,并求出置换的循环节个数,然后求和m的循环节个数的次数,再除以置换个数。

  1. 旋转置换,分为选择0个珠子、1个珠子、…、n-1个珠子,记其循环节个数分别为c(i)。显然c(0)为n,对于其他c(i),一个点转lcm(n,i)/i次回到原来位置,于是循环节长度为lcm(n,i) / i,循环节个数为n / (lcm(n,i)/i) = gcd(n,i)。
  2. 翻转置换,分n为奇数和偶数讨论:
    • n为奇数,共有n种翻转情况,均是以一个顶点和中心的连线翻转,翻转后一个点保持得到自身,另外的点两两配对,于是循环节的长度为1+(n-1)/2。
    • n为偶数,有两种翻转情况。
      1. n/2个以两点连线为轴的翻转。翻转后两个点回到自身,另外的点两两配对,于是循环节长度为2+(n-2)/2。
      2. n/2个以两边中点连线为轴的翻转。翻转后所有点两两配对,循环节长度为n/2.于是一个也是n个置换,n/2置换的循环节长度为n/2,n/2置换的长度为2+(n-2)/2。

于是可以求出不同的染色方案数。

例6(POJ2145):n种颜色染n个珠子,旋转后一样的视为同一种,求不同方案数(模p)。
跟上题一样,只是只有旋转置换,可以枚举所有的n个旋转置换应用Polya定理求出:

ans = sum(n^(gcd(n,i)/n)) for i = 0…n

这里n很大(10^9),以上方法复杂度过高。考虑上上述枚举i时会出现许多相同的gcd(n,i),这些相同值的和可以直接用乘法求出,于是可以考虑枚举gcd(n,i)的取值k,于是问题变为存在多少个不同的i,使得gcd(n,i)=k,答案是欧拉函数φ(n/k)个。
由于k是n的约数,于是枚举时只需枚举1到sqrt(n),计算为(Polya定理最后要除以n,这里在计算过程指数的减一已经除了n):

ans = sum(phi(n/k) * n^(k-1) + phi(k) * n^(n/k-1)) for 1<=k<=sqrt(n), k|n

如果n刚好是完全平方数,还需

ans += phi(k) * n^(k-1)

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论