(完整版)組合數(shù)學試題集

1、組合數(shù)學試題集一.簡單題目可以根據(jù)需要改成選擇題或者填空題1在1到9999之間，有多少個每位上數(shù)字全不相同而且由奇數(shù)構成的整數(shù)？參見課本21頁)解：該題相當于從“1，3，5，7，9”五個數(shù)字中分別選出1，2，3，4作排列的方案數(shù)；(丄)選i個，即構成i位數(shù)，共有pi個；5選2個，即構成兩位數(shù)，共存2個；5選3個，即構成3位數(shù)，共有P3個；5選4個，即構成4位數(shù)，共有P4個；5由加法法則可知，所求的整數(shù)共有：i+P2+P3+P4二205個。55552一教室有兩排，每排8個座位，今有14名學生，問按下列不同的方式入座，各有多少種做法？(參見課本21頁)各類入座方式互相不同，由加法法則，總的入座方式

2、總數(shù)為：C(14,6)P(8,6)P(8,8)+C(14,7)P(8,7)P(8,7)+C(14,8)P(&8)P(8,6)二104613949440003一位學者要在一周內(nèi)安排50個小時的工作時間，而且每天至少工作5小時問共有多少種安排方案？（參見課本21頁）解：用x表示第j天的工作時間，i二1,2,L,7，則問題轉化為求不定方程ix+x+x+x+x+x+x=50的整數(shù)解的組數(shù)，且5，于是又可以轉化為求1234567i不定方程y+y+y+y+y+y+y二15的整數(shù)解的組數(shù)。1234567該問題等價于：將15個沒有區(qū)別的球，放入7個不同的盒子中，每盒球數(shù)不限，即相異元素允許重復的組合問題。故安

3、排方案共有：RCS,15）=C（15+7-1,15）=54264（種）另解：因為允許y二0，所以問題轉化為長度為的15條線段中間有14個空，再加上前后兩i個空，共16個空，在這16個空中放入6個“”號，每個空放置的“”號數(shù)不限，未放”號的線段合成一條線段，求放法的總數(shù)。從而不定方程的整數(shù)解共有：RC6)=C(16+61,6)=54264(組)21x20 x19x18x17x166x5x4x3x2x1即共有54264種安排方案。4求下列函數(shù)的母函數(shù)：n（n-1）；（參見課本51頁）母函數(shù)為：TOC o 1-5 h z&頭2x2x2x2G(x)=n(n一1)xn=n(n+1)x一2nx=一=(1-

4、x)3(1-x)2(1-x)3n=0n=0n=0方法二：G(x)=藝n(n-1)xn=0+0+x2藝n(n-1)xn-2n=0n=2=x2藝(n+2)(n+1)xn=x2藝C+2)=x2IXxn+2n=0 x211-x丿n=0n=02x2(1-x)35求下列函數(shù)的母函數(shù):n(n+2)；(參見課本51頁)x3x一x2+=(1-x)3(1-x)2(1-x)3母函數(shù)為：G(x)=Sn(n+2)xn=Sn(n+1)xn+Snxn=n=0n=0n=0方法二：G(x)=藝n(n+2)xn=藝(n+1)(n+2)xn一藝(n+1)x0=n=X-12+nx11nxX-1-丿x-1X-1-=X-1-=6利用遞推

