组合数学6

1组合数学Combinatorics6容斥和鸽巢6-1且容且斥清华大学马昱春从加法法则谈起[加法法则]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。ABAB3容斥原理AB•容斥原理–InclusionandExclusionPrinciple–容斥的计数思想是:•先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来；•然后再把计数时重复计算的数目排斥出去；•使得计算的结果既无遗漏又无重复。4容斥原理例[1，20]中2或3的倍数的个数[解]2的倍数是：2，4，6，8，10，12，14，16，18，20。10个3的倍数是：3，6，9，12，15，18。6个但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=135•若A和B是集合U的子集，补集complement•[德摩根DeMorgan定理]{|}AxxUxA且(a)ABAB(b)ABAB容斥原理引论UBA6容斥原理引论DeMogan定理的推广：设A1,A2,….An是U的子集,证:采用数学归纳法212......nnAAAAA1则(a)A212......nnAAAAA1A正确2112121111...(...)(......nnnnnnnnAAAAAAAAAAAAAA1则A即定理对n+1也是正确的。容斥原理求有限集合A和B的并的元素数目。ABABABABCABCABBCABCAC-8容斥原理定理：ABCABCABBCABCAC-9容斥原理ABCDABCDABBCADABCABDBCDABCDAC四个集合的：10容斥原理1211112......(1)...nii=1jikj+AnnniijiijijknnAAAAAAAAAAA121211112.........(1)...nii=1jikj-AnnnnniijjkiijinnAAANAAAANAAAAAAAA,NA又A11Inclusion-ExclusionPrinciple||||||||||212121AAAASAA计算不在A1也不在A2中的元素个数若x不属于A1或A211-0-0+0=1若x属于A1但不属于A201-1-0+0=0若x属于A2但不属于A101-0-1+0=0若x属于A2且属于A101-1-1+1=0两边相等12计算不满足任意属性的元素.x不满足任何属性11-0-0…+(-1)m0=1x只满足1个属性01-1-0…+(-1)m0=0x只满足n个属性nm0C(n,0)-C(n,1)+C(n,2)+…+(-1)mC(n,m)=C(n,0)-C(n,1)+C(n,2)+…+(-1)nC(n,n)+0…+0=0两边相等，同样计算不满足任何属性的元素个数mmkjijiimAAAAAAAAASAAA2121)1(………(x+y)m=C(m,0)xm+C(m,1)xm-1y+…+C(m,m)ymIfx=1,y=-1：0=C(m,0)-C(m,1)+…+(-1)mC(m,m)•Inclusion–exclusionprinciple–ThisconceptisattributedtoAbrahamdeMoivre(1718)–ItfirstappearsinapaperofDanieldaSilva(1854)–LaterinapaperbyJ.J.Sylvester(1883)Oneofthemostusefulprinciplesofenumerationindiscreteprobabilityandcombinatorialtheoryisthecelebratedprincipleofinclusion–exclusion.Whenskillfullyapplied,thisprinciplehasyieldedthesolutiontomanyacombinatorialproblem.15组合数学Combinatorics6容斥和鸽巢6-2容斥的精妙清华大学马昱春16举例例求从1到500的整数中能被3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合500500166,100;355003315ABAB被3或5除尽的数的个数为16610033233ABABAB例求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：6个字母全排列：|S|=6!设A为ace作为一个元素出现的排列集:|A|=4!，B为df作为一个元素出现的排列集:|B|=5!，A∩B为同时出现ace、df的排列数:|A∩B|=3!。17举例||||||||||BABASBABA5823546!!!!18举例例求由a,b,c,d四个字母构成的n位符号串中，a,b,c都至少出现一次的符号串数目。解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3n个，即：32nnBCABACCBA1ABCa，b，c至少出现一次的n位符号串集合即为4()(33243)1nnnnABCABACCBABCABC19举例例求不超过120的素数个数。因112=121，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设Ai为不超过120的数i的倍数集，i=2，3，5，7。2357232527351201206040231201202417,571201202012,2310120120881415AAAAAAAAAAAA，，，，，，203757235237257120120532135120423512022371201257AAAAAAAAAAAAA，，，，，235723572325273537572352372573572357120AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA120(60402417)(20128853)(4211)27.注意：因为27个数中排除了2，3，5，7四个素数，又包含了1这个非素数。故所求的不超过120的素数个数为：27+4-1=3021例欧拉函数(n)是求小于n且与n互素的数的个数。在计算机领域中广泛使用的RSA公钥密码算法也正是以欧拉函数为基础的。(8)=48=23，小于8且与8互素有1357分析的化身:欧拉欧拉进行计算看起来毫不费劲儿，就像人进行呼吸，像鹰在风中盘旋一样。他是历史上最多产的数学家。•彼得堡学院为了整理他的著作整整花了47年。•欧拉确实常常在两次叫他吃晚饭的半小时左右的时间里赶出一篇数学论文•欧拉是史上发表论文数第二多的数学家，全集共计75卷；他的纪录一直到了20世纪才被保羅·埃尔德什打破人生波折：失明，火灾1783年9月18日，他77岁的时候，欧拉写出了他对天王星轨道的计算。他在喝着茶跟孩子玩的时候，中风发作。手中烟斗掉了，只说出一句话我要死了,欧拉便停止了生命和计算。23举例kipnAii...,,||21jikjippnAAjiji,...,,,,||21例欧拉函数(n)是求小于n且与n互素的数的个数。解：若n分解为不同素数的乘积1212...kaaaknppp设1到n的n个数中为pi倍数的集合为Ai对于pi≠pj,Ai∩Aj既是pi的倍数也是pj的倍数。24举例例欧拉函数(n)是求小于n且与n互素的数的个数。解：n=|𝐴1∩𝐴2∩⋯∩𝐴𝑘|=𝑛−(𝑛𝑝1+𝑛𝑝2+⋯+𝑛𝑝𝑘)+(𝑛𝑝1𝑝2+𝑛𝑝2𝑝3+⋯+𝑛𝑝1𝑝𝑘)…±(𝑛𝑝1𝑝2…𝑝𝑘)(𝑛)=𝑛1−1𝑝11−1𝑝2…1−1𝑝𝑘25•例欧拉函数(n)是求小于n且与n互素的数的个数。260235，111(60)60(1)(1)(1)16235n例如则即比60小且与60无公因子的数有16个：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外还有一个1。(8)=8(1-1/2)=48=23，小于8且与8互素有1357(𝑛)=𝑛1−1𝑝11−1𝑝2…1−1𝑝𝑘26组合数学Combinatorics6容斥和鸽巢6-3回忆过去，容斥新解清华大学马昱春27回顾求不定方程x1+x2+x3=15,求非负整数解的数目C(n+b-1,b)=C(3+15-1,15)若附加约束为0≤x1≤5,0≤x2≤6,0≤x3≤7,28例求不定方程x1+x2+x3=15的非负整数解个数,附加约束为0≤x1≤5,0≤x2≤6,0≤x3≤7,求整数解的数目。解：对于x1+x2+…+xn=b的非负整数解的个数为C(n+b-1,b)没有约束情况下的不定方程x1+x2+x3=15的非负整数解的个数为C(15+3-1,15)=C(17,2)设A1为x1≥6的解，y1+6+x2+x3=15|A1|=C(9+3-1,9)=C(11,2)设A2为x2≥7的解，x1+y2+7+x3=15|A2|=C(8+3-1,8)=C(10,2)设A3为x3≥8的解，x1+x2+y3+8=15|A3|=C(7+3-1,7)=C(9,2)29例求不定方程x1+x2+x3=15的非负整数解个数,附加约束为0≤x1≤5,0≤x2≤6；0≤x3≤7,求整数解的数目。解：没有约束情况下的不定方程x1+x2+x3=15的非负整数解的个数为C(15+3-1,15)=C(17,2)|A1|=C(9+3-1,9)=C(11,2)|A2|=C(8+3-1,8)=C(10,2)|A3|=C(7+3-1,7)=C(9,2)A1∩A2:y1+6+y2+7+x3=15|A1∩A2|=C(2+3-1,2)=C(4,2)A1∩A3:y1+6+x2+y3+8=15|A1∩A3|=C(1+3-1,1)=C(3,1)A2∩A3:x1+y2+7+y3+8=15|A2∩A3|=1A1∩A2∩A3:y1+6+y2+7+y3+8=15;|A1∩A2∩A3|=0|A1∩A2∩A3|=C(17,2)–C(11,2)-C(10,2)-C(9,2)+C(4,2)+C(3,1)+1=103030容斥原理应用举例例有障碍的格路问题:从(0,0)点到(10,5)点的路径中,求不能过AB,CD,EF,GH的路径数,各点坐标为A(2,2),B(3,2),C(4,2),D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)解:所有的路径数为C(15,5);经过AB的路径数为|A1|=C(2+2,2)C(7+3,3);经过CD的路径数为|A2|=C(4+2,2)C(5+3,3);经过EF的路径数为|A3|=C(8,2)C(6,2);经过GH的路径数为|A4|=C(9,2)C(5,2);3131容斥原理应用举例(0,0)(10,5)ABCDFHEG经过AB,CD的路径数为|A1∩A2|=C(4,2)C(8,3);经过AB,EF的路径数为|A1∩A3|=C(4,2)C(6,2);经过AB,HG的路径数为|A1∩A4|=C(4,2)C(5,2);经过CD,EF的路径数为|A2∩