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

第二章 容斥原理与鸽巢原理

1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000.

记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有：

|A 1| = L 10000/4」=2500,

|A 2| = L 10000/5」=2000,

|A 3| = L 10000/7」=1428,

于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为

| A 1∩A 2|=L 10000/20」=500；

同理， | A 1∩A 3|=L 10000/28」=357,

| A 2∩A 3|=L 10000/35」=285,

A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为

| A 1∩A 2∩A 3|=L 10000/140」= 71.

由容斥原理知，A 中不能被4，5，7整除的整数个数为

||321A A A ??

= |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 5143

2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，A 中不能被4，5，7整除的整数个数为

||321A A A ?? = |A| - ||321A A A ?? - 2 = 10000 - L 10000/140」- 2 = 9927

3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多少个？

解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除，也能被7整除的整数集。则：

|A 1| = L 10000/20」= 500,

|A 2| = L 10000/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={P 1,P 2,P 3,P 4},其中：

P 1：5组合中a 的个数大于等于3；

P 2：5组合中b 的个数大于等于4；

P 3：5组合中c 的个数大于等于3；

P 4：5组合中d 的个数大于等于5.

将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由

S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142

2

-+ = 10.

类似地，有

|A 2| =()1445

45-+-- = 4. |A 3| =()1435

35-+-- = 10. |A 1| =()1455

5

5-+-- = 1. |A 1∩A 2| =()14435

4

35-+---- = 0. | A 1∩A 3| = | A 1∩A 4| = | A 2∩A 4| = | A 2∩A 3| = | A 3∩A 4| = | A 1∩A 2∩A 4|

= | A 1∩A 2∩A 3| = | A 3∩A 2∩A 4| =| A 1∩A 2∩A 3∩A 4| = 0

而a 的个数小于等于2，b 的个数小于等于3，c 的个数小于等于2，d 的个数小于等于4的5组合全体为||4321A A A A ???，由容斥原理知，它的元素个数为 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={ P 1,P 2 },其中：

P 1：10组合中b 的个数大于等于4；

P 2：10组合中c 的个数大于等于11；

将满足性质P i 的10组合全体记为A i (1≤i ≤4). 那么， |A 1| =()13410

4

10-+-- = 28. 类似地，有 |A 2| =()131110

11

10-+-- = 0. |A 1∩A 2| = = 0. 故由容斥原理知，所求组合数为

66-(28+0)-0 =38。

6、求集合{a·x, b·y, c·z }的m 组合数（a,b,c 全非无穷大）.

解 用上面的方法可以得出该集合的m 组合数为：

()()()()[]()()()[]()()()()()[]()()()[]()

1222212

1

2122133312321232123211311131113113----------+-+-+-+-----+--------+-------+-------+------+-----+-----+---+-+++++-=-+++++-c b a m b c m c a m b

a m c m

b m a m m m b a

c m b a c r a c m a c r c b m c b r b a m b a r c m c r b m b r a m a r m m 7、某班学生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。 故没有选修的人数为：|J G F |?? = 25 – (12 + 14 + 6) + (6+5+3) – 2 = 5。 8、1到120的整数中有多少质数？多少合数？

解 先求合数的个数。设a 为合数，p 为a 的最小质因子，则p ≤a 。由于120<11，故不超过120的合数必定是2，3，5，7的倍数。

根据容斥原理可得，合数的个数为89，质数为119-89 = 30。

9、求方程x 1 + x 2 + x 3 = 10的大于2的整数解的个数.

解 相当于求S={∞·a, ∞·b,∞·c }的10-2*3＝4组合数的个数。

()1

344-+＝15

10、 求方程x 1 + x 2 + x 3 + x 4 = 18的非负整数解的个数，其中0≤x 1≤5, 0≤x 2≤6, 5≤x 3≤9, 2≤x 4≤10.

提示 令y 1= x 1，y 2=x 2，y 3=x 3 -5，y 4= x 4-2。相当于求{5·x 1 ,6·x 2 ,4·x 3 ,8·x 4}的11组合数。

11、 一花店某时只有6枝红玫瑰，7枝粉玫瑰和8枝黄玫瑰。这时要从中选12枝做花篮，问有多少种选法？

