概要信息：

第一章： 
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
!9
2 ,故两人不坐在一起的方式数为：9！-2*8！。 
 
1.14. 求 1 到 10000 中，有多少正数，它的数字之和等于 5？又有多少数字之和小于 5 的整
数？ 
解：(1)在 1 到 9999 中考虑，不是 4 位数的整数前面补足 0， 
例如 235 写成 0235,则问题就变为求： 
x1+x2+x3+x4=5 的非负整数解的个数，故有 
F（4，5） 




 

5
154
56 
(2)分为求： 
x1+x2+x3+x4=4       的非负整数解，其个数为 F（4，4）=35 
x1+x2+x3+x4=3       的非负整数解，其个数为 F（4，3）=20 
x1+x2+x3+x4=2       的非负整数解，其个数为 F（4，2）=10 
x1+x2+x3+x4=1       的非负整数解，其个数为 F（4，1）=4 
x1+x2+x3+x4=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.5. 在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。 
 
解：每列着色的方式只可能有2 2 4  种，现有5列，由鸽笼原理知，至少有二列着色方式
相同。   
 
2.7. 一个学生打算用 37 天总共 60 学时自学一本书，他计划每天至少自学 1 学时，证明：无
论他怎样按排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为 13 学
时。 
解：设
1a 是第一天自学的时数，
2a 是第一，二天自学的时数的和，
ja 是第一，二，… ，
第 j 天自学时数的和， 1,2, ,37j    
于是，序列
1 2 37, , ,a a a 是严格递增序列(每天至少一学时)，而且，
1 371, 60a a    
于是序列
1 3713, , 13a a   也是严格递增的序列，故
37 13 73a    
因此 74 个数
1 37 1 37, , 13, , 13 73a a a a     都在 1 和 73 两个整数之间，由鸽笼原理
知，这 74 个数中必有两个是相等的，由于
1 2 37, , ,a a a 中任何两数都不相等，故
1 3713, , 13a a   中任何两个数也是不相等的，因此，一定存在两个数 ,i j 使得 
13 13i j i ja a a a      
因此，在 1, 2, ,j j i   这些天中，这个学生自学总时数恰好为 13。   
 
2.10. 证明：在任意 52 个整数中，必存在两个数，其和或差能被 100 整除。 
证明：设 52 个整数 a1，a2，….，a52 被 100 除的余数分别为 r1，r2，….， 
r52,而任意一整数被 100 除可能的余数为 0，1，2，….,99，共 100 个，它可分为 51 个类：{0}，
{1，99}，{2，98}，…..{49，51}，{50}。因此，将 51 个类看做鸽子笼，则由鸽笼原理知，
将 r1，r2，….，r52  个鸽子放入 51 个笼中，，至少有两个属于同一类，例如 ri,rj,于是 ri=rj 
或 ri+rj=100,这就是说 ai—aj  可 100 整除，或 ai + aj  可被 100 整除。 
 
第三章 
3.2. 求 1 到 1000 中既非完全平方又非完全立方的整数个数。 
解：设 S ＝{1,2,…,1000}; 1A 表示 1 到 1000 中完全平方数的集合，则 1A 表示 1 到 1000
中不是完全平方数的集合； 2A 表示 1 到 1000 中完全立方数的集合，则 2A 表示 1 到 1000
中不是完全立方数的集合。 
故
__
2
__
1 AA  表示 1到 1000中既非完全平方又非完全立方的整数的集合，由容斥原理（（3.5）
式）知： 
212121 AAAASAA         (3.5) 
其中 
|| S ＝1000， 
1| | 1000 31A   
  , 
3
2| | 1000 10A   
   
21 AA  表示 1 到 1000 中既是完全平方又是完全立方的数的集合，故 
21 AA  =
6 1000 
  =3, 
将以上数值代入(3.5)式得 
21 AA  ＝1000－(31+10)+3=962  
故 1 到 1000 中既非完全平方又非完全立方的整数个数为 962。   
 
3.8. 在所有的 n 位数中，包含数字 3，8，9 但不包含数字 0，4 的数有多少？ 
解：除去 0，4，则在 1，2，3，5，6，7，8，9 这 8 个数字组成的 n 位数中， 
令 S 表示由这 8 个数字组成的所有 n 位数的集合。则|S|=8
n
. 
P1 表示这样的性质：一个 n 位数不包含 3； 
P2 表示这样的性质：一个 n 位数不包含 8； 
P3 表示这样的性质：一个 n 位数不包含 9； 
并令 Ai表示 S 中具有性质 Pi的元素构成的集合（i=1,2,3）。 
则 AAA 321
 表示 S 中包含 3，又包含 8，又包含 9 的所有 n 位数的集合。 
