当前位置:首页 >> 数学 >>

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


3.1 题(宗传玉) 宗传玉) 某甲参加一种会议,会上有 6 位朋友,某甲和其中每人在会上各相遇 12 次,每二人各相遇 6 次,每三人各相遇 3 次,每五人各相遇 2 次,每六人各相遇一次,1 人也没有遇见的有 5 次,问某甲共参加了几次会议 解: 设 Ai 为甲与第 i 个朋友相遇的会议 集,i=1,…,6.则

故甲参加的会议数为:28+5=33. 3.

2 题(宗传玉) 宗传玉 求从 1 到 500 的整数中被 3 和 5 整除但不被 7 整除的数的个数. 解: 设 A3:被 3 整除的数的集合 A5:被 5 整除的数的集合 A7:被 7 整除的数的集合 所以

3.3.题(宗传玉) 题 宗传玉) n 个代表参加会议,试证其中至少有 2 人各自的朋友数相等。 解: 每个人的朋友数只能取 0,1,…,n-1.但若有人的朋友数为 0,即此人和其 他人都 不认识,则其他人的最大取数不超过 n-2.故这 n 个人的朋友数的实际取数只 有 n-1 种 可能. ,所以至少有2人的朋友数相等.

3.4 题(宗传玉) 宗传玉) 试给出下列等式的组合意义.

解:

(a) 从 n 个元素中取 k 个元素的组合,总含有指定的 m 个元素的组合数为 ( 设这 m 个元素为 a1,a2,…,am,Ai 为不含 ai 的组合(子集) i=1,…,m. ,

nm k m

)=(

nm nk

)。

n l A i1 I A i 21 I L I A i1 = k n m nk=
l n m A i = + ∑ (1) l ∑ I Ai j I k ( i1 ,...,il )∈ ( m ,l ) j =1 i =1 l =1 m

m l m n l = ∑ ( 1) k k l =0

3.5 题(宗传玉) 宗传玉) 设有三个 7 位的二进制数:a1a2a3a4a5a6a7,b1b2b3b4b5b6b7, c1c2c3c4c5c6c7.试证存在 整数 i 和 j,1≤i≤j≤7,使得下列之一必定成立:ai=aj=bi=bj, ai=aj=ci=cj,bi=bj=ci=cj. 证:

显然,每列中必有两数字相同,共有

种模式, 有0或1两种选择.故共有

2

种选择.

2=6.现有 7 列,

.即必有2列在相同的两行选择相同的数字,即

有一矩形,四角的数字相等. 3.6 题(宗传玉) 宗传玉) 个点试证其中至少有两点, 在边长为 1 的正方形内任取 5 个点试证其中至少有两点,其间距离小于 证:

把1×1正方形分成四个(1/2)×(1/2)的正方形. 如上图.则这5点中必有两点落在同一个 小正方形内.而小正方 形内的任两点的距离都小于 .

3.7 题(王星) 在边长为 1 的等边三角形内任取 5 个点试证其中至少有两点,期间距离小于 1/2. 证: 把边长为1的三角形分成四个边长为 1/2 的三角形,如上图:则这5点中必有两点落在 同 一个小三角形中.小三角形中任意两点间的距离都小于 1/2. 3.8 题(王星) 任取 11 个整数,求证其中至少有两个数它们的差是 10 的倍数。 证: 整数的个位数的可能取值为0,1,…,9.共10种可能.11 个整数中必有 2个数的个 位数相同,即这两个数之差能被10整除. 3.9 题(王星) 把从 1 到 326 的 326 个整数任意分为 5 个部分,试证其中有一部分至少有一个数是某两个 数之和, 或是另一个数的两倍。 证: 用反证法。设存在划分 P1∪P2∪P3∪P4∪P5=[1,326], Pi 中没有数是两数之差. ,则 有一 Pi 中至少有 66 个数, A={ a1 ,…,a66} ,a1<a2<<a66 , 以下按书上 174 页的例 题证明可得. 3.10 题(王星) A、B、C 三种材料用作产品 I、II、III 的原料,但要求 I 禁止用 B、C 作原料,II 不能用 B

作原料, III 不允许用 A 作原料,问有多少种安排方案?(假定每种材料只做一种产品的 原料) 解: 按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区. 棋盘多项式为: R( )=R( )R( ) =(1+x)(1+3x+x2 ) =1+4x+4x2 + x 3 故方案数=3!-42!+4 1!-1 0!=1 3.11 题(王星) n 个球放到 m 个盒子中去,n<(m/2)(m-1),试证其中必有两个盒子有相同的球数。 解: 设 m 个盒子的球的个数是 a1,…,am, 各不相等,且有 0≤a1<a2<<am.则有 a2≥1、 am≥m-1,故 ≥1+2+…+m-1=(m/2)(m-1) , 与 n<(m/2)(m-1)相矛盾! 所以必有两个盒子的球数 相等. 3.12 题(王星) 一年级有 100 名学生参加中文、英语和数学的考试,其中 92 人通过中文考试,75 人通过英 语考试,65 人通过数学考试;其中 65 人通过中、英文考试,54 人通过中文和数学考试, 45 人通过英语和数学考试,求通过 3 门学科考试的学生数。 解: 设: 通过中文考试的 92 人为集合 A,通过英语考试的 75 人为集合 B,通过数学考试的 65 人为集合 C 则∣A∩B∣=65,∣A∩C∣=54,∣B∩C∣=45 由∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C∣∣B∩C∣+∣A∩B∩C∣ 故∣A∩B∩C∣=∣A∪B∪C∣-∣A∣-∣B∣-∣C∣+∣A∩B∣+ ∣A∩C∣+∣B∩C∣ =100-92-75-65+65+54+45 =32 通过 3 门学科考试的学生数为 32。 3.13 题(王丹竹) 王丹竹) 试证 (1) | A ∩ B |=| B | | A ∩ B | (2) | A ∩ B ∩ C |=| C | | A ∩ B | + | A ∩ B ∩ C | 证明: 证明 (1) A I B = AI B ≠ A I B = B A I B =B AI B = B AI B

