李凡长版-组合数学课后习题答案-习题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组合数为：122221212122133312321232123211311131113113cbambcmcambamcmbmammmbacmbacracmacrcbmcbrbambarcmcrbmbramarmm7、某班学生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，可分为