5、關系求下列和：S=Snk(k+2)(參見課本第92頁)nk=0顯然，S-S=n(n+2),nn-1同理對應的齊次方程的特征根為，特解為廠=A(1=A,n非齊次方程的特解為：S*=n(Bn2+Cn+D)=Bn3+Cn2+Dn,n所以，非齊次方程的通解為:S=Bn3+Cn2+Dn+A，n初始條件為：S=0,S=3,S=11,S=26，代入上式，可得0123S=A=0，S=B+C+D+A=3，S=8B+4C+2D+A=11，012137S=27B+9C+3D+A=26，解得：A=0，B=-，C=-，D=-TOC o 1-5 h z326所以Sn=-3+2n2+6n=n(n+1)(2n+-)方法二顯然

6、，S-S=n(n+2)，類似可得,S-S=(n-1)(n+1)，nn-1n-1n-2兩式相減得S-2S+S=2n+1，nn-1n-2同理可得S-2S+S二2(n-1)+1，兩式再相減得n-1n-2n-3S-3S+3S-S二2，同理得S-3S+3S-S二2,nn-1n-2n-3n-1n-2n-3n-4兩式再相減，可得關于S的齊次定解問題：nS-4S+6S-4S+S二0nn-1n-2n-3n-4S二0,S二3,S二11,S二260123由(丄)知，方程的通解為：S二A+Bn+Cn+Dn，代入初始條件得:nS二A二0，S二A+B+C+D二3，S二A+2B+4C+8D二11，012731S3二A+3B

7、+9C+27D二26，解得：A二0，B二6,C=2,D=3731n(n+1)(2n+7)故S_n+n2+n3_TOC o 1-5 h zn623方法三(快速求系數(shù))通解為：S初始條件：3!代入得_A+An+AP+An(n-1)(n-2)0122!3S二0,S二3,S二11,S二26，01+A=3，01A+2A+A二11，012A+3A+3A+A二26，0123解得：所以，A=0，A=3，A=5，A=201233!S=3n+5n(n-1)十？n(n-1)(n-2)_n(n+1)(2n+7)n_32!7利用遞推關系求下列和：S_k(k+1)(k+2)(參見課本第92頁)nk_0顯然，S-S_n(n

8、+1)(n+2)，nn-1同理對應的齊次方程的特征根為，特解為廠_A(1_A，n非齊次方程的特解為：S*_n(Bn3+Cn2+Dn+E)_Bn4+Cn3+Dn2+En,n所以，非齊次方程的通解為:S_Bn4+Cn3+Dn2+En+A，n初始條件為：S_0,S_6,S_30,S_90,S_210，代入上式，可得01234S二A二0,S二B+C+D+E+A二6,S二16B+8C+4D+2E+A二30,012S二81B+27C+9D+3E+A二90,S二256B+64C+16D+4E+A二21034解得：A二0,B=-,C=-,D=11,E=-2423113n(n+l)(n+2)(n+3)所以S=n

9、4+n3+n2+n=n4242方法二n一1n-2顯然，S-S=n(n+l)(n+2)，類似可得,S-S=n(n-l)(n+1),nn一1兩式相減得S-2S+S=3n(n+1),nn一1n一2同理可得S-2S+S=3n(n-1)，兩式再相減得n一1n一2n一3S-3S+3S-S=6n，同理得S-3S+3S-S=6(n-1),nn-1n一2n-3n-1n一2n-3n一4TOC o 1-5 h z兩式再相減得S-4S+6S-4S+S=6，nn-1n-2n-3n-4同理可得S-4S+6S-4S+S=6，n-1n-2n-3n-4n-5兩式再相減，可得關于S的齊次定解問題：nS-5S+10S-10S+5S

10、-S=0nn-1n-2n-3n-4n-5S=0,S=6,S=30,S=90,S=21001234其特征方程為：x5-5x4+10 x3-10 x2+5x-1=0，x=1是五重特征根,所以方程的通解為：S=A+Bn+Cn2+Dn3+En4，代入初始條件得：nS=A=0，S=A+B+C+D+E=6，S=A+2B+4C+8D+16E=30，012S=A+3B+9C+27D+81E=90，S=A+4B+16C+64D+256E=210，34解得：A=0,B=,C=U,D=,E=，TOC o 1-5 h z4241131n(n+1)(n+2)(n+3)故S=n+n2+n3+n4=n24244方法三(快速

11、求系數(shù))通解為：S=A+An+人叢+An(n一1)(n一2)+An(n一1)(n一2)(n一3),n0122!33!44!初始條件：S=0,S=6,S=30,S=90,S=210，代入得01234A二0,A+A二6,A+2A+A二30,A+3A+3A+A二90,0010120123A+4A+6A+4A+A二21001234解得：A=0,A=6,A=18,A=18,A=601234S=6n+18n(n-1+丄n(nl)(n2)十&n(n_l)(n_2)(n_3)n2!3!4!所以_n(n+1)(n+2)(n+3)48.求從1到500的整數(shù)中能被3和5整除但不能被7整除的數(shù)的個數(shù)。（參見課本123

12、）解：設A為1到500的整數(shù)中能被i整除的數(shù)的集合，i_3,5,7,5003x5x7lA3A5AJ_i_50033，|AA|_500_23，|AA|_5003x5373x7*57*L5x7J3則|A_|50|_166,|AJ_|甞卜100,也|_1501_71,14，4，|A3A5滿足條件的整數(shù)個數(shù)為：AAA，根據(jù)容斥原理有:357_334_29AAA_|AA|AAA|35713V135719某人參加一種會議，會上有6位朋友，他和其中每一人在會上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，與六人都相遇1次，一人也沒遇見的有5次。問該人共參加幾次會議？（

13、參見課本123）解：設S為該人參加的所有會議組成的集合，設A表示該人與第i個朋友相遇的所有會議構成的子集，i_1,2,L,6，則i=|A|=12,i=1,2,L,6=6,R=AAAijkR1iR=|AAR=IAAAAAAij=1，=4,R=AAAA=3,R=AAAAA5123456|A+A+A+A+A+AI123456=C1RC2R+C3RC4R+C5RC6R6則，61626364656=6x1215x6+20 x415x3+6x21次）。=28則該人共參加會議次數(shù)為：|S|=28+5=3310.n位的四進制數(shù)中，數(shù)字1,2,3各自至少出現(xiàn)一次的數(shù)有多少個？（參見課本123）解：設S表示所有n

14、位四進制數(shù)構成的集合，A為不出現(xiàn)i的數(shù)的集合，i=1,2,3，i則|AI=|AI=|AI=3n，|AA=AA=|AATOC o 1-5 h z121r11213123則由逐步淘汰原理，可得AgAgA=|S|(A+|A|+|A|)+(AA|+AA+|AAI)|AAAI23II1I2丨I3I111312r11231=4n3n+1+3x2n111.一次考試采用百分制，所有考生的總分為10101，證明如果考生人數(shù)不少于202，則必有三人得分相同。（參見課本145）證明：采用百分制，則所有可能的分數(shù)為0100，共101個分數(shù)，現(xiàn)人數(shù)不少于202，則平均每個分數(shù)有兩個人得分相同。分情況討論：（1）若有某些

15、分數(shù)沒有考生得該分數(shù)，則202名考生，可能的考生成績最多100種，根據(jù)抽屜原理，必有三個的得分相同。（2）若有1個考生的分數(shù)與其他人都不同，則其余201名考試可能的分數(shù)只有100種，則必有三人的得分相同。（3）若每個分數(shù)線都有兩個人，則所有考生的總分為：2（1+2+L+100）=10100，與題目矛盾。所以這種情況不可能存在。綜上所述，必有三人得分相同。證畢。方法二：反證法。假設沒有三個考生考試成績相同因為分數(shù)的分布為）100分，共101種分數(shù)，若考生人數(shù)大于202人，則根據(jù)抽屜原理必然有三人考試成績相同，矛盾；若考生人數(shù)恰好202個，要求沒有三個考生考試成績相同，則所有考生必然恰好兩兩得分相

16、同。而此時所有考生的總分為：(0+1+2+L+100)=10100，矛盾。故結論成立。12.一張卡片分成4X2個方格，每格用紅藍兩色涂染，可有多少種方法？(參見課本176)參考修改意見：把紅藍色改成其他顏色解：如圖所示將卡片的八個格進行編號，則對應集壽1,2,L,8，用紅藍兩色12345678涂染，卡片只能旋轉不能翻轉,則可得S上的置換群Q=p,p，12其中，p=(1)(2)(3)(4)(5)(6)(7)(8)，p=(18)(27)(36)(45)，12現(xiàn)在用兩種顏色進行涂染，則不同的涂染方案有：L=1(28+24)=136(種)若卡片還能翻轉，但同一個格子對應的正反面要求同色，則除了上述兩個

17、置換外，還有沿著橫、豎兩個對稱軸翻轉的置換p=(17)(28)(35)(46)，p=(12)(34)(56)(78)34從而可知不同的染色方案有：L=1(28+24x3)=76(種)24若同一個格子對應的正反面不要求同色，且卡片既能旋轉，又能翻轉則相應的置換為：q=(1)(2)L(8)(A)(B)L(H)，q=(18)(27)(36)(45)(AH)(BG)(CF)(DE)q=(1G)(2H)(3E)(4F)(5C)(6D)(7A)(8B)，3q=(1B)(2A)(3D)(4C)(5F)(6E)(7H)(8G)4其中A,B,L,H是卡片的背面分別依序與,2丄,8對應的格子。那么，此時的染色方案

18、有L=1(216+28x3)=16576(種)3413一根木棍等分成n段，用m種顏色涂染，問有多少種染法？(參見課本176)參考修改原則：當n=m=2和n=m=3時各有多少種方法?12n-1n解：如圖給木棍的每段依次編號為2,L,n，則對應集合S二1,2,L,n，用m中顏色進行涂染，當n為偶數(shù)時，可得5上的置換群Q二p,p，其中12p二(1)(2)L(n)，p=(1n)(2n-1)L(-+1)，(木棍只能翻轉180。)1222用m種顏色進行涂染，則不同的染色方案有：=1(mn+m；)；當n為奇數(shù)時，可得S上的置換群Q二p,p，其中13n-1n-1n+1p=(1n)(2n-1)L(+2)()，3

19、222則不同的染色方案有：L=(mn+m羅)。22綜上所述，不同的染色方案有:：=(mn+mLI)。2當n=m=2時，不同的染色方案有：L=1(22+21)=312當n=m=3時，不同的染色方案有：L=1(33+32)=182214.一個圓分成6個相同的扇形，分別涂以三色之一，可有多少種涂法?(參見課本176)解：如圖所示，用三個顏色對圓的六個扇形進行涂染，圓可以繞其圓心逆時針旋轉0o,60o,120o,180o,240o,300。，于是可以得到置換群3所包含的置換如下：6534p=(1)(2)(3)(4)(5)(6)，p=(123456)，12p=(135)(246)，p=(14)(25)(

20、36)，34p=(153)(264)，p=(654321)，56根據(jù)Polya定理，則不同的染色方案有：L=1(36+2x31+2x32+33)=130(種)三應用題1比5400小并具有每位的數(shù)字全不同的正整數(shù)有多少個？參見課本21頁）解：（1）比5400小且每位數(shù)字全不同的正整數(shù)：按正整數(shù)的位數(shù)可分為以下幾種情況：一位數(shù)，可從19中任取一個，共有個；兩位數(shù)。十位上的數(shù)可從19中選取，個位數(shù)上的數(shù)可從其余個數(shù)字中選取,根據(jù)乘法法則，共有9x9二81個；三位數(shù)。百位上的數(shù)可從9中選取，剩下的兩位數(shù)可從其余個數(shù)中選2個進行排列，根據(jù)乘法法則，共有xP2二648個;9四位數(shù)。又可分三種情況：千位上的

21、數(shù)從14中選取，剩下的三位數(shù)從剩下的個數(shù)字中選B個進行排列，根據(jù)乘法法則，共有xP3二2016個;9千位上的數(shù)取5,百位上的數(shù)從1B中選取，剩下的兩位數(shù)從剩下的個數(shù)字中選2個進行排列，共有xP2二168個;8千位上的數(shù)取5,百位上的數(shù)取0,剩下的兩位數(shù)從剩下的?個數(shù)字中選2個進行排列，共有P2二56個;8根據(jù)加法法則，滿足條件的正整數(shù)共有9+81+648+2016+168+56二2978個；2比5400小并具有每位數(shù)字不同且不出現(xiàn)數(shù)字2與7的正整數(shù)有多少個？（參見課本21頁）按正整數(shù)的位數(shù)可分為以下幾種情況：設二0,1,3,4,5,6,8,9一位數(shù)，可從A-0中任取一個，共有7個；兩位數(shù)。十位

22、上的數(shù)可從A-0中選取，個位數(shù)上的數(shù)可從中其余7個數(shù)字中選取，根據(jù)乘法法則，共有x7二49個；三位數(shù)。百位上的數(shù)可從-0中選取，剩下的兩位數(shù)可從其余7個數(shù)中選2個進行排列，根據(jù)乘法法則，共有xP2二294個;7四位數(shù)。又可分三種情況：千位上的數(shù)從1,S4中選取，剩下的三位數(shù)從中剩下的7個數(shù)字中選3個進行排列，根據(jù)乘法法則，共有xP3二630個;7千位上的數(shù)取5,百位上的數(shù)從9,1,3中選取，剩下的兩位數(shù)從中剩下的6個數(shù)字中選2個進行排列，共有xP2二90個;6根據(jù)加法法則，滿足條件的正整數(shù)共有7+49+294+630+90二1070個;3.投擲兩個骰子，點數(shù)之和為r（2.rW，其組合數(shù)是多少?

23、參見課本51頁）解：用Xi表示骰子的點數(shù)為，（1）若兩個骰子不同，則問題等價于的特殊有序2-分拆r二r+r2121r6,i=1,2Vi故相應的母函數(shù)為G(x)二(X+X2+X3+X4+X5+X6)2二X2+2X3+3x4+4X5+5X6+6X7+5X8+4X9+3x10+2X11+X12則點數(shù)之和為r的方案總數(shù)就是Xr的系數(shù)（2rrr112而此問題又可轉化為求的最大分項等于2,且項數(shù)不超過6的分拆數(shù),廠1-X+2-X二r即求方程212的非負整數(shù)解的個數(shù)。X0,X1,X+X1時，（參見課本第92頁）(1)F2-FF二(l)nn+1nn+2用數(shù)學歸納法：n二1時，F(xiàn)2-FF二12-lx2=1，命題

24、成立；13n二2時，F(xiàn)2-FF二22-1x3二1，命題成立；24假設當n二k時，命題成立，即F2FF=(-1)k,k+1kk+2當n=k+1時，F(xiàn)2-FF二F(F+F)-F(F+F)k+2k+1k+3k+2kk+1k+1k+1k+2二FFF2=-(一1)k二(-1)k+1kk+2k+1所以，n二k+1時，命題也成立；由歸納原理知，命題成立。.方法二F2-FFn+1n+22n+21lf1+V5)n+1n+11|仃+75n+2仃-75n+2n+1-22n+2仃-75175n+1n+2+(-1)n=(-1)n仃-巧2n+2n+2仃-752n+2357357=500=33，|AA|=500=23，|A

25、A|=5003x513713x71571L5x7J二14，lA3A5I二100，IAJ彳孕卜71,lA3A5AJ二5003x5x75證明Fibonacci數(shù)列的性質(zhì)，當n1時，nF+(n一1)F+L+2F+F=F-(n+3)(參見課本第92頁)12n1nn14證明：采用數(shù)學歸納法。n=1時，F(xiàn)=1=5(1+3)=F(1+3)，命題成立；15n二2時，2F+F二3二8(2+3)=F(2+3)，命題成立；126假設n二k時，命題成立，艮即F+(k1)F+L+2F+F二F(k+3),12k1kk+4當n=k+1時，(k+1)F+kF+(k1)F+L+2F+F123kk+1=LkF+(k1)F+L+2

26、F+FJ+Lf+F+L+F+FJ12/kk12kk+1=(F(k+3)+(F1)k+4k+3=F(k+4)k+5即n二k+1時，命題也成立，根據(jù)歸納法，命題成立。6求從1到500的整數(shù)中能被3和5整除但不能被7整除的數(shù)的個數(shù)。（參見課本第123）解：設A為1到500的整數(shù)中能被i整除的數(shù)的集合，i=3,5,7，i500II500丁卜166，旳=|丁滿足條件的整數(shù)個數(shù)為：AAA，根據(jù)容斥原理有:57AAA=|AAI|AAA1=334=29357353577某學生準備恰好用11個星期時間做完數(shù)學復習題，每天至少做一題，一個星期最多做12題，試證必有連續(xù)幾天內(nèi)該學生共做了21道題。（參見課本第145）證明：11個星期總共有77天，每天做的題數(shù)設為（i二1,2,L,77）,i則a1,a+a+L+a12,k=0,1,L,70,TOC o 1-5 h zik+1k+2k+7構造序列s=a，則1ssLs132,ij1277j=1若存在某個s=21，則問題得證。k否則，所有的s豐21，令集合A=s,s,L,s,s+21,s+21,L,s+21，i12771277貝9有22s+21s+21Ls+21i，ki故21=s-s=丈a。證畢。kijj=i+18證明任意給定的52個整數(shù)中，總存在兩個數(shù)它們的和或