由容斥原理（（3.5）式）得 
 | 321 AAA  |= |||||||| 321
3
1
AAAAAAS
ji
ji
i
i   

     （3.5） 
而 
777 321
,,
nnn
AAA   
666 323121
,,
nnn
AAAAAA    
5321
n
AAA  ， 
代入（3.5）式得 
1 2 3 8 3 7 3 6 5n n n nA A A          
故所求的 n 位数有
nnnn 563738  个。 
 
3.10. 求重集  3 ,4 ,5B a b c    的 10-组合数。 
解：构造集合 B′= },,{ cba  。令集合 B′的所有 10-组合构成的集合为 S。由
第一章的重复组合公式(1.11)有 
|| S ＝F（3，10）＝ 




 
10
1103
=66。 
令 p1 表示 S 中的元素至少含有 4 个 a 这一性质，令 p2表示 S 中的元素至少含有 5 个 b
这一性质，令 p3表示 S 中的元素至少含有 6个 c 这一性质，并令 Ai(i=1,2,3)表示 S中具有
性质 pi(i=1,2,3)的元素所构成的集合，于是 B 的 10-组合数就是 S 中不具有性质 p1,p2,p3的
元素个数。由容斥原理（（3.5）式）有： 
| 321 AAA  |= |||||||| 321
3
1
AAAAAAS
ji
ji
i
i   

        (3.5) 
由于已经求得 || S =66，下面分别计算(3.9)式右端其他的项。 
由于 A1中的每一个 10-组合至少含有 4个 a，故将每一个这样的组合去掉 4个 a就得到
集合 B′的一个 6-组合。反之，如果取 B′的一个 6-组合并加 4 个 a 进去，就得到了 A1的
一个 10-组合。于是 A1的 10-组合数就等于 B′的 6-组合数。故有 
  || 1A =F（3，6）＝ 




 
6
163
＝28 
同样的分析可得 
|| 2A =F（3，5）＝ 




 
5
153
＝21 
|| 3A =F（3，4）＝ 




 
4
143
＝15 
用类似的分析方法可分别求得 
|| 21 AA  ＝F（3，1）＝ 




 
1
113
＝3 
|| 31 AA  ＝F（3，0）＝ 




 
0
103
＝1 
|| 32 AA  ＝0（因为 5＋6＝11>10） 
|| 321 AAA  ＝0 （同上） 
将以上数值代人(3.9)式得到： 
| 321 AAA  |＝66－（28＋21＋15）＋（3＋1＋0）－0 
＝6 
故所求的 10-组合数为 6。   
 
3.14. 求由数字 1，2， 8 所组成的全排列中，恰有 4 个数字在其自然位置上的全排列个
数。 
解：4 个数在其自然位置共有 





4
8
种方式，对某一种方式，均有 4 个数字不在其自然位置，
这正好是一个错排，其方式数为
4D （见定理 3.2），由乘法规则有，恰有 4 个数字在其自然
位置上的全排列数为 
4
8
4
D
 
 
 
＝630。   
 
 
第四章 
4.6   求重集 }7,5,3,{ dcbaB  的 10-组合数。 
解：设重集 B 的 n-组合数为 na ，则序列{ na }的普通母函数为 
2 2 3 2 3 4 5( ) (1 )(1 )(1 )f x x x x x x x x x x x             
        
2 3 4 5 6 7(1 )x x x x x x x         
  =
x
x
x
x
x
x
x 








 1
1
1
1
1
1
1
1 864
 
  =(1-x
4
-x
6
-x
8
+x
10
+x
12
+x
14
-x
18
)







 
0 3
3
k
kx
k
 
 所以 a10= 




 





 





 





 





 
3
03
3
23
3
43
3
63
3
103
 
     =286-84-35-10+1=158 
故重集 B 的 10－组合数为 158。 
4.9. 设重集  1 2 3 4 5 6, , , , ,B b b b b b b            ,并设 ra 是B 满足以下条件的 r-组合数，
求序列  0 1, , , ,ra a a  的普通母函数。 
a. 每个 Ib  出现 3 的倍数次。  1,2,3,4,5,6I   
b. 
1b ,
2b 至多出现 1 次，
3 4,b b 至少出现 2 次，
5 6,b b 最多出现 4 次。 
c. 
1b 出现偶数次，
6b 出现奇数次，
3b 出现 3 的倍数次，
4b 出现 5 的倍数次。 
d. 每个
Ib  1,2,3,4,5,6I  至多出现 8 次。 
解： 
a. 
3 6 9 6( ) (1 )f x x x x     3
0
(6, )( )k
k
F k x


  
b. 
2 2 3 4 2 2 3 4 2( ) (1 ) ( ) (1 )f x x x x x x x x x          
c. 
2 4 3 5 3 6 9 5 10( ) (1 )( )(1 )(1 )f x x x x x x x x x x x                  
       (1 x x x 2 3 2+ + + + )  
d. 
2 3 8 6( ) (1 )f x x x x      
 
4.10  有两颗骰子，每个骰子六个面上刻有 1，2，3，4，5，6 个点。问掷骰子后，点数之
和为 r ，两颗骰子的点数有多少种搭配方式？ 
解：每个骰子是不同的，但讨论点数之和的时候不考虑顺序，故该问题是组合问题。设
有满足条件的搭配方式有 ra 种，则其普通母函数为 
    
2 6 2( ) ( )f x x x x     
   其中
rx 的系数 ra 即为所求的搭配方式数。 
 
4.14  求由数字 2，3，4，5，6，7 组成的 r 位数中，3 和 5 都出现偶数次，2 和 4 至少出现
一次的 r 位数的个数。 
解：这是一个排列问题。设满足条件的 r 位数的个数为
ra ，则序列 1 2( , , , , )ra a a  对
应的指数母函数为： 
2 4 2 2 3
2 2 2( ) (1 ...) ( ...) (1 ...)
2! 4! 2! 2! 3!e
x x x x x
x x xf            
2 2 2
2
1
( ) ( 1)
2
x x x xe e e e  
         
= 1
!
)2233443526(
4
1
1


r
r
rrrrr
r
x
 
所以， 







0),2233443526(
4
1
0,0
r
r
a rrrrrr  
 
5.2. 如果用 an 表示没有两个 0 相邻的 n 位三元序列（即由 0，1，2 组成的序列）的个数。
求 an 所满足的递归关系并解之。  
解：对 n 位三元序列的第一位数有三种选择方式: 
1)第一位选 1，则在剩下的 n-1 位数中无两个 0 相邻的个数为 an-1; 
2)第一位选 2，则在剩下的 n-1 位数中无两个 0 相邻的个数为 an-1;  
 3)第一位选 0,则在第二位又有两种选择方式： 
     (1)第二位选 1，则在剩下的 n-2 位数中无两个 0 相邻的个数为 an-2； 
     (2)第二位选 2，则在剩下的 n-2 位数中无两个 0 相邻的个数为 an-2 