提示 相当于求S={6·a, 7·b,8·c }的12组合数的个数。

12、 某人要给5个朋友每人一件生日礼物，问礼物全部送错的概率是多少？ 解 D 5 = 5!

13、 对集合{1,2,…,10}的元素进行排列，恰有5个元素在其自然位置上的排列有多少种？

.解 任意选出5个元素放在其自然位置上，其余的全部错排：

()10

5

D 5 14、 说明组合恒等式

()()()0

110D D D n n

n n n n n

+?++=-! 的组合意义.（设D 0 = 1）

解 S={1,2,…,n}排列可分成下列情况：

没有一个数在其自然位置上的排列数为()n 0

D n 。 恰有i （i=1,2,…,n ）个数在其自然位置上的排列数为()n i D n-i 。

S 的所有排列的个数为n!。根据加法原理，有：

n! = ()n

0D n + ()n 1D n-1 +…+ ()n n

D 0 15、 计算机接到n 个用户的信号，每个信号都由一个A 类数据加一个B 类数据组成；然后计算机随机发给这n 个用户每人一个A 类数据和一个B 类数据。那么没有人接到的数据与他发出的相同的概率是多少？

解 如果发给用户的A 类数据全排列，B 类错排：n!D n

如果发给用户的B 类数据全排列，A 类错排：n!D n

如果发给用户的A 类、B 类数据全部错排：D n 2

则没有人接到的数据与他发出的相同的方案数为：n!D n + n!D n - D n 。 所求概率为：(2* n!D n - D n )/( n!)2。

16、 把20个相同的球放入5个不同的盒子，其中前2个盒子每个最多可以放6个球。问共有多少种不同的方法？

解 (

)()∑=---+60202012i i i

i i 17、

10个人在舞会中跳舞。问有多少种方法？若在第二支舞曲中，每个人都

换了舞伴呢？

解 从原来的每一对舞伴种选出一个，让这5个人错排：25D 5。

18、 证明：n 对夫妻围坐于一圆桌旁，假定n 位妻子w 1,w 2,…,w n 先坐好，将丈夫们h 1,h 2,,…h n 插在两个妻子之间，则正好有r 对夫妻相邻而坐的方案数为

M(n,r)＝()

()∑=-----n r k k

n k

k

r r k k n k n n )!()(2221 证明 设N 是h 1,h 2,…,h n 的所有排列的集合

令 A 1：h 1坐在w 1右边的排列；

A 2：h 1坐在w 1左边的排列；

A 3：h 2坐在w 2右边的排列；

A 4：h 2坐在w 2左边的排列；

……

A 2n-1：h n 坐在w n 左边的排列；

A 2n ：h n 坐在w n 左边的排列。

注意：A i 和A i+1不可能同时成立i=1,2,…,2n 。

若依序将A 1，A 2，…，A 2n 沿一圆周排列，则 |A i ∩A i+1| = 0 （i=1,2,…,2n ） 假如k i i i A A A ,...,,21沿圆周有两个相邻时，则k i i i A A A ???...21＝0。

总之：

（1） 对于整数k ，n

a(k) =

∑<<<<≤n i i i k 2...121k i i i A A A ???...21＝0。

（2） 对于1≤k ≤n ，根据n 对夫妻问题，有

a(k) =

∑≤<<<≤n i i i k 2...121k i i i A A A ???...21＝())!(2121k n k n k n k -?---。

由容斥原理有：

M(n,r)＝()∑-=--r n r k k r r k k a 2)