A=B A I B = B A I B =

所以 A I B = B A I B 成立 (2) A I B I C = A U B I C AI B = AU B

AU B = A + B AI B = C AIC B IC + AI B IC

又因为 由(a)得 原式= C ( A U B) I C = C ( A I C ) U ( B I C ) 3.14 题(王丹竹) 王丹竹)
N = {1,2, L ,1000} ,求其中不被 5 和 7 除尽,但被 3 除尽的数的数目。

解: 设

A
5

3

为被 3 除尽的集合

A A

为被 5 除尽的集合 为被 7 除尽的集合

7

所以由题意得:

A IA IA
3 5

7

=

A

3



A IA
3

5

+

A IA IA
3 5

7

-

1000 1000 1000 1000 = + 3 3× 5 3× 7 3× 5 × 7 =333-66-47+9=229 3.15 题(王丹竹) 王丹竹)
N = {1,2, L ,120} ,求其中被 2,3,5,7 中 m 个数除尽的数的数目,m=0,1,2,3,4。求不

超过 120 的素数的数目。 解: (1) m=0 时 不被 2,3,5,7 除尽的数为

A IA IA IA
2 3 5

7

=1207

A

2



A

3

+

A

5



A
7

+

A IA
2 5 7

3

+

A IA
2 2 3

5

+

A IA
2 5

7

+
3 7

A IA
5 2

3

A IA
3 7

+

A IA - A IA IA
5 7


5

A IA IA
2 7

-

A IA IA
5



A IA IA
3

+

A IA IA IA
2 3

=120- ( 60+40+24+17 ) +

(20+12+8+8+8)-(4+2+1+1)=27
m=0 时

A IA
2

3

120 = = 20 2×3

A IA
2

5

120 = = 12 2×5 120 = =8 2×7 120 = =5 3× 7 120 = =3 5× 7 120 = =4 2 × 3× 5

A IA
2

7

A IA
3

7

A IA
5

7

M=3 时

A IA IA
2 3 3 7

5

A IA IA
2

120 = =2 2 × 3× 7 120 = =1 2×5× 7 120 = =1 3× 5× 7 120 = =0 2 × 3× 5 × 7

A IA IA
2 5

7

A IA IA
3 5

7

M=4 时 (2)

A IA IA IA
2 3 5

7

因为

11

2

= 121 ,故不超过 120 的合数必然是 2,3,5,7 的倍数

而且不超过 120 的合数的因子不可能超过 11 设

A 为不超过 120 的数的倍数集合,i=2,3,5,7
i

排除 2,3,5,7 这四个数又包含 1 这个非素数 2,3,5,7 本身是素数,故所求不超过 120 的素数个数应该为 27+4-1=30 3.16 题(王丹竹) 王丹竹) 求正整数 n 的数目,n 除尽10 , 20 中的至少一个数。 解: N 为正整数 设 A 40 为被10 除尽 10
40 40 30

A20

30

为被 20 除尽

30

n = 40 A10 10
40

n = A20 30 20
30

A10

40

IA

n = 40 30 20 10 × 20
30

