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

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

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

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

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

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

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

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