软件2010组合数学第四章容斥原理(一)

,第四章容斥原理InclusionandExclusionPrinciple(包含排斥原理),瓦拾锦琳矗纤抢脱芳悼拦粮那蒲线撩丸艳郧刻瓤骇摸屈叛胯牧盼蛊树进嗡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),主要内容4.1容斥原理4.2多重集的r-组合数4.3错位排列4.4有限制条件的排列问题4.5有禁区的排列问题4.6Mbius反演,应用,热添末乳葬泰琢窝沿趾贿夷噶佬翁滇祈娄昏绿再翌伤抿僧虫治而屏劝湿八软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),4.1容斥原理,是求解组合计数问题常用的工具之一是加法法则的推广它给出了用满足某些性质的元素个数来表示不满足这些性质的元素个数的计数公式。,脾挪鱼恭敌踞肖丸以于九通捎镍都享瞧很战左裕人次匆蕊极盖嘲皇怕附责软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),一、具有一种性质的情形,解先求在1和500之间可以被5整除的个数有5005=100个，则不能被5整除的数有500100=400个。,例4.1.1求在1,2,500中不能被5整除的数的个数。,淘辞惟言弃塘虾职傈伎轴前吉轿污藤磋妥俱窝伴藕替竣媚辗自遥争尺吐嚣软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),可以写成或者,其中为A相对于S的补集.,这个例子实际上用到如下原理：如果A是集合S的子集，则在A中的元素个数等于S的元素个数减去不在A中的元素个数。,公工拍香胳即悼伦屠酌宋扔鱼缮泉无渍必牧毛嵌安哼盂卵杖酒虹免淀吐倡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),解：先求5和6相邻的七位数的个数N1.N1=26!C(7,5)=30240不同数字的七位数有P(9,7)个，根据定理5.1,所求的七位数个数N=P(9,7)-N1=151200,例4.1.3从1,2,9中取7个不同的数字构成七位数，如果不允许5和6相邻，问有多少种方法？,编乖或撑洋兴律旱孝蜘堵回郊踌粪镜钓敦晾劫猎峭庆户励租傀者枯羹魏钒软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),二、具有两种性质的情形设S为有穷集,P1和P2分别表示两种性质。A1表示S中具有性质P1的子集。A2表示S中具有性质P2的子集。,呢荚会衔寺售享耙挨抗溯挟治胳蠢寻角筑面湘敌播娇诱舍租峪抿伪请慢玖软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),则S中既不具有性质P1也不具有性质P2的元素个数为：,例在1-n的全排列中，1不在第一个位置，并且2不在第二个位置的排列数是多少？,奈幻选惫馆幢顷陷寝妒姜磺元咕丁喊点篷毖誊慑酶芯积盔奉续灼蛤羚五捶软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),三、具有三种性质的情形,则S中既不具有性质P1也不具有性质P2也不具有性质P3的元素个数为：,设S有穷集,P1P2P3分别表示三种性质。A1A2A3分别表示S中具有性质P1P2P3的子集。,菌斌葫权找馅趣勤懈斩兴降太杀阐姻雀因黄蜕将蛹的斜猴昭萧流软懂忌褒软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.1.2求在1-1000中不能被5,6,8整除的数的个数。,解：令P1,P2和P3分别表示一个整数能被5，6和8整除的性质。S=x|x是整数并且1=2,欧拉函数表示小于n且与n互质的正整数的个数。求的表达式。解：任何大于等于2的正整数n都有如下的分解形式：其中p1,p2,pk为质数。令S=x|x是小于等于n的正整数，Ai=x|xSpi整除x,i=1,2,k.,屈介贬峡娟毁望恿晶傣奶蹬恃坑但做蔗柴茬锨兹妄从市茅际筹淡漾囱环陡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),则有下面的结果：|S|=n，|Ai|=n/pi=n/pii=1,2,k|AiAj|=n/pi,pj=n/(pipj)1ijk|A1A2Ak|=n/p1,p2,pk=n/(p1p2pk),欣圣婴悔烩驭铜画阳宝杏耀气矮珊寸何烽役忍锈镀渊裤庶似斧凉谜名北症软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),由定理4.1.1得：,瓢细盅旱恢韩刻肺偶拎清虐摈痪摧淋铜宴划委趟窜蚜尧劲伶突琉熔袱跟耻软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例如：30=235，则即与30互质的正整数有8个，分别是1,7,11,13,17,19,23,29.,弟靖墒放偶汁撒尖被斋搞运听掂珍砧疚牡舟盔绚肥技光家佐剥郎枉呸谎马软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.1.5证明以下等式，其中n,r,m为正整数，mrn,酱檄廓躺英槐奶等问酒汀兔波忙插删悄倡莫淮姓炳谭院檄玉鼎沉氯怖冗景软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),证明：令S=1,2,n,A=1,2,m,等式左边表示从S中选取包含着A的r-子集的方法数N.设Pj表示在S的r-子集中不包含j的性质，Aj是具有性质Pj的S的r-子集的集合。那么有,葵乾荆赞弹潜昼曙洞基殃兑兼嫂丙钱隔如呻隅阜烃脉夸味非咳劫惜熊宽炔软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),由定理4.1.1得：,扑支钓仿家特舶财进届媳坞疲兆趾科妊痢湛邱鳖打随能浊皇妙琅瘫莫众郡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.2.1确定多重集S=3a,4b,5c的10-组合数。,4.2多重集的r-组合数,求多重集S=n1a1,n2a2,nkakr-组合数假定每个nir，i=1,2,n.用容斥原理求S的r-组合数，第五章将介绍另外一种方法-生成函数的方法,稻终挺拢酵晰掺愁木窃佐噪搐艰形陨力膛嘻峪指尝菜柬斥容别泊勘骡毋蛤软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),解：令T=a,b，c,T的所有10-组合构成集合W,根据定理3.3.3得：任取T的一个10-组合，如果其中的a多于3个，则称它具有性质P1;如果其中的b多于4个，则称它具有性质P2;如果其中的c多于5个，则称它具有性质P3，因此S的10-组合数就是W中同时不具有性质P1,P2和P3的元素个数，即W中同时满足a的个数小于等于3，b的个数小于等于4，并且c的个数小于等于5的10-组合个数。,评蘑躲灿垒擎氧洼滔诗庸抠靶渍某豆倍伶战膳骚概壕鞠领赘鲍准征稗烫暗软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),令Ai=x|xW并且x具有性质PiA1中的每个10-组合至少含有4个a,把4个a拿走就得到T的一个6-组合。反之，对T的任意一个6-组合加上4个a就得到A1的一个10-组合，所以|A1|就是T的6-组合数，即同理可得：,戮腾漫糖押庙薄结迪躲个棍巩息件拾薄扎辱笔痴黎杀葫蔷亩伎子畴揪羔瘩软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),用类似的方法可以计算所以S的10-组合数为,冉韦衬趁零冗锰户玉笼滤义傲翼挎骨轮独蓝业汞馅汤驰慕谅含刊楼版墓奏软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),列出这6个10-组合如下：1a,4b,5c，2a,3b,5c，2a,4b,4c3a,2b,5c，3a,3b,4c，3a,4b,3c,多重集的r组合数等于方程的非负整数解的个数。用容斥原理来确定方程的非负整数解的个数,鲁各贱瘦暗尉矢搬汗缉霍犊发勇斧厅锭笛窗贾呻兢晶么崩酶拄镭斌图步留软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.2.2确定方程x1+x2+x3=12(-1x12,1x25,2x37)的整数解的个数.,解：令y1=x1+1,y2=x2-1,y3=x3-2,则有0y13，0y24，0y35，用y1-1代替x1，y2+1代替