3.17 题和 3.18 题(未完成) 王丹竹) 未完成) 王丹竹) ( 3.19 题(孔令琪) {1000,1001,。,3000},求其中是 4 的倍数但不是 100 的倍数的数目。 。。 解: 设 A,B 分是 4,100 的倍数。 3000 1000 A = = 500 4 3000 1000 A∩ B = =5 4 * 100
A ∩ B = A A ∩ B = 500 5 = 450 3.20 题(孔令琪) 在由 a,a,a,b,b,b,c,c,c,组成的排列中,求满足下列条件的排列数, (1)不存在相邻 3 元素相同;

解: A,B,C 分别表示 aaa,bbb,ccc 则:
A= B =C =

(3!)2
5! 3!

7!

A∩ B = A∩C = B ∩C = A∩ B ∩C =1 S =


(3!)3


9!

A∩ B∩ C = S ( A + B + C ) + ( A ∩ B + A ∩ C + B ∩ C ) A ∩ B ∩ C =

(3!)

9!

3

3*

(3!)

7!
2

+ 3*

5! 1 3!

(2)相邻两元素不相同。

3.21 题(孔令琪) 求从 O(0,0)点到(8,4)点的路径数。已知(2,1)到(4,1)的线段, (3,1) 到(3,2)的线段被封锁 解: 设 A 点坐标(2,1) 点坐标(4,1) 点坐标(3,1) 点坐标(3,2) ,B ,C ,D 令 a 为从 O 点到 M 点经过 AC b 为从 O 点到 M 点经过 CB c 为从 O 点到 M 点经过 CD
s = c(12,4) = a = c(3,1) * c(8,3) = 168 b = c(4,1) * c(7,3) = 140 c = c(4,1) * c(7,2) = 84 a ∩ b = 105 a ∩ c = 63 b∩c = 0 a∩b∩c = 0 a ∩ b∩ c = s ( a + b + c ) + ( a ∩ b + a ∩ c + b ∩ c ) a ∩ b ∩ c = 271


3.22 题(孔令琪) 求满足下列条件 x1+x2+x3=20,
3 ≤ x1 ≤ 9,0 ≤ x 2 ≤ 8,7 ≤ x3 ≤ 17

解:

令 y1=x1-3,y2=x2,y3=x3-7 0 ≤ z1 = 6 y1,0 ≤ z 2 = 8 y 2,0 ≤ z 3 = 17 y3, z1 + z 2 + z 3 = 6 y1 + 8 y 2 + 17 y3
= 31 ( y1 + y 2 + y3) = 41 ( x1 + x 2 + x3) = 21

则所求整数解的数目:c(23,21)=c(23,2)=253 3.23 题(孔令琪) 此题解法与上题一样,所以不在求解,如有凝问请与我联系! 3.24 题(周英华) 求满足下列条件的整数解数目:x1+ x2+ x3+ x4=20 1≤x1≤5,0 ≤x2≤7,4 ≤x3≤8,2≤x4≤6 解: 设 y1= x1 -1, y2= x2, y3= x3 -4, y4= x4 -2,

y1+y2+y3+y4=13 0 ≤y 1≤4, 0 ≤y 2≤7, 0 ≤y 3≤4, 0 ≤y 4≤4, 若不附加上界条件的解根据公式应为 13 + 4 1 16 16 = = = 560 13 13 3 对于有上界的问题要作变换 ε1=4-y1, ε2=7-y2, ε3=4-y3, ε4=4-y4, ε1≥0 , ε2≥0 , ε3≥0 , ε4≥0 , 于是问题变为 ε1+ε2+ε3+ε4=6 整数解的数目 6 + 4 1 9 9 = = = 84 6 6 3 3.25 题(周英华) 证明满足下列条件:x1+ x2+……+ xn=r i=1,2,……,n 0≤xi≤k ,

的整数解数目为

∑ (1) i r 1
i i =0

n

n r (k + 1)i + n 1

解: n + r 1 S, |S|= r 令 S 中具有 x1≥k+1 的子集 A1,……,xi≥k+1 的子集 Ai , 问题转化为求| A1∩A2∩…∩An | |A1|= r + n k 2 |A1∩A2 |=
r 1 r + n 2k 4 r 1




n n r (k + 1)i + n 1 = ∑ (1)i i =0 i r 1

| A1∩A2∩…∩An |

3.26 题(周英华) 证明满足下列条件:x1+ x2+……+ xn=r 1≤xi≤k , i=1,2,……,n

的整数解数目为

∑ (1) i r 1
i i =0

n

n r ki 1

证明: 证明: 令 yi= xi-1 则 y1+ y2+……+ yn=r-n

0≤yi≤k ,

i=1,2,……,n

n n r (k + 1)i + n 1 由上题知 ∑ (1)i i =0 i r 1

代入得整数解数目为

∑ (1) i r 1
i i =0

n

n r ki 1

3.27 题(周英华) 求 n 对夫妻排成一行,夫妻不相邻的排列数。 解: (1)n 个人排成一行方案数为 n! N 对夫妻排成一行方案数为 n!2n 令 Ai 第 i 对夫妻相邻而坐的集合,i=1,2,……,n (2)2n 个人排成一行方案数为(2n)! |Ai|相当于将第 i 对夫妻作为一个对象排列一行然后换位,故 |A1|=2(2n-1)! |A1∩A2 |=22(2n-2)! … … |A1∩A2∩…∩An|=2n n! 故夫妻不相邻排列数为 n n N=(2n)!-2 (2n-1)!+ 22 (2n-2)!- ……+(-1)n2n n! 1 2
n n = ∑ 2h (2n-h)! h =0 h

3.28 题(周英华) 设 p,q∈N,p 是奇数,现在有 pq 个珠子,着 q 种颜色,每种颜色有 p 个珠子。假定相 同颜色的珠子无区别。试分别求满足以下条件的珠子的排列数。 (1)同颜色的珠子在一起; (2)同颜色的珠子处于不同的块; (3)同颜色的珠子最多在两个块。 解: 同颜色的珠子在一起的排列数 p! 同颜色的珠子处于不同的块的排列数 p!qp 同颜色的珠子最多在两个块的排列数 Ai 相当于第 i 个某色球处于不同块 | A1 |=q(pq)! |A1∩A2 |=q2(pq-1)! … … |A1∩A2∩…∩Ap|=qp(pq-p)!

p N= q(pq)!- q2 (pq-1)! +……+(-1)pqp(qp-p)! 1
p p = ∑ q p ( pq i ) i =0 i

3.29 题(翟聪) 将 r 个相同的球放进 n 个有标志的盒子里,无一空盒,求方案数。 解: 先拿出 n 个球在每个盒子里放一个球,再将剩下的 r-n 个球无限制地放入 n 个盒子中。根 据定理 1.3, 个球无限制地放到 n 个盒子中共有 C(n+r-n-1,r-n)=C(r-1,r-n)=C(r-1,n-1) r-n 种放法。 3.30 题(翟聪) 30
n 1 n n + r i 1 r 1 = 试证 ∑ (1) i i n 1 ,r,n∈N,r>n r i 0

解: 设共有 r-1 个不同的红球和 n 个不同的白球,从中取出 n-1 个球. 等式左边每个累加项(不考虑符号)可化为:C(n,i)C(n+r-1-i,n-1-i)表示从这些球中取 i 个白球和 n-1-i 个红球,表示至少取 i 个白球的组合数,即β(i)。 等式右边表示只从 r-1 个红球中取出 n-1 个球的组合数,表示恰好取 0 个白球的组合数, 即α(0)。 n-1 根据广义容斥定理α(0)= β(0)-β(1)+β(2)-…+(-1) β(n-1)。原式证毕。 3.31 题(翟聪) 设 B 是 A 的子集, A =n, B =m,求 A 的子集包含 B 的子集的数目,设子集的元素数目为
r,m≤r≤n。 (没看懂,不会做) 3.32 题(翟聪)

n m m i m,r,,n∈N,满足 m≤r≤n,试证 n r = ∑ (1) i =0 证明: 证明:

m i

n i r

n m n m 从 n 个元素中取 k 个的组合,总含有制定的 m 个元素的组合数为 k m = n k ,设这 m 个元素为 a1 , a2 ,.....am , Ak 为不含 ak 的组合(子集) i=1,…,m. , n i AK 1 I AK 2 I ... I AKi = r
i m n m m n m = I Ai = + ∑ (1) i (1) i I AKj ∑ nr r ( k1 , k 2 ,..k i )∈Φ ( m ,i ) j =1 i =1 i =1

r k

3.33 题(翟聪)

求证 a) D(n, r , k ) = ( r ) D(n k , r k , 0) k 证明: 证明: 右边=
=( r ) * k

