您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 李凡长版-组合数学课后习题答案-习题2
10第二章容斥原理与鸽巢原理1、1到10000之间(不含两端)不能被4,5和7整除的整数有多少个?解令A={1,2,3,…,10000},则|A|=10000.记A1、A2、A3分别为在1与1000之间能被4,5和7整除的整数集合,则有:|A1|=L10000/4」=2500,|A2|=L10000/5」=2000,|A3|=L10000/7」=1428,于是A1∩A2表示A中能被4和5整除的数,即能被20整除的数,其个数为|A1∩A2|=L10000/20」=500;同理,|A1∩A3|=L10000/28」=357,|A2∩A3|=L10000/35」=285,A1∩A2∩A3表示A中能同时被4,5,7整除的数,即A中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数,其个数为|A1∩A2∩A3|=L10000/140」=71.由容斥原理知,A中不能被4,5,7整除的整数个数为||321AAA=|A|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A3∩A2|)-|A1∩A2∩A3|=51432、1到10000之间(不含两端)不能被4或5或7整除的整数有多少个?解令A={1,2,3,…,10000},记A1、A2、A3分别为在1与1000之间能被4,5和7整除的整数集合,A中不能被4,5,7整除的整数个数为||321AAA=|A|-||321AAA-2=10000-L10000/140」-2=99273、1到10000之间(不含两端)能被4和5整除,但不能被7整除的整数有多少个?解令A1表示在1与10000之间能被4和5整除的整数集,A2表示4和5整除,也能被7整除的整数集。则:|A1|=L10000/20」=500,|A2|=L10000/140」=71,所以1与10000之间能被4和5整除但不能被7整除的整数的个数为:500-71=429。4、计算集合{2·a,3·b,2·c,4·d}的5组合数.解令S∞={∞·a,∞·b,∞·c,∞·d},则S的5组合数为1455=56设集合A是S∞的5组合全体,则|A|=56,现在要求在5组合中的a的个数小于等于2,b的个数小于等于3,c的个数小于等于2,d的个数小于等于4的组合数.定义性质集合P={P1,P2,P3,P4},其中:P1:5组合中a的个数大于等于3;P2:5组合中b的个数大于等于4;P3:5组合中c的个数大于等于3;P4:5组合中d的个数大于等于5.将满足性质Pi的5组合全体记为Ai(1≤i≤4).那么,A1中的元素可以看作是由S∞的5-3=2组合再拼上3个a构成的,所以|A1|=1422=10.11类似地,有|A2|=144545=4.|A3|=143535=10.|A1|=145555=1.|A1∩A2|=14435435=0.|A1∩A3|=|A1∩A4|=|A2∩A4|=|A2∩A3|=|A3∩A4|=|A1∩A2∩A4|=|A1∩A2∩A3|=|A3∩A2∩A4|=|A1∩A2∩A3∩A4|=0而a的个数小于等于2,b的个数小于等于3,c的个数小于等于2,d的个数小于等于4的5组合全体为||4321AAAA,由容斥原理知,它的元素个数为56-(10+4+10+1)-(0+0+0+0+0+0)+(0+0+0)-0=31。5、计算{∞·a,3·b,10·c}的10组合数.解令S∞={∞·a,∞·b,∞·c},则S的10组合数为131010=66设集合A是S∞的10组合全体,则|A|=66,现在要求在10组合中的b的个数小于等于3,c的个数小于等于10的组合数.定义性质集合P={P1,P2},其中:P1:10组合中b的个数大于等于4;P2:10组合中c的个数大于等于11;将满足性质Pi的10组合全体记为Ai(1≤i≤4).那么,|A1|=13410410=28.类似地,有|A2|=1311101110=0.|A1∩A2|==0.故由容斥原理知,所求组合数为66-(28+0)-0=38。6、求集合{a·x,b·y,c·z}的m组合数(a,b,c全非无穷大).解用上面的方法可以得出该集合的m组合数为:122221212122133312321232123211311131113113cbambcmcambamcmbmammmbacmbacracmacrcbmcbrbambarcmcrbmbramarmm7、某班学生25人可以选修二外,其中有14人选修日语,12人选修法语,5人选修日语和德语,6人选修法语和日语,2人选修这3种语言,而且6个选修德语的都选了另一种外语(这3种内的一种)。问有多少人没有选修二外?解设选修日语,法语,德语的学生集合分别为J,F,G,则|J|=14,|F|=12,|G|=6,|F∩J|=6,|G∩J|=5,|F∩J∩G|=2,|F∩G|=6-5+2=3。故没有选修的人数为:|JGF|=25–(12+14+6)+(6+5+3)–2=5。8、1到120的整数中有多少质数?多少合数?解先求合数的个数。设a为合数,p为a的最小质因子,则p≤a。由于12011,故不超过120的合数必定是2,3,5,7的倍数。根据容斥原理可得,合数的个数为89,质数为119-89=30。129、求方程x1+x2+x3=10的大于2的整数解的个数.解相当于求S={∞·a,∞·b,∞·c}的10-2*3=4组合数的个数。1344=1510、求方程x1+x2+x3+x4=18的非负整数解的个数,其中0≤x1≤5,0≤x2≤6,5≤x3≤9,2≤x4≤10.提示令y1=x1,y2=x2,y3=x3-5,y4=x4-2。相当于求{5·x1,6·x2,4·x3,8·x4}的11组合数。11、一花店某时只有6枝红玫瑰,7枝粉玫瑰和8枝黄玫瑰。这时要从中选12枝做花篮,问有多少种选法?提示相当于求S={6·a,7·b,8·c}的12组合数的个数。12、某人要给5个朋友每人一件生日礼物,问礼物全部送错的概率是多少?解D5=5!13、对集合{1,2,…,10}的元素进行排列,恰有5个元素在其自然位置上的排列有多少种?.解任意选出5个元素放在其自然位置上,其余的全部错排:105D514、说明组合恒等式0110DDDnnnnnnn!的组合意义.(设D0=1)解S={1,2,…,n}排列可分成下列情况:没有一个数在其自然位置上的排列数为n0Dn。恰有i(i=1,2,…,n)个数在其自然位置上的排列数为niDn-i。S的所有排列的个数为n!。根据加法原理,有:n!=n0Dn+n1Dn-1+…+nnD015、计算机接到n个用户的信号,每个信号都由一个A类数据加一个B类数据组成;然后计算机随机发给这n个用户每人一个A类数据和一个B类数据。那么没有人接到的数据与他发出的相同的概率是多少?解如果发给用户的A类数据全排列,B类错排:n!Dn如果发给用户的B类数据全排列,A类错排:n!Dn如果发给用户的A类、B类数据全部错排:Dn2则没有人接到的数据与他发出的相同的方案数为:n!Dn+n!Dn-Dn。所求概率为:(2*n!Dn-Dn)/(n!)2。16、把20个相同的球放入5个不同的盒子,其中前2个盒子每个最多可以放6个球。问共有多少种不同的方法?解60202012iiiii17、10个人在舞会中跳舞。问有多少种方法?若在第二支舞曲中,每个人都13换了舞伴呢?解从原来的每一对舞伴种选出一个,让这5个人错排:25D5。18、证明:n对夫妻围坐于一圆桌旁,假定n位妻子w1,w2,…,wn先坐好,将丈夫们h1,h2,,…hn插在两个妻子之间,则正好有r对夫妻相邻而坐的方案数为M(n,r)=nrkknkkrrkknknn)!()(2221证明设N是h1,h2,…,hn的所有排列的集合令A1:h1坐在w1右边的排列;A2:h1坐在w1左边的排列;A3:h2坐在w2右边的排列;A4:h2坐在w2左边的排列;……A2n-1:hn坐在wn左边的排列;A2n:hn坐在wn左边的排列。注意:Ai和Ai+1不可能同时成立i=1,2,…,2n。若依序将A1,A2,…,A2n沿一圆周排列,则|Ai∩Ai+1|=0(i=1,2,…,2n)假如kiiiAAA,...,,21沿圆周有两个相邻时,则kiiiAAA...21=0。总之:(1)对于整数k,nk2n,kiiiAAA...21=0。亦即a(k)=niiik2...121kiiiAAA...21=0。(2)对于1≤k≤n,根据n对夫妻问题,有a(k)=niiik2...121kiiiAAA...21=)!(2121knknknk。由容斥原理有:M(n,r)=rnrkkrrkka2)()1(=nrkknkkrrkknkn)!(2)1(121=nrkknkkrrkknknn)!()(222119、A,B,C,D,E五位学生选课,共有a,b,c,d,e五门课可选。由于基础不同,A不可以选a和c,B不可以选b,C不可以选c,d和e,D不可以选a,b和c,E可以选任何课。如果每人选一门,共有多少种选法?每人选两门呢?解令S为每人选一门的所有选法集合,则|S|=55.定义性质集合P={P1,P2,P3,P4},其中:P1:A选a或c;P2:B选b;P3:C选c,d或e;P4:D选a,b或c。设Si为S中具有性质Pi的全排列全体(1≤i≤4),所以14|A1|=2*54;|A2|=1*54;|A3|=3*54;|A4|=3*54。|A1∩A2|=2*1*53;|A3∩A2|=3*1*53;|A1∩A3|=2*3*53;|A1∩A4|=2*3*53;|A4∩A2|=3*1*53;|A3∩A4|=3*3*53。|A1∩A2∩A3|=2*1*3*52;|A1∩A2∩A4|=2*1*3*52;|A1∩A3∩A4|=2*3*3*52;|A2∩A3∩A4|=1*3*3*52。|A1∩A2∩A3∩A4|=2*1*3*3*51;因此,满足题意的排列数为:||4321AAAA=|A|-(|A1|+|A2|+|A3|+|A4|)+(|A1∩A2|+|A3∩A2|+|A1∩A3|+|A1∩A4|+|A2∩A4|+|A3∩A4|)-(|A1∩A2∩A3|+|A2∩A3∩A4|+|A1∩A2∩A4|+|A1∩A3∩A4|)+|A1∩A2∩A3∩A4|同理可做每人选两门的20、一个班共有10个女生和10个男生,那么至少要叫出多少人,才能保证叫出的人中有一个女生?解11人21、证明:从1至2n的2n个自然数中任选n+1个,那么其中至少有一对数互质.证明首先证明:任何两个相邻的正整数是互质的。用反证法:假设n与n+1有公因子q(q≥2),则有n=qp1,n+1=qp2,p1,p2是整数。因此qp1+1=qp2,即q(p2–p1)=1。这与q≥2,p2–p1是整数矛盾。因此,任何两个相邻的正整数是互质的。现把1,2,…,2n分成以下n组:{1,2},{3,4},…,{2n-1,2n},从中任取n+1个不同的数。由鸽巢原理可知:至少有两个数取自同一组。它们是互质的。得证。22、证明:任意给定的52个整数中,至少存在两个数,它们的和或差可以被100整除.证明设52个整数a1,a2,…,a52被100整除的余数分别是r1,r2,…,r52。另外,可能的余数共100个:0,1,…,99,可分为
本文标题:李凡长版-组合数学课后习题答案-习题2
链接地址:https://www.777doc.com/doc-7420865 .html