李凡长版 组合数学课后习题答案 习题2

1、第二章 容斥原理与鸽巢原理1、1到 10000之间（不含两端）不能被 4，5和 7整除的整数有多少个？解 令A=1,2,3,10000，则 |A|=10000.记A 、A 、A 1与1000之间能被4,5和7整除的整数集合，则有：123|A | =L10000/4=2500,1|A | =L10000/5=2000,2|A | =L10000/7=1428,3于是A A 表示中能被4和5整除的数,即能被20 整除的数，其个数为12| A A L10000/20=500；12同理，| A A L10000/28=357,13| A A L10000/35=285,23A A A 表示中能同时被4

2、,5,7中能被4,5,7的最小公倍123数lcm(4,5,6)=140整除的数，其个数为| A A A L10000/140= 71.123由容斥原理知，中不能被4，5，7整除的整数个数为| A A A |123= |A| - (|A | + |A | +|A |) + (|A A | + |A A | +|A A |) - |A A A |123121332123= 51432、1到 10000之间（不含两端）不能被 4或 5或 7整除的整数有多少个？解 令A=1,2,3,10000A A A 1与1000之间能被4,5和7整除123的整数集合，中不能被4，5，7整除的整数个数为= |A|

3、- - 2 = 10000 -L10000/140- 2 = 9927| A A A | A A A |1231233、1到 10000之间（不含两端）能被 4和 5整除，但不能被 7整除的整数有多少个？解 令A 表示在1与10000之间能被4和5整除的整数集，A 表示4和 5 整除，12也能被 7 整除的整数集。则：|A | =L10000/20= 500,1|A | =L10000/140= 71,2所以 1 与 10000 之间能被 4 和 5 整除但不能被 7 整除的整数的个数为：500-71=429。4、计算集合2a,3b, 2c, 4d的 5组合数. 解 令S a, b,c,d，则

4、S的5组合数为= 565415设集合是S 的5565组合中的的个数小于等于2b的个数小于等于3的个数小于等于2d的个数小于等于4的组合数. 定义性质集合P=P ,P ,P ,P ,其中：1234P ：5组合中的个数大于等于3；1P ：5组合中b的个数大于等于4；2P ：5组合中c的个数大于等于3；3P ：5组合中d的个数大于等于5.4将满足性质P的5A(1i4). 那么，A 中的元素可以看作是由i1i S 的5323个a构成的，所以|A | = 10.2411210类似地，有 |A | = 4. |A | = 10. |A | = 1.544153415541231545355 |A A |

5、= 0.5344153412| A A | = | A A | = | A A | = | A A | = | A A | = | A A A |1314242334124= | A A A | = | A A A | =| A A A A | = 01233241234而的个数小于等于2b的个数小于等于3的个数小于等于2d的个数小于等于4的5组合全体为 ，由容斥原理知，它的元素个数为| A A A A |123456-(10+4+10+1)-(0+0+0+0+0+0)+(0+0+0)-0=31。5、计算a,3b, 10c的 10 组合数. 解 令S a, b,c，则S的10组合数为= 661

6、031设集合是S 的106610组合中的b的个数小于等于3，的个数小于等于10的组合数. 定义性质集合P= P ,P ,其中：12P ：10组合中b的个数大于等于4；1P ：10组合中c的个数大于等于11；2 将满足性质P的10A (1i4). 那么， |A | = 28.10431104i1i 类似地，有 |A | =故由容斥原理知，所求组合数为= 0. |A A | = = 0.10312121066-(28+0)-0 。6、求集合ax, by, cz的 m 组合数（a,b,c全非无穷大）.解 用上面的方法可以得出该集合的m 组合数为： 3m13ma13mb13mc1 mra1rb1rc1

7、3mab213mbc21rbc23mca21rca23mcab31rcab3 rab22mmma1mb12mc1 22mab2macmcb2mabc1227、某班学生 25 人可以选修二外，其中有 14 人选修日语，12 人选修法语，5 人选修日语和德语，6 人选修法语和日语，2 人选修这 3 6 个选修德语的都选了另一种外语（这 3 解 设选修日语，法语，德语的学生集合分别为J，则|J| = ，|F| = ，|G| = 6，J| = ，J| = 5，JG| = ，G| =6-5+23。故没有选修的人数为：|FG J| = 25 (12 + 14 + 6) + (6+5+3) 2 = 5。8、

