组合数学期末考查卷
一、选择题。

（每小题3分，共24分）
1.在组合数学的恒等式中n k ⎛⎫= ⎪⎝⎭
A 11(1)1n n n k k k --⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭
B 1(1)1n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭
C 1(1)11n n n k k k -⎛⎫⎛⎫+>≥ ⎪ ⎪--⎝⎭⎝⎭
D (1)1n n n k k k ⎛⎫⎛⎫+>≥ ⎪ ⎪-⎝⎭⎝⎭
2、14321=++x x x 的非负整数解个数为（ ）。

A.120
B.100
C.85
D.50
3、()()=94P 。

A. 5
B. 8
C. 10
D. 6
4、递推关系12432(2)n n n n a a a n --=-+≥的特解形式是（a 为待定系数）（）
A 、2n an
B 、2n a
C 、32n an
D 、22n
an 5、错排方式数n D =（）
A 1(1)n n nD ++-
B (1)(1)n n n D ++-
C -1(1)n n n
D +- D 1(1)(1)n n n D +++-
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 ，使得第0j 个盒子里至少装有0j q 件东西，我们把该定理称为__________________。

3、1S n n-1（，）=__________________。

4、Fibbonacci 数f(9)=
5、数列｛1, 2, 3, 4, . . .｝的生成函数为__________________。

三、计算题。

（1,2,3,4小题，每小题6分。

其余的每小题8分，共40分） 1、10个节目中有6个演唱、4个舞蹈。

今编写节目单，要求任意两个舞蹈之间至少有1个演唱，问可编写出多少种不同的演出节目单？
2、求{}5,3M a b =的6排列数。

3、求()6
231234x x x +++展开式中5x 的系数。

4、从1至2000的整数中，至少能被2,3,5中的两个数整除的整数有多少个？
5、已知()f n 是n 3的次多项式且()()()()01,11,23,319,f k f f f ==== ()f n 确定()0n
k f k =∑并求。

6、（河内宝塔问题）有三根和n 个大小递增的在一根木桩上的环形盘子，最大盘子在底部。

这些盘子可一次一个地从一个木桩转移到另一个木桩，但不允许较大的盘子放在较小的盘子上面。

现在把n 个盘子从木桩A 全部转移到木桩B ，问必须移动的次数是多少？
四、证明题。

（每小题8分，共16分）
1、Ｆ（ｍ＋ｎ）＝Ｆ（ｍ）Ｆ（ｎ）＋Ｆ（ｍ－１）Ｆ（ｎ－１）
2、证明下列组合恒等式：
()()()()201
231212n n k n n k k k n n +=⎛⎫--= ⎪++++⎝⎭∑
《组合数学》期末考查卷答案
一、选择题。

（每小题3分，共24分）
1 A
2 A
3 D
4 B
5 C
6 C
7 C
8 A
二、填空题（（每小题4分，共20分）
1 15120
2 抽屉原理（的一般形式）
3 2n ⎛⎫- ⎪⎝⎭
4 5
5 5
2x （1-x ）
三、解答题。

（1,2,3,4小题，每小题6分。

其余的每小题8分，共40分） 1、解：设可编写出N 种不同的演出节目单。

可依如下三个步骤去编写节目单： ① 作6个演唱节目的全排列，有6!720=种方法； ② 从作成的排列的左边、右边及6个元素形成的7个空挡中选出4个位置，有7354⎛⎫= ⎪⎝⎭
种
方法；
③ 把4个舞蹈节目放在已选出的4个位置上，每个位置放一个舞蹈节目，有4！=24种方法。

