新婚祝贺词-孤独的牧羊人歌词

第一章：
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 个人围圆就坐共有
两人坐在一起的方式数为
2
10!
种方式。
10
9!
,故两人不坐在一起的方式数为：9！-2*8！。
9

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）




45 1




56
5

(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个点，则其中至少有两个点的距离

12。
解： 将边为1的正三角形分成边是为12的四个小正三角形，将5个点放入四个小正三角形
中，由鸽笼原理知 ，至少有一个小正三角形中放有2个点，而这两点的距离

12。
12


12 12

2.5. 在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。

解：每列着色的方式只可能有
224
种，现有
5
列， 由鸽笼原理知，至少有二列着色方式
相同。 

2.7. 一个学生打算用37 天总共60学时自学一本书，他计划每天至少自学1学时，证明：无
论他怎样按排自学时间表，必然存在 相继的若干天，在这些天内其自学总时数恰好为13学
时。
解：设
a
1是第一天自学的时数，
a
2
是第一，二天自学的时数的和，
a
j
是第一，二，… ，
第
j
天自学时数的和，
j1,2,,37

于是，序列
a
1
,a
2
,,a
37
是严格递增序列(每天至少一学时)，而且，
a
1
1,a
37
6 0

于是序列
a
1
13,,a
37
13
也是严格递增的序列，故
a
37
1373

因 此74个数
a
1
,a
37
,a
1
1 3,,a
37
1373
都在1和73两个整数之间，由鸽笼原理知，这74个数中必有两个是相等的，由于
a
1
,a
2
, ,a
37
中任何两数都不相等，故
中任何两个数也是不相等的，因此，一定存在 两个数
i,j
使得
a
1
13,,a
37< br>13
a
i
a
j
13a
i
a
j
13

因此，在
j1,j2,,i
这些天中 ，这个学生自学总时数恰好为13。 

2.10. 证明：在任意52个整数中，必存在两个数，其和或差能被100整除。
证明：设52个整数a
1
，a
2
，….，a
52
被100除的余数分别为r
1< br>，r
2
，….，
r
52
,而任意一整数被100除可能的余 数为0，1，2，….,99，共100个，它可分为51个类：{0}，
{1，99}，{2，98} ，…..{49，51}，{50}。因此，将51个类看做鸽子笼，则由鸽笼原理知，
将r
1
，r
2
，….，r
52
个鸽子放入51个笼中，，至少有两个属 于同一类，例如r
i
,r
j,
于是r
i
=r
j
或r
i
+r
j
=100,这就是说a
i
—< br>a
j
可100整除，或a
i
+ a
j
可被100整除。

第三章
3.2. 求1到1000中既非完全平方又非完全立方的整数个数。
解：设
S
＝{1,2,… ,1000};
A
1
表示1到1000中完全平方数的集合，则
A
1
表示1到1000
中不是完全平方数的集合；
A
2
表示1到1000 中完全立方数的集合，则
A
2
表示1到1000
中不是完全立方数的集合。

故
A
1
A
2
表示1到1000中既非完全 平方又非完全立方的整数的集合，由容斥原理（（3.5）
式）知：
____
A1
A
2
SA
1
A
2
A
1< br>A
2
其中
(3.5)
|S|
＝1000，

|A
1
|


1000

 31
,
3

10

|A
2
|

1000

A
1
A
2
表示1到1000中 既是完全平方又是完全立方的数的集合，故
6

A
1
A
2
=


1000

=3,
将以上数值代入(3.5)式得
A
1
A
2
＝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
.
P
1
表示这样的性质：一个n位数不包含3；
P
2
表示这样的性质：一个n位数不包含8；
P
3
表示这样的性质：一个n位数不包含9；
并令A
i
表 示S中具有性质P
i
的元素构成的集合（i=1,2,3）。
则
A
1

A
2

A
3
表示S中包含3，又包含8，又包 含9的所有n位数的集合。
由容斥原理（（3.5）式）得
|
A
1A
2
A
3
|=
|S|

而
< br>|A|


|A

A
ii
i1ijn
3
j
|

|A
1

A
2< br>
A
3
|
（3.5）
A
1
< br>7
,
A
2

7
,
A
3
< br>7
n
nn

nn
A
1

A
2

6
,
A
1

A
3

6
,
A
2

A
3

6
A
1

A
2

A
3

5
代入（3. 5）式得
n

，
A
1
A
2
A
3
8
n
37
n
36
n
5
n< br>

故所求的n位数有
8
n
37
n
36
n
5
n
个。

3.10. 求重集
B

3a,4b,5c

的10-组合数。
解：构造集合B′=
{a,b,c}
。令集合B′的所有10-组合构成的集合 为S。由
第一章的重复组合公式(1.11)有

3101

|S|
＝F（3，10）＝


10


=66。

令p
1
表示S中的元素至少含有4个a这一性质，令p
2
表示S中的元素至少含有5个b
这一性质，令p
3
表示S中的元素至少含有6个c这 一性质，并令A
i
(i=1,2,3)表示S中具有
性质p
i
(i= 1,2,3)的元素所构成的集合，于是B的10-组合数就是S中不具有性质p
1
,p
2
,p
3
的
元素个数。由容斥原理（（3.5）式）有：
|A
1
A
2
A
3
|=
|S|

|A|


|A

A
ii
i1i j
3
j
|

|A
1

A
2
A
3
|
(3.5)
由于已经求得
|S|
=66，下面分别计算(3.9)式右端其他的项。
由 于A
1
中的每一个10-组合至少含有4个a，故将每一个这样的组合去掉4个a就得到
集合B′的一个6-组合。反之，如果取B′的一个6-组合并加4个a进去，就得到了A
1
的
一个10-组合。于是A
1
的10-组合数就等于B′的6-组合数。故有


361

|A
1
|
=F（3， 6）＝


6


＝28


351

|A
2
|
=F（3，5）＝

< br>5


＝21


341

|A
3
|
=F（3，4）＝


4


＝15

同样的分析可得
用类似的分析方法可分别求得
< br>311

|A
1
A
2
|
＝F（3，1 ）＝


1


＝3


3 01

|A
1
A
3
|
＝F（3，0）＝

0


＝1

|A
2
A
3
|
＝0（因为5＋6＝11>10）
|A
1
A
2
A
3
|
＝0 （同上）

将以上数值代人(3.9)式得到：
|
A
1
A< br>2
A
3
|＝66－（28＋21＋15）＋（3＋1＋0）－0
＝6
故所求的10-组合数为6。

3.14. 求由数字1，2，

8所组成的全排列中，恰有4个数字在其自然位置上的全排列个
数。
解：4个数在其自然位置共有

对某一种方式，均有4个数字不在其自然位置，


种方式，
这正好是一个错排，其方式数为
D
4
（见 定理3.2），由乘法规则有，恰有4个数字在其自然
位置上的全排列数为

8

4


8


D
4< br>＝630。

4



第四章
4.6 求重集
B{a,3b,5c,7d}
的10-组合数。
解：设重集B的n- 组合数为
a
n
，则序列{
a
n
}的普通母函数为
f(x)(1xx
2
)(1xx
2
x
3
)( 1xx
2
x
3
x
4
x
5
)

(1xxxxxxx)

234567

11x
4
1x
6
1x
8
=

1x1x1x1x


3k

k
=(1-x-x-x+x+x+x-x)



3

x

k0

46810121418



所以a
10
=



310

36

34

32

30












3

3

3

3

3

=286-84-35-10+1=158
故重集B的10－组合数为158。
4.9. 设重集
B

b
1
,b
2
,b
3< br>,b
4
,b
5
,b
6

,并设
a
r
是
B
满足以下条件的r-组合数，
求序列

a
0
,a
1
,,a
r
,

的普通母函数。
a. 每个
b
I

出现3的倍数次。

I1,2,3,4,5,6


b.
b
1
,
b
2
至多出现1次，
b
3
,b
4
至少出现2次，
b
5
,b6
最多出现4次。
c.
b
1
出现偶数次，
b
6
出现奇数次，
b
3
出现3的倍数次，
b
4
出现 5的倍数次。
d. 每个
b
I

I1,2,3,4,5,6

至多出现8次。
解：
3k
f(x)(1xxx)
F(6,k)(x)


a.
3696

k0
b.
f(x)(1x)(xxx
c.
f(x)(1xx

(1+x+x+x+
d.
f(x)(1xx
23
23< br>24
2234
)
2
(1xx
2
x
3< br>x
4
)
2

)(xx
3
x
5
)(1x
3
x
6
x
9
)(1x
5
x
10
)

)
2

x
8
)
6


4.10 有两颗骰子，每个骰 子六个面上刻有1，2，3，4，5，6个点。问掷骰子后，点数之
和为
r
，两颗骰子 的点数有多少种搭配方式？
解：每个骰子是不同的，但讨论点数之和的时候不考虑顺序，故该问题是组 合问题。设
有满足条件的搭配方式有
a
r
种，则其普通母函数为

f(x)(xx
22


6
x)
其中
x
r
的系数
a
r
即为所求的搭配方式数。

4.14 求由数字2，3，4，5，6，7组成的
r
位数中，3和5都出现偶数次 ，2和4至少出现
一次的
r
位数的个数。
解：这是一个排列问题。设满足条 件的
r
位数的个数为
a
r
，则序列
(a
1
,a
2
,
应的指数母函数为：
,a
r
,)
对f
x
2
x
4
x
2
x
2
x3
22
(x)(1...)(x...)(1x...)
2

e
2!4!2!2!3!

1
xx2x22x
(ee)(e1)e

2
2
1

r< br>x
r
rrrr
=

(625344332 2)

4
r1
r!
所以，

0,r0



a
r


1
rrrrr
(6253443322),r0
< br>
4

5.
2.
如果用a
n
表示没有两个 0相邻的n位三元序列（即由0，1，2组成的序列）的个数。
求a
n
所满足的递归关 系并解之。
解：
对n位三元序列的第一位数有三种选择方式:
1)第一位选1，则在剩下的n-1位数中无两个0相邻的个数为a
n-1
;
2)第一位选2，则在剩下的n-1位数中无两个0相邻的个数为a
n-1
;
3)第一位选0,则在第二位又有两种选择方式：
(1)第二位选1，则在剩下的n-2位数中无两个0相邻的个数为a
n-2
；
(2)第二位选2，则在剩下的n-2位数中无两个0相邻的个数为a
n-2