( )
r k

(n r )! i =0

∑ (1)

r k

i

(

r k i

) (n k i)!

∑ (1) ( (n k r + k )!
i i=0

( )
r k 0

r k 0

r k 0 i

) (n 0 i)!

1 r k ∑ (1)i (n r )! i =0

( ) (n k i)! =左边
r k i

b)
D ( n, r , k )

= D (n 1, r 1, k 1) +(n-1) D (n 1, r 1, k ) +(r-1)( D (n 2, r 2, k ) - D (n 2, r 2, k 1) )

()
r k

( r 2 ) r k 2 ( rk12 ) rk1 (1)i rk1 (n k i 1)! k i r k 2 (r 1) ∑ (1) ( i ) (n k i 2)! (n r)! ∑ ( i ) i =0 (n r)! i=0

(n r)! i=0

∑(1)

r k

i

( ) (n k i)! = (n r)! ∑(1) ( ) (n k i)!+ (n 1)* (n r)! ∑ (1) (
r k i i i =0 r k i i i =0

( )
r 1 k 1

r k

( )
r 1 k

r k 1

r k 1 i

) (n k i 1)!+

(

r k

) ∑ (1)i
i =0

r k

(

r k i

) (n k i)! = ( kr 11 ) ∑ (1)i
i =0

r k

(

rk i

) (n k i)! + (n 1) * ( kr 1 )
r k i =0

r k 1 i=0

∑ (1) (
i

r k 1 i

) (n k i 1)! +

r k 2 (r 1) ( r 2 ) ∑ (1)i k i=0

(

r k 2 i

) (n k i 2)! ( kr 12 ) ∑ (1)i

(

r k 1 i

) (n k i 1)!


r! (r 1)! (r 1)! r k r k (r k )! (r k )! (r k )!k ! (r k )!(k 1)! (r k 1)!k ! r k 1 (1)i (n k i)! = (1)i (n k i)!+ (n 1)* ∑ (r k i)!i! ∑ (r k i)!i! ∑ (1)i (n r)! i=0 (n r)! i=0 (n r)! i=0 (r 2)! (r 2)! r k 2 r k 1 (r k 2)!k ! (r k 2)! (r k 1)! (r k 1)!(k 1)! (r 1) ∑ (1)i (r k i 2)!i! (n k i 2)! (n r)! ∑ (1)i (r k i 1)!i! (n k i 1)! i =0 i =0 (n r)!
r ∑ (1)i
i =0 r k rk r k 1 (n k i )! (n k i )! 1 = k ∑ (1)i + (n 1) ∑ (1)i + (r k i )!i ! (r k i )!i ! (r k i 1)!i ! i =0 i =0

r k r k 2 (n k i 1)! i ( n k i 2)! k ∑ (1)i ∑ (1) (r k i 2)!i ! (r k i 1)!i ! i =0 i =0

(r k )∑ (1)i
i=0

r k

r k 1 (n k i )! (n k i 1)! r k 2 (n k i 2)! = (n k 1) ∑ (1)i + ∑ (1)i (r k i )!i ! (r k i 1)!i ! i = 0 (r k i 2)!i ! i =0

(r k )∑ (1)i
i =0

r k

r k 1 (n k i)! (n k i 1)! r k 2 (n k i 2)! = (n k 1) ∑ (1)i + ∑ (1)i (r k i )!i ! (r k i 1)!i ! i = 0 (r k i 2)!i ! i =0

c)
D(n, n, k ) = n * D(n 1, n 1, k ) + (1) n k ( n ) k
nk n k 1 n! (n k )! n! (n k 1)! (1)i (n k i )! = ∑ ∑ (1)i (n k i 1)!i ! (n k i 1)! + (n k )!k ! i =0 (n k i )!i ! (n k 1)!k ! i = 0 n! (1) n k (n k )!k !

n ! nk 1 n ! n k 1 1 n! (1)i = ∑ ∑ (1)i i ! + (1)nk (n k )!k ! k ! i =0 i ! k ! i =0

n ! nk 1 n ! n k 1 1 n! ∑ (1)i i ! = k ! ∑ (1)i i ! + (1)nk (n k )!k ! k ! i =0 i =0

得证。 d)

( ) D ( n, r , k ) = ( ) D ( n t , r t , k t )
k t r t

( )( )
k t r k

(n r )! i =0

∑ (1)i

r k

(

r k i

) (n k i)! =

( )( )
r t r t k t

∑ (1) ( ) (n k i)! (n r )!
i i=0 r k i

r k

