组合数学试卷A(2014-2015-1)答卷

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 )种不同的排列方式. A、 63 ; B、 126 ; C、 252 ; D、 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页)

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4