由乘法原则得
N =720×35×24=604800
2、 解：根据题意有：{}15,M a b =，{}24,2M a b =，{}33,3M a b =.
1236!6!6!6,15,205!4!2!3!3!
N N N ====== 则{}5,3M a b =全排列数123=6+15+20=41N N N N =++
3、解：
()()()()()
()()()
()()623622121082246361234121211211260112160112x x
x x x x x x x x x x x x x x +++⎡⎤=+++⎣⎦=+++++++++++⋅⋅⋅ 所以()6231234x x x +++的展开式中5x 系数为
1210108122602253217922520072026772
⎡⎤⎡⎤⎛⎫⎛⎫⎛⎫⎛⎫++•+⨯+•⎢⎥⎢⎥ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎣⎦⎣⎦
=++=
4、解：设 a 为具有能被 2 整除的性质;设b 为具有能被 3 整除的性质; 设c 为具有能被 5 整除的性质;
则所求为:N (2) + N (3)
()()()()()23323233N N -N ,N 3=N 223200020002000N N +N +N 666232535200066235534
ab ac bc N N abc ⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭
⎡⎤⎡⎤⎡⎤==++=⎢⎥⎢⎥⎢⎥⨯⨯⨯⎣⎦⎣⎦⎣⎦
⎡⎤===⎢⎥⨯⨯⎣⎦
∴=而又原式
5、解：数列()0{}n f n ≥的查分表为
1 1 3 19 ……
0 2 16 ……
2 14 ……
12 ……
……
因为()f n 是n 3的次多项式，所以当4k ≥时，()()001,2k f n n ∆==⋅⋅⋅，，，于是
()()
()()()()
3032300324320121225312310111121234137466
121512323
k k n j k j n f n f k n n n n n n f k f j n n n n n n n n n n n ===⎛⎫=∆ ⎪⎝⎭
⎛⎫⎛⎫=++=-++ ⎪ ⎪⎝⎭⎝⎭
+⎛⎫=∆ ⎪+⎝⎭++⎛⎫⎛⎫=++•+• ⎪ ⎪⎝⎭⎝⎭
+-++==--++∑∑∑
6、解 令()H n 表示把n 个盘从一个木桩移到另一木桩所必须的移动次数。

显然有()00H =，()11H =。

对于n 个盘，先把木桩A 上的1n -个盘套到木桩C 上而保持相对位置不变，需用()1H n -次。

再把木桩A 上的最大的盘套到B 上，用1次。

然后再把C 上的盘套回到B 上，又用()1H n -次。

所以有
()()211H n H n =-+
迭代此关系式得
()()211H n H n =-+
()22221H n =-++
……
()12202221n n H -=++++
12222221n n --=+++
所以有 ()21
2121n n H n -==--
四、证明题。

（每小题8分，共16分）
证明：当ｍ＝１时，Ｆ（１）Ｆ（ｎ）＋Ｆ（１）Ｆ（ｎ－１） ＝Ｆ（ｎ）＋Ｆ（ｎ－１）
＝Ｆ（ｎ＋１）
等式成立；
假设当ｍ≤ｋ时，等式成立；
当ｍ＝ｋ＋１时，
Ｆ（ｋ＋１＋ｎ）＝Ｆ（ｋ＋ｎ）＋Ｆ（ｋ－１＋ｍ）
＝Ｆ（ｋ）Ｆ（ｎ）＋Ｆ（ｋ－１）Ｆ（ｎ－１）
＋Ｆ（ｋ－１）Ｆ（ｎ）＋Ｆ（ｋ－２）Ｆ（ｎ－１）
＝Ｆ（ｋ＋１）Ｆ（ｎ）＋Ｆ（ｋ）Ｆ（ｎ－１）
等式成立；
所以，Ｆ（ｍ＋ｎ）＝Ｆ（ｍ）Ｆ（ｎ）＋Ｆ（ｍ－１）Ｆ（ｎ－１）
2、证明：
()()()()()()()()()()()()()()()()()
000222
02
112121121221212211221211223
12n k n
k n k n j n j n n k k k n n n k n n k k n k n n n j n n n n j n n n n n ===+=+=+⎛⎫
⎪++⎝⎭
++⎛⎫
= ⎪++++⎝⎭
+⎛⎫
= ⎪+++⎝⎭
+⎛⎫
= ⎪++⎝⎭
⎡+⎤
⎛⎫
=-+-⎢⎥ ⎪++⎝⎭⎣⎦
--=++∑∑∑∑∑。