nbhkdz.com冰点文库

组合数学习题2(共5章)

时间:2010-08-31


第二章

容斥原理与鸽巢原理

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整除的整数个数为
| A1 ∩ A2 ∩ A3 |

= |A| - (|A1| + |A2| +|A3|) + (|A1∩A2| + |A1∩A3| +|A3∩A2|) - |A1∩A2∩A3| = 5143 2、1 到 10000 之间(不含两端)不能被 4 或 5 或 7 整除的整数有多少个? 解 令A={1,2,3,…,10000},记A1、A2、A3分别为在1与1000之间能被4,5和7整除 的整数集合,A中不能被4,5,7整除的整数个数为 | A1 ∪ A2 ∪ A3 | = |A| - | A1 ∩ A2 ∩ A3 | - 2 = 10000 - L10000/140」- 2 = 9927 3、1 到 10000 之间(不含两端)能被 4 和 5 整除,但不能被 7 整除的整数有多 少个? A 解 令 A1 表示在 1 与 10000 之间能被 4 和 5 整除的整数集, 2 表示 4 和 5 整除, 也能被 7 整除的整数集。则: |A1| = L10000/20」= 500, |A2| = L10000/140」= 71, 所以 1 与 10000 之间能被 4 和 5 整除但不能被 7 整除的整数的个数为: 500-71=429。 4、计算集合{2a, 3b, 2c, 4d}的 5 组合数. 解 令S∞={∞a, ∞b,∞c,∞d},则S的5组合数为 ( 5+ 41 ) = 56 5 设集合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的10组合全体记为Ai(1≤i≤4). 那么,A1中的元素可以看作是 由S∞的5-3=2组合再拼上3个a构成的,所以|A1| = ( 2+ 41 ) = 10. 2
10

类似地,有 |A2| = ( 54+ 41 ) = 4. 5 4 |A3| = ( 53+ 41 ) = 10. 53 |A1| = ( 55+ 41 ) = 1. 55

|A1∩A2| = ( 53 4+ 41 ) = 0. 5 3 4 | 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组合全体为 | A1 ∩ A2 ∩ A3 ∩ A4 | ,由容斥原理知,它的元素个数为 56-(10+4+10+1)-(0+0+0+0+0+0)+(0+0+0)-0=32。 5、计算{∞a, 3b, 10c}的 10 组合数. 解 令S∞={∞a, ∞b,∞c },则S的10组合数为 (10+31 ) = 66 10 设集合A是S∞的10组合全体,则|A|=66,现在要求在5组合中的b的个数小于 等于3,c的个数小于等于10的组合数. 定义性质集合P={ P1,P2 },其中: P1:10组合中b的个数大于等于4; P2:10组合中c的个数大于等于11; 类似地,有 |A2| = (1011+31 ) = 0. |A1∩A2| = = 0. 10 11 故由容斥原理知,所求组合数为 66-(28+0)-0 =38。 6、求集合{ax, by, cz}的 m 组合数(a,b,c 全非无穷大). 解 用上面的方法可以得出该集合的 m 组合数为: 将满足性质Pi的10组合全体记为Ai(1≤i≤4). 那么, |A1| = (10 4+31 ) = 28. 10 4

(

)+ ( )+ ( )+ ( + [( ) + ( ) + ( )] = ( ) [( ) + ( ) + ( )] ( + [(
3+ m 1 m 3+ m a 11 r a 1 3+ m b 11 r b 1 3+ m a b 2 1 r a b 2 3+ m b c 21 r b c 2 m b +1 2 2+ m m m a +1 2 m c +1 2 m a b 2 m a c 2 m c b 2

) [(

)+ (

3+ m c 11 r c 1

3+ m c a 2 1 r c a 2

)] )] (

3+ m c a b 31 r c a b 3

)

m a b c 1 2

)

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。 故没有选修的人数为: | F ∩ G ∩ J | = 25 – (12 + 14 + 6) + (6+5+3) – 2 = 5。 8、1 到 120 的整数中有多少质数?多少合数? 设 p 则 由于 120 <11, 解 先求合数的个数。 a 为合数, 为 a 的最小质因子, p≤ a 。 故不超过 120 的合数必定是 2,3,5,7 的倍数。 根据容斥原理可得,合数的个数为 89,质数为 119-89 = 30。
11

9、求方程 x1 + x2 + x3 = 10 的大于 2 的整数解的个数. 解 相当于求 S={∞a, ∞b,∞c }的 10-2*3=4 组合数的个数。

(

4 + 31 4

)=15

