波利亚定理.ppt

1
第四章Burnside引理和Pólya定理
马昱春
清华大学计算机系
教学评估
2014年12月15日9:00-12月26日21:00
2
学期计划
Project II

选做
任选题目
论文,分组1-3人
心路历程
期末考试
17周周二(1月13日)晚或者周三(1月14日)晚
3
4
回顾
定义回顾
置换群用G表示,G中的每个置换表示为ai
G={a1,a2….ag}={e,(1 2),(3 4),(1 2)(3 4)}
G中某个置换ai的k阶循环出现的次数为 ck(ai)
a1=e=(1)(2)(3)(4) c1(a1) = 4 (1)4
a4=(12)(34) c1(a4) = 0 c2(a4) = 2 (2)2
G中使某元素k不动置换类,记做Zk
G中的Z1={e,(3 4)}
G中数k所属的等价类记为Ek
E1=E2={1,2} E3=E4={3,4}
几个常用群
对称群Sn
交错(交代)群An
转动群
S4={(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243), (1234), (1243), (1324), (1342), (1423), (1432), (12)(34), (13)(24), (14)(23)}.
A4={ e,(123),(124),(132),(134),(142), (143), (234), (243), (12)(34), (13)(24), (14)(23)}.
5
6
Burnside引理
Burnside引理(Burnside lemma(1897)
Cauchy(1845)-Frobenius(1887) lemma
Orbit-counting theorem
The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to Frobenius(1887).
设G={a1,a2,…ag}是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。c1(ak)是在置换ak的作用下不动点的个数,也就是长度为1的循环的个数。 G将[1,n]划分成l个等价类。等价类个数为:
7
Burnside引理
例一正方形分成4格,2着色,有多少种方案?
图象:看上去不同的图形。
方案:经过转动相同的图象算同一方案。图象数总是大于方案数。
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
8
图象与方案
图象:固定不动,物理位置上具有不同染色的即为不同的图象
方案:经过外力变换,可以完全重合的不同图象为同一个方案
内部结构不变
置换:外力产生的变换,如转动,翻转
图象中的等价类
9
不动:a1=(1)(2)…(16)
逆时针转90度:a2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)
顺时针转90度:a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
转180度:a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16)
(16+2+2+4)/4=6(种方案)
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
l=[c1(a1)+c1(a2)+…+c1(ag)]/|G|
10
QUIZ