()1( ＝()

()∑=------n r

k k n k k r r k k n k n )!(2)1(121 ＝()

()∑=-----n r k k

n k

k

r r k k n k n n )!()(2221 19、 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={P 1,P 2,P 3,P 4},其中：

P 1：A 选a 或c ；

P 2：B 选b ；

P 3：C 选c ，d 或e ；

P 4：D 选a ，b 或c 。

设S i 为S 中具有性质P i 的全排列全体(1≤i ≤4)，所以

|A 1| = 2*54 ； |A 2| = 1*54 ； |A 3| = 3*54 ；|A 4| =3*54 。

|A 1∩A 2 | = 2*1*53；|A 3∩A 2 | = 3*1*53；|A 1∩A 3 | = 2*3*53；

|A 1∩A 4 | = 2*3*53；|A 4∩A 2 | = 3*1*53；|A 3∩A 4 | = 3*3*53。

|A 1∩A 2∩A 3 | = 2*1*3*52；|A 1∩A 2∩A 4 | = 2*1*3*52；

|A 1∩A 3∩A 4 | = 2*3*3*52；|A 2∩A 3∩A 4 | = 1*3*3*52。

|A 1∩A 2∩A 3∩A 4| = 2*1*3*3*51；

因此，满足题意的排列数为：

||4321A A A A ???

= |A|-(|A 1| + |A 2| + |A 3| + |A 4|)+(|A 1∩A 2| + |A 3∩A 2| + |A 1∩A 3|

+ |A 1∩A 4| +|A 2∩A 4| + |A 3∩A 4|)-(|A 1∩A 2∩A 3| + |A 2∩A 3∩A 4|

+ |A 1∩A 2∩A 4| +|A 1∩A 3∩A 4|) +|A 1∩A 2∩A 3∩A 4|

同理可做每人选两门的

20、 一个班共有10个女生和10个男生，那么至少要叫出多少人，才能保证叫出的人中有一个女生？

解 11人

21、 证明：从1至2n 的2n 个自然数中任选n+1个，那么其中至少有一对数互质.

证明 首先证明：任何两个相邻的正整数是互质的。

用反证法：假设n 与n+1有公因子q （q ≥2），则有

n=qp 1,n+1=qp 2,p 1,p 2是整数。

因此qp 1+1= qp 2，即q (p 2 – p 1)=1。这与q ≥2，p 2 – p 1是整数矛盾。

因此，任何两个相邻的正整数是互质的。

现把1,2,…,2n 分成以下n 组：

{1,2},{3,4},…,{2n-1,2n}，

从中任取n+1个不同的数。由鸽巢原理可知：至少有两个数取自同一组。它们是互质的。

得证。

22、 证明：任意给定的52个整数中，至少存在两个数，它们的和或差可以被100整除.

证明 设52个整数a 1,a 2,…,a 52被100整除的余数分别是r 1,r 2,…,r 52。另外，可能的余数共100个：0，1，…，99，可分为51类{0}，{1,99}，{2,98}，…，{49,51}，{50}。因此r i (0

23、 西方风俗中，如果13日是星期五，会被认为是不祥的日子，被称作“黑色星期五”.试证明：非闰年时每年都至少有一个“黑色星期五”.

证明 每年中共有12个13日，它们分别是(下面用m.n 表示m 月n 日，wx 星期x)1.13，2.13，…，12.13。

下面用反证法来证明。假设它们均非星期5，则它们是w1，w2，w3，w4，w6，w7之一。我们知道2.13，3.13和11.13必是同一个wx 1（因为它们之间分别相隔28天及245天）。同样，1.13和10.13是同一个wx 2而且x 1≠x 2；

4.13与7.13同为x 3，9.13与12.13同为x 4（所有x i ≠x j ）。这样剩下的3个13日是剩下的两个wx 5和wx 6。根据鸽巢原理，这3日中至少有两个是属于同一个wx 的，而实际情况是它们间相隔天数都不是7的整数被。因此原假设

是不正确的；也就是说，至少有一个“黑色星期五”。

24、 证明：任意7个实数中必存在两个实数x ，y ，满足 33xy 1y x 0≤+-≤

证明 令x = tan α, y = tan β，则

xy 1y x +- = tan(α-β)。 若0≤α-β≤π/6，则0≤tan(α-β)< 3

3。 这7个实数，至少有7个非负或非正。这里假设有4个非负，为tan α, y = tan β, tan υ, tan ε，0≤α,β, υ, ε≤π/2。将它们分布于[0,π/6], [π/6,π/3],

[π/3,π/2]之中，则必有两个属于同一区间。设α,β属于同一区间且0≤α-β，则0≤α-β≤π/6。

得证。

25、 在一次会议中，有5位听众每人均离开两次，而且每两人均有同时离开的时刻。证明：一定有三人同时离开的时刻.

证明 5人中人一位，设为A ，按题意，共离开两次；在这两次中，其余4人都离开过，按照鸽巢原理，这4人中必然至少有两人是同时离开的。即，必然有三人同时离开的时刻。得证。

26、 设a 1,a 2,…,a n 是1,2,…,n 的一个排列.试证明：当n 为奇数时，(a 1 -1)(a 2 -2)…（a n –n )是偶数.

证明 当n 是奇数时，1，2，…，n 和a 1,a 2,…,a n 中的奇数是2

1+n 个，而偶数只有21-n 个。因此在a 1 -1，a 3 -1，…，a n –1中a 1,a 3,…,a n （共2

1+n 个）至少有1个是奇数，例如a i 是奇数，则a i -1是偶数。于是可知整个乘积是偶数。

27、 证明：对9个顶点的完全图K 9任意进行红、蓝两边着色，都或者存在一个红色K 4，或者存在一个蓝色K 3.

证明 在K 9中如果与每个顶点关联的红边均为5条，因为一条红边连着两个顶点，所以K 9中应该有5*9/2＝45/2条边。它不是整数，所以不成立。故必有一个顶点关联的红边数不为5。设此顶点为a ，则与a 关联的红边至少为6或至多为4。

（1）若红边数≥6：与6条红边相关联的6个顶点构成的K 6中：要么有蓝色的K 3，要么为红色的K 4。

（2）若红边数≤4：则蓝边数≥4。与4条蓝边相关联的4个顶点构成的K 4中：要么是红色的K 4，要么有蓝色的K 3。

28、 证明：对任意正整数a ，b ，有：（1）r(a,b)＝r(b,a)；（2）r(a,2)＝a .

（1）证明 r(a,b)可以这样理解：一个完全图，用红、蓝两种颜色着色，a 代表红色顶点的个数，b 代表蓝色顶点的个数。显然，红、蓝两色交换并不会对结果数产生影响。因此，r(a,b)=r(b,a)。

（2）证明 a 个顶点的完全图的边，用红、蓝两色染色，或存在一个a 个顶点着红（蓝）色的完全图，或至少存在一条蓝（红）色的边。即r(a,2)=a 。

29、 有一项工作要在37天内完成，但一人只要60小时就可以完成.此人决定每天至少在该工作上花费1个小时.试证明：无论他的工作计划如何，在此期

间都存在连续的一些天，他共在该工作上花费了13个小时.

证明设a i是第1到i天内工作的小时数（1≤i≤37）。由于他每天至少工作1小时，因此，1≤a1<…

考虑序列a1+13，a2+13，…，a37+13。显然，1

则1～73之间的74个数a1，…，a37，a1+13，…，a37+13，根据鸽巢原理，至少有两个相等。

可设a i = a j+13（j

(完整word版)组合数学课后答案

习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

组合数学作业答案

第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。

组合数学题库答案.docx

填空题 1．将 5 封信投入 3 个邮筒，有 _____243_种不同的投法． 2． 5 个男孩和 4 个女孩站成一排。如果没有两个女孩相邻，有43200方法． 3． 22 件产品中有 2 件次品，任取 3 件，恰有一件次品方式数为__ 380 ______． 4．( x y)6所有项的系数和是_64_ _．答案：645．不定方程 x1x2x3 2 的非负整数解的个数为 _ 6 ___． 6 ．由初始条件 f (0)1, f (1) 1 及递推关系 f ( n2) f (n1) f ( n) 确定的数列{ f (n)} ( n0) 叫做Fibonacci数列 10 7．（ 3x-2y ）20的展开式中 x10y10的系数是c20310( 2)10． 8．求 6 的 4 拆分数P4(6)2． 9．已知在Fibonacci数列中，已知 f (3)3,f (4)5, f (5) 8 ，试求Fibonacci 数f (20)10946 10 ．计算P4(12) 4 P4 (12)P k (12)P1 (8)P2 (8)P3 (8)P4 (8) k1 34 P1 (8) P2 (8)P k (5)P k (4)14 5 515 k1k 1 11．P4(9)（ D） A． 5 B. 8 C. 10 D. 6 12．选择题 1．集合 A{ a1 , a 2 ,L , a10 } 的非空真子集的个数为（A） C. 1024 2．把某英语兴趣班分为两个小组，甲组有 2 名男同学， 5 名女同学；乙组有 3 名男同学， 6名女同学，从甲乙两组均选出 3 名同学来比赛，则选出的 6 人中恰有 1 名男同学的方式数是（ D ） A． 800 B. 780 C. 900 D.850 3．设( x , y) 满足条件x y10 ，则有序正整数对( x, y) 的个数为（D） A. 100 C. 50 4．求( x03x12x2x3 )6中 x02 x13 x2项的系数是（C） B. 60 5．多项式(2 x0x14x2x3 )4中项 x02x12x2的系数是（C） A． 78 B. 104 C. 96 D. 48 6．有 4 个相同的红球， 5 个相同的白球，那么这9 个球有（ B）种不同的排列方式 A. 63 B. 126 C. 252 7．递推关系 f (n ) 4 f ( n1) 4 f (n 2) 的特种方程有重根2，则（ B ）是它的一般解 A．c12n 1c2 2n B.(c1c2n)2 n C.c(1n)2 n D.c1 2n c2 2n 8．用数字 1,2,3,4（数字可重复使用）可组成多少个含奇数个1、偶数个 2 且至少含有一个 3 的n (n1) 位数（）运用指数生产定理 A. 4n 3n ( 1)n B.4n3n14n2n 1 .4n3n( 1)n 4433

组合数学课后答案

作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：

清华组合数学()习题答案

?1.证：对n 用归纳法。先证可表示性： 当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立， 设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性： 设n=∑a i ·i!=∑b i ·i!, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证： 组合意义： 等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证： 设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑 一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒， 要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而 要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第1步从特定引擎对面的3个中取1个有 C(3,1)种取法，第2步从特定引擎一边的2个中 取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现 了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后 按乘法法则放到一起，而男女分别在前面,应该 再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下， 根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一 个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。

组合数学题目及标准答案

组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k h ，使得 ah+1+…+ ak= 39 证 令Sj= ，j =1 , 2 , …,100。显然 ∑=j i i a 1 ∑=h i i a 1

组合数学课后标准答案

组合数学课后标准答案

————————————————————————————————作者：————————————————————————————————日期：

习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

排列组合测试题(含答案)

排例组合专题训练 1． 将3个不同的小球放入4个盒子中，则不同放法种数有A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113 23233A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5．在8 2 x ? ?的展开式中的常数项是A.7 B ．7- C ．28 D ．28- 6．5 (12)(2)x x -+的展开式中3 x 的项的系数是A.120 B ．120- C ．100 D ．100- 7．22n x ???展开式中只有第六项二项式系数最大,则展开式中的常数项是 A ．180 B ．90 C ．45 D ．360 8．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 9．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 10．n N ∈且55n <,则乘积(55)(56)(69)n n n ---L 等于 A ．5569n n A -- B ．15 69n A - C ．15 55n A - D ．14 69n A - 11．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 12．把10 )x -把二项式定理展开，展开式的第8项的系数是 A ．135 B ．135- C ．- D ． 13．2122n x x ??+ ?? ?的展开式中，2 x 的系数是224，则2 1x 的系数是A.14 B ．28C ．56 D ．112 14．不共面的四个定点到面α的距离都相等，这样的面α共有几个A ．3 B ．4 C ．6 D ．7

