组合数学之母函数形式Polya定理及其应用.ppt

《组合数学之母函数形式Polya定理及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《组合数学》第十一讲母函数形式Polya定理及其应用1第十一讲:内容提要III.Boole函数的计数II.母函数形式的Polya定理IV.图简单图的计数*I.Polya定理及其证明*2Pòlya定理设G是n元集合S上的置换群,CS是用集合C中m种颜色对S中元素进行染色的全部方案组成的集合,则CS中在G作用下互不等价的染色方案数为:I.Pòlya定理及其证明*3其中PG(x1,x2,…,xn)为置换群G的轮换指标,c(g)是置换g中不相交轮换总数.若g的类型为(c1,c2,…,cn),则c(g)=c1+c2+…+cn.我们给出的其实是特殊形式的P

2、olya定理,更一般形式的是带权的形式.可以用来计算有条件限制的计数问题.下面我们简单介绍Polya定理的证明.4123456781011121316151495证明设CS是n个对象集合S={a1,a2,…,an}用m种颜色C={c1,c2,…,cm}进行涂色所得的全部方案的集合.显然

3、CS

4、=mn.对于置换群G中任何一个元素g,它是S的一个置换,自然也诱导出CS上的一个置换g*.具体方式:g*:ffg,fCS.即：g*(f)=fg,或：(g*(f))(a)=f(g(a)),aS.6G*={g*

5、gG}构成CS的一个置换群,而且

6、G*

7、

8、=

9、G

10、.互不等价的染色方案数正好是G*在CS上的不同轨道数目.而要计算轨道数目,需要应用Burnside引理.既然

11、G*

12、=

13、G

14、,我们只需要计算G*中每个元素不动点数目.设gG,下面来计算g*的不动点的数目.不仿设置换g的轮换分解如下:g=(a,b,c,…,p,q)(r,s,…,t)…(u,v,…,w),7如果fCS在g*下不动,即g*(f)=f,那么f(b)=f(g(a))=f(a),类似可以得到f(c)=…=f(p)=f(q)=f(a).说明轮换(a,b,c,…,p,q)中的元素颜色相同.同样有,f(r)=f(s)=…=f(t);…

15、;f(u)=f(v)=…=f(w).由此可见,如果f是g*的一个不动点,那么f一定把位于置换g的同一个轮换中的元素染成了同样的颜色.8反过来,如果f把位于g的同一个轮换中的元素染成同样的颜色,则必然是g*的不动点.这样g*不动点的数目就等于这样染色的数目,它把g的同一个轮换中的元素染同样的颜色.因为g有c(g)个轮换,每个轮换可以染一种颜色,共有mc(g)种不同的染色方案.所以,c1(g*)=mc(g).由Burnside引理可以得到结论.9我们这里给出的Polya计数定理其实是一种特殊形式.一般形式的Polya定理还可以用来解决有条件限制而

16、且互相不等价的染色方案数目.还有一个问题是如何列举出所有不同类型的染色方案?显然Polya定理无法告诉我们这些.它只能告诉我们总数.母函数形式Polya定理可以满足这个要求.II.母函数形式的Pòlya定理10先通过一个简单例题说明思想.例1.假设要用b,g,r,y这4种颜色涂染3个同样的球,则所有方案可形式地表示为(b+g+r+y)3.由于三个球无区别,故乘法是可交换的,例如b2g=gb2.把这个形式展开:(b+g+r+y)3=b3+g3+r3+y3+3b2g+3b2r+3b2y+3g2b+3g2r+3g2y+3r2b+3r2g+3r2y+3

17、y2g+3y2r+3y2b+6bgr+6bgy+6brg+6gry展开式中的不同项表示不同的方案,每项系数表示该方案的数目.11只要把上面这种思想方法用于Polya定理,就可以得到母函数形式Polya定理.设G是n个对象集合S={a1,a2,…,an}上的一个置换群,要用m种颜色b1,b2,,bm进行染色,我们需要讨论并决定互不等价的染色方案的情况.根据Polya定理,不等价的染色方案数目可以通过下面的公式得到:12其中c(g)是置换g的轮换总数目,而是置换群G的轮换指标.如果置换g的类型为:(c1(g),c2(g),…,cn(g)),c(g

18、)=c1(g)+c2(g)+…+cn(g),我们知道13其含义是让置换g的ci个长为i的轮换中每个轮换中的元素染同样的颜色,这是为了得到由g诱导出的置换g*的不动点.当时我们并不关注这个同样的颜色究竟是哪一种颜色.现在我们想列举出染色方案情况,就需要关注这个问题.根据刚才例题的思想,对应于置换g的每个长为i的轮换因子,其中i个元素的颜色可以形式的表示为:14既然g有ci=ci(g)个长为i的轮换,自然长为i的轮换中出现的元素的染色方案可以形式的表示为:考虑到g的全部轮换分解情况,相应于置换g的染色方案可以形式表示为:由此可以知道,总的染色方案的

19、列举只要在轮换指标中令:15即可得到能列举出方案情况的母函数形式的Polya定理:这就是母函数形式的Polya定理的计数公式,在具体应用中展开并按照同