显然有  
a1=3,a2=8 
∴ 由加法规则得 an 所满足的递归关系为： 




 
8,3
)3(22
21
21
aa
naaa nnn
 
其特征方程为  
x
2
-2x-2=0 
∴ 特征根为  
x1=1+ 3 ,x2=1- 3  
由定理 5.3知其通解为 
a n=c1 (1+ 3 )
n
+c 2(1- 3 )
n  
由初始条件有  
     





8)31()31(
3)31()31(
2
2
2
1
21
cc
cc
   
解以上方程组得       
6
323
1

c  ，
6
323
2

c  
∴      



 
nn
na 3132331323
6
1
     
 
 
5.4.  某人有 n 元钱，她每天要去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱
的蔬菜，或者买两元钱的猪肉，或者买两元钱的鱼。问，她有多少种不同的方式花完这 n
元钱? 
解：设花完这 n 元钱的方式有 an种，则第一次花钱可分为下面几种情况： 
   1)若第一次买一元钱的菜，则花完剩下的 n-1 元钱就有 a n - 1 种方式，  
   2)若第一次买二元钱的肉，则花完剩下的 n-2 元钱就有 a n - 2 种方式，  
   3)若第一次买二元钱的鱼，则花完剩下的 n-2 元钱就有 a n - 2 种方式，  