10、 求方程 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。相当于求{5x1 ,6x2 ,4x3 ,8x4}的 11 组合数。 11、 一花店某时只有 6 枝红玫瑰,7 枝粉玫瑰和 8 枝黄玫瑰。这时要从中选 12 枝做花篮,问有多少种选法? 提示 相当于求 S={6a, 7b,8c }的 12 组合数的个数。 12、 某人要给 5 个朋友每人一件生日礼物,问礼物全部送错的概率是多少? 解 D5 = 5! 13、 对集合{1,2,…,10}的元素进行排列, 恰有 5 个元素在其自然位置上的排 列有多少种? .解 任意选出 5 个元素放在其自然位置上,其余的全部错排: 解

( ) D5
10 5

14、

说明组合恒等式
n!=

( )D + ( )D
n 0 n n 1

n 1

+…+

( )D
n n

0

的组合意义.(设 D0 = 1) 解 S={1,2,…,n}排列可分成下列情况:
n 没有一个数在其自然位置上的排列数为 ( 0 ) Dn。

恰有 i(i=1,2,…,n)个数在其自然位置上的排列数为 ( in ) Dn-i。
S 的所有排列的个数为 n!。根据加法原理,有: n! =

( ) Dn + ( ) Dn-1 +…+ ( ) D0
n 0 n 1 n n

15、 计算机接到 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 个球。问共有多少种不同的方法? 解 17、
12

∑(
6 i =0

i + 2 1 i

)( )
20 i 20 i

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

换了舞伴呢? 解 从原来的每一对舞伴种选出一个,让这 5 个人错排:25D5。 18、 证明:n 对夫妻围坐于一圆桌旁,假定 n 位妻子 w1,w2,…,wn 先坐好,将 丈夫们 h1,h2,,…hn 插在两个妻子之间, 则正好有 r 对夫妻相邻而坐的方案数为
n M(n,r)= ∑ (1) k r ( k ) 2n r k =r

2n k

( )(n k )!
2nk k

证明 设 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) 假如 Ai1 , Ai2 ,..., Aik 沿圆周有两个相邻时,则 Ai1 ∩ Ai2 ∩ ... ∩ Aik =0。 总之: (1) 对于整数 k,n<k<2n, Ai1 ∩ Ai2 ∩ ... ∩ Aik =0。亦即 a(k) =
1≤i1 <i2 <...<ik < 2 n



Ai1 ∩ Ai2 ∩ ... ∩ Aik =0。

(2) 对于 1≤k≤n,根据 n 对夫妻问题,有 a(k) = 由容斥原理有: M(n,r)= ∑ (1)k r (k )a(k ) r
2n r k =r = ∑ (1)k r (k ) 2n (2 n 1 k 1 )(n k )! r k n k =r

1≤i1 <i2 <...<ik ≤ 2 n



Ai1 ∩ Ai2 ∩ ... ∩ Aik =

2n k

(

2 n k 1 k 1

) (n k )! 。

k

n = ∑ (1) k r ( k ) 2n r k =r

2n k

( )(n k )!
2nk k

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={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),所以
13

|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; 因此,满足题意的排列数为:
| A1 ∩ A2 ∩ A3 ∩ A4 |

= |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。另外,可能 0, …, 可分为 51 类{0}, {1,99}, {2,98}, {49,51}, …, 的余数共 100 个: 1, 99, {50}。因此 ri(0<i<53)中至少有两个属于同一类,例如 rj,rk。于是或者 rj=rk, 或者 rj+rk=100。这就是说,它们的和或者差可被 100 整除。 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 必是同一个 wx1(因为它们之间 分别相隔 28 天及 245 天) 。同样,1.13 和 10.13 是同一个 wx2 而且 x1≠x2; 4.13 与 7.13 同为 x3,9.13 与 12.13 同为 x4(所有 xi≠xj) 。这样剩下的 3 个 13 日是剩下的两个 wx5 和 wx6。根据鸽巢原理,这 3 日中至少有两个是属于同 一个 wx 的,而实际情况是它们间相隔天数都不是 7 的整数被。因此原假设
14

是不正确的;也就是说,至少有一个“黑色星期五” 。 24、 证明:任意 7 个实数中必存在两个实数 x,y,满足
xy = tan(α-β)。 1 + xy

0≤

xy 3 ≤ 1 + xy 3

证明 令 x = tanα, y = 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。 得证。 在一次会议中,有 5 位听众每人均离开两次,而且每两人均有同时离开 25、 的时刻。证明:一定有三人同时离开的时刻. 证明 5 人中人一位,设为 A,按题意,共离开两次;在这两次中,其余 4 人都 离开过,按照鸽巢原理,这 4 人中必然至少有两人是同时离开的。即,必然 有三人同时离开的时刻。得证。 26、 设 a1,a2,…,an 是 1,2,…,n 的一个排列.试证明:当 n 为奇数时,(a1 -1)(a2 -2)…(an –n)是偶数. 证明 当 n 是奇数时,1,2,…,n 和 a1,a2,…,an 中的奇数是
n +1 个,而偶数只 2 n 1 n +1 有 个。因此在 a1 -1,a3 -1,…,an –1 中 a1,a3,…,an(共 个)至少有 1 2 2

个是奇数,例如 ai 是奇数,则 ai-1 是偶数。于是可知整个乘积是偶数。 27、 证明:对 9 个顶点的完全图 K9 任意进行红、蓝两边着色,都或者存在一 个红色 K4,或者存在一个蓝色 K3. 证明 在 K9 中如果与每个顶点关联的红边均为 5 条,因为一条红边连着两个顶 点,所以 K9 中应该有 5*9/2=45/2 条边。它不是整数,所以不成立。故必有 一个顶点关联的红边数不为 5。设此顶点为 a,则与 a 关联的红边至少为 6 或 至多为 4。 (1)若红边数≥6:与 6 条红边相关联的 6 个顶点构成的 K6 中:要么有蓝色 的 K3,要么为红色的 K4。 (2)若红边数≤4:则蓝边数≥4。与 4 条蓝边相关联的 4 个顶点构成的 K4 中:要么是红色的 K4,要么有蓝色的 K3。 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。 有一项工作要在 37 天内完成, 但一人只要 60 小时就可以完成.此人决定 29、 每天至少在该工作上花费 1 个小时.试证明:无论他的工作计划如何,在此期
15

间都存在连续的一些天,他共在该工作上花费了 13 个小时. 证明 设 ai 是第 1 到 i 天内工作的小时数(1≤i≤37) 。由于他每天至少工作 1 小时,因此,1≤a1<…<a37≤60。 考虑序列 a1+13,a2+13,…,a37+13。显然,1<a1+13<a2+13<…<a37+13≤ 60+13=73。 则 1~73 之间的 74 个数 a1,…,a37,a1+13,…,a37+13,根据鸽巢原理, 至少有两个相等。 可设 ai = aj+13(j<i) 。即必存在连续的一些天,他共在该工作上花费了 13 个 小时。

16


赞助商链接

组合数学课后答案

组合数学课后答案_理学_高等教育_教育专区。如标题 作业习题答案 习题二 2.1 ...证明: 将S划分为{1,3,5},{7,9,11}……,{ 595,597,599}共100组,由...

组合数学引论课后答案

习题二 2.1 证明:在一个至少有 2 人的小组中,总存在两 个人,他们在组内...(5) =10种,这样一列中两个同色单元格的位置组合共有 2 10*4=40种情况。...

组合数学第二章课后习题答案

组合数学二章课后习题答案_工学_高等教育_教育...x ? x 3 ? x 5 ? L ? x 2 n +1 ? L...( ) (x ) : 共 91457520. 2.48 题(王卓) ...

组合数学第二章 《容斥原理》习题

组合数学二章 《容斥原理》习题 - 第二章 容斥原理习题 1,求出 1 ? 10000 之间不能被 4,5,和 6 整除的整数个数。 2,求出 1 ? 10000 之间不能被 ...

清华版组合数学(第二版)第四章习题答案

清华版组合数学(版)第四章习题答案清华版组合数学...5.解:相当于4.7节中例2中求b 5r3的系数, 解为...? (续前)n个球用n种颜色着色共有n!种不同 ...

组合数学第2章答案

组合数学2章习题解答 暂无评价 10页 2财富值喜欢此文档的还喜欢 ...5 ( ? x)( ? x) 2 2 设 H ( x) = A 3+ 5 ?x 2 + B 3? ...

清华版组合数学(第二版)第二章习题答案

清华版组合数学(版)第二章习题答案 - 组合数学二章答案 1. 解: ? (1 ? x) 2 n ? (1 ? x) n ? (1 ? x) n 2. 解: ? (1 ? x 4...

武大计算机学院组合数学试题+参考答案(2010A)

武汉大学计算机学院 2009-2010 学年度第学期期末考试 《组合数学》试卷 (A 卷)参考答案 1. (20 分,每小题 5) (a) n 个男孩和 n 个女孩排成一行...

组合数学(西安电子科技大学(第二版))习题4答案

组合数学(西安电子科技大学(第))习题4答案 - 习题习题四(容斥原理) 1.试求不超过 200 的正整数中素数的个数。 解:因为 152 ? 225, 132 ? 169 ...

组合数学 (2)

组合数学 (2)_数学_自然科学_专业资料。(一) ...(5)不全相异的元素的全排列:设 n 个元素可分为...题中常含有“至少有” “必有” “一定有” “...