a
1
=3,a
2
=8


显然有
∴ 由加法规则得
a
n
所满足的递归关系为
： < br>
a
n
2a
n1
2a
n2


a
1
3,a
2
8
其特征方程为
x
2
-2x-2=0
(n3)

∴
特征根为
x
1
=1+
3
,x
2
=1-
3

由定理5.3知其通解为
a
n
=c
1
(1+
由初始条件有

3
)
n
+c
2
(1-
3
)
n

c
1
(13)c
2
(13)3
< br>
22

c
1
(13)c
2
(13) 8
解以上方程组得
c
1

323
323
，
c
2


6
6
n
1
32313
∴
a
n



6



 


323

13






n

5.4. 某人有n元钱，她每天要去 菜市场买一次菜，每次买菜的品种很单调，或者买一元钱
的蔬菜，或者买两元钱的猪肉，或者买两元钱的 鱼。问，她有多少种不同的方式花完这n
元钱?
解：设花完这n元钱的方式有a
n
种，则第一次花钱可分为下面几种情况：
1)若第一次买一元钱的菜，则花完剩下的n-1元钱就有a
n-1
种方式，
2)若第一次买二元钱的肉，则花完剩下的n-2元钱就有a
n-2
种方式，
3)若第一次买二元钱的鱼，则花完剩下的n-2元钱就有a
n-2
种方式，
显然有a
1
=1，a
2
=3.
由加法规则,得递归关系如下：


