2014年組合數(shù)學(xué)試題及答案

1、一、 （10分）用組合意義證明恒等式：n+3k=nk+3nk-1+3nk-2+nk-3證明：考慮對集合a1,a2,an,b1,b2,b3的k-組合計數(shù)可以表示為n+3k，同時該K-組合可以分成如下四類：第一類：從 a1,a2,an 中取k個，再從 b1,b2,b3中取0個；計數(shù)為nk 第二類：從 a1,a2,an 中取k-1個，再從 b1,b2,b3中取1個；計數(shù)為3nk-1第三類：從 a1,a2,an 中取k-2個，再從 b1,b2,b3中取2個；計數(shù)為3nk-2第四類：從 a1,a2,an 中取k-3個，再從 b1,b2,b3中取3個；計數(shù)為nk-3 因此，根據(jù)加法原則該恒等式成立。二、（

2、10分）由2n個人圍成一個圓圈，問有多少種圍法？若從中抽出n個人圍成一圓圈有多少種圍法？(1) (2n-1)!(2) 2n!/n n! 或 2n (2n-1) (n+1)/n三、（10分）設(shè)計從格路平面（0,0）走到（10,5）點，只能沿格路走水平或垂直方向，不可回退，且途徑道路上會有若干蘿卜坑（如圖所示），請問恰巧只經(jīng)過2個坑的格路數(shù)是多少？ 從左到右依次編號為1,2, 3, 4。分類考慮如下： 經(jīng)過1、2的：C(4,2)*(C(7,2)+C(5,2)=186； 經(jīng)過2、3的：(C(6,2)-C(4,2)*C(6,2)=135； 經(jīng)過2、4的：(C(6,2)-C(4,2)*C(5,2)=90

3、； 共有：186+135+90=411四、（10分）有5對父子（共10人）參加“爸爸去哪兒”節(jié)目。一期節(jié)目是“交換爸爸”，即每位父親在節(jié)目中的孩子不是自己的孩子。請問一共有多少種不同的安排方法？解：此題為n=5的錯排問題，也可看做是n=5的有限制排列問題，棋盤多項式如下： RC=1+x5=n=055nxn所以，排列方法數(shù) ：D5=r05!-r14!+r23!-r32!+r4.1!-r5 =5!-54!+103!-102!+5.1!-1 =44五、（10分）設(shè)有兩個隊Q1和Q2，每隊都是30人，其中Q1隊有15名男孩和15名女孩組成，Q2隊男、女孩的人數(shù)不限。這兩隊按序號面對面地站好，如圖所示，

4、然后，Q1隊不動，Q2隊迂回往右錯動，每次依序錯動一個位置。試證明當Q2錯動到某一位置上時，Q1和Q2在對應(yīng)位置上的兩個小孩至少有15對是性別相同的。a 1a2a 3a 29a 30b1b2b 3b 29b 30a 1a2a 3a 29a 30b30b1b 2b 28b 29證明：Q2隊迂回錯動一圈再回到初始狀態(tài)時，每個小孩無論是男孩還是女孩，在對應(yīng)位置上都與Q1隊的15個小孩同性別。故同性別的總對數(shù)為15*30=450。因此，每個錯動位置上同性別的平均對數(shù)為450/30=15。根據(jù)鴿巢原理，必存在某一位置，當Q2錯動到這個位置上時，則性別相同的小孩至少有15對。六（10分）設(shè)有N條封閉曲線畫

5、在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。解：令an為n條封閉曲線把平面分割成的區(qū)域個數(shù)。若n-1條封閉曲線把平面分割成的區(qū)域個數(shù)為an-1,則第n條封閉曲線與這n-1條封閉曲線相交于2（n-1）個點，這2（n-1）個點把第n條封閉曲線截成2（n-1）段弧，這些弧把原來的2（n-1）個區(qū)域中的每個區(qū)域一分為二，故新增加的區(qū)域個數(shù)為2（n-1）。所以，滿足如下的遞歸關(guān)系： an=an-1+2n-1,a1=2, 解該遞歸關(guān)系得：an=n2-n+2七（10分）面包店出售豆沙餡、椰蓉餡，果醬餡三種面包，小紅到面包店時剛好有3個豆

6、沙餡，2個椰蓉餡，2個果醬餡面包出爐，小紅帶的食品袋正好可以裝下5個面包，那么小紅購買5個面包共有多少種不同的購買方案呢？解：該組合問題的母函數(shù)為Gx=1+x+x2+x3.(1+x+x2)2對上述母函數(shù)進行展開合并，得到x5的系數(shù)為6故，共有6種購買方案。八（10分）今安排5位女士和17位男士圍圓桌而坐（22個座位均已編號），使得任何兩位女士之間至少有3位男士，求有多少種不同的安排座位的方案？解：先任選一位女士，記為，則可依如下步驟安排座位：1 安排入座，有22種方法； 2 安排其他4位女士入座，使得任何兩位女士之間至少有3個空座位。設(shè)由開始按逆時針順序，5位女士依次為，且與之間有個空位，與之

7、間有個空位，則且 ，設(shè)為該式中滿足條件的整數(shù)解個數(shù)，則完成本步驟的方法共有種。 因為是 展開式中的系數(shù)，而 所以完成本步驟的方法有：種。3 安排17位男士入座共有17！種方法； 綜合上述三個步驟，由乘法法則得：不同的安排座位的方法數(shù)共有： 九（10分）用紅、白、藍三色珠子穿成一條長度為n的珠串，要求藍色珠子的個數(shù)為偶數(shù)，問滿足條件的長度為n的珠串有多少種穿法？（用母函數(shù)法）解：該排列問題的母函數(shù)為：Gx=(1+x+x22!+x33!+)2.1+x22!+x44!+ =e2xex+e-x2=e3x+ex2=123n+1xnn! 所以方法數(shù)為：an=(3n+1)/2十.（10分）設(shè)用三種顏色對一個五角星的五個區(qū)域著色，求在允許旋轉(zhuǎn)和翻轉(zhuǎn)的情況下,有多少種不同的染色方案？解：該問題可以用波利亞定理求解，共