ACM培训第十三讲-组合数学

ACM程序设计第十二讲-组合数学湖南工学院张新玉[e-mail]主要内容•1母函数及其应用•2群的概念•3polya定理2020/1/13研究以下多项式乘法：可以看出：x2项的系数a1a2+a1a3+...+an-1an中所有的项包括n个元素a1，a2，…an中取两个组合的全体；同理：x3项系数包含了从n个元素a1，a2，…an中取3个元素组合的全体；以此类推。(13－1)2020/1/14若令a1=a2=…=an=1，在（8-1）式中a1a2+a1a3+...+an-1an项系数中每一个组合有1个贡献，其他各项以此类推。故有：（13－2）特例：2020/1/15母函数定义：•对于序列a0，a1，a2，…构造一函数：称函数G(x)是序列a0，a1，a2，…的母函数2020/1/16Forexample:(1+x)n是序列C(n,0),C(n,1),...,C(n,n)的母函数。如若已知序列a0，a1，a2，…则对应的母函数G(x)便可根据定义给出。反之，如若已经求得序列的母函数G(x)，则该序列也随之确定。序列a0，a1，a2，…可记为{an}。2020/1/17实例分析2020/1/18例1：若有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？如何解决这个问题呢？考虑构造母函数。如果用x的指数表示称出的重量，则：1个1克的砝码可以用函数1+x表示，1个2克的砝码可以用函数1+x2表示，1个3克的砝码可以用函数1+x3表示，1个4克的砝码可以用函数1+x4表示，2020/1/19几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：(1+x)(1+x2)(1+x3)(1+x4)=(1+x+x2+x3)(1+x3+x4+x7)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10从上面的函数知道：可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克的方案有2：5=3+2=4+1；同样，6=1+2+3=4+2；10=1+2+3+4。故称出6克的方案有2，称出10克的方案有12020/1/110例2：求用1分、2分、3分的邮票贴出不同数值的方案数——•因邮票允许重复，故母函数为：以展开后的x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4；即：4=1+1+1+1=1+1+2=1+3=2+22020/1/111概念：整数拆分•所谓整数拆分即把整数分解成若干整数的和（相当于把n个无区别的球放到n个无标志的盒子，盒子允许空，也允许放多于一个球）。•整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。2020/1/112练习（写出以下问题的母函数）：•例3：若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出哪几种重量？各有几种方案？例4:整数n拆分成1，2，3，…，m的和，求其母函数。例5：如若上例中m至少出现一次，其母函数又如何？2020/1/113如何编写程序实现母函数的应用呢？核心问题——关键：对多项式展开2020/1/114以整数拆分为例：观察以下的母函数：…首先思考：如果让你手工计算，你是怎样处理的？实际编程：让计算机按照自己的思路计算即可～//Authorbyzxy-戏称木头大神#includeiostreamusingnamespacestd;constintlmax=10000;intc1[lmax+1],c2[lmax+1];intmain(){intn,i,j,k;while(cinn){for(i=0;i=n;i++){c1[i]=0;c2[i]=0;}for(i=0;i=n;i++)c1[i]=1;for(i=2;i=n;i++){for(j=0;j=n;j++)for(k=0;k+j=n;k+=i){c2[j+k]+=c1[j];}for(j=0;j=n;j++){c1[j]=c2[j];c2[j]=0;}}coutc1[n]endl;}return0;}2020/1/116例题：HDOJ_1398SquareCoinsSampleInput210300SampleOutput14272020/1/117算法分析：典型的利用母函数可解的题目。G(x)=(1+x+x2+x3+x4+…)(1+x4+x8+x12+…)(1+x9+x18+x27+…)…//HDOJ_1398SquareCoins#includeiostreamusingnamespacestd;constintlmax=300;intc1[lmax+1],c2[lmax+1];intmain(void){intn,i,j,k;while(cinn&&n!=0){for(i=0;i=n;i++){c1[i]=1;c2[i]=0;}for(i=2;i=17;i++){for(j=0;j=n;j++)for(k=0;k+j=n;k+=i*i){c2[j+k]+=c1[j];}for(j=0;j=n;j++){c1[j]=c2[j];c2[j]=0;}}coutc1[n]endl;}return0;}//HDOJ_1398SquareCoins…intmain(void){intn,i,j,k;intelem[17]={1,4,9,16,25,36,…,169,196,225,256,289}while(cinn&&n!=0){for(i=0;i=n;i++){c1[i]=1;c2[i]=0;}for(i=2;i=17;i++){for(j=0;j=n;j++)for(k=0;k+j=n;k+=elem[i-1]){c2[j+k]+=c1[j];}for(j=0;j=n;j++){c1[j]=c2[j];c2[j]=0;}}coutc1[n]endl;}return0;}相关习题基础题：1028，1085，1171Polya计数定理211，置换群2，循环、奇循环与偶循环3，Burnside引理4，Polya定理5，母函数形式的Polya定理及其应用引论22在组合计数问题中经常碰到两大困难:(1)找出问题通解表达式的困难.这个困难通过引入生成函数能够克服.(2)区分所讨论的问题类型的困难,即哪些问题是相同的,哪些是不同的.解决这个困难,就能在计数过程中避免重复或遗漏.考虑下面的计数问题：把一个22的方格棋盘用绿或白两色涂色，如果棋盘可以随意转动，问有多少种不同的涂色方案？2312345678910111213141516引论且看上图,若棋盘固定不动,每个方格都可以涂上绿或白色,有两种选择.根据乘法法则,共有2⁴=16种不同的涂色方案。但当棋盘可转动时，其中的一些方案可以变成另一些方案。如方案3逆时针旋转90º即得方案4。同样，方案也可以变成方案5和6，于是我们说方案3，4，5，6是同一类方案。为真正求出不同的方案数。我们需要新的工具。24Redfield-Polya定理是组合数学理论中最重要的定理之一．自从1927年Redfield首次运用groupreductionfunction概念，现在称之为群的循环指标（circleindexofagroup），至今80多年来，它在许多实际计数问题上得到了广泛的应用，它以置换群为理论基础，与生成函数有机地结合在一起,揭示了一类具有组合意义的计数的规律性．•抽象地说，在一集合内，定义了一个等价关系，人们往往关心由这个等价关系所决定的等价类的数目，Refield-Polya理论就是为解决这类问题而发展起来的复杂计数理论．引论251.置换群1，群的定义(iv)存在逆元:对G的任意元素a,恒有一个bG,使得a•b=b•a=e,元素b称为元素a的逆元，记为a-1(iii)存在单位元:G中存在一个元素e,使得对于G的任意元素a,恒有a•e=e•a=a定义1：给定一个集合G={a,b,c,…}和集合G上的二元运算•，满足如下条件：(i)封闭性：若a,bG,则存在cG使得a•b=c(ii)结合律：(a•b)•c=a•(b•c)则称集合G在运算•之下是一个群，或称G是一个群。26定义2：置换即[1,n]到自身的1-1变换:[1,n][1,n],2，置换群是最重要的有限群，所有的有限群都可以用之表示n阶置换共有n!个。12n12...npaa...ap:iai=ip,(aiaj,ij)于是,a1a2…an是[1,n]的一个全排列。称此置换为n阶置换，记为1置换群272.1置换的乘法运算12341234,3124432112pp212341234p31244321123431241234==3124243124311p先看一个例子，设定义1置换群28这表示先作p1的置换，再作p2的置换：1置换群12121212pppppppp132,214,323,441.故21234p24311p类似的有212341234p43213124123443211234=4321421342131p29评注：1置换群1221pppp1212ppppi(i)12n12niii12nii...i12...npaa...aaa...a于是我们定义乘法如下：12n12n12n12n12aaa12n12n12n12aaaaaa12naa...a12...n12...np,pbb...baa...abb...baa...a12...n12...npp=bb...bbb...baa...a30定理1[1,n]上所有的置换按上述乘法构成一个群。即满足1）封闭性2）结合律3）有单位元4）有逆元1置换群12n12...np,aa...a112n112n12...naa...apaa...a12...n我们称此群为n个文字的对称群，记为Sn。311置换群令P={Pi|ai∈G},则P≈G设G={a1,a2,…,an}，指定G中任一元ai,任意aj∈G，Pi：aj→ajai，则Pi是G上的一个置换。定理2:任一n阶有限群同构于一个n个文字的置换群。12ni1i2iniaa...apaaaa...aaii11Pa映射定义3：Sn的任意一个子群称为置换群。321231置换群例1等边三角形的运动群。绕中心转动120，不动，绕对称轴翻转。123456123123123p,p,p,123231312123123123p,pp132321213123240º231213180ºp3p5332循环、奇循环与偶循环为一个m阶循环置换(简称为循环或轮换),12345(14523)431522.2,置换的表示方法12m1m12m23m1aa...aa(a,a,...,a)aa...aa定义4：称于是注意到(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)即一个m长循环有m种表示方法。12345(154)(2)(3)52314342循环、奇循环与偶循环定义5：两个循环称为不相交的，若它们无共同文字.若p=(a1a2…an),则pn=(1)(2)…(n)=e.定理3任一置换可表成若干不相交循环的乘积。不相交的循环相乘可交换。如(132)(45)=(45)(132).12345(132)(45),31254例如352循环、奇循环与偶循环定理3任一置换可表成若干不相交循环的乘积。12n12...np.aa...