k !r ! (k t )!t !(r k )!k ! r k ∑ (1)i (n r )! i=0 r! (k t )!t !(r k )! r k ∑ (1)i (n r )! i=0

r !(r t )! (r t )!t !(r k )!(k t )! r k r k (n k i )! = (i ) ∑ (1)i (n r )! i=0

( ) (n k i)!
r k i

r! r k )!( ( ir k ) (n k i)! = t !(r nk r k t )! ∑ (1)i ( )! i =0

( ) (n k i)!
r k i

反过程可证。 e)
D (n, r , k ) = r * D (n 1, r 1, k ) + D (n 1, r , k )

∑ (1) ( ) (n k i)! = (n r )!
i

( )
r k

r k i =0

r k i

r *(

∑ (1) ( (n r )!
i i =0

r 1 k

)

r k 1

r k 1 i

) (n k i 1)!+ (n r 1)! ∑ (1) ( ) (n k i 1)!
i i =0 r k i

( )
r k

r k

r! (r k )!k ! r k ∑ (1)i ( ir k ) (n k i)! = (n r )! i =0 (r 1)! r! r* r k 1 (r 1 k )!k ! (r k )!k ! r k (1)i ( ir k 1 ) (n k i 1)!+ ∑ ∑ (1)i (n r )! (n r 1)! i =0 i =0

( ) (n k i 1)!
r k i

∑ (1)i
i =0

r k

r k (n k i )! r k 1 (n k i 1)! (n k i 1)! = ∑ (1)i + (n r )∑ (1)i (r k i )!i ! i = 0 (r k i 1)!i ! (r k i )!i ! i =0

当 i=0 时,各项左右相等,对应当 n=r-k-1 时候,左右也相等。 剩余左右当 i=r-k 时候也相等,得证。 F)
r n i 1 r! (1) j n (1) j =∑ (n i )!∑ n !∑ r ! i = 0 (r i )!i ! j! j! j =0 j =0

3.34 题(王卓) 王卓)
n ∈ N , 设 Pn 表示在{1,2,……,n}的全排列中,排除了 k,紧随以 k+1,k=1,2……,k+1,

试证 Pn=Dn+Dn-1, n ∈ N . (不会做) 3.35 题(王卓) 王卓) 令 Dn(k)=D(n,n,k),试证
(a)

n Dn(k)= Dn-k k

证明: 证明: n nk i i k n k n nk n k Dn (k ) = D (n, n, k ) = ∑ (1) i (n k i )!= k ∑ ( 1) i (n k i )!i (n n)! i =0 i =0
Dn k n k nk ∑ (1) = 0 i =0
i i nk n k n k (n k i )!= ∑ ( 1) (n k i )! i i i=0

n ∴ Dn (k ) = Dn k k n n n (b) D1 + D2 + K + Dn = n! 1 2 n

证明: 证明: 上面等式可变换为:
n n n n 1 D1 + n 2 D2 + L + 0 Dn = n!

考虑 n 元素的集合 S={1,2,…,n},设 T 为 S 的排列全体,则|T|=n!。设 Ai 是 S 中恰有 i 个在其自然位置的 n-排列全体,则
Ai ∩ A j = φ
n

T = U Ai
i =0

n

所以, | T |= ∑ | Ai |
i =0

n 而, | Ai |= Dni i
n n 因此, n! = ∑ Dni i =0 i

(c)(k+1) Dn+1(k+1)=(n+1) Dn(k) 证明: 证明:

n + 1 i k + 1 n +1k 1 i n + 1 k 1 n + 1 n k n k (n + 1 k 1 i )!= ∑ ( 1) (n k i )! Dn+1 (k + 1) = ∑ (1) i k + 1 i 0! i =0 i =0

(k + 1)Dn+1 (k + 1) = (k + 1)

n + 1 n k ∑ (1) k + 1 i = 0

i

n k (n k i )! i

i n nk n k (n k i )!= (n + 1)Dn (k ) = (n + 1) ∑ ( 1) k i i =0

3.36 题(王卓) 王卓) 令 Dn(k)=D(n,n,k),试证
(a) ∑ kDn (k ) = n!
k =0 n

(b) Dn(0)- Dn(1)=(-1)n (c)

∑ (k 1)
k =0 n

n

2

Dn (k ) = n! (k ) = n!

(d)

∑ k (k 1)K (k r + 1) D
k =0

n

3.37 题(王卓) 王卓) 试证
(a) φ (m, n ) = φ (m )φ (n )

(b)对于素数 p1 ,i ≥ 1 , φ ( p i ) = p i p i 1

1 1 1 α α α K 1 根据n = p1 1 p 2 2 K p k k 则φ (n ) = n1 1 p1 p2 pk
n = pi

φ ( p i ) = φ (n ) = n1

3.38 题(王卓) 王卓) 试证
(a) ∑ φ (d ) = n
d/n

1 1 = p i 1 = p i p i 1 p p

φ (n ) = n∑
d /n

(d )

d 根据反演定理可得 n = ∑ φ (d )
d /n

(b) φ (m, n )φ (h ) = φ (m )φ (n )h, 其中m, n ∈ N , h = (m, n ) (c) n ∈ N , n ≥ 3, φ (n )通常是偶数 3.39 题(王振华) 3.40 题(王振华) 3.41 题(王振华) (未完成) 3.42 题(王振华) 一组人有 1990 个人,每个人至少有 1327 个朋友,试证其中四位,使得彼此都是好朋友 解; 令外边的都与括号里的 1327 个是朋友, 1 {1989} ,从里边不是外边人朋友的找出 2 {1988} ….. 663 {1327} 再从里边找人出来 662,1 { {1},1236} 直至 663 { {663} 664} 按上面的方法继续 663 {{663} {663} 1} 把里边的 1 拿出外边一个进去为 662,1 { {1} {663} {663}} 这样 1 与里边的都是朋友,括号里前面括号的人与后边的都是朋友,所以一定有四个人彼 此是朋友。 3.43 题(王振华) 在边长为 1 的等边三角形内任取 5 个点试证其中至少有两点,期间距离小于 1/2. 证:

把边长为1的三角形分成四个边长为 1/2 的三角形,如上图:则这5点中必有两点落在 同 一个小三角形中.小三角形中任意两点间的距离都小于 1/2. 3.44 题(王居柱) 单位圆圆周上任意 n + 1 个不同的点至少存在两点其间距离不超过 2sin 证明: 证明: 把圆周等分成n段相等的弧,每段弧所对的最大弦长为S= 2sin
π
π
2

π
2



,把n+1个点

放到这n个圆弧上,根据鸽巢原理,必有两个点在同一段弧上,这两点的距离必 小于等于 2 sin 2 。
3.45 题 (王居柱) 边长为 1 的正方形内任取 9 点,试证存在 3 个不同的点,由此构成的三角形面积不

过8。 证明: 证明: 把正方形等分为 8 个三角形,每个三角形的面积为 8 ,产生以正方形中心的 8 条边,把
9 个点放到 8 条边上,根据鸽巢原理,必有两个点在同一条边上,所以可以得到
1 1

1

一个三角形的面积小于 8 。
3.46 题(王居柱) 任给 5 个整数,试证其中必存在 3 个数的和被 3 除尽。 证明: 证明: 课本 145 页例题,第(4)题 3.47 题(王居柱) A 是 n+1 个数的集合,试证其中必存在两个数,它们的差被 n 除尽。 证明: 证明

构造一个序列 s1 = a2 - a1 ,

s

2

= a3 - a1 ,…….

s =a
n

n +1

- a1 ,

si



sj

(i ≠ j ),
( 1 ≤ m ≤ n )是 n 的倍数,则定理得证。

有两种可能(1)若有一个 sm

(2)设在序列中没有任何一个元素是 n 的倍数,则 s1 , s 2 ……….. s n 除 n 的余数为 1,2,3,……….n-1,因为有 n 个数,由鸽巢原理得,必有两个 数的余数是相同的,不妨设 si , s j 的余数相同, 则

si = ai+1 - a1 =bn+r…………………..(1)

s j = a j +1 - a1 =cn+r…………………. (2)
两式相减的 3.48 题(王居柱) ai +1 - a j +1 =(b-c)n 原式得证。

a A={ a1 , 2 , a ………… a2 k +1 } k ≥ 1, ai 是正整数, k=1,2,3,……2k+1,试证 A 的任意排列: i1 , ai2 ,…………, ai2 k +1
证明: 证明: 根据鸽巢原理, a1 , a2 ,………… a2 k +1 这 2k+1 个数中必有 k+1 个数同为偶数或同为 奇 数 , 不 妨 设 这 k+1 个 数 为 a1 , a2 , ………… ak +1 , 且 同 为 奇 数 , 则 a1 , a2 ,………… a2 k +1 中至多有 k 个偶数,根据鸽巢原理, 恒有

Π ( ai a j )为偶数。
2 k +1 j =1
j

ai1 , ai2 ,…………, aik +1 中至少有一个是奇数,奇数和奇数之差为偶数,所以

ai j a j

中必有一个是偶数,同理,有 k+1 个数同为偶数时也成立,
2 k +1 j =1

所以原式 Π ( ai j 3.49 题(王健)

a j )为偶数

得证。

A 是{1, ……………,2n}中任意 n+1 个数,试证至少存在一对 a,b ∈ A,使下面结果成立: 2, a

b

证明: 证明: 设所取 n+1 个数是 a1, a2,……….. an, an+1 对 a1, a2,……….. an, an+1 序列中的每一个数去掉一切 2 的因子,直至剩下一个奇数为止。 结果得到由奇数组成的序列 r1, r2,……….. rn, rn+11 到 2n 中只有 n 个奇数,故序列中至少有两个 是相同的。设 ri= rj=r 为,对应地有 ai= 2
ai
r,

aj= 2

aj
r,

若,则至少存在一对 a,b ∈ A,使下面结果成立:a 3.50(王健) 未完成 3.51(王健) 未完成 3.52(王健) 未完成

b

3.53(王健) 未完成

3.54 题(孙明柱) 孙明柱) 二维空间的(x,y)点的坐标 x 和 y 都是整数的点称为格点,任意 5 个格点的 集合 A,试证 A 中至少存在两点,它们的中点也是格点。 证明: 证明: 任意 5 个格点,对于 x,y,5 个整数中至少存在 3 个数为偶数或者为奇数 它们的中点就是两个点的对应数的和的一半, 1,当存在三个偶数时,则其中任意两个数的和的一半能被 2 整除,余下的两 个奇数的和也能被 2 整除,即存在两个格点。 2,当存在四或五个偶数时,则四个偶数中任意取两个的数和是 2 的倍数,即 存在两个格点 反之存在奇数的情况也一样。 所以存在至少存在两点,它们的中点也是格点。 3.55 题(孙明柱) 孙明柱) 令 A 为等差数列 1,4,7,10,…,100 中任选 20 个不同的数,试证其中至少存在两个数,它们的和为 104. 证明: 证明: 在这 34 个数中,除去 1 和 52,余下的 4 和 100,7 和 97,…..49 和 55,它们 的和为 104,共 16 对,从 A 中任取 20 个数,除去 1 和 52,从余下的 16 对数 中取 18 个,根据鸽巢原理,其中至少存在一对数的和为 104 3.56 题(孙明柱) 孙明柱)

