組合數(shù)學(xué)試卷A2012011答卷

1、2014-2015-1組合數(shù)學(xué)試卷（A）答案、填空題（每小題3分，共24分）. （x + y）6所有項(xiàng)的系數(shù)和是（64 ）.將5封信投入3個(gè)郵筒，有（243 ）種不同的投法.在5M3棋盤中選取兩個(gè)相鄰的方格（即有一條公共邊的兩個(gè)方格），有 （22）種不同的選取方法.把9個(gè)相同的球放入 3個(gè)相同的盒，不允許空盒，則有（7 ）種不同方式.把5個(gè)不同的球安排到 4個(gè)相同盒子中，無(wú)空盒，共有種（10 ）不同方法. 一次宴會(huì)，5位來(lái)賓寄存他們的帽子，在取帽子的時(shí)候有（44 ）種可能使得 TOC o 1-5 h z 沒(méi)有一位來(lái)賓取回的是他自己的帽子.在邊長(zhǎng)為a的正方形中，任意給定九點(diǎn)，這些頂點(diǎn)的三角形中必

2、有一個(gè)三角形的面積不大于（a%）.棋盤多項(xiàng)式 R( Eb )= ( x2 +3x+1)、單項(xiàng)選擇題（每小題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的展開(kāi)式在合并同類項(xiàng)后一共有(B )項(xiàng). TOC o 1-5 h z HYPERLINK l bookmark16 o Current Document n+3- n-A、n ;B、；C、；D、n!.In).多項(xiàng)式(2x0+x1+4x2 +x3 )4中項(xiàng)x0 x2 x2的系數(shù)是( C ).A、 78 ;B、104 ;C

3、、 96 ;D、 48.有4個(gè)相同的紅球，5個(gè)相同的白球，則這9個(gè)球有（B ）種不同的排列方式A、 63 ;B、 126 ; C、252 ; D、 378.13.設(shè)x, y均為正整數(shù)且x + y M10 ,則這樣的有序數(shù)對(duì)（x, y）共有（D ）個(gè).100 ;81 ;50 ;D. 45.組合數(shù)學(xué)試題（第 1頁(yè) 共5頁(yè)）14.遞推關(guān)系an =4%3%n + 2n（n22）的特解形式是（B ） （s為待定常數(shù)）A、2n15.遞推關(guān)系f（n） =6f（n-1）_9f （n2）的一般解是（ B ） （ C1, C2為任意常數(shù)）.16.17.A、G3n,+C23n； B、(C1 +C2 n)3數(shù)列an

4、= n的普通母函數(shù)是（ 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 （數(shù)字可重復(fù)使用）可組成多少個(gè)含奇數(shù)個(gè)1、偶數(shù)個(gè)2且至少含一個(gè)3的n位數(shù)（n 1 ）.解:由指數(shù)母函數(shù)At =I1!3!12!1! 2!1! 2!4t 3t_te -e e:-1-1 4nn=0 4- 3n-1ntn!tn _,J的系數(shù)n!4n _3n +(-1 n即為所求.10分18.解遞推關(guān)系:an =5an46an二十n +2,(n -2),a。27449 aT解：遞推關(guān)系an-5an 1 - 6an 2

5、 n 一 2(1)的特征方程為2x -5x +6 = 0 ,特征根為=3.故其通解為4分)an =c1 2n c2 3n.因?yàn)椋?）式無(wú)等于1的特征根，所以遞推關(guān)系an =5anj -6an +n +2(n 2)(2)有特解an = An十B ,其中a和B是待定常數(shù)，代入（2）式得An B =5A(n -1) B - 6A(n - 2) B n 2組合數(shù)學(xué)試題（第 2頁(yè) 共5頁(yè)）化簡(jiǎn)得2An +2B _7A =n +2,所以an = C1 2C22A = 12B7A=2Jn 113 n ,248分)其中g(shù),C2是待定常數(shù)由初始條件得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整除的自然數(shù)的個(gè)數(shù).解：設(shè)A為1至1000的整數(shù)中能被5整除的數(shù)的個(gè)數(shù)；B為1至1000的整數(shù)中能被 6整 除的數(shù)的個(gè)數(shù)；C 為1至1000的整數(shù)中能被 8整除的數(shù)的個(gè)數(shù).則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.設(shè)x0 :=0, xk :=x(x 1)(x k+1), k N , s(n, k), S(n,k)分別為第一、第二 nn類 Stirling 數(shù)，定義為：xn = s(n, k) xk , xn = S(n,k) xk .證明： k=0k=0(1)第二類 Stir

8、ling 數(shù)滿足遞推關(guān)系：S(n+1,k)=S(n,k1) + kS(n,k), n, k 1 ；n0, m = n(2)兩類 Stirling 數(shù)滿足關(guān)系：Z S(n, k) s(k, m)=，.kom1, m=n證明：(1)組合數(shù)學(xué)試題（第 3頁(yè) 共5頁(yè)） 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因?yàn)閤n+ = S(n +1,k)xk，

9、所以比較兩等式的xk的系數(shù)，即得遞推關(guān)系： k OS(n+1,k)=S(n,k 1) + kS(n,k), n, k 之1.,6 分nk(2)因?yàn)?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的系數(shù)，即得：/0, m 二 n工 S(n,k)s(k,m) = 4.,11 分k#1, m = n21.考慮n個(gè)數(shù)a1，a2,，an的乘積aa2a3an ,依據(jù)乘法的結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積.設(shè)pn為n個(gè)數(shù)乘積的n-1對(duì)括號(hào)

10、插入的不同方案數(shù).(1)證明Pn的遞推關(guān)系為：Pn = PPn+ P2Pn/ + PnP1, 52);(2)用母函數(shù)方法證明：Pn =- 2n -2 , (n之2).n n -1 J證明：(1) n個(gè)數(shù)a1, a2，an的乘積的最后一次乘法運(yùn)算是前k個(gè)數(shù)的積與后n - k個(gè)數(shù)的積之間進(jìn)行，其中k =1,2，n -1.前k個(gè)數(shù)可以有Pk種不同的方法加括號(hào)，而后 n-k 個(gè)數(shù)可以用p一種不同的方法加括號(hào).這樣，當(dāng)k取遍1,2，n-什時(shí)，集所有可能性， 于是我們得到Pn = P1 Pn-1 + P2 Pnq + Pn 二 P1 , 5 2 2).,5 分n-1顯然p1=p2=1 ,設(shè)G(x) = pnxn,由遞推公式pn=Epk pn_k,n之2.有n 1k=1組合數(shù)學(xué)試題(第 4頁(yè)共5頁(yè)) 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