8、1 到 120 的整数中有多少质数？多少合数？解 a为合数，p为ap ，a故不超过 120 的合数必定是 2，3，5，7 的倍数。根据容斥原理可得，合数的个数为 89，质数为 119-89 = 。119、求方程 x + x + x = 10的大于 2 的整数解的个数.123解 相当于求 S=a, b,c的 10-2*34 组合数的个数。 15431410、 求方程 x + x + x + x = 18 的非负整数解的个数，其中 0 x 5, 0 x1234126, 5x 9, 2x 10.34提示 令 y = x y =x y =x y = x 5x ,6x ,4x ,8x 的 11组合数。1

9、1223344123411、 一花店某时只有 6 枝红玫瑰，7 枝粉玫瑰和 8 枝黄玫瑰。这时要从中选12 枝做花篮，问有多少种选法？提示 相当于求S=6a, 7b,8c 的 12 组合数的个数。12、 某人要给 5 个朋友每人一件生日礼物，问礼物全部送错的概率是多少？解 D = 5!513、 对集合1,2,10 5 个元素在其自然位置上的排列有多少种？.解 任意选出 5 个元素放在其自然位置上，其余的全部错排： D5514、 说明组合恒等式 n! D D Dnn0n1n1n0的组合意义.（设 D = ）0解 S=1,2,n排列可分成下列情况：没有一个数在其自然位置上的排列数为 D 。nn0恰