平面上 6 个点,不存在 3 点共一条直线,其中必存在 3 点构成一个三角形,有 一内角小于 30o 。 证明: 证明: 首先任意选三个点构成一个三角形,把平面分成三角形内和三角形外两部分, 根据鸽巢原理,剩下的三个至少有两个点在三角形内或三角形外,假设至少两 个点在三角形内,由于没有三个点共线, (1)当有两个点在三角形内时, 一个三角形至少存在一个内角是锐角, 这两点把 三角形的这个锐角内角分成三等分,则至少有一个角是小于 30o ,的,即存在 一个内角小于 30o 的三角形的 (2)当有三个点在三角形内则,由(1)知,肯定存在一个内角小于 30o 的三角形的 同理在三角形外也有同样的结论。 3.57 题(孙明柱) 孙明柱) n 是大于等于 3 的整数,则下列数的集合: {2-1, 22 1, 23 1, , 2n1 1 } 中存在一数被 n 除尽。 解: 我认为此题有争议,当 n=4 时,数的集合是{2-1, 22 1, 23 1 } 即:{1,3,7} 都不能被 4 除尽。 3.58 题(孙明柱) 孙明柱) n 个人的集体,试证存在两个人,在余下的 n-2 个人中,至少有 二人认识,要么与这两个人均不相识。 (未完成)
n -1 个要么与 2

3.59 题(李拂晓) 李拂晓) 3.60 题(李拂晓) 李拂晓) 3.61 题(李拂晓) (李拂晓) n 各单位各派两名代表去出席一会议。2n 位代表围一圆桌坐下。试问: (1)各单位代表并排坐着的方案是多少? (2)各单位的两人互不相邻的方案数又是多少? 解: (1)方案数=(n-1)!2n (2)设第 i 个单位的代表相邻的方案数为 Ai,i=1,2,…,n

I Ai = ∑ ( 1)
i =1 k =0

n

n

k

n k n Ai = ∑ ( 1) (2n 2k 1)!2 k ∑,k ) U k I ∈ ( n k =0 i∈I

3.62 题(李拂晓) 一书架有 m 层, 分别放置 m 类不同种类的书, 每层 n 册。 先将书架上的图书全部取出清理。 清理过程要求不打乱所有的类别。试问: (1)m 类书全不在各自原来层次上的方案数有多少? (2)每层的 n 本书都不在原来位置上的方案数等于多少? (3)m 层书都不在原来层次,每层 n 本书也不在原来位置上的方案数又有多少? 解:

3.63 题(李拂晓) 李拂晓)

m+1 行

列的格子同 m 种颜色着色,每格着一种颜色,其中必有一个 4 角同色

的矩形。 证: 每列有(m+1)行,只有 m 种颜色,故一列中必有两格同色.同色的2个格子的行 号有

种取法.有 m 种色,故有 m

种同色模式,现有 m

+1 列,必有两列

的同色模式相同.即由这两列的对应行上有 4个格子同色,正好是一个矩形的4个角上的 格子.得证. 3.64 题(高亮) 两名教师分别对6 名学生同时进行两门课程的面试(每名教师各管一门课程)每名学生 每门面试的时间都是半个小时,共有多少不同的面试顺序? 解

第一门课的顺序有6!种; 第二门课的顺序有: D6=6! ( (1/2!)-(1/3!)+(1/4!)-(1/5!)+(1/6!) )=265; 故总顺序有 6!×265 种. 3.65 题(高亮) 未完成 3.66 题(高亮) 未完成 3.67 题(高亮) 未完成 3.68 题(高亮) 未完成 3.69 题(顿绍坤) 试证(mn)!被(m!)m 整除。 证明: 证明: 我认为本题肯定缺少已知的某个或几个条件。 例如,当 m=2,n=1 时,(mn)!=2!=2 右边, (m!)m= (2!) 2 =4 2 不能被 4 整除,命题错误。 3.70 题(顿绍坤) 从(0,0)点出发,每走一步任意到达左、右、上、下相邻格子点。试问 10 步后返回到原点, 共有多少种不同的回路。 解: 因为从(0.0)点出发,又回到原点,那么可以知道在这一路径中向上走的步数和向下走 的步数相等;向左走的步数和向右走的步数相等。 设横向走的步数为 m,纵向走的步数为 n,则 m+n=10。 由以上分析还可得知,m 和 n 都是偶数。 那么,m 的取值只能是 0,2,4,6,8,10,而 n 的取值是 10-m。 当 m 为确定的某一数时,则回路构成的步的方案实际上也就是 m,n 构成的一个排列,因 为同一个方向走无区别,因此应去掉这种排列。例如,m=0 时,回路个数为:
10! 10! = m m n n 5!5! ( )! ! ! ! 2 2 2 2

因此,将各种情况相加,得到的回路个数为:
10! 10! 10! 10! 10! 10! + + + + + 5!5! 1!1!4!4! 2!2!3!3! 3!3!2!2! 4!4! 5!5! 10 × 9 × 8 × 7 × 6 10 × 9 × 8 × 7 × 6 × 5 10 × 9 × 8 × 7 × 6 × 5 × 4 = 2× + + 4 × 3 × 2 ×1 3!×4 5 × 4 × 3 × 2 ×1 = 2 × (36 × 7 + 100 × 63 + 400 × 63) = 2 × 31752 = 63504 3.71 题(顿绍坤)

