2014-2015-1《组合数学》试卷（A）答案
一、填空题（每小题3分，共24分）
1．(x?y)6所有项的系数和是（ 64 ）.
2．将5封信投入3个邮筒，有（ 243 ）种不同的投法.
3．在5?3棋盘中选取两个相邻的方格（即有一条公共边的两个方格），有 （ 22 ）种不同的选取方法.
4．把9个相同的球放入3个相同的盒，不允许空盒，则有（ 7 ）种不同方式. 5．把5个不同的球安排到4个相同盒子中，无空盒，共有种（ 10 ）不同方法. 6．一次宴会，5位来宾寄存他们的帽子，在取帽子的时候有（ 44 ）种可能使得没有一位来宾取回的是他自己的帽子.
7. 在边长为a的正方形中，任意给定九点，这些顶点的三角形中必有一个三角形的面积不大于（ 8．棋盘多项式 R(
a28 ）.
)=（ x2 +3x+1 ）.
二、单项选择题（每小题3分，共24分）
9．?????????p??q??p??q??p??q?pq,. }， r?min{?...???????（ B ）
?0??r??1??r?1??r??0??p?q??p?q??p?q??p?q?1?A、??； B、??； C、??； D、??.
r?1rr?1r????????10. (a?b?c?d)的展开式在合并同类项后一共有（ B ）项. A、n； B、?n?n?3??n?； C、???； D、n!. n???4?211．多项式(2x0?x1?4x2?x3)4中项x0x1x2的系数是（ C ）.
A、 78 ； B、 104 ； C、 96 ； D、 48.
12．有4个相同的红球，5个相同的白球，则这9个球有（ B ）种不同的排列方式. Ａ、 63 ； Ｂ、 126 ； Ｃ、 252 ； Ｄ、 378.
13. 设x,y均为正整数且x?y?10，则这样的有序数对?x,y?共有（ D ）个.
A. 100 ； B. 81 ； C. 50 ； D. 45.
《组合数学》试题（第1页 共5页）
14. 递推关系an?4an?1?3an?2?2n(n?2)的特解形式是（ B ）（?为待定常数）.
A、?n?2n； B、?2n； C、?n32n； D、?n22n.
15．递推关系f(n)?6f(n?1)?9f(n?2)的一般解是（ B ）（C1,C2为任意常数）.
A、C13n?1?C23n； B、(C1?C2n)3n； C、C1(1?n)3n； D、C13n?C23n. 16. 数列an?n的普通母函数是（ D ）
A、
1tt-1 ； B、 ； C、 ； D、. 1?t1?t(1?t)2(1?t)2
三、解答题（每小题10分，共30分）
17. 用数字1、2、3、4（数字可重复使用）可组成多少个含奇数个1、偶数个2且至少含一
个3的n位数 ( n > 1 ). 解：由指数母函数
?tt3??t2??tt2??tt2?e4t?e3t?e?t A?t????1!?3!??????1?2!??????1!?2!??????1?1!?2!?????4????????nnnn4?3???1?t1ntnn=?4?3???1?，的系数 即为所求. ????10分
n!4n!4n?0???n
18. 解递推关系：an?5an?1?6an?2?n?2，(n?2),解：递推关系an?5an?1?6an?2a0?2749,a1?. 44?n?2? （1）
2的特征方程为x?5x?6?0，特征根为x1?2,x2?3. 故其通解为
an?c1?2n?c2?3n. ?????????????（4分）
因为（1）式无等于1的特征根，所以递推关系
an?5an?1?6an?2?n?2?n?2? （2）
有特解 an?An?B，其中A和B是待定常数，代入（2）式得
An?B?5[A(n?1)?B]?6[A(n?2)?B]?n?2
《组合数学》试题（第2页 共5页）
化简得2An?2B?7A?n?2,所以 ?2A?1解之得A?111,B?.于是 24??2B?7A?211n?,???????????（8分） 24an?c1?2n?c2?3n?1127?c?c??2??144其中c1,c2是待定常数. 由初始条件得?
?2c?3c?1?11?4912?244?nn解之得c1?3,c2?1. 所以an?3?2?3?111n?(n?2).????????（10分） 24
19. 求1到1000之间不能被5、6 或8整除的自然数的个数.
解：设A为1至1000的整数中能被5整除的数的个数；B为1至1000的整数中能被6整除的数的个数；C为1至1000的整数中能被8整除的数的个数. 则
?1000??1000??1000??1000?A???200,B??166,C??125,A?B???6??8??30??33,5????????
100010001000??????A?C???25,B?C??41,A?B?C??8??????40??24??120?所以
A?B?C?A?B?C?A?B?A?C?B?C?A?B?C?200?166?125?33?25?41?8?400
即所求为：1000?400?600. ??????????????????10分
四、证明题（每小题11分，共22分）
20. 设[x]0:?0,[x]k:?x(x?1)?(x?k?1),k?N，s(n,k),S(n,k)分别为第一、第二类Stirling数，定义为：[x]n??s(n,k)xk?0nk，x?n?S(n,k)[x]k?0nk. 证明：
（1）第二类Stirling数满足递推关系：S(n?1,k)?S(n,k?1)?kS(n,k),n,k?1；
?0,m?n（2）两类Stirling数满足关系：?S(n,k)s(k,m)??.
1,m?nk?m?n证明：（1）
《组合数学》试题（第3页 共5页）