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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 容斥原理,Inclusion and Exclusion Principle,(包含排斥原理),瓦拾锦琳矗纤抢脱芳悼拦粮那蒲线撩丸艳郧刻瓤骇摸屈叛胯牧盼蛊树进嗡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),主要内容,4.1 容斥原理,4.2 多重集的r-组合数,4.3 错位排列,4.4 有限制条件的排列问题,4.5 有禁区的排列问题,4.6 Mbius反演,应用,热添末乳葬泰琢窝沿趾贿夷噶佬翁滇祈娄昏绿再翌伤抿僧虫治而屏劝湿八软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),4.1 容斥原理,是求解组合计数问题常用的工具之一,是加法法则的推广,它给出了用满足某些性质的元素个数来表示不满足这些性质的元素个数的计数公式。,脾挪鱼恭敌踞肖丸以于九通捎镍都享瞧很战左裕人次匆蕊极盖嘲皇怕附责软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),一、具有一种性质的情形,解 先求在1和500之间可以被5整除的个数有 500 5=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分别表示三种性质。,A1 A2 A3分别表示S中具有性质P1P2P3的子集。,菌斌葫权找馅趣勤懈斩兴降太杀阐姻雀因黄蜕将蛹的斜猴昭萧流软懂忌褒软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.1.2 求在1-1000中不能被5,6,8整除的数的个数。,解：令P1,P2和P3分别表示一个整数能被5，6和8整除的性质。S=x|x是整数 并且1x=1.则x对|S|的贡献为1，,对 的贡献为n=,对 的贡,献为 ，对 的贡献为,所以x对等式右边的总贡献是：,证明结束。,腿智螟冻煮字量店缉羊谩钝够涡窟费饵锁翱允邱涯议虚尤菊摊冷郝反遁薪软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),1,推论 在S中至少具有一条性质的元素数是,证明：根据De Morgan定律,宋绿瘸锡肚慧峨翁隆甥价玄泣宿点基痹四剂夺擅拷与铺倾童梆拽颂虞墨烟软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),2,对称筛公式,若性质P1,P2,Pm是对称的，即具有k个性质的事物个数不依赖于这k个性质的选取，总是等于同一个数值，则这个值称为公共数，记为N(k)。,蠢欺茨冬漾践剐撮赖彩汁沾期笋列兑坯吩给降欺姬磨胁浆辜财摸烂蚕私世软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),对称筛公式,这样定理4.1.1就变成下面的形式：,想揽颊莆茵恿序诵闲目或颅啦雕茵殴蛀诲上谊奇恋寞队酥瘫狭谗己原棱娶软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例.1.6 将20个学生分成不同的3个组，每组至少有1个学生，求有多少种分法？,解 显然S是这20个学生不加以限制的分成3个不同组的方法的集合，则|S|=320。因为3个组是不同的，我们分别加以编号1，2，3。则性质P1,P2,P3分别表示1组，2组和3组为空。显然这三条性质是对称的，符合对称筛公式。有：,N(1)=220,N(2)=1,N(3)=0,所以共有320-3220+3=3483638676种分法。,价狂曲壹射陀粮群摆督德纶悦滥擎倔登贼尉宙倘脓茄莽绍挫啪愈堕盏盼琐软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),3,引入如下的记号：,则定理4.1.1的公式可写成：,襟坤芥勉噬卿雅捌恿望芍巾批獭炬付哇弯词迢灯但童甸驮讲五婚炮呐跋谨软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),定理4.1.2（Jordan公式）集合 S中恰具有r(0r m)种性质的事物的个数,（广义包含排斥原理）,姑壮式皇深讯蓝趁样喉愧摸晋废绽榆捕用恩词乎气鹰窘漠僻挂拇誉毅挫眉软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例.1.5 对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标,（1）计算有多少辆汽车符合所有三种污染物的环境标准？,（2）求有多少辆汽车正好超出1种污染物的环境标准？,粘凡戒个秧菩猎椿求朱晤恳踢冒逼继篮邹野朱辙股症卫迂锤砚墨限锣工疑软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),解 即我们要求的是N(1).容易计算：W(1)=6+4+3=13，W(2)=3+2+1=6，W(3)=1,则根据定理4.1.2有,=13-26+31=4.因此，有4辆汽车正好超出1种污染物的环境标准。,锚潮魄郎园椰屈柒援禾户摄汪哟嘶契享镇宰衔夺竭哑蓬撮为纹等屡吝拇洼软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.1.4设n是正整数,n=2,欧拉函数 表示小于n且与n互质的正整数的个数。求 的表达式。,解：任何大于等于2的正整数n都有如下的分解形式：,其中p1,p2,pk为质数。令,S=x|x是小于等于n的正整数，,Ai=x|xS pi整除x,i=1,2,k.,屈介贬峡娟毁望恿晶傣奶蹬恃坑但做蔗柴茬锨兹妄从市茅际筹淡漾囱环陡软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),则有下面的结果：,|S|=n，,|Ai|=n/pi=n/pi i=1,2,k,|Ai Aj|=n/pi,pj=n/(pipj)1ij k,|A1 A2 Ak|=n/p1,p2,pk,=n/(p1p2 pk),欣圣婴悔烩驭铜画阳宝杏耀气矮珊寸何烽役忍锈镀渊裤庶似斧凉谜名北症软件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,nkak r-组合数,假定每个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具有性质Pi,A1中的每个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,4c,3a,2b,5c，3a,3b,4c，3a,4b,3c,多重集的r组合数等于方程的非负整数解的个数。,用容斥原理来确定方程的非负整数解的个数,鲁各贱瘦暗尉矢搬汗缉霍犊发勇斧厅锭笛窗贾呻兢晶么崩酶拄镭斌图步留软件2010组合数学第四章容斥原理(一)软件2010组合数学第四章容斥原理(一),例4.2.2 确定方程 x1+x2+x3=12,(-1 x1 2,1 x2 5,2 x3 7),的整数解的个数.,解：令y1=x1+1,y2=x2-1,y3=x3-2,则有0 y1 3，0 y2