组合数学试卷A2012011答卷

1、2014-2015-1组合数学试卷（A）答案、填空题（每小题3分，共24分）. （x + y）6所有项的系数和是（64 ）.将5封信投入3个邮筒，有（243 ）种不同的投法.在5M3棋盘中选取两个相邻的方格（即有一条公共边的两个方格），有 （22）种不同的选取方法.把9个相同的球放入 3个相同的盒，不允许空盒，则有（7 ）种不同方式.把5个不同的球安排到 4个相同盒子中，无空盒，共有种（10 ）不同方法. 一次宴会，5位来宾寄存他们的帽子，在取帽子的时候有（44 ）种可能使得 TOC o 1-5 h z 没有一位来宾取回的是他自己的帽子.在边长为a的正方形中，任意给定九点，这些顶点的三角形中必

2、有一个三角形的面积不大于（a%）.棋盘多项式 R( Eb )= ( x2 +3x+1)、单项选择题（每小题3分，共24分）9小+卜10B ),p+q1B、p + qrC、p+q、r十1r m m i n p q. 1 p + q +1、D、 .r J. (a +b +c +d)n的展开式在合并同类项后一共有(B )项. TOC o 1-5 h z HYPERLINK l bookmark16 o Current Document n+3- n-A、n ;B、；C、；D、n!.In).多项式(2x0+x1+4x2 +x3 )4中项x0 x2 x2的系数是( C ).A、 78 ;B、104 ;C

3、、 96 ;D、 48.有4个相同的红球，5个相同的白球，则这9个球有（B ）种不同的排列方式A、 63 ;B、 126 ; C、252 ; D、 378.13.设x, y均为正整数且x + y M10 ,则这样的有序数对（x, y）共有（D ）个.100 ;81 ;50 ;D. 45.组合数学试题（第 1页 共5页）14.递推关系an =4%3%n + 2n（n22）的特解形式是（B ） （s为待定常数）A、2n15.递推关系f（n） =6f（n-1）_9f （n2）的一般解是（ B ） （ C1, C2为任意常数）.16.17.A、G3n,+C23n； B、(C1 +C2 n)3数列an

4、= n的普通母函数是（ D ）A、11 -tB、C、解答题（每小题10分，共30分）C、G(1 + n)3n；D、C1 3nC 23n.-1(1-t)2D、t (1-t)2.2、3、4 （数字可重复使用）可组成多少个含奇数个1、偶数个2且至少含一个3的n位数（n 1 ）.解:由指数母函数At =I1!3!12!1! 2!1! 2!4t 3t_te -e e:-1-1 4nn=0 4- 3n-1ntn!tn _,J的系数n!4n _3n +(-1 n即为所求.10分18.解递推关系:an =5an46an二十n +2,(n -2),a。27449 aT解：递推关系an-5an 1 - 6an 2

5、 n 一 2(1)的特征方程为2x -5x +6 = 0 ,特征根为=3.故其通解为4分)an =c1 2n c2 3n.因为（1）式无等于1的特征根，所以递推关系an =5anj -6an +n +2(n 2)(2)有特解an = An十B ,其中a和B是待定常数，代入（2）式得An B =5A(n -1) B - 6A(n - 2) B n 2组合数学试题（第 2页 共5页）化简得2An +2B _7A =n +2,所以an = C1 2C22A = 12B7A=2Jn 113 n ,248分)其中g,C2是待定常数由初始条件得1127c1 c2 二 HYPERLINK l bookmar

6、k60 o Current Document 44c c 1112 g 3c22449(10 分) TOC o 1-5 h z 111 .解之得 g =3,c2 =1.所以 an =3父2n +3n +-n + (n 2). , 2419.求1到1000之间不能被5、6或8整除的自然数的个数.解：设A为1至1000的整数中能被5整除的数的个数；B为1至1000的整数中能被 6整 除的数的个数；C 为1至1000的整数中能被 8整除的数的个数.则A =陪卜200, B =暗卜 166 C =噌=125, A。B =喈卜 33, _ 5_ 6_ 8_ 30.AC = l1000-l = 25, B

7、C = 110001iA”nc = 1100081 40！ 24M20aUbUc = A 十 B + C AB AC - BC + Arl BC 所以= 200 166 125 -33 -25 -41 8 =40010分即所求为：1000 -400 =600.,四、证明题(每小题11分，共22分) TOC o 1-5 h z 20.设x0 :=0, xk :=x(x 1)(x k+1), k N , s(n, k), S(n,k)分别为第一、第二 nn类 Stirling 数，定义为：xn = s(n, k) xk , xn = S(n,k) xk .证明： k=0k=0(1)第二类 Stir

8、ling 数满足递推关系：S(n+1,k)=S(n,k1) + kS(n,k), n, k 1 ；n0, m = n(2)两类 Stirling 数满足关系：Z S(n, k) s(k, m)=，.kom1, m=n证明：(1)组合数学试题（第 3页 共5页） TOC o 1-5 h z nnnxn1 =xn x- S(n,k)xk(x-k) k =- S(n,k)xki 八 kS(n,k)xk k -0k=Ok=On 1nn=、 S(n,k1)xk 八 kS(n,k)xk -% n,k1) kS(n,k)lxkS(n,n)xnik 4m 4k 1n 1因为xn+ = S(n +1,k)xk，

9、所以比较两等式的xk的系数，即得递推关系： k OS(n+1,k)=S(n,k 1) + kS(n,k), n, k 之1.,6 分nk(2)因为 xn = S(n,k)xk, xk= s(k,m)xm,所以k Om 0nkn nxn =、, S(n,k)“ s(k,m)xm 、S(n, k)s(k,m) xmk =0m=0m=0k 矛比较两等式的xm的系数，即得：/0, m 二 n工 S(n,k)s(k,m) = 4.,11 分k#1, m = n21.考虑n个数a1，a2,，an的乘积aa2a3an ,依据乘法的结合律，不改变其顺序，只用括号表示成对的乘积.设pn为n个数乘积的n-1对括号

10、插入的不同方案数.(1)证明Pn的递推关系为：Pn = PPn+ P2Pn/ + PnP1, 52);(2)用母函数方法证明：Pn =- 2n -2 , (n之2).n n -1 J证明：(1) n个数a1, a2，an的乘积的最后一次乘法运算是前k个数的积与后n - k个数的积之间进行，其中k =1,2，n -1.前k个数可以有Pk种不同的方法加括号，而后 n-k 个数可以用p一种不同的方法加括号.这样，当k取遍1,2，n-什时，集所有可能性， 于是我们得到Pn = P1 Pn-1 + P2 Pnq + Pn 二 P1 , 5 2 2).,5 分n-1显然p1=p2=1 ,设G(x) = pnxn,由递推公式pn=Epk pn_k,n之2.有n 1k=1组合数学试题(第 4页共5页) TOC o 1-5 h z 二二二二二二nn：nG(x)=PnXn=X+PnXn=X+ PkPn&Xn= X+PkPn+Xnn 1n-2n=2k4n4k 400 8oooO= X+ Pk Pn*4Xn* =x+ PkXkZ PnXn=X + G2(X)k 4 n zkkJnJ-2 _1 二 J - 4x二G(x)2 -G(x) +x = 0,解得 G(x)=.2