显然有 a1=1， a 2=3.    
由加法规则 ,得递归关系如下：  
   




 
3 , 1
)3(2
21
21
aa
naaa nnn
 
其特征方程为：  
.022  xx  
特征根  
2,1 21  xx .  
通解   
nn
n cca 2)1( 21  .  
由初始条件得  





32)1(
12)1(
2
2
2
1
21
cc
cc
 
解得  
3
2
,
3
1
21  cc .  
故该递归关系的解为  
3
2
2)1(
3
1
 nn
na   
 故她有
3
2
2)1(
3
1
 nn 种不同的方式花完这 n 元钱。 
 
5.6．求解下列递归关系 
a．




 
1 , 0
)2(    396
10
21
aa
naaa nnn
 
解：这是一个常系数线性非齐次递归关系式，其导出的齐次递归关系为： 
*
2
*
1
* 96   nnn aaa  
∴其特征方程为 
0962  xx ，  
解得 
 321  qq  
由定理 5.3知，所导出的齐次线性递归关系的通解为 
   nn ncca 3- · 21
*   
由于 f(n) =3, 且 1不是式递归关系式的特征根，故设特解为 
Aan   
将 Aan  代入递归关系得 
396  AAA  
∴            
16
3
A  
由定理 5.6知，递归关系式的通解为 
                 n
21
* (-3) 
16
3
nccaaan   
将初值条件代入上式并解得 








12
1
16
3
2
1
c
c
 
故            
n(-3) 
12
1
16
3
16
3






 nan
。 
b．




 
1 , 0
)2(    365
10
2
21
aa
nnaaa nnn  
解：这也是一个常系数线性非齐次递归关系式，其导出的齐次递归关系的特征方程
为  
0652  xx  
∴特征根为  
3,2 21  xx  
由定理 5.3知，所导出的齐次线性递归关系的通解为 
nn
n cca )3()2( 21 
 
由于 f(n) =3n
2 ,且 1不是递归关系式的特征根，故设特解为 
21
2
0 AnAnAan   
将上式代入递归关系式解得  
     
288
115
,
24
17
,
4
1
210  AAA  
∴通解  
288
115
24
17
4
1
)3()2( 2
21   nnccaaa nn
nnn  
由初始条件有  
 







1
288
115
24
17
4
1
32
0
288
115
21
21
cc
cc
  
解得  
32
37
,
9
14
21 

 cc  
故递归关系的解为：  
288
115
24
17
4
1
)3(
32
37
)2(
9
14 2 

  nnaaa nn
nnn    
c .
1 2
0 1
7 10 3 ( 2)
0, 1
n
n n na a a n
a a
 
    

 
 
解：对应齐次递归关系的特征方程为  
x
2
-7x+10=0 
其特征根  
x1=5,x2=2 
∴  
*
1 25 2n n
na c c   
又 f(n)=3
n
, 且 3不是递归关系式的特征根，故设特解为 3n
na A  ，将  3n
na A 
代入原递归关系得  
1 23 7 3 10 3 3n n n nA A A        
解得  
A= 9
2
  
∴通解为  
*
1 2
9
5 2 3
2
n n n
n n na a a c c      
由初始条件有  
9
1 2 2
9
1 2 2
0
5 2 3 1
c c
c c
  

   
 
解出  
c1=11/6,c 2=8/3 
故原递归关系的解为：  
nnn
na 3
2
9
2
3
8
5
6
11
   
 
d.
1 2
0 1
5 6 42 4 ( 2)
0, 1
n
n n na a a n
a a
 
      

 
 
解：对应齐次递归关系的特征方程为  
x
2
+5x+6=0 
解得  
x1=-2,x 2=-3。  
齐次递归关系的通解为：  
nn
n cca )3()2( 21 
 
又 f(n)=42
n4 , 且 4不是递归关系式的特征根，故设特解为   
n
n Aa 4 ,  
将
n
n Aa 4 代入递归关系得  
A4
n
+5A4
n - 1
+6A4
n - 2
=42×4
n  
解得  
A=16,  
故通解为  
a n=a  na*
c1(－ 2)
n
+c2 (－ 3)
n
+16×4
n
 
由初始条件有  
1 2
1 2
16 0
2 3 64 1
c c
c c
  

   
 
解得  
c1=－ 111,c2=95 
所以有  
a n=－ 111×(－ 2)
n
+95× (－ 3)
n
+16×4
n  
e.
1 2
0 1
5 6 3 2 ( 2)
0, 1
n
n n na a a n
a a
 
     

 
 
解：对应齐次递归关系的特征方程为  
x
2
-5x+6=0 
解得  
x1=2,x2=3。  
故齐次递归关系的通解为：  
nn
n cca 32 21 
 
又 f(n)=3
n2 , 且 2是递归关系式的 1重特征根，故设特解为   
n
n BAna 2)(
__
  
代入递归关系求得  
A=－ 6 
从而通解为  
a n=a  na*
c12
n
+c23
n
-6n2
n  
由初始条件有  
1 2
1 2
0
2 3 12 1
c c
c c
 

  
 
解得  
c1=-13,c 2=13 
所以有  
a n=-13×2
n
+13×3
n－ 6n×2
n