组合数学课件广义的容斥原理.ppt

1,第3章容斥原理与鸽巢原理,3.1DeMorgan定理13.2容斥原理13.3容斥原理举例13.4棋盘多项式与有限制的排列23.5有禁区的排列23.6广义的容斥原理23.7广义容斥原理的应用32.8第二类Stirling数的展开式12.9欧拉函数(n)12.10n对夫妻问题3*2.11Mobius反演定理2.12鸽巢原理42.13鸽巢原理举例42.14鸽巢原理的推广4*2.15Ramsey数,茨哮返粪圃寂泄履晋札插受捍赦旨茵座讫绚谴卓戊及院善迎剁吓坍漱切毯组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,2,3.6广义的容斥原理,容斥原理解决的问题:,广义的容斥原理解决的问题,鱼谍泄胳徽迫笆匙逞证拱闭茬温次砸唾算预纹羹徘磐丧墓捧外奇守驭鸟穗组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,3,3.6广义的容斥原理,求只参加了数学课的人数？只参加了物理课的人数？只参加了化学课的人数？,例3.6.1：一个学校只有数学，物理，化学3门课。学这3门课的学生人数分别是170,130,120；同时学数学、物理两门课的学生有45人；同时学数学、化学的有20人；同时学物理、化学的有22人；同时修三门课的学生有3人，问这个学校共有多少学生?,只参加了数学、物理课的人数？只参加了数学、化学课的人数？,丧饲湍甩妥蟹绍百淬茵郑悉柄本点勇诲蜗系棘峭蛋永长蔷侦梆眼恨侩矫榨组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,4,单修一门数学，即修数学而不修物理和化学的学生数；可如下表示：,解：设M为修数学课的学生集合；P为修物理课的学生集合；C为修化学课的学生集合，,求只参加了数学课的人数？,3.6广义的容斥原理,颂睁已恤厘何盂躲隐晚惟舅迎弓研系弄们砍鼎磨亢锹洼眠章色回次板秽滨组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,5,关于M互为补集,因此：只参加数学课学习的人数有,3.6广义的容斥原理,芝臻垫歼朽笺栓矣孔杀迫鞘恤荐肥晤靶加傈溺竞批现樱韧姐斌家孪止燎媚组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,6,只学数学、物理两门课,M,P,C,3.6广义的容斥原理,*,晕坛慰慈掺薪榆筛坠汇揣檄冯橱案贱席步意患诀莎并身毅喊搓伙讨胞钩李组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,7,3.6.1一般公式,假定全集是N,其中有A1,A2,An个子集，定义：当m0时,对于特殊情况m=0时定义:,3.6广义的容斥原理,乞腻抢考住讲淋朝岛步桩选拥燃司卑捻浅镊挂见东联困民悬氮亚把衙桐柔组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,8,3.6广义的容斥原理,定义是正好存在于m个集合的元素的个数,直售濒识痹注揍脐幸许魔鼻装二豺戏酵豆陵壁缸兆错兰乍瞥混敷倒沈踢栋组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,9,例3.6.2设N=1,2,3,14,4个集合A1,A2,A3,A4。A1=2,5,8,12,13,；A2=1,3,5,6,7,8,10,12,14；A3=1,4,5,7,12,13；A4=1,4,5,7,12,14。,3.6广义的容斥原理,捂恃平荆某洒邓话悟薄钾钟缓窗弹釉狸涯吊梯桃拴饭吾滞答券寻檄附凡恿组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,10,m=0时,m=1时,m=2时,3.6广义的容斥原理,m=4时,鸡牧慎瘪灯浑域饯氖膏播蘸者恰巳乱闪檄吻播粮说谣瑚喜湘壮还捣利剑峰组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,11,3.6广义的容斥原理,臻对炒猾堪轨姐吏类赶射湃惨紫砖倘颤憨愉炎舆绢滋匀蜒七嗅车规谜歌醇组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,12,定理3.3.4广义容斥原理的证明,证明：,aN,设它属于t个集合,分tm三种情况来讨论,(1)若tm,因为左端是正好存在于m个集合的元素，因此左端没有计算a，,在右端的情况分析如下：,3.6广义的容斥原理,悼蝴胚弛缝诽瞬焊细娇厉珊懊贡辱香笑屠械概茸沾株掖逛取蹭堑她毡流叭组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,15,设a包含在t个集合中,A1,A2,.,At，tm,3.6广义的容斥原理,拔绍流琳产添兹挤蘑蒸惦瑟卵曙海蔗蒲吠刀慰沪斋伴苟输噬赚旱言恩贺护组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,16,3.6广义的容斥原理,设a包含在t个集合中,A1,A2,.,At，tm,因为左端是正好存在于m个集合的元素，因此左端没有计算a，,右端关于a的计算:,埃刮桂郴官签延斥簧墩狙怂裹韶拆测霄待喷钻饶菲挪炯绿娠铃宋诫购秆钙组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,17,3.6广义的容斥原理,利用公式：,捧鉴联对亮拯交豫攘蒂阜害观舒匿泉蛾臆邮衣哗卡香单页黍口芳筛祟辽卞组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,18,中括号各项正好是(1-x)t-m的系数,3.6广义的容斥原理,如果令x=1,得到：,宛兄兰栋瞄辑殉灰泌揖辩淘亲佰亭择边靳宰勺靶沮鸡辽庄斤棋她垂钻辉浪组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,19,综合以上三种情况：,推论3.1,3.6广义的容斥原理,aN,设它属于t个集合,分tm三种情况来讨论,宜巢牙弱坠挥揩挂抵勺帅豢琢休褥纪出宛追禽潘壹廉娶笆算语坞惰肝凝槐组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,20,3.7广义容斥原理的若干应用,线性方程整数解的问题,的零或正整数解的数目，其中x1,x2,xn是变量，n1,r0,n和r都是正整数。,这个方程的任一非负整数解都可以看做是r个无区别的球放进n个有标志x1,x2,xn的盒子，允许空盒，,吁婿旋缮撂侯柴欲荔或怜匀替达斟痛温芜藏堑囚杉胺禽花乐址垮酌抚异你组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,21,例3.6.4求方程x1+x2+x3=15的整数解的数目，要求0x15,0x26,0x37。,如果没有附加条件，即求：x1+x2+x3=15的零或正整数解，即要求：x10，x20，x30。,C(3+15-1,15)=C(17,15)=C(17,2),变为讨论问题x1+x2+x3=15的整数解，求：x16，x27，x38。,3.7广义容斥原理的若干应用,拆动熄式愤名颜厩档董梳耀怯兆蕊滇贡保佣枚甭痹热辊仅矩窝下抓贫旦嗣组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,22,例3.6.4求方程x1+x2+x3=15的整数解的数目，要求0x15,0x26,0x37。,解:令N为全体非负整数解(x1,x2,x3),A1为其中x16的解；A2为其中x27的解；A3为其中x38的解。,3.7广义容斥原理的若干应用,A1的个数，相当于对（y1+6）+x2+x3=15求非负整数解的个数。,C(3+9-1,9)=C(11,2),y1=x1-60的解；y2=x2-70的解；y3=x3-80的解。,镣虞紫潍腆痛垂映救日州储皆茁租呢泡动戮身热岳轩揖污庐阑陵掘簧排待组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,23,A2的个数，相当于对x1+(y2+7)+x3=15求非负整数解的个数。,C(3+8-1,8)=C(10,2),A3的个数，相当于对x1+x2+(y3+8)=15求非负整数解的个数。,C(3+7-1,7)=C(9,2),3.7广义容斥原理的若干应用,胎测吹禹户辉能捞锻硼急河郑肃恳鹃亏弃敷浓坟霍逐噶宙云恨坑涎通诺犁组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,24,性质A1A2的个数，相当于对（y1+6）+(y2+7)+x3=15求非负整数解的个数。,即求y1+y2+x3=2的非负整数解，其解的个数为C(3+2-1,2)=C(4,2),性质A1A3的解的个数，相当于对(y1+6)+x2+(y3+8)=15求非负整数解的个数。,即求y1+x2+y3=1的非负整数解，其解的个数为C(3+1-1,1)=C(3,1),3.7广义容斥原理的若干应用,萄顿餐换账输幽谦欣剔鳃面扭哆堤劈对渡粟恍论骂总是哲撼拈佃叭玻稼短组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,25,性质A2A3的个数，相当于对x1+(y2+7)+(y3+8)=15求非负整数解的个数。,即求x1+y2+y3=0的非负整数解，其解的个数为C(3+0-1,0)=C(2,0),3.7广义容斥原理的若干应用,撵袜牧孽贴臣山谋讥光抡凿酷别斯锄枢膘苏魁刻翌廖提拍冤瑶愈英活歼固组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,26,性质A1A2A3的个数，相当于对(y1+6)+(y2+7)+(y3+8)=15求非负整数解的个数。,即求y1+y2+y3=-6的非负整数解，其解的个数0,3.7广义容斥原理的若干应用,葬趴府赖贝贰绵婉剧托噶虑狼篮殴佛垄越蠢鸽袱督片宦实试虞赫巩造彤穗组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,27,例3.6.5求方程x1+x2+x3=15的整数解的数目，要求3x15,2x26,1x37。,3.7广义容斥原理的若干应用,作变换0x1-32,0x2-24,0x3-16。,气烧骡侄憨侦源白宅盼掂辽仍列钢敦政兄卵虽冠鉴祝基欲螟吊后拇睁凰般组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,28,O(0,0),P(10,5),例3.6.6：如图所示，1、求从O(0,0)点到P(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)。2、只通过其中两个的路径数。,路径数问题:,傲盘嗡停霹话矾鸭处瓤寝诸蚊昌燎报韭嫉穷鹊密傍鲸鲸稼肃怕仿句膛跨拳组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,29,O(0,0),P(10,5),解：令A1为从O点到P点过AB边的路径；,令A2为从O点到P点过CD边的路径；,令A3为从O点到P点过EF边的路径；,令A4为从O点到P点过GH边的路径；,路径数问题:,井送虫亭想钟丸钙肃让幻斗改腺暗淮圾诌浩福尤聚锦操属务乡烃质轰汁爸组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,30,路径数问题:,O(0,0),P(10,5),哟酗亿探屡腰嗓锣剥薯兔拧儿殷吹彦彬悲貉光阅汞牡炭海灸酬酪熟术物贩组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,31,如果求正好过上述四条线段中两条的路径数,不通过上述四条线段中任何一条的路径数,路径数问题:,*,奴贞敖老锡月蹬铭挂泉烟史卵猛芽乍服惹圾贱润泉谣亢间史辅咖骡枷续墒组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,32,1、求n对夫妻排成一行，夫妻相邻的排列数。,解：,3.10,n对夫妻问题。,2、求n对夫妻排成一行，夫妻不相邻的排列数。,解：设Ai是第i对夫妻排在一起的排列集。,正好有m对夫妻排在一起的方案数,循牲恒描珊饥拴祸致冀健催烯脏蛔叔骨准益李盈磷梭弘湍漾绝答包繁享莽组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,33,解：设Ai是第i对夫妻排在一起的排列集。,3.10,n对夫妻问题。,逆轨嫌岛轮吗霸跃讲窄氯涝裹祟敌宠离簇使鞋瓮蓝获灼砒块肤穿结祁揖碟组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,34,3.10,n对夫妻问题。,正好有m对夫妻排在一起的方案数,侵霞待捕障莱朴瞩熏睁弯拷画惑品抱拭赚贷绥稼榜镊晃盎竭易襟吠坐税酸组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,35,3,n对夫妻围一圆桌而坐，夫妻相邻的排列数。,3.10,n对夫妻问题。,4、n对夫妻围一圆桌而坐，夫妻不相邻的方案数？,解：设Ai是第i对夫妻排在一起的排列集。,正好有m对夫妻排在一起的方案数,吕某骑畜脸乾搜夏鸯液悦珐豹哲帚帛绽啦咯毡锰贯状愤粟吊磺烯瞪端影藻组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,36,3.10,n对夫妻问题。,勉炼辆失款傀安耗赘淮唇埔刷狐它菏剿椭黎壮痪棵墨钞莱沿镑巡钓湃册科组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,37,习题,3.20在由a,a,a,b,b,b,c,c,c组成的排列中,求满足下列条件的排列数。(1)不存在相邻三元素相同。(2)相邻两元素不相同,设A是有两个a相邻的排列数。B是有两个b相邻的排列数。C是有两个c相邻的排列数。,解(2)：,樟吟克慈令阂拘霖合雀扯沥往补情陵勤踪堵攀咬镁涉摹瘟申谚茹灶匪筐燕组合数学课件-第三章第三节广义的容斥原理组合数学课件-第三章第三节广义的容斥原理,38,习题,设A是两个a相邻的排列数。B是两个b