最新小学数学组合图形试题及答案

一、填空题 1.如图,阴影部分的面积是 . 2 1 2 2.大圆的半径比小圆的半径长6厘米,且大圆半径是小圆半径的4倍.大圆的面积比小圆的面积大平方厘米. 3.在一个半径是 4.5厘米的圆中挖去两个直径都是2厘米的圆.剩下的图形的面积是平方厘米.(π取3.14,结果精确到1平方厘米) 4.右图中三角形是等腰直角三角形,阴影部分的面 积是 (平方厘米). 5.如图所求,圆的周长是1 6.4厘米,圆的 面积与长方形的面积正好相等.图中阴影部分 π 的周长是厘米.) 14 .3 (= 6.有八个半径为1厘米的小圆,用它们的圆周的一部分连成一个花瓣图形 π,那么花瓣图形的面积(如图).图中黑点是这些圆的圆心.如果圆周率1416 .3 = 是平方厘米.

7.已知:ABC D 是正方形, ED =DA =AF =2厘米,阴影部分的面积是 . 8.图中,扇形BAC 的面积是半圆ADB 的面积的3 11倍,那么,CAB 是 度. 9. 算出圆内正方形的面积为 . 10.右图是一个直角等腰三角形, 直角边长2厘米,图中阴影部分面积是 平方厘米 11一个扇形圆心角120,以扇形的半径为边长画一个正方形,这个正方形的面积是120平方厘米.这个扇形面积是 . 12.如图所示,以B 、C 为圆心的两个半圆的直径都是2厘米,则阴影部分的周长是 厘米.(保留两位小数)

13.三角形ABC 是直角三角形,阴影部分①的面积比阴影部分②的面积小28 长 厘米 . 积为2平方厘米,等腰直角三角形的面积 15.扇形的面积是31.4平方厘米,它所在圆的面积是157平方厘米,这个扇形的圆心角是 度. 16.图中扇形的半径OA =OB =6厘米.45=∠AOB , AC 垂直OB 于C ,那么图中阴影部分的面积是 平方厘米.)14.3(=π 17.右图中正方形周长是20厘米.图形的总面积是 平方厘米. 45

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

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

第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17

组合数学 试题及答案11

组合数学试题 共 5 页 ，第 1 页 电子科技大学研究生试卷 （考试时间： 至 ，共 2 小时） 课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2011 年 11 月 日 成绩 考核方式： （学生填写） 一、(共10分) 1、（4分）名词解释：广义Ramsey 数R (H 1，H 2，…，H r )。 2、（6分）证明：R(C 4,C 4) ≥ 6，其中C 4为4个顶点的无向回路图。 解： 1、使得K n 对于(H 1，H 2，…，H r )不能r －着色的最小正整数n 称为广义Ramsey 数R (H 1，H 2，…，H r )。-----------------4分 2、如下图所示的5个顶点的完全图就没有一个纯的C 4，实线和虚线分别代表不同的颜色。 -----------------4分 故R(C 4,C 4)>=6。-----------------2分 二、(16分)未来5届欧盟主席职位只能有法国、德国、意大利、西班牙、葡萄牙五国的人当选，一个国家只能当选一次。假如法国只能当选第一届、第二届或者第三届，德国不能当选第二届和第三届，意大利不能当选第一届，西班牙不能当选第五届，葡萄牙只能能当选第二届、第四届或者第五届。问未来的5届欧盟主席职位有多少种不同的当选方案？ 解：原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C 如下图的阴影部分。 -----------------4分 学 号 姓 名 学 院 ……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………

组合数学作业答案1-2章2016

组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。

组合数学 试题及答案07

组合数学试题 共 4 页 ，第 1 页 电子科技大学研究生试卷 （考试时间： 19：30 至 21：30 ，共 2 小时） 课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2007 年 11 月 27 日 成绩 考核方式： （学生填写） 一、填空题（每空3分，共27分） 1．将6本无区别的书放入3个无区别的箱子中的放法数为 7 ，又每个箱子都不为空的放法数为 3 。 2．将8个有区别的球放入6个无区别的盒子中,每个盒子不空的放法数为 266 ；将8个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数又为28 。（注：将9个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数为462）。 3．现有4个女士6个男士围圆桌就坐，则其中女士两两不相邻的入座方式数有 5!·6·5·4·3= 43200 种； 所有女士坐在一起的方式数有 6!·4!= 17280 种。 4．将单词〝motorola 〞中的所有字母作排列，其排列方式数有 8!/3!＝6720 种；其中所有〝o 〞均不相邻的排列方式数有 ???? ???36!5＝2400 种。（两问均只要求给出解的表达式，不必算出最终结果）。 5. 方程???≥≥≥=+++0,1,2123214321x x x x x x x 的整数解的个数为 F(4,9)=220 。 学 号 姓 名 学 院 …… … …… …… …密 …… …… … 封 … … … … … 线 … … … … … 以 … … … … … 内 … … … … … 答 … …… … … 题 … …… … … 无 … … … … … 效… … … …… …… …

排列组合练习试题和答案解析86421

《排列组合》 一、排列与组合 1.从9人中选派2人参加某一活动，有多少种不同选法 2.从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法 3. 现从男、女8名学生干部中选出2名男同学和1名女同学分别参加全校“资源”、“生态”和“环保”三个夏令营活动，已知共有90种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4.一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 个个个个 5．用0，1，2，3，4，5这六个数字， （1）可以组成多少个数字不重复的三位数 （2）可以组成多少个数字允许重复的三位数 （3）可以组成多少个数字不允许重复的三位数的奇数 （4）可以组成多少个数字不重复的小于1000的自然数 （5）可以组成多少个大于3000，小于5421的数字不重复的四位数 二、注意附加条件 人排成一列（1）甲乙必须站两端，有多少种不同排法 （2）甲乙必须站两端，丙站中间，有多少种不同排法 2.由1、2、3、4、5、6六个数字可组成多少个无重复数字且是6的倍数的五位数 3.由数字1，2，3，4，5，6，7所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379个数是

4. 设有编号为1、2、3、4、5的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在五个茶杯上，至少有两个杯盖和茶杯的编号相同的盖法有 种 种 种 种 5.从编号为1，2，…，10,11的11个球中取5个，使这5个球中既有编号为偶数的球又有编号为奇数的球，且它们的编号之和为奇数，其取法总数是 种 种 种 种 6.从6双不同颜色的手套中任取4只，其中恰好有1双同色的取法有 种 种 种 种 7. 用0，1，2，3，4，5这六个数组成没有重复数字的四位偶数，将这些四位数从小到大排列起来，第71个数是 。 三、间接与直接 1.有4名女同学，6名男同学，现选3名同学参加某一比赛，至少有1名女同学，由多少种不同选法 2. 6名男生4名女生排成一行，女生不全相邻的排法有多少种 3.已知集合A 和B 各12个元素，A B I 含有4个元素，试求同时满足下列两个条件的集合C 的个数：（1）()C A B ?U 且C 中含有三个元素；（2）C A ≠?I ,?表示空集。 4. 从5门不同的文科学科和4门不同的理科学科中任选4门，组成一个综合高考科目组，若要求这组科目中文理科都有，则不同的选法的种数 种 种 种 种 5.四面体的顶点和各棱中点共有10个点，在其中取4个不共面的点不同取法有多少种 6. 以正方体的8个顶点为顶点的四棱锥有多少个 7. 对正方体的8个顶点两两连线，其中能成异面直线的有多少对 四、分类与分步 1.求下列集合的元素个数． （1）{(,)|,,6}M x y x y N x y =∈+≤； （2）{(,)|,,14,15}H x y x y N x y =∈≤≤≤≤．

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

1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5)

组合数学 课后答案

习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

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

第二章 容斥原理与鸽巢原理 1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000. 记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有： |A 1| = L 10000/4」=2500, |A 2| = L 10000/5」=2000, |A 3| = L 10000/7」=1428, 于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为 | A 1∩A 2|=L 10000/20」=500； 同理， | A 1∩A 3|=L 10000/28」=357, | A 2∩A 3|=L 10000/35」=285, A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为 | A 1∩A 2∩A 3|=L 10000/140」= 71. 由容斥原理知，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 5143 2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除 的整数集合，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - ||321A A A ?? - 2 = 10000 - L 10000/140」- 2 = 9927 3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多 少个？ 解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除， 也能被7整除的整数集。则： |A 1| = L 10000/20」= 500, |A 2| = L 10000/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={P 1,P 2,P 3,P 4},其中： P 1：5组合中a 的个数大于等于3； P 2：5组合中b 的个数大于等于4； P 3：5组合中c 的个数大于等于3； P 4：5组合中d 的个数大于等于5. 将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由 S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142 2 -+ = 10.