aa
n1
2a
n2
(n3)


n


a
1
1 , a
2
3
其特征方程为：
x
2
x20.

特征根
x
1
1,x
2
2
.
通解
a
n
c
1
(1)
n
c
2
2
n
.
由初始条件得

c
1
(1)c
2
21


22
c(1)c23
2

1
解得
12
c
1
,c
2

.
33
故该递归关系的解为


12
(1)
n
2
n


33
12
nn
故她有
(1)2
种不同的方式花完这n元钱。
33
a
n

5.
6．
求解下列递归关系


a
n
6a
n1
9a
n2
3 (n2)
a．



a
0
0 , a
1
1
解：这是一个常系数线性非齐次递归关系式，其导出的齐次递归关系为：
***
a
n
6a
n1
9a
n2

∴其特征方程为
x
2
6x90
，

解得


q
1
q
2
3

由定理5.3知，所导出的齐次线性递归关系的通解为
n
*
a
n< br>

c
1
c
2
n

·

-3


由于f(n) =3, 且1不是式递归关系式的特征根，故设特解为
a
n
A

将
a
n
A
代入递归关系得
A6A9A3

3
∴
A

16
由定理5.6知，递归关系式的通解为
*

a
n
aa
3


c
1
c
2
n

(-3)
n

16
将初值条件代入上式并解得
3

c


1
16


1

c
2

12

故
a
n

3

31



n

(-3)
n
。

16

161 2


a
n
5a
n1
6a
n2
3n
2
(n2)
b．


a0 , a1
1

0
解：这也是一个常系数线性非齐次递归关系式，其导出的齐次递 归关系的特征方程
为
x
2
5x60

∴特征根为
x
1
2,x
2
3

由定理5.3知，所导出的齐次线性递归关系的通解为

a
n
c
1
(2)
n
c
2
(3)
n

2
由于f(n) =3n,且1不是递归关系式的特征根，故设特解为
a
n
A
0
n
2
A
1
nA
2

将上式代入递归关系式解得

A
1
0
4
,A
17
24
,A
115
12

288

∴通解
aa

1
2
1711 5
n

n
a
n
c
1
(2)
n
c
2
(3)
n

4
n
24
n
288

由初始条件有

c
115
1
c0


2

288



2c
1 17115
1
3c
2

4

24
288
1
解得
c
14
1


9< br>,c
37
2

32

故递归关系的解为：
aa

14
nn
a
n

9
(2)
n

37
32
(3)
n

1
4
n
2

17
24
n
115
288



a
n
7a
n1
10a
n2
3
n
c.
(n2)


a
0< br>0,a
1
1
解：对应齐次递归关系的特征方程为
x
2
-7x+10=0
其特征根
x
1
=5,x
2
=2
∴
a
*n
n
5
n
c
1
2c
2

又f(n)=3
n
, 且3不是递归关系式的特征根，故设特解为
a
n
n
A3
，将
代入原递归关系得
A3
n
 7A3
n1
10A3
n2
3
n

解得
A=

9
2

∴通解为
a
*
9
n
a
n
a
n
5
n
c
12
n
c
2

2
3
n

由初始条件有


c
1
c
2

9
2
0

5c
1
2c
2

9
2
31

解出
c
1
=116,c
2
=83
故原递归关系的解为：
a
n
A3
n

a
n


11
n
8
n
9
n
523

632

a
n
5a
n1
6a
n2
424
n
d.


a
0
0,a
1
1
(n2)

解：对应齐次递归关系的特征方程为
x
2
+5x+6=0
解得
x
1
=-2,x
2
=-3。
齐次递归关系的通解为： < br>
a
n
c
1
(2)
n
c
2< br>(3)
n

n
又f(n)=42
4
, 且4不是递归关系式的特征根，故设特解为
a
n
A4
n
,
将
a
n
A4
n
代入递归关系得
A4
n
+5A4
n-1
+6A4
n-2
=42×4
n
解得
A=16,
故通解为
*
a
n
=a
a
n

c
1
(－2)
n
+c
2
(－3)
n
+16×4
n

由初始条件有

c
1
c
2
160


2c3c641

12
解得
c
1
=－111,c
2
=95
所以有
a
n
=－111×(－2)
n
+95×(－3)
n
+16×4
n

a
n
5a
n1
6a
n2
32
n
e.


a
0
0,a
11
(n2)

解：对应齐次递归关系的特征方程为
x
2
-5x+6=0
解得
x
1
=2,x
2
=3。
故齐次递归关系的通解为： 
a
n
c
1
2
n
c
2
3
n

n
又f(n)=3
2
, 且2是递归关系式的1重特征根，故设特解为

a
n
(AnB)2
n

代入递归关系求得
A=－6
从而通解为
a
n
=a*
a
n

c
1
2
n
+c
2
3
n
-6n2
n
由初始条件有
__

c
1
c
2
0



2c
1
3c
2
121
解得
c
1
=-13,c
2
=13
所以有
a
n
=-13×2
n
+13×3
n
－6n×2
n