10、有 i（i=1,2,n）个数在其自然位置上的排列数为 D 。nn-iiS 的所有排列的个数为 。根据加法原理，有： nn! =D +D +Dnnnn-1001n15、 计算机接到 n 个用户的信号，每个信号都由一个 A 类数据加一个 B 类数 n 个用户每人一个 A 类数据和一个 B 类数据。那么没有人接到的数据与他发出的相同的概率是多少？解 如果发给用户的 A类数据全排列，B类错排：n!Dn如果发给用户的 B类数据全排列，A类错排：n!Dn如果发给用户的 A类、B类数据全部错排：D2n则没有人接到的数据与他发出的相同的方案数为：n!D + n!D - D 。nnn所求概率为：(2* n!D

11、- D )/( ) 。2nn16、 把 20 个相同的球放入 5 2 个盒子每个最多可以放6 个球。问共有多少种不同的方法？ 6解i21 20ii20ii017、 10 个人在舞会中跳舞。问有多少种方法？若在第二支舞曲中，每个人都12换了舞伴呢？解 从原来的每一对舞伴种选出一个，让这5 个人错排：2 D 。5518、 证明：n 对夫妻围坐于一圆桌旁，假定 n 位妻子 w ,w ,w 先坐好，将12n丈夫们 h ,h ,h r对夫妻相邻而坐的方案数为12n 2n2nkM(n,r)n()kr(nkk2nkrkkr证明 设 N是 h ,h ,h 的所有排列的集合12n令 A ：h 坐在 w 右边的排

12、列；111A ：h 坐在 w 左边的排列；211A ：h 坐在 w 右边的排列；322A ：h 坐在 w 左边的排列；422A ：h 坐在 w 左边的排列；2n-1nnA ：h 坐在 w 左边的排列。2nnn注意：A 和 A 不可能同时成立i=1,2,2n。ii+1若依序将 A ，A ，A 沿一圆周排列，则 |AA | = 0 （i=1,2,2n）122nii+1假如沿圆周有两个相邻时，则0。A A . AA ,A ,.,Aiiiiii12k12k总之：（1） 对于整数 k，0。亦即A A . Aiii12ka(k) =0。A A . Ai1ii2ki i i 2n12k（2） 对于 1kn，

13、根据 n 对夫妻问题，有 2na(k) =(nk)!。A A . A2 1n kk1iiik12ki i i 2n12k由容斥原理有：M(n,r)2nr(a(k)kr krkr 2nn(kr(nk)!k2nk1r k k1kr 2n2nkn()kr(nkk2nkrkkr19、 A,B,C,D,E 五位学生选课，共有a,b,c,d,e 五门课可选。由于基础不同，A 不可以选 a 和 cB 不可以选 bC 不可以选 c,d 和 eD 不可以选 a,b 和 c，E 可以选任何课。如果每人选一门，共有多少种选法？每人选两门呢？解 令 S 为每人选一门的所有选法集合，则|S| = 5 .5定义性质集合P

14、=P ,P ,P ,P ,其中：1234P ：选或；1P ：选b；2P ：C选，d或；3P ：选，b或。4设S为SPi，所以ii13|A | = 2*5 ； |A | = 1*5 ； |A | = 3*5 ；|A | =3*5 。44441234|A A | = 2*1*5 ；|A A | = 3*1*5 ；|A A | = 2*3*5 ；|A A | = 2*3*5 ；|A A | = 3*1*5 ；|A A | = 3*3*5 。|A A A | = 2*1*3*5 ；|A A A | = 2*1*3*5 ；|A A A | = 2*3*3*5 ；|A A A | = 1*3*3*5 。3

15、331232133331442342212312422134234|A A A A | = 2*1*3*3*5 ；1123因此，满足题意的排列数为：4| A A A A |1234= |A|-(|A |+ |A |+ |A | + |A )+(|A A | + |A A | + |A A |1234123213+ |A A | +|A A | + |A A )-(|A A A | + |A A A |142434123234+ |A A A | +|A A A |) +|A A A A |同理可做每人选两门的124134123420、 一个班共有 10个女生和 10个男生，那么至少要叫出多少人

16、，才能保证叫出的人中有一个女生？解 11人21、 证明：从 1至 2n的 2n个自然数中任选 n+1个，那么其中至少有一对数互质.证明 首先证明：任何两个相邻的正整数是互质的。用反证法：假设 n 与 n+1有公因子 q（q2n=qp ,n+1=qp ,p ,p 是整数。1212因此 qp +1= qp ，即 q (p p 。这与 q，p p 是整数矛盾。因此，任何两个相邻的正整数是互质的。122121现把 1,2,2n 分成以下 n 组：1,2,3,4,2n-1,2n，从中任取 n+1 个不同的数。由鸽巢原理可知：至少有两个数取自同一组。它们是互质的。得证。22、 52100整除.证明 设 5

17、2 个整数 a ,a ,a 被 100 整除的余数分别是r ,r ,r 。另外，可能1 2521 252的余数共 100 个：0199 51 类01,992,9849,51，50。因此 r(0i53)中至少有两个属于同一类，例如 r,r 。于是或者 r=r ，ij kjk或者 r+r =100。这就是说，它们的和或者差可被 100 整除。jk23、 西方风俗中，如果13日是星期五，会被认为是不祥的日子，被称作“黑色星期五”.试证明：非闰年时每年都至少有一个“黑色星期五”.证明 每年中共有 12 个 13 日，它们分别是(下面用 m.n 表示 m 月 n 日，wx 星期 x)1.13，2.13，

18、。下面用反证法来证明。假设它们均非星期 5，则它们是 w1，w2，w3，w4，w6w7之一。我们知道2.133.13 和 11.13必是同一个 wx （因为它们之间1分别相隔 28 天及 245 1.13 和 10.13 是同一个 wx 而且 x x ；2124.13 与 7.13 同为 x 9.13与 12.13 同为 x（所有xx 3 个 1334ij日是剩下的两个 wx 和 wx 。根据鸽巢原理，这 3 日中至少有两个是属于同56一个 wx 的，而实际情况是它们间相隔天数都不是 7 的整数被。因此原假设14xy324、 证明：任意 7个实数中必存在两个实数 x，y，满足 01xy 3x

19、y证明 令x = tan , y = tan ，则= tan( )。1 3若 0 /6，则 0tan( )。3这 7 7 4 tan , y = tan , tan , tan ，0 , , , /2。将它们分布于0, /6, /6, /3, /3, /2之中，则必有两个属于同一区间。设 , 属于同一区间且 0 - ，则 0 /6。得证。25、 在一次会议中，有 5位听众每人均离开两次，而且每两人均有同时离开的时刻。证明：一定有三人同时离开的时刻.证明 5 人中人一位，设为，按题意，共离开两次；在这两次中，其余4 人都离开过，按照鸽巢原理，这 4 人中必然至少有两人是同时离开的。即，必然有三人同时离开的时刻。得证。26、 设 a ,a ,a 是 1,2,n 的一个排列.试证明：当 n为奇数时，(a -1)(a1 2n12（a n)是偶数.nn12证明 当 n 是奇数时，1，2，n 和 a ,a ,a 中的奇数是个，而偶数只1 2nn1n1有个。因此在a a ，a 1 中 a ,a ,a （共个）至少有113n1 3n22个是奇数，例如 a 是奇数，则 a-1是偶数。于是可知整个乘积是偶数。ii27、 9 个顶点的完全图 K 9个红色 K ，或者存在一个蓝色 K .43证明 在 K 中如果与每个顶点关