第一章答案
1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )
(b) 45?5+(4+3+2+1) = 235
( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!
(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!
(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!
5. 2?5?P(8,2)+3?4?P(8,2)
6. (n+1)!-1
7. 用数学归纳法易证。 8. 41?31
9. 设 n=p 1
n 1p 2
n 2…p k
n k , 则n 2的除数个数为 ( 2p 1
+1) (2p 2
+1) …(2p k
+1).
10．1）用数学归纳法可证n 能表示成题中表达式的形式；
2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。
11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。 组合意义：
右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；
左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。
12．考虑,)1(,)1(10
1
-=-=+=+=∑∑n n
k k k n n
n
k k
k
n
x n x kC x x C 求导数后有
令x=1, 即知.210-==∑n n
k k
n n kC
13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。当第二组最大数为a k 时，
第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。故符合要求的
不同分组共有12)2()12(2111
1+-=-----=∑n k n k n k n 种。
（另解：设两组共含k 个数(k=2,3,…,n)，则分组数为
∑2≤k ≤n
C(n,k) (k-1) = n 2n-1- 2n +1 . ）
14. 3?2?2.
15. 用k 表示数的位数，用i 表示k 位数中零的个数，则0出现的次数为
.
15940945924959 )
15954910391029519()149439629419()139329319()2929(9 99
9234523452342321
621
1
11
621
1
?+?+?+?+?=??+??+??+??+??++??+??+??+??+??+??+??+?+?+==--=-=---=-=∑∑∑∑i
k i k k k i i
k i k k k i C i i C
16. C(n-1, r-1) (每盒中先放一个，再r 中取n-r(可重复)) 17. 易用P(m,n)=m!/(m-n)! 验证等式成立。
18. 5! C(8-3+1,3) （先将球作全排列，再作8中选3的不相邻组合）
19. 在n+m 位中选出n 位不相邻的位放入1，其余位放入0。故符号串个数为
.11)(n
m n n m n C C ++-+=
20. 代表团中含乙单位男同志的个数只可能是1,2,3, 故组团的方案总数为
C(15,1)C(10,2)C(10,4)+C(15,2)C(10,1)C(10,3)4+C(15,3)C(10,2)C(4,2) 21. 设??
?=次为黑球
第次为白球第i i A i ,0,1，则
.21)
3()
31()3|1(3
6
2
56
1
6
1
66
1
6=??=====
==∑∑∑C a C a A P A A P A A P i i i 且 22. (a) C(3+2,3)C(5+3,5) (b) C(3+2,3)C(4+3,4)
(c) C(3+2,3)C(3+1,3)C(2+4,2) (d) C(8+5,5)- C(3+2,3)C(4+3,4) 23．Z 取k+1时，x,y 共有k 2种取法，故第一个式子成立, k=1,2,…,n 。
另外，(x,y,z)中x 与y 相同的取法有2
1
+n C 种，x,y,z 互不相同的取法有3
12+n C 种，故第二个式子成立。
24．(a)只需确定长方形的左下角和右上角坐标即可。
在0-9中任选两不同数，小的作为左下角x 坐标，大的作为右上角x 坐标，共有2
10C 种选法；在0-5中任选两不同数，小的作为左下角y 坐标，大的作为右上角y
坐标，共有26C 种选法。故共有210C 26
C 个长方形。 (b)只需确定正方形的边长和左下角坐标即可。
边长k 的取值范围为1…5。边长为k 时，正方形左下角x 坐标可取0…9-k ，y 坐标可取0…5-k ，共有(10-k)(6-k)种选法。故正方形的个数为
.105)6)(10(5
1
=--∑=k k k
25．(a) 12
5215+-C C
(b) 3
5
315C C - 26．S 中被5整除的数有200个，不能被整除的有800个。
分两种情况：(1)a,b 中一个被5整除，另一个不能被5整除，共有200?800种取法；(2)a,b 均能被5整除，共有200?200种取法。所以，符合要求的数偶个数为
200?800+200?200=200?1000=200000.
27. (a) 5!6! (b) 5!6! (c) P(6,2) 8! 28．假设每张桌坐n 人, 则方案数为
.)!
(...)2()(k
n n n n n n n n k n n n n k n n n kn n
kn Q C Q C Q C Q C =
-- 29. P(n,r)/r. 31．因为
r
n
C r n r n =?+!
1!)!(，根据组合意义它是一个整数。 32．根据要求，x,y 的排列必须是xyxyx.将其作为一个整体与a,b,c,d,e,f 一起作排列，
共有符合要求的排列7！种。
33. 每个盒中先放入k 个球，然后作允许有重复的组合。共有C(n+(r-nk)-1, r-nk)种方案。 34．2?7！
35．由于任意四个不同顶点恰好对应一个对角线的交点，故交点共有4
10C 个。 36．若m= n 2，设n 的素因数分解为n=p 1
n 1p 2
n 2…p k
n k , 则m 的除数个数为 ( 2p 1
+1) (2p 2
+1) …(2p k
+1), 这是一个奇数。反之，若m 的除数个数是奇数，则它的素因
数分解必为m=q 1
2m 1q 2
2m 2…q k
2m k ，从而m=n 2，其中n= q 1
m 1q 2
m 2…q k
m k 。
37. 右为原点到(m, n+r+1-m)的路径数，左边分别为原点分别经线段A i B i
的路径数之
和，其中点A i
的坐标为(i, n-m),点B i
的坐标为(i, n-m+1), i =0,1,2,….,m.
38: 可看成“从a 1,a 2,…,a n+1中选r+1个不同元素作为一组，共有多少种选法”的问题。
左端：
C(n, r): 此组含a n+1，还要在a 1,a 2,…,a n 中选r 个;
C(n-1, r): 此组不含a n+1，但含a n ，还要在a 1,a 2,…,a n-1中选r-1个; C(n-2, r): 此组不含a n+1,a n ，但含a n －1，还要在a 1,a 2,…,a n-2中选r-2个; …………….
39．考虑以下组合问题：用红、蓝、黄三种颜色给m 个不同的球上色，要求涂黄色球为m-n 个，其余的球可随意涂红蓝色。
从中随意选定n 个球用于涂红色或蓝色，其余球涂黄色，因此方案总数为n n
m C 2?。 另一方面，对于任意k(0≤k ≤n)，由于恰好有k 个球涂红色且符合要求的方案有k n k m k m C C --个，故全部方案按红色球个数分组后有
.20k
n k m k m n
k n
m
n
C C C --=∑= 40．!/r P Q r n r
n =
43．易证当k+1≤ n/2时 1+≤k n k n C C ，利用k n n k n C C -=知k ≥ n/2时 1
+≥k n k n C C 。 44. (a) 编号1,2,…,n 的球每种两个，全部排列的个数；
编号1,2,…,n 的球每种三个，全部排列的个数；
(b) 编号1,2,…,n 的球每种n 个，将此n 2个球全部放入n 个无区别的盒中，要
求每盒n 个球，全部放法的方案数。 45. (a) C(n, n)+C(n, n-1)+…+C(n, 0) = 2n .
(b) C(2n+1, 0)+C(2n+1, 1)+C(2n+1, n) = 22n +1/2 = 22n .
46．(a) 设出现偶数次0的长为n 的字符串个数为a n , 则考虑末位为非0和末位为0两种情况，有递推式
a n = 2a n-1+(3n-1-a n-1) = a n-1+3n-1 =……
=3n-1+3n-1+…+3n-1+ a 1=3n-1+3n-1+…+3n-1+2=(3n +1)/2.
(b) 根据(a)得到等式右端；考虑0出现0次、2次、4次、….及所有偶数次的情形，得等式左端。
47．使用第一台和第二台机器的人数均为k 时，分配方案数为k
m k k k m C C 2223
-?，故方案总数为∑=-?]2
[02223
n
k k m k k k m C C 。
48. 这相当于求从原点出发，中途必须行走在直线y=x 及以上，最后到达点(n, n)的全部路径数 C(n+n, n)-C(n+n, n-1)。 49．C(n-k+1, k) .
50．(a) 在00000的间隔中插入1。使得01和10的总次数为4，只有两种方法：一是两头有1且中间一间隔插入余下的1；二是两头均无1且中间两处插入全部的1。 两头有1共三种情形，中间插入1有四种选择，此时共有3?4=12种方案。
两头无1时有C(4,2)种选择间隔的方法，选定后每种方法有三种安排1的办法(前1后3, 前2后2，前3后1)，此时共有C(4,2)?3=18种方案。
所以，总方案数为 12+18=30 。 (b) 在0m 的间隔中插入1。
当k 为奇数时，两头之一必为1，其余的1插入中间的(k-1)/2个空档中。先让每个空中放入一个1，再将剩余的1任意放入这(k+1)/2个空中。此时符合要求的字符串的个数为
2211
21121
1
211)21
(21211
)(222--+-
---+-
-+-++--==k m k m m k m k m k m k k m C
C
C
C
C
.
当k 为偶数时，两头必须同时为1或同时为0。
两头同时为0时，其余的1应插入中间的k/2个空档中，此时符合要求的字符串的个数为
.2121
2
1)2
(221
k m m k m k
m k m k
k m C
C
C C
-
---
--+-=
两头同时为1时，其余的1应插入中间的(k-2)/2个空档中，此时符合要求的字符串的个数为
.21
22
1
221)22
(22221
k m k m k m k m k k m C
C
C
C
---+-
-+-++--=
所以k 为偶数时符合要求的字符串的个数为
.21
221
2121
k m k m k m m k m C
C
C
C
----
--+
51. C(20-3+1, 3) 52．C(n-k+1, k) 53. C(n+n-1, n)
54.相当于从n+m 个位置中选取m 个不相邻的位置：
C(m+n-m+1, m) = C(n+1,m).
55．设m=a k …a 2a 1a 1a 2…a k , 则
.,)110(10)10
10
(11
121
∑∑==----++=?+?=k
i k
i i i k i i
k i i k i a a a m
因为.,11)1(111
)1(110
1
20
2
20
121
2121
21
2∑∑-=-=--------=
+-=+i j i j j i j j i j
i j j i i C
C
式中每项均含因子
11，故m 能被11整除。
56．(a) !)!1(!n n n Q n
n -=
(b) n
m
n n P Q 57．.)
(!
)!1()!1(r n r n r n r C r
n -=
---
58．如果交点无重叠，则四个点（的交叉连线）对应一个交点，故共有4
n C 个点。
第二章答案
返回
1．母函数为
.)1(6)1(6)1()')')'11((()(4
320
3x x
x x x x x x x x x n x f n n -+---=-==∑∞
= 2．因为∑∞
=--+=-0
11)1(1n n
k k n k
x C x ，故此数列的母函数为 .)1(1
)(4
033x x C x f n n
n -=
=∑∞
=+
3．因为1-3x-54x 2 = (1+6x)(1-9x)，设
,9161)
91)(61(783x B
x A x x x -++=-++ 解得A=－4, B = 7。故∑∞
=-?-?=0
))6(497()(n n n n x x G ，从而 a n = 7?9n －4?(-6)n 。
4．类似上题可得a n = 8n +2?(-7)n 。
5．G n -3G n-1+G n-2 = F 2n -3F 2n-2+F 2n-4 = F 2n-1+ F 2n-2 -3F 2n-2+F 2n-4
= F 2n-2+ F 2n-3 -2F 2n-2+F 2n-4= -F 2n-2+ F 2n-3 +F 2n-4= -F 2n-2+ F 2n-2 = 0.
设母函数,)(0∑∞
==n n n x G x f 则利用递推式可得
.311)(2
x
x x
x f ---=
6．母函数
.)
1()
1()'1(
)'( )12()0)12(()(2
22
21
121
1
2121
2x x x x x x x x x
n x x
n x f n n n n n n
n -+=-==-=?+-=∑∑∑∞
=-∞
=-∞
=-
7．因为2
10)1(1)'11()'()1(x x x x n n n n n
-=-==+∑∑∞
=+∞=，所以 ,)1(1
)1()(2
20
2x x n x G n n -=+=∑∞
= 从而.1)()1( ,11
)()1(222
2=--=-x G x x
x G x
8．(a) 2
211
)(x x x f n n -=
=∑∞
= (b) 2
121)(x x
x x f n n --=-=∑∞
=+ (c) x x x f n n +=-=∑∞
=11
)()(0
9．因为∑∞=--+=-011)1(1n n k k n k x C x ，故.)1(1)(3
22x x C x G n n
n -==∑∞
=+于是(a)(b)(c)均易证。 10．因为∑∞=--+=-011)1(1n n k k n k x C x ，故.)1(1)(4
033x x C x H n n
n -==∑∞
=+于是(a)(b)均易证。 11．由于,)1(1
)1(2
x x n n n -=+∑∞
=于是 ,)1(1)')1((
)')1(()1()(3
20
10
2
x x
x x x n x n x G n n n n
-+=-=+=+=∑∑∞
=+∞=
从而(1-3x+3x 2-1)G(x)=1+x 是一个多项式。
12．.)
1(111)1(1)1()(4
30
2
x x
x x x x
x
n x a x G n n
n n
n n
n -+=-?-+=
+==∑∑∑∞
=∞
=∞
= 13．.)1(4111)1(41)1()(5
2
420
03
0x x x x x x x x x n x a x G n n
n n
n n
n -++=-?-++=+==∑∑∑∞
=∞
=∞
=
14．记,21)(2
x
x x
x f --=则有 (a) p 0 = f(0) = 0 ; p 1 = f ’(0) = 1.
(b) 递推关系式为 a n －2a n-1－a n-2 = 0, n = 2, 3, …. 15．仿上题可得
(a) a 0 = f(0) = 1 ; a 1 = f ’(0) = 1.
(b) 递推关系式为 a n －a n-1＋a n-2 = 0, n = 2, 3, …. 16．略
17．因为∑∞
=--+=-0
11)1(1n n
k k n k
x C x ，故.)1(1)(2x x G -=于是(a)(b)(c)均易证。 18．(a) A ?2n +B ?4n
(b) (A+Bn)7n (c) A ?3n +B ? (-3)n (d) A ?7n +B ? (-1)n (e) (A+Bn)6n (f) A ?5n +B ? (-5)n
20.
21. a n = 2?5n +3?(-4)n ? 特征方程为(r -4)(r+5) = 0 ? 递推关系为 a n +a n-1-a n-2 = 0.
22. 设a n + x a n-1 + y a n-2 = 0 ? x= -2, y= -3 ? 递推关系为 a n -2a n-1-3a n-2 = 0.
23．由a n 的表达式可推知特征方程为(x+3)2 = 0，从而递推关系为a n +3a n-1+9a n-2 = 0。
24．解a n -2a n-1+a n-2 = 0，a 0=1,a 1=2得a n = 1+n , n=0,1,2,…。
因为1是特征方程的二重根，故设a n -2a n-1+a n-2 = 5的一个特解为t n =An 2。代入递推式可得A=5/2。
故解为 a n = 1+n+5/2n 2。
25．设,)1)(1(34)(3
x x x x
x a x f n n n -+--==∑∞
=则 .)1(34)()()(3
010x x x x xf x f x a a x b n n
n n n n n -+-=-=-=∑∑∞
=-∞= 26．因为∑∞
==0)(n n
n x a x G ，所以,))((0
100
2
∑∑∑∞
=+∞
=-===n n n n n
k n n
k k x a x a a x G 故
).( 1))((10
1
12
x G x a x
a x x G n n n n n n ∑∑∞
=∞
=++==+=+
27. (a) a n =A ?4n +5n+1
(b) a n =A ?(-6)n +5/3?3n (c) a n =A ?4n +n ?4n
(d) a n =A ?(-6)n +4n ?(-6)n
(e) a n = A ?4n +(10?5n -3n ?4n ) (f) a n = A ?4n +(7n ?4n +15?5n )
(g) a n =A ?(-6)n + (-6)n ?n(3/2+5/2?n+n 2) (h) a n =A ?4n + 4n ?n(4/3+n+1/3?n 2)
n n n n n n b b B A a )21()21( )()21(42)21(42 )()21()21( )(-++--+-++
(i) a n =A+ n(2+ n 3)
(j) a n =A ?3n +B ?4n +10?2n +13n ?3n (k) a n =A ?2n +B ?(-4)n +2n ?(-4)n -18?3n (l) a n =(A+Bn)?3n + 3n ?n 2/2
(m)对应的齐次线性常系数递推关系式的特征方程为
x 3 -7x 2+16x -12 = 0, 即(x -2)2(x -3) = 0,
故x =2(二重根), 3 (单根)，于是齐次线性常系数递推关系式的通解为A ?2n +B ?3n 。 设递推关系a n -7a n-1+16a n-2-12a n-3 =2n 的一个特解为 Cn 2?2n , 代入后比较等式两端得C=-1。
设递推关系a n -7a n-1+16a n-2-12a n-3 =3n 的一个特解为 Dn ?3n , 代入后比较等式两端得D=9。
故原递推关系式的通解为a n =A ?2n +B ?3n -n 2?2n +9n ?3n 。 (n) a n =A ?2n +n ?2n +3?3n +2?4n 。
28. 若a 2=0，则a n =0, n ≥3；若a 2≠0，则a n 与a 2同正负, n ≥3。不妨设a n >0, n ≥1。 在原递推式两边取对数，记b n =ln(a n ), 则有 b n =3b n-1+10b n-2,
解此递推关系式，得 b n = A ?5n +B ?(-2)n , 故 a n = exp(A ?5n +B ?(-2)n ) 。 29．若a 1或a 2为0，则a n =0, n ≥3；若a 1>0, a 2 < 0, 则a 3k >0, a 3k-1 < 0, a 3k-2 < 0, k=1,2,3,….；若a 1<0, a 2 > 0, 则a 2+3k >0, a 3k+1 < 0, a 3k < 0, k=0,1,2,3,….；若a 1>0, a 2 > 0, 则a k >0, k=1,2,3,…。
因此不妨设a 1>0, a 2 > 0（否则考虑b n = a n ，仍有关系b n = b n-1b n-2，求得b n 后即可得到a n ）。在原递推式两边取对数，记c n =ln(a n ), 则有 c n =c n-1+c n-2, 解此递推关系式，得
).)2
51()251(e xp(,)251()251(
n
n n n n n B A a B A c -++=-++=从而 30．在原递推式两边取对数，记b n =ln(a n ), 则有
b n =2b n-1+3b n-2, b 0=0, b 1= ln2.
解此递推关系式，得 b n = 3n ?(ln2)/4- (-1)n ? (ln2)/4, 故
a n = exp(3n ?(ln2)/4- (-1)n ? (ln2)/4) 。
31．在原递推式两边取对数，记b n =ln(a n ), 则有 b n =7b n-1-12b n-2, b 0=0, b 1= ln2.
解此递推关系式，得 b n = 4n ?ln2- 3n ? ln2, 故 a n = exp(4n ?ln2- 3n ? ln2) 。
32．(a) a n = n!
(b) a n = 6-1/2n (c) a n = A -1/2?1/3n
33．因为))251()251((5
1n
n n F --+=，而,2211n n n n F F a a -=-+- 所以
),(...)()()(...)()(212221222101211F F F F F F a a a a a a n n n n n n n n -++-+-=-++-+--+---故.)1(5
2)253(51)253(5111210n n n n n A F a a -+-+++
=+=+++ 34．因为),23(61!3)2)(1(322
3n n n n n n n ++=++=???
? ??+ 所以 .
2
3
4112341 )
2
)
1(2)12)(1(613)2)1(((61)23(6123421230n n n n A n n n n n n n A k k k a a n k n ++++=+?+++?+++=+++=∑=
35．类似上题，略。
36．(a)
.2
1
3212n )3...331(33....... )31(32)133(3)31(323 1
3)133(313312101232122121+?-=
++++-?+==+-?+-+=+-?+=-+-+=-+=-------n n n n n n n n n n n n n n n n a a a a a a
(b)
.
443
1 )4...44(4....... )44()44(4)44(4 4)44(4442121011212211）（n n n n n n n n n n n n n n
n n n n n a a a a a a -=++++==+++=++=++=+=-++-+---
37．令a n =b 2n , 则有 b n =2b n-1+3b n-2, b 0=1, b 1=2.
用特征根法求得b n = ( (-1)n +3n+1)/4，故a n = ( (-1)n +3n+1) 2/16。
38．令a n = n!b n , 则有 b n =2b n-1+7, b 0=1.
易解得 b n = 8?2n －7，从而a n = (8?2n －7) n!.
39．令na n = b n , 则有 b n =b n-1+1, b 1=1. 易解得 b n = n ，从而a 0= 5, a n = 1, n=1,2,….
40．(a) 令a n = n!b n , 则有 b n =4b n-2+5/9?3n , b 0=1 , b 1= -1.
易解得 b n = ( 2n +3?(-2)n )/4－5?3n-1，从而
a n = ( 2n +3?(-2)n )/4－5?3n-1 )n! .
(b) 令a n = n!b n , 则有 b n =9b n-2+14?2n , b 0=42 , b 1= 38.
易解得 b n = (82?3n +44?(-3)n )/3－4?2n ，从而
a n = ( (82?3n +44?(-3)n )/3－4?2n ) n! .
41．证：( a n + b 1a n-1 + b 2a n-2)－r(a n-1 + b 1a n-2 + b 2a n-3) = 5r n －r ?5r n-1 = 0,
即 a n + (b 1－r)a n-1 + (b 2－r b 1)a n-2－r b 2a n-3 = 0,
这是一个三阶齐次线性常系数递推关系，其特征多项式为
x 3 + (b 1－r)x 2 + (b 2－rb 1)x －rb 2= (x －r)(x 2+ b 1x+ b 2).
42．由题设条件立得 c n －c n-1－c n-2 = b n-1 .
记 d n ＝c n －c n-1－c n-2, 则由b n 的递推关系有d n －d n-1－d n-2 = 0，即
c n －2c n-1－c n-2+ 2c n-3+ c n-4 = 0 .
47. (1) 由(1+x)n (1+x)n = (1+x)2n ，展开后比较两边x n
的系数，得.20
n
n k n n n
k k n C C C =-=∑
(2) 由于
故x 20的系数为
48．(1+x+x 2)4(1+x+x 2+x 3)3=…+678 x 10+…
49. 设n 位排列中AB 至少出现一次的排列个数为a n , 则最后两位为AB 的排列有4n-2个；最后两位不是AB 的排列分为两种情况：最后一位不是B 的情形有3 a n-1个，最后一位是B 的情形有3a n-2个，故
a n =3 a n-1 + 3a n-2 + 4n-2， n=3,4,…. a 1=0，a 2=1。
50．这是一个可重复的排列计数问题，可以使用指数型母函数求解。
出现偶数次2的指数型母函数为∑∞
=02)!
2(n n
n x ，出现偶数次3的指数型母函数为
∑∞=02)!2(n n n x ，出现0的指数型母函数为∑∞=0!n n n x ，出现1的指数型母函数为∑∞
=0!
n n
n x 。所以总的母函数为
),12(412!)!2(2422
2
02
02++=???
? ?
?+=???? ?????
? ??-∞=∞=∑∑x
x x x
x n n n n e e e e e n x n x 故a 0=1, a n = (4n
+2
n+1
)/4, n=1,2,….
51．设n 位符号串中符合要求的排列有a n 个，则最后一位不是a 的排列有2a n-1个，最后一位是a 的排列有2a n-2个。于是 a n =2a n-1 + 2a n-2， n=3,4,….
,)()(1100)1(3
213218410032110084n n n n n n x x n n n x x ????
??? ??=++∑
=++.
!2!1!97!100!1!3!96!100!0!5!95!1001001005210032120841003213232132321∑
∑=+=++=+=++++=???? ??=???? ??n n n n n n n n n n n n n n n n
a 1=3，a 2=8。
52．证：由p.36恒等式，知 ∑∑=+=+++==m
k n
k n m
k k k
n m
m n C C
C 0
1
. 54．因为相应的母函数为
...,14 (8)
3
5
4
++=∑∑∑===x x x
x
k k k k k
k
故共有14种分配方案。
55．用数学归纳法：n=1时，n 可表示为F 1；设n=k 时，
,... 2 ,...2121m i i i i i i F F F k m <<<≤+++=其中
(i)若i 1>2, 则; (121)
1m i i i F F F F k ++++=+
(ii)若i 1=2，设p=max{k: i k =k+1, 1≤k ≤m}。当p;......1212112m p p m p p i i i p p i i i p F F F F F F F F F k +++++=++++=+++++++
当p=m 时 21+=+m F k 。
56．设n 个平面将整个空间分为D n 部分。根据p.158例54的结果，因为其它平面总与第n 平面相交于一条直线，因此第n 平面被前n-1个平面分为1+n(n-1)/2个部分，而每个部分将前n-1个平面分割得到的一个区域变为两个，故有
D n = D n-1+1+n(n-1)/2, n=2,3,….
由于D 1 =2，可推得D 0 =1.
由递推式得∑=+-+=n
k n k k D 1
1)2)1(1(，可设3
2n
n n C D C C Bn A D ?+?++=，代入n=0,1,2,3的D n 值，知A=1，B=1，C=1，D=4。
57．设a n 为符合要求的n 位二进制数的0的总个数，b n 为符合要求的n 位二进制数的个数，则a n 中尾为0的n 位二进制数的0的总个数为a n-2 + b n-2，a n 中尾不为0的n 位二进制数的0的总个数为a n-1；b n 中尾为0的n 位二进制数的个数为b n-2，b n 中尾不为0的n 位二进制数的个数为b n-1；故
a n = (a n-2 +
b n-2)+ a n-1
b n = b n-2+ b n-1 ， n=3,4,….
a 1=1,a 2=2,
b 1=2, b 2=3.
58. 设a n 为n 个盘按编号的奇偶性要求移动到目的地的移动总次数，b n 为n 个盘移动到目的地的移动总次数(不管编号的奇偶性)，则
n 为奇数时，先将上面n-1个盘移到B 柱(移动b n-1次)，然后将最后一个盘移至C 柱(移动1次)；再将B 柱上面n-3个盘移到A 柱(移动b n-3次)，而后将B 柱最上面的盘移至C 柱(移动1次)。最后根据假设，A 柱中剩下的n-3个盘按编号的奇偶性要求移动到目的地的移动总次数为a n-3，故
a n =
b n-1+1+ b n-3+1+ a n-3。
n 为偶数时，情况完全类似，只需在移动的办法中将B 与C 的地位对换即可。这时仍有a n = b n-1+1+ b n-3+1+ a n-3。
对于，按照汉诺塔问题有 b n = 2b n-1+1, b 1= 1, 可以解得 b n = 2n -1 . 于是有
a n = a n-3+(2n-1 +2n-2) ， n=4,5,….
a 1=1 ，a 2=2， a 3=5。
59．设AD=a ，则a AB 2
5
1+=。因为矩形B 1BCC 1中B 1C=a ，
,2
152511-=-+=a a B B
.25
12
15: 11+=-=a a B B C B 故
即新的矩形与原矩形相似。
60．使用数学归纳法。n=1时等式成立。设n 时等式成立，则对于n+1，有
.011101111
12111111
???? ??=???? ??++=???? ?????? ??=????
??+++-++-++n n n n n n n n n n n n n n n F F F F F F F F F F F F F F 故命题成立。
61. 设符合要求的n 位符号串的个数为a n ，则其中最后一位不是0的符号串有a n-1个，最后一位是0的符号串有a n-2个。于是
a n = a n-1+ a n-2 ， n=3,4,….
a 1=2,a 2=3。
62．设圆周上符合要求的n 个点的弦将整个圆分为a n 部分。
因为圆周上不同的四点对应一个交点（四点构成的四边形的两对角线的交点），
故从第n 点出发所作的弦新增的交点个数为3
1-n C ，从第n 点出发所作的弦被交点分
隔后共有(n-1)+31-n C 段（n-1为与其它点相连的段，每增加一个交点即增加一段），于是而每段将前n-1个点分割得到的一个区域变为两个，故有
a n = a n-1+( (n-1)+6
)
3)(2)(1(---n n n ), n=4,5,….
由于a 1 =1，可推得a 0 =1.
因为,)6)
3)(2)(1(1(11
∑=---+-+=n
k n k k k k a 可设
,4
32n n n n C E C D C C Bn A a ?+?+?++= 代入n=0,1,2,3,4的a n 值，知A=1，B=0，C=1，
D=0, E=1。
63．设符合要求的n 位二进制数的个数为a n ，则其中最后一位不是1的二进制数有
a n-1个，最后一位是1的二进制数有a n-2个。于是
a n = a n-1+ a n-2 ， n=3,4,….
a 1=2,a 2=3。
64．设符合要求的m 位排列的个数为a m ，所选的k 个文字已定、最后一位所用文字已定且符合要求的m 位排列的个数为b m ，则 a m = C(n,k)kb m 。由于最后两位文字互异时有(k-1) b m-1种排列，最后两位文字相同时有(k-1) b m-2种排列，故
b m =(k-1) b m-1+(k-1) b m-2, m=3,4,….
b 1=1, b 2=k 。
65．类似书上例题可得
S n - 6S n-1 + 15S n-2 -20 S n-3 +15 S n-4 -6 S n-5 + S n-6 =0,
对应特征方程为 (r-1)6 = 0, 故有六重根 r=1. 于是
S n =A+B ?C(n,1)+C ?C(n,2)+D ?C(n,3)+E ?C(n,4)+F ?C(n,5),
将S 1，S 2，…，S 6的值代入，解线性方程组即可确定全部待定常数。
66．用数学归纳法易证
,...3,2 ,32 ,1 ,20320131
11=-=-=???
? ??=???? ??---n a a a a n n n n n n n
其中
解以上后面部分的递推关系式，得 a n =2n －3n ，n=1,2,3,…
67．(1) 类似书上例题可得一个齐次线性常系数递推关系，其特征方程仅有一个四
重根x=1。故可设,3
2n n n C D C C Bn A S ?+?++=将S 0，S 1，S 2，S 3的值代入，得A=0，B=0，C=2，D=2.
(2) 类似书上例题可得一个齐次线性常系数递推关系，其特征方程仅有一个四
重根x=1。故可设,3
2n n n C D C C Bn A S ?+?++=将S 0，S 1，S 2，S 3的值代入，得A=0，B=3，C=5，D=2.
(3) 类似书上例题可得一个齐次线性常系数递推关系，其特征方程仅有一个五
重根x=1。故可设,4
32n n n n C E C D C C Bn A S ?+?+?++=将S 0，S 1，S 2，S 3，S 4的值代
入，得A=0，B=6，C=18，D=18，Ｅ=6.
68．根据题设a 1=2, a 2=4，且有以下递推关系：
a 2n+1= a 2n +2, a 2n+2= a 2n+1+(2n+2), n=1,2,….
故 a 2n+1＝a 2n －1+(2n+2), n=1,2,….
于是a 2n+1＝a 2n －1+(2n+2)＝(2n+2)+2n+…+4+ a 1=(n+1)(n+2), 从而a 2n = a 2n －1+2n = n(n+1)+2n=n(n+3)。 所以 a 2n =n(n+3)，a 2n+1＝(n+1)(n+2), n=1,2,….
70．(a) 此题结果有误，当l 为偶数时三角形的个数应为l (l+2)/4。
易知三边(a,b,c),0c 。因此，当边长为整
数、最大边长为l 时：
(i) 若l =2m+1时，全部三角形为
(k, i, 2m+1), 1≤ k ≤ i ≤ 2m+1, i+k ≥2m+2,
当取定k 后，i 的取值范围为max{k, 2m+2-k}≤ i ≤ 2m+1。所以当1≤ k ≤m+1时，2m+2-k ≤ i ≤ 2m+1；当k>m+1时，k ≤ i ≤ 2m+1。
故三角形的个数为 .
)1(4
1
)1(2)22)(1(2)1(2)2)(1( 2)33()22(2)2)(1()22(221
22
11+=+=++=++++=+-++++=-++∑∑++=+=l m m m m m m m m
m m m m m k m k m m k m k (ii) 若l =2m 时，全部三角形为
(k, i, 2m), 1≤ k ≤ i ≤ 2m, i+k ≥2m+1,
当取定k 后，i 的取值范围为max{k, 2m+1-k}≤ i ≤ 2m 。所以当1≤ k ≤m 时，2m+1-k ≤ i ≤ 2m ；当k>m 时，k ≤ i ≤ 2m 。
故三角形的个数为 ).
2(4
1
)1(2)1(2)1( 2)13()12(2)1()12(21
1+=+=+++=+-+++=-++∑∑+==l l m m m m m m m
m m m m m k m k m
m k m k
71．
.
][][][]
[][]
[ ][][][][ )(][][)(][]
[ )
(][][)(][]
[11
1
1
1
1
11
1
100
00
1
r r n n r r n k
k n n k k n
r
r n n
r r n
r r n n
r r
n r r n n
r r
n
r r n n
r r
n r
r
n n
r r
n
r r n n
r r n
n
n y x C
y x C
y x C
y x C y x C
r y y x C r n x y x C
n y x y x C
n y x y x y x +-+=++-+=-+-=+-=+-=-=-=-=+∑∑∑∑∑∑∑∑=
+=
+=++-+=++=
+++=+
72．这相当于从m 个不同元素中取n 个出来的组合（允许有重复），其个数为1
11--+-+=m n m n n m C C 。
73．作变换y i = x i －S i , i =1,2,…,m ，则方程变为
y 1+y 2+…+y m = n －S 1－S 2－…－S m , y i ≥0, i =1,2,…,m
记N= n －S 1－S 2－…－S m ，则当N<0时方程无整数解；当N ≥0时方程有1
1--+m N m C 个整数解。
74．(a)
,
211221************++=+====+=???
?
??++=???? ??-++???? ??+=???? ??++++???? ??+=+∑∑∑∑∑n n k n k n k n k n
k n n a k k n k k n k k n k k n k k n b a
.
12112211221100101
00+-==-=-===???
?
??+++=???? ??+++???? ??++=???? ??+++???? ??+=+∑∑∑∑∑n n k n k n k n k n
k n n b k k n k k n k k n k k n k k n b a
(b) 据(a)，递推关系为
a n = a n-1+
b n , b n = b n-1+a n-1, n ≥1.
易知a 0=1，b 1=1，从而b 0=0。设{ a n }的母函数为f(x)，{ b n }的母函数为g(x)，则有
f(x)-xf(x)-g(x)=a 0, g(x)-xg(x)-xf(x)=b 0,
解得
.)
13(1
)( ,131)(2
2+-=+--=x x x x g x x x x f (c) 容易验证b 1= F 1，a 1= F 2。下面用数学归纳法证明
b k = F 2k-1，a k = F 2k , k=1,2,3,…
k=1时命题成立。设对k=n 命题成立。对于k=n+1，根据递推关系和归纳假设，我们有
b n+1 = a n +b n = F 2n-1+ F 2n = F 2n+1，a n +1= a n +b n+1 = F 2n + F 2n+1= F 2n+2, 此时命题亦成立。
75．(a) 用数学归纳法证明：
容易验证k=2时等式成立。设F n =F k F n-k+1+ F k-1 F n-k ，当kF n =F k F n-k+1+ F k-1 F n-k =F k (F n-k + F n-k-1)+ F k-1 F n-k =F k+1 F n-k + F k F n-k-1 ， 故对k+1等式也成立。
(b) 用归纳法证明：对于任一正整数m ，有F m | F km , k=1,2,… m=1时命题显然成立，以下考虑m>1的情形。
k=1时命题显然成立。设k 时命题成立；对于k+1，据(a)有
F (k+1)m = F m F km+1+ F m-1 F km ，
根据归纳假设有F m | F km ，故F m | F (k+1)m 。
再证明另一个方向：若F n | F m , 则n | m 。
先用归纳法证明F n 与F n-1的最大公约数为1：n=2时显然；若F n 与F n-1的最大公约数为1，如果F n+1 与F n 的最大公约数a>1，则由F n+1= F n + F n-1知 a | F n-1，从而a 也是F n 与F n-1的公因数，这与F n 与F n-1的最大公约数为1的假设矛盾。
下面证明若F n | F m , 则n | m 。
显然m ≥n 。若m=n ，命题显然成立。若m>n ，据(a)有F m =F n F m-n+1+ F n-1 F m-n ，于是有 F n | F n-1 F m-n 。由于F n 与F n-1的最大公约数为1，故F n | F m-n 。
若m-n>n, 重复以上过程又有F n | F m-2n ，…。设m=kn+r, 0≤r ≤n-1，反复进行上述过程，可知r=0，即n | m 。
(c) 据(a)有
F n+m -2 = F m F n-1+ F m-1 F n-2 = F m (F n －F n-2)+ F m-1 F n-2 = F m F n －F m-2 F n-2， 即 F n+m - 2 = F m F n －F m-2 F n-2， 同理有 F n+m - 6 = F m-2 F n-2－F m-4 F n-4，
F n+m - 8 = F m-4 F n-4－F m-6 F n-6， ……………………………….
相加即得要求的结果。 (d) 先用数学归纳法证明：对于任意的m ≤n, n=1,2,…，必存在正整数k = k(m,n)，使得(F m , F n ) = F k .
m=n 时取k=m ，命题成立。以下只考虑mF n+1 = F m F n-m+1+ F m-1 F n-m ，
由此并注意到前面已证的结果(F m , F m-1) =1，有(F m , F n+1) = (F m , F n-m ) ,由归纳假设知命题成立。
再证本问题的结论。设(F m , F n ) = F k ，则存在整数a,b 使aF m +bF n = F k 。 于是由F k | F m , F k | F n ，据(b)推得k|m, k|n ，从而k|(m,n)。另外，由(m,n)|m, (m,n)|n 推得F (m,n) | F m , F (m,n) | F n ，从而F (m,n) | (F m , F n )=F k ，故(m,n)|k 。
所以 (m,n)=k ，证毕。
76．(a) f(n,k) = C(n-k+1,k) = C(n-k, k)+C(n-k, k-1) = f(n-1,k)+f(n-2, k-1),
所以递推关系为 f(n,k) = f(n-1,k)+f(n-2, k-1)。 (b) f(n,k) = C(n-k+1,k).
(c) 应为f(n,k)减去同时选中1和n 的方案个数( 即在3,4,…,n -2中选k-2个不相邻的数的方案个数)，故
g(n,k) = f(n,k) - f(n-4, k-2).
77．设a 是n+1个球中的一个。先将a 放入一个盒中，此盒记为A 。
若放入A 以外的m-1个盒的球共k 个(其余n-k 个球均放入A 盒)，则此情形共有C(n,k)S 2(k,m-1)种放法。由于k 可取m-1,m,…,n ，故
78．设从A 点到点n 的路径数为a n ，则
a n =a n-1 +a n-2， n=3,4,….
a 1=1，a 2=2。
79．k
k n C 1+-
80．由题76(c)，结果为2
1121)2()4(1---+--+---+--=-k k n k k n k k n k k n C C C C 。
81．(i) 当n=m 时：若k=n, 则 S(n,k)S(k,m)=S(n,n)S(n,n)=1；若kn ，则S(n,k)=0。故此时命题成立。
(ii) 当nn ，则S(n,k)=0。故此时命题成立。
(iii) 当n>m 时：若k ≥n, 则 S(k,m)=0；若k第三章答案
).1,(),1(21
2-=+∑-=m n S C m n S n m k k
n
返回
1．记 A i ={第i 人参加过的(有某甲参加的)会议}，i =1,2,3,4,5,6.
则甲参加的会议次数为
2．设A k 为1到500的整数中被k 整除的数的集合，则要求的数的个数为
3．每人的朋友个数为0,1,2,…,n -2或1,2,…,n -1。将一种情形看作一个盒子，一个代表看作一个球，如果一个人有k 个朋友则放此球进第k 号盒。
这是一个将n 个球放入n-1个盒中的问题，故必有一个盒中至少有两个球，即至少有两个人的朋友一样多。
4．(a) 设有n 个不同的球a 1,a 2,…,a n ，现在要从此n 个球中选k 个球出来(m ≤k ≤n)，使选出的这组球中含有a 1,a 2,…,a m ，，求共有多少种选取方案。
因为a 1,a 2,…,a m 已包含在选出的组内，其余的球只能在a m+1,a m+2,…,a n 中任选k-m 个，故共有C(n-m, k-m)=C(n-m, n-k)种选法。
另一方面，令
A i ={从a 1,a 2,…,a n 中选k 个球且结果不含a i 的方案}，i =1,2,…,m. 则符合要求的的方案数为
(b) 考虑将l 个相同的球放入n-m 个不同盒中且要求每个盒不空的方案个数。 我们可以先将每个盒放入一个球，这个就保证每个盒不空。剩下的l -(n-m)个球任意放入的方案就是符合要求的方案。得到全部方案可以用“从n-m 个不同盒中选l -(n-m)个盒(允许有重复)”的方法实现(譬如第i 号盒被选中k i 个，意为第i 号盒中放k i 个球)，这是一个允许有重复的组合的问题，所以方案个数为
C((n-m)+( l -(n-m))-1，l -(n-m)) = C( l -1，l -(n-m)) = C( l -1，(n-m)-1) . 另一方面，设A i 表示将l 个相同的球放入n-m 个不同盒中且要求第i 盒为空的方案的集合，i =1,2,…,n -m ， 则将l 个相同的球放入n-m 个不同盒中且要求每个盒不空的方案个数为
.335123466125||6
65646362661
=+?-?+?-?+?-?=+=C C C C C A i i .2943310550015500 |
||| ||75353753=-=??
????-??????=??-?=??A A A A A A A A k
i n i m i m
i k i n i m i m i k n m i i m i i C C C C C A S A -=--===∑
∑-=--=-=01111)1( )1( |||| ||
.
)1( )1( |
...||| |...|1)(0
1
)(1
11)(2121l
l i m n m n i i m n i l l i m n m
n i i m n i l l m n m n m n C C C C C A A A S A A A -+---=--+---=---+---∑∑-=--=???-=???
所以命题中等式成立。
5．每列(a i ,b i ,c i )T 中三数必有两数相同，i =1,2,…,7。若(a i ,b i ,c i )T 中a i =b i ，则说此列属于第一类；若a i =c i ，则说此列属于第二类；若b i =c i ，则说此列属于第三类。 视一类为一个盒子，一列为一个球，则7个球放入3个盒中必有一个盒中至少有两个球。即此7列必有两列属于同一类，此即命题中三个等式之一必然成立。
6．将正方形四等分：
将五个点放入大正方形内部，则必有一个小正方形中至少含两点，且此两点必不21/2/2，故命题成立。
7．将等边三角形四等分：
将五个点放入大等边三角形内部，则必有一个小等边三角形中至少含两点，且此两点必不在同一条边的两端上。由于小等边三角形的边长为1/2，故命题成立。
8．此11个整数中必有两个数的个位相同，因此它们的差是10的倍数。
9．设这五部分为P 1,P 2,P 3,P 4,P 5，且题目中的结论对它们均不成立。下面将导出一个矛盾。
由鸽巢原理，必有一部分至少含[325/5]+1=66个数，不妨设P 1含a 1由于c 1,c 2,...,c 16均在[1, 326]范围内，故应在P 3,P 4,P 5中。由鸽巢原理，这三部分之一至少含[15/3]+1=6个数，不妨设P 3含c 1由于d 1,d 2,…,d 5均在[1, 326]范围内，故应在P 4,P 5中。由鸽巢原理，这二部分之一至少含[4/2]+1=3个数，不妨设P 4含d 1由于e 1,e 2均在[1, 326]范围内，故应在P 5中。
记f= e 2－e 1，则f 在[1, 326]范围内，与前面类似可证f ?P i ，i =1,2,3,4,5，这与包括了P 1,P 2,P 3,P 4,P 5内全部数的假设矛盾。
10．这是一个有禁区的棋盘布局问题：
(1) 计算r 0, r 1, r 2, r 3:
直接计算右边棋盘的棋盘多项式为 1+4x+4x 2+x 3, 故安排方案个数为 3! - 4?2! + 4?1! -1 = 1 . 11．如果有一种放法使得每个盒中的球数互异，设各盒中的球数由小到大排列后为：
n 1 < n 2 <…< n m ,
则n ≥ n 1 + n 2 +…+ n m ≥ 0+1+2+…+(m -1) = m(m-1)/2, 矛盾。
12．|L ?M ?E| = |L ?M ?E|-(|L|+|M|+|E|-|L ?M|-|L ?E|-|M ?E|)
=120-(92+65+75) +(54+65+45)=…
13．(a) 由于|||| |)()(| |)(| ||A B A B A B A B A A B B ?+?=???=??=，即知命题成立。
(b)据(a)知
.|||)(||)(| || |
)()(| || |
)(| || |)(| ||C B A C B C A C C B C A C C B A C C B A C B A ??+?-?-=???-=??-=??=??
14．设A k 为1到1000的整数中被k 整除的数的集合，则要求的数的个数为
15．设A k 为1到120的整数中被k 整除的数的集合(k=2,3,5,7)，则广义容斥原理中
α0 =120，
α1 = |A 2|+|A 3|+|A 5|+|A 7|=60+40+24+17=141，
α2 = |A 2 ? A 3| |+| A 2?A 5|+| A 2?A 7|+|A 3?A 5|+| A 3?A 7|+|A 5?A 7| = 20+12+8+8+5+3=56，
α3 = |A 2 ? A 3?A 5| +| A 2 ? A 3?A 7|+| A 2 ? A 5?A 7|+|A 3?A 5?A 7| = 4+2+1+1=8，
α4 = |A 2 ? A 3?A 5?A 7| = 0 。
因为1到120的整数中被2，3，5，7中m 个数整除的数的个数为βm ，由于 故
.22994766333 ) 1051000 211000 151000 (31000 ) |||||| (|| |
)(||| |)(| ||753735337533753753=+--=?
?
???-??????+??????-??????=??-?+?-=??-=??=??A A A A A A A A A A A A A A A A A A .
4,3,2,1,0 , α)1(β40
=-=++-=∑i C i m i
i m m
i i m
β0 = α0-α1+α2-α3+α4 =120-141+56-8+0 = 27， β1 = α1-2α2+3α3-4α4 = 141-2?56+3?8-4?0 = 49， β2 = α2-3α3+6α4 =56-3?8+0 = 32， β3 = α3-4α4 = 8-0 = 8， β4 = α4= 0 。
16．记 A 1={n: 1040被正整数n 整除}，A 2={n: 2030被正整数n 整除}，则要求的数的个数为
|A 1? A 2| = |A 1 | +|A 2 | －|A 1 ? A 2| = 412+61?31 - 61?41 = 1071.
17．记 A 1={n: 1060被正整数n 整除}，A 2={n: 2050被正整数n 整除}，A 3={n: 3040被正整数n 整除}，则要求的数的个数为
|A 1? A 2? A 3| = (612+101?51+413) - (61?51+412+412)+ 412 = 73001.
18．(a) 记 A 1={n 2：1≤ n 2 ≤104}，A 2={ n 3：1≤ n 3 ≤104}，则要求的数的个数为
.
98834211010 ]
10
[]10
[1010 |||||||| |
||| ||246
/43
/42
4
21212121=+--=+--=?+--=?-=?A A A A S A A S A A
(b) 记 A 1={n 2：103≤ n 2 ≤104}，A 2={ n 3：103≤ n 3 ≤104}，则要求的数的个数为
.
99211116910 |||||||| |
||| ||421212121=+--=?+--=?-=?A A A A S A A S A A
19．
20．(a) 记 A a ={三个a 在一起的全部排列}，A b ={三个b 在一起的全部排列}，A c ={三
个c 在一起的全部排列}，则要求的排列的个数为
.1314!3!
3!1!1!
53!3!3!1!73!3!3!3!9 |||||||||||||||| |
||| ||=-?+?-=
??-?+?+?+---=??-=??c b a c b c a b a c b a c b a c b a A A A A A A A A A A A A S A A A S A A A (b)
21．
.
49555004002001) 42000 1( |||| ||100441004=-=???
???-??????+=?-=?A A A A A .
43 )011( |||| ||2
7374122
4)24()38(11314)14()48(1124482121C C C C C C C C A A S A A ?-?-=-??+??-=?-=?--+-+--+-++
吉林大学离散数学课后习题答案
第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每
一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故
G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G
(完整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个相同种类的水果。
最新组合数学习题解答
第一章： 1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。 解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？ 解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。 1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有10 ! 10 种方式。 两人坐在一起的方式数为9 ! 92? ,故两人不坐在一起的方式数为：9！-2*8！。 1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？ 解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求： x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=??? ? ??-+=515456 (2)分为求： x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35 x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20 x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10 x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4 x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1 将它们相加即得， F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。 第二章： 2.3. 在边长为1的正三角形内任意放置5个点，则其中至少有两个点的距离≤1/2。 解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离≤1/2。 1/2 1/2 1/2
组合数学课后答案
作业习题答案 习题二 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个点。
组合数学课后标准答案
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有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.题1 (方法对比，二星) 题面：(1)有5个插班生要分配给3所学校，每校至少分到一个，有多少种不同的分配方法？ (2)有5个数学竞赛名额要分配给3所学校，每校至少分到一个名额，有多少种不同的名额分配方法？ 解析：“名额无差别”——相同元素问题 (法1)每所学校各分一个名额后，还有2个名额待分配， 可将名额分给2所学校、1所学校，共两类： 2 1 33C C +(种) (法2——挡板法) 相邻名额间共4个空隙，插入2个挡板，共： 246C =(种) 注意：“挡板法”可用于解决待分配的元素无差别，且每 个位置至少分配一个元素的问题.(位置有差别，元素无差别) 同类题一 题面： 有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？ 答案：6 9C 详解： 因为10个名额没有差别，把它们排成一排。相邻名额之间形成9个空隙。在9个空档中选6个位置插个隔板，可把名额分成7份，对应地分给7个班级，每一种插板 方法对应一种分法共有69C 种分法。 同类题二 题面： 求方程X+Y+Z=10的正整数解的个数。 答案：36. 详解： 将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x 、y 、z 之值, 故解的个数为C 92=36（个）。 2.题2 (插空法，三星) 题面：某展室有9个展台，现有3件展品需要展出，要 求每件展品独自占用1个展台，并且3件展品所选用的展台既不在两端又不相邻，则不同的展出方法有______种；如果进一步要求3件展品所选用的展台之间间隔不超过两个展位，则不同的展出方法有____种. 答案：60，48 同类题一 题面： 6男4女站成一排，任何2名女生都不相邻有多少种排法？ 答案：A 66·A 47种. 详解： 任何2名女生都不相邻，则把女生插空，所以先排男生再让女生插到男生的空中，共有A 6 6·A 4 7种不同排法． 同类题二 题面： 有6个座位连成一排，现有3人就坐，则恰有两个空座位相邻的不同坐法有( ) A ．36种 B ．48种 C ．72种 D ．96种 答案：C. 详解：恰有两个空座位相邻，相当于两个空位与第三个 空位不相邻，先排三个人，然后插空，从而共A 33A 2 4＝72种排法，故选C. 3．题3 (插空法，三星) 题面：5个男生到一排12个座位上就座，两个之间至少隔一个空位． 1]没有坐人的7个位子先摆好， [2](法1——插空)每个男生占一个位子，插入7个位子所成的8个空当中，有： 58A =6720种排法. (法2)[1]5个男生先排好：55A ； [2]每个男生加上相邻的一个座位，共去掉9个位置，当作5个排好的元素，
组合数学题目及标准答案
组合数学 例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
李凡长版-组合数学课后习题答案-习题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
中国人民大学出版社第四版高等数学一第6章课后习题详解
高等数学一第6章课后习题详解 课后习题全解 习题6-2 ★ 1．求由曲线 x y =与直线 x y =所围图形的面积。 知识点：平面图形的面积 思路：由于所围图形无论表达为X-型还是Y-型，解法都较简单，所以选其一做即可 解： 见图6-2-1 ∵所围区域D 表达为X-型：?? ?<<<∵所围区域D 表达为X-型：?????<<< <1 sin 2 0y x x π， （或D 表达为Y-型：???<<<∴所围区域D 表达为Y-型：?? ?-<<<<-2 2 422y x y y ， ∴23 16 )32 4()4(2 2 32 222= -=--=- - ? y y dy y y S D （由于图形关于X 轴对称，所以也可以解为： 2316 )324(2)4(22 32 22=-=--=? y y dy y y S D ） ★★4．求由曲线 2x y =、24x y =、及直线1=y 所围图形的面积 知识点：平面图形面积 思路：所围图形关于Y 轴对称，而且在第一象限内的图形表达为Y-型时，解法较简单 解：见图6-2-4 ∵第一象限所围区域1D 表达为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个相同种类的水果。
最新同济大学第六版高等数学上下册课后习题答案7-5
同济大学第六版高等数学上下册课后习题 答案7-5
仅供学习与交流，如有侵权请联系网站删除 谢谢4 习题7-5 1. 求过点(3, 0, -1)且与平面3x -7y +5z -12=0平行的平面方程. 解 所求平面的法线向量为n =(3, -7, 5), 所求平面的方程为 3(x -3)-7(y -0)+5(z +1)=0, 即3x -7y +5z -4=0. 2. 求过点M 0(2, 9, -6)且与连接坐标原点及点M 0的线段OM 0垂直的平面方程. 解 所求平面的法线向量为n =(2, 9, -6), 所求平面的方程为 2(x -2)+9(y -9)-6(z -6)=0, 即2x +9y -6z -121=0. 3. 求过(1, 1, -1)、(-2, -2, 2)、(1, -1, 2)三点的平面方程. 解 n 1=(1, -1, 2)-(1, 1, -1)=(0, -2, 3), n 1=(1, -1, 2)-(-2, -2, 2)=(3, 1, 0), 所求平面的法线向量为 k j i k j i n n n 6930 1332021++-=-=?=, 所求平面的方程为 -3(x -1)+9(y -1)+6(z +1)=0, 即x -3y -2z =0. 4. 指出下列各平面的特殊位置, 并画出各平面: (1)x =0; 解 x =0是yOz 平面. (2)3y -1=0; 解 3y -1=0是垂直于y 轴的平面, 它通过y 轴上的点)0 ,3 1 ,0(. (3)2x -3y -6=0;
仅供学习与交流，如有侵权请联系网站删除 谢谢4 解 2x -3y -6=0是平行于z 轴的平面, 它在x 轴、y 轴上的截距分别是3和-2. (4)03=-y x ; 解 03=-y x 是通过z 轴的平面, 它在xOy 面上的投影的斜率为3 3. (5)y +z =1; 解 y +z =1是平行于x 轴的平面, 它在y 轴、z 轴上的截距均为1. (6)x -2z =0; 解 x -2z =0是通过y 轴的平面. (7)6x +5-z =0. 解 6x +5-z =0是通过原点的平面. 5. 求平面2x -2y +z +5=0与各坐标面的夹角的余弦. 解 此平面的法线向量为n =(2, -2, 1). 此平面与yOz 面的夹角的余弦为 3 21)2(22||||) ,cos(cos 122^=+-+=??==i n i n i n α; 此平面与zOx 面的夹角的余弦为 3 21)2(22||||) ,cos(cos 122^-=+-+-=??==j n j n j n β; 此平面与xOy 面的夹角的余弦为 3 11)2(21||||) ,cos(cos 122^=+-+=??==k n k n k n γ.
李凡长版组合数学课后习题标准答案习题
第二章 容斥原理与鸽巢原理 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.
李凡长版 组合数学课后习题答案习题4
第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?? ???=41(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=（2 11x -）2 . （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ????????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1) x x -=0k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= ()1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得
组合数学参考答案(卢开澄第四版) - 修改版
1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？ 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！ n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１ 1.7题 试证：)2()2)(1(n n n ++被2n 除尽。 证明：因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。