1,2,…,n 的全排列中不出现相邻两数相邻的排列数等于多少? (未完成) 3.72 题(顿绍坤) 0,1,2,…,n-1 的原排列,求不出现相邻数的排列数等于多少? (未完成) 3.73 题(顿绍坤) 4 位十进制数 a b c d,试求 a+b+c+d=31 的数的数目。 解: 因为 a b c d 分别是 4 位数的十进制位数,因此必有
0 < a ≤ 9, 0 ≤ b ≤ 9, 0 ≤ c ≤ 9, 0 ≤ d ≤ 9

设 ε 1 = 9 a, ε 2 = 9 b ε 3 = 9 c ε 4 = 9 d

ε 1 + ε 2 + ε 3 + ε 4 = 36 (a + b + c + d ) = 36 31 = 5 ε 1 ≥ 0, ε 2 ≥ 0 ε 3 ≥ 0 ε 4 ≥ 0
这个问题可以看作 4 取 5 允许重复组合的组合数。 整数解得数目为 4 + 5 1 8 5 = 3 = 56 上试中还得去掉 a=0 时的情况。 当 a=0 时,b+c+d=31 由 b,c,d 的限制条件这是不可能的。 因此,满足条件的解得个数是 56 个。 3.74 题(陈兴) 陈兴) 未完成) (未完成) 3.75 题(陈兴) 陈兴) 已知 n 是正整数, d1 = 1, d 2 , L , d r = r 是 n 的除数,即 d i | n, i = 1,2, L , r ,试证:

∑ φ (d ) = n
i di

证明: 证明:

φ (n ) = n∑
d n

(d )
d

n 根据反演定理 : f (n ) = ∑ φ (d )成立的充要条件是g (n ) = ∑ φ (d ) f d d n d n n = ∑ φ (d )
d n

这里, φ (n ) = g (n ), f (n ) = n, (见书P 225原题)

3.76 题(陈兴) 陈兴)

试证欧拉函数有

φ ( n) = n∑
d |n

(d )
d

解: φ (n )
k 1 = n∏ 1 p i =1 i 1 t = n 1 ∑ (1)t ∑ ∏ pi I∈C ( k ,i ) i∈I i=1 (d ) = n∑ d d n1

= n∑
dn

(d )
d
a a2 a

(当n > 1, n = p1 1 p2 L pk k , n1 = p1 p2 L pn ) (当n = 1, 显然成立)

3.77 题(陈兴) 陈兴)
设 f 满足 f (m, n) = f (m) f (n), g (n) = ∑ f (d )
d |n

试证: g (m, n) = g (m) g (n) 证明: 证明: 因为若 m 不同的除数为 d1 , d 2 ,L, d s ; n的除数为d 1 , d 2 ,L, d t , 则
g (m) = ∑ f (d i )
i =1 s

g (n ) =



t

f (d

j =1

j

)

因为 m 和 n 互素,则 mn 的不同除数为 d i d j , i = 1,2, L , s; j = 1,2, L , t , 共st个, 且d i 和d j 互素,

g (mn) = ∑∑ f (d i d j )
i =1 j =1 t

s

t

= ∑ f ( d i )∑ f ( d j )
i =1 j =1

s

= g ( m) g ( n) 3.78 题(陈兴) 陈兴) (未完成)


相关文章:
李凡长版 组合数学课后习题答案 习题3
李凡长版 组合数学课后习题答案 习题3_哲学_高等教育_教育专区。李凡长版 组合数学课后习题答案习题3第三章 递推关系 1. 在平面上画 n 条无限直线,每对直线都在...
组合数学习题解答
组合数学习题解答_数学_自然科学_专业资料。组合数学 组合数学 ★★★第一章:★★★ 1、用六种方法求 839647521 之后的第 999 个排列。提示:先把 999 换算成...
组合数学答案
组合数学第三章答案 25页 1财富值 组合数学课后答案 15页 2财富值 组合数学第...组合数学习题答案 26页 2财富值 组合数学第三讲 43页 免费如要投诉违规内容,请...
清华版组合数学(第二版)第三章习题答案
清华版组合数学(第二版)第三章习题答案清华版组合数学(第二版)第三章习题答案隐藏>> 组合数学第三章答案 1.解设Ai为甲与第i个朋友相遇的会议 解集,i=1,…...
组合数学习题解答
组合数学习题解答_理学_高等教育_教育专区。组合数学习题解答第一章: 1.2. 求...第三章 3.2. 求 1 到 1000 中既非完全平方又非完全立方的整数个数。 解:...
组合数学课后答案
组合数学课后答案_理学_高等教育_教育专区。 今日推荐 88份文档 2014...科目三实际道路驾驶考试注意事项 驾考新题抢先版36份文档 2015开学季 ...
组合数学课后答案
组合数学课后答案_理学_高等教育_教育专区。组合数学 第四版 第一学期 课后答案1.3 题 1.14 题 1.16 题 1.18 题 1.22 题 1.28 题 1.34 题 1.47 题...
组合数学课后答案
作业习题答案 习题二 2.1 证明:在一个至少有 2 人的小组中,总存在两个人,...分别来自第一组和第二组, 2) 如果这两个分别来自第一组和第三组,则有 ...
组合数学 课后答案
另外,每列中两个单元格的不同 位置组合有 (5)=10种,这样一列中两个同色...组合数学第三章课后习题... 25页 1下载券 组合数学1章课后习题答案... 22页...
组合数学-卢开澄-习题答案
组合数学-卢开澄-习题答案_理学_高等教育_教育专区。组合数学-卢开澄-卢华明-清华大学出版社第一章答案 第二章答案 第三章答案 第四章答案 第一章答案 1.(a) ...
更多相关标签: