保卫黄河钢琴曲-我愿等

组合数学期末考查卷
一、选择题。（每小题3分，共24分）

n

1.在组合数学的恒等式中




k


n1

n1

n1

n

A



(nk1)
B



(nk1)

kk1kk1

C


n

n1

n

n

D
(nk1)



(nk1)

k1

k1

k

k1

2、
x
1
x
2
x
3
14
的非负整数解个数为
（ ）。
A.120 B.100 C.85 D.50
3、
P
4

9



。
A. 5 B. 8 C. 10 D. 6
4、
递推关系
a
n
4a
n1
3a
n2
2
n
(n2)
的特解形式是（a为待定系数）（）
A、
an2
B、
a2
C、
an2
D、
an2

n
n
3n2n
5、错排方式数
D
n
=（）
A
nD
n
(1)
n1
B
(n1)D
n
(1)
n
C
nD
n-1
(1)
n
D
(n1)D
n
(1)
n1

6、将n个不同的球放入m个不同的盒子且每盒非空的方式数为（
）。
Ａ（
n
m
） Ｂ
P

n,m

Ｃ ｍ！Ｓ
2
（ｎ，ｍ） Ｄ（
n
m
）ｍ！
7、有100只小鸟飞进6个笼子，则必有一个笼子至少有（ ）只小鸟。
A 15 B 16 C 17 D 18
8、
若颁发26份奖品给4个人，每人至少有3份，有（ ）种分法
A 55 B 40 C 50 D 39
二、填空。（每小题4分，共20分）
1、现有7本不同的书，要分给6个同学，且每位同学都要有书，有
____________ ______
种不同的分法


2、设
q
1
, q
2
,…… ,q
n
是n个正整数，如果将
q
1
+ q
2
+…+q
n
－n﹢1
件东西放入n个
盒子里，则必存在 一个盒子
j
0
，1≤j
0
≤n，
使得第
j
0
个盒子里至少装有
q
j
0
件东西，
我们把该定理称为__________________。
3、
S（
1
n，n-1）=
__________________。

1

4、Fibbonacci数f(9)=

5、
数列
｛1, 2, 3, 4, . . .｝
的生成函数为_
_________________。

三、计算题。（1,2,3,4小题，每小题6分。其余的每小题8分，共40分）
1、10个节目中有6个演唱、4个舞蹈。今编写节目单，要求任意两个舞蹈之间至少有1个
演唱，问可 编写出多少种不同的演出节目单？


2、求
M

5a,3b

的6排列数。

3、求

12x3x
2
4x
3

展开式中
x
5
的系数。
6
4、从1至
2000
的整数中， 至少能被2,3,5中的两个数整除的整数有多少个？

5、已知
f
n

是
n
的3次多项式且
f

0
< br>k1,f

1

1,f

2

3,f

3

19,

确定f

n< br>
并求

f

k

。
k0n
6、
（河内宝塔问题）有三根和
n
个大小递增的在一根木桩上的环形盘 子，最大盘子在底部。
这些盘子可一次一个地从一个木桩转移到另一个木桩，但不允许较大的盘子放在较 小的盘子
上面。现在把
n
个盘子从木桩
A
全部转移到木桩
B
，问必须移动的次数是多少？

四、证明题。（每小题8分，共16分）

1、Ｆ（ｍ＋ｎ）＝Ｆ（ｍ）Ｆ（ｎ）＋Ｆ（ｍ－１）Ｆ（ｎ－１）
2、证明下列组合恒等式：

n

2
n2
n3


 


n1

n2

k0
k1

k2


k

n
1




《组合数学》期末考查卷答案

一、选择题。（每小题3分，共24分）
1 A 2 A 3 D 4 B 5 C 6 C 7 C 8 A

二、填空题（（每小题4分，共20分）
1 15120 2
抽屉原理（的一般形式）
3




2

n


2


x

2
（1-x）
三、解答题。（1,2,3,4小题，每小题6分。其余的每小题8分， 共40分）
1、
解：设可编写出N种不同的演出节目单。可依如下三个步骤去编写节目单：
① 作6个演唱节目的全排列，有
6!720
种方法；
4 55 5

7

② 从作成的排列的左边、右边及6个元素形成的7个空挡中选出 4个位置，有

35
种

4

方法；
③ 把4个舞蹈节目放在已选出的4个位置上，每个位置放一个舞蹈节目，有4！=24种方
法。
由乘法原则得
N =720×35×24=604800
2、 解：根据题意有：
M
1


5a,b

，
M
2

4a,2b

，
M
3


3a,3b

.
N
1

6!6!6!
6,N
2
15,N
3
20

5!4!2!3!3!
则
M

5a,3b

全排列数
NN
1
N
2
N
3
=6+15+20=41

3、解：


12x3x
12
2
4x
3
6
6

2



1x
< br>2x
2

12x




8 2


1x

12x
2

1x
6
10

12x

60x
4

1x

12x

5
160x
6

1x

12x


所以
12x3 x4x
3

23
6

的展开式中
x
系数 为


10

10



8



12


12

 


2

60


22


5



3

2



1



79225200720
26772
4、解：设 a
为具有能被 2 整除的性质;设b 为具有能被 3 整除的性质; 设c 为
具有能被 5 整除的性质;
则所求为:
N (2) + N (3)

3


2

3

3

而N

N
2
-

N
3
,N

3

=

N
3

2

2

3


2000

2000

2000

又N
2
N

ab

+N

a c

+N

bc






666


23

25
35


2000

N
3
N

abc



66


2 35

原式534


5、解：数列
{f

n

}
n0
的查分表为
1 1 3 19 ……
0 2 16 ……
2 14 ……
12 ……
……
因为
f

n

是
n
的3次多项式
，所以当
k 4
时，

k
f

n

0
n01，,2，

，于是

n

f

n





k
f

0

k0

k


n

n

12

12

2n
3
5 n
2
3n1

2

3

3

n1

j
fk



f< br>
0

j1
j0


k0

n1

n1

n12
12

34

n3


n1


3n
3
7n
2
4n 6

6
1215
n
4
n
3
n2
n1
2323
6、
解 令
H

n
表示把
n
个盘从一个木桩移到另一木桩所必须的移动次数。显然有
H< br>
0

0
，
H

1

 1
。
对于
n
个盘，先把木桩
A
上的
n1
个盘套到木桩
C
上而保持相对位置不变，需用
H

n1

次。再把木桩
A
上的最大的盘套到
B
上，用
1
次 。然后再把
C
上的盘套回到
B
上，又用
H

n1

次。所以有
H

n

2H

n1

1


4

迭代此关系式得
H

n

2H

n1

1


2
2
H

n2

2

1
……

2
n
H
< br>0

2
n1
2
2
21


2
n1
2
n2
2
2
2

1
所以有
H

n


2
n1
21
2
n
1



四、证明题。
（每小题8分，共16分）

证明
：当ｍ＝１时，Ｆ（１）Ｆ（ｎ）＋Ｆ（１）Ｆ（ｎ－１）
＝Ｆ（ｎ）＋Ｆ（ｎ－１）
＝Ｆ（ｎ＋１）
等式成立；
假设当ｍ≤ｋ时，等式成立；
当ｍ＝ｋ＋１时，
Ｆ（ｋ＋１＋ｎ）＝Ｆ（ｋ＋ｎ）＋Ｆ（ｋ－１＋ｍ）
＝Ｆ（ｋ）Ｆ（ｎ）＋Ｆ（ｋ－１）Ｆ（ｎ－１）
＋Ｆ（ｋ－１）Ｆ（ｎ）＋Ｆ（ｋ－２）Ｆ（ｎ－１ ）
＝Ｆ（ｋ＋１）Ｆ（ｎ）＋Ｆ（ｋ）Ｆ（ｎ－１）
等式成立；
所以，Ｆ（ｍ＋ｎ）＝Ｆ（ｍ）Ｆ（ｎ）＋Ｆ（ｍ－１）Ｆ（ｎ－１）
2、证明：

n
1

n

k0

k1< br>
k2



k


n

1

n1

n2


n


n1

n2


k0
< br>k1

k2



k

< br>n

1

n2

n1

n 2


k0



k2




1
n

2

n2

n1

n2

j2


j


1

n2


n2
< br>
n1

n2


n



j0


j



2
1



2
n2
n3
< br>n1

n2



5