組合數(shù)學(xué)(西安電子科技大學(xué)(第二版))習(xí)題1

習(xí)題一習(xí)題一（排列與組合）1．在1到9999之間，有多少個(gè)每位上數(shù)字全不相同而且由奇數(shù)構(gòu)成的整數(shù)？解：該題相當(dāng)于從“1，3，5，7，9”五個(gè)數(shù)字中分別選出1，2，3，4作排列的方案數(shù)；（1）選1個(gè)，即構(gòu)成1位數(shù)，共有個(gè)；P15（2）選2個(gè)，（3）選3個(gè)，（4）選4個(gè)，由加法法則可知，即構(gòu)成兩位數(shù)，共有個(gè)；P25即構(gòu)成3位數(shù)，共有P個(gè)；35即構(gòu)成4位數(shù)，共有P個(gè)；45所求的整數(shù)共有：PP2P3P4205個(gè)。155552．比5400小并具有下列性質(zhì)的正整數(shù)有多少個(gè)？（1）每位的數(shù)字全不同（2）每位數(shù)字不同且不出現(xiàn)數(shù)字2與7；1）比5400小且每位數(shù)字全不同的；解：（正整數(shù)；按正整數(shù)的位數(shù)可分為以下幾種情況：①一位數(shù)，②兩位數(shù)字中選取，③三位數(shù)1～9中選取，剩下的兩位數(shù)中選2個(gè)進(jìn)行排列，④四位數(shù)千位上的數(shù)從3個(gè)進(jìn)行排列，千位上的數(shù)取5，百位上的數(shù)從8個(gè)數(shù)字中選2個(gè)進(jìn)行排列，共有可從1～9中任取一個(gè)，共有1～9中選取，個(gè)位數(shù)上的數(shù)9981個(gè)；可從其余9個(gè)數(shù)9P648個(gè)；9個(gè)；。十位上的數(shù)可從可從其余9個(gè)數(shù)根據(jù)乘法法則，共有。百位上的數(shù)可從根據(jù)乘法法則，共有29。又可分三種情況：1～4中選取，剩下的三位數(shù)從剩下的9個(gè)數(shù)字中選根據(jù)乘法法則，共有4P2016個(gè)；391～3中選取，剩下的兩位數(shù)從剩下的3P168個(gè)；28取5，百位上的數(shù)取4，剩下的兩位數(shù)從剩下的8個(gè)數(shù)千位上的數(shù)字中選2個(gè)進(jìn)行排列，共有P56個(gè)；28根據(jù)加法法則，滿足條件的正整數(shù)共有：9816482016168562978個(gè)；（2）比5400小且每位數(shù)字不同且不出現(xiàn)數(shù)字2與7的正整數(shù)可分為以下幾種情況：設(shè)A{0,1,3,4,5,6,8,9}A{0}中任取一個(gè)，共有7個(gè)；；按正整數(shù)的位數(shù)①一位數(shù)，可從第1頁(yè)（共10頁(yè)）習(xí)題一②兩位數(shù)。十位上的數(shù)可從{0}中選取，個(gè)位數(shù)上的數(shù)可從A中其余7A個(gè)數(shù)字中選取，根據(jù)乘法法則，共有7749個(gè)；③三位數(shù)。百位上的數(shù)可從{0}中選取，剩下的兩位數(shù)可從A其余7AP294個(gè)；2個(gè)進(jìn)行排列，根據(jù)乘法法則，共有727個(gè)數(shù)中選④四位數(shù)。又可分三種情況：千位上的數(shù)從1，3，4中選取，剩下的三位數(shù)從A中剩下的7個(gè)630個(gè)；數(shù)字中選3個(gè)進(jìn)行排列，根據(jù)乘法法則，共有3P37千位上的數(shù)取5，百位上的數(shù)從0，1，3中選取，剩下的兩位數(shù)從A中剩下的6個(gè)數(shù)字中選2個(gè)進(jìn)行排列，共有3P90個(gè)；26749294630901070個(gè)；根據(jù)加法法則，滿足條件的正整數(shù)共有：3．一教室有兩排，每排8個(gè)座位，今有14名學(xué)生，問按下列不同的方式入座，各有多少種做法？（1）規(guī)定某5人總坐在前排，某4人總坐在后排，但每人具體座位不指定；（2）要求前排至少坐5人，后排至少坐4人。解：（1）因?yàn)榫妥怯写涡虻?，所有是排列問題。5人坐前排，其坐法數(shù)為P(8,5)，4人坐后排，其坐法數(shù)為5個(gè)人在其余座位的就坐方式有P(7,5)種，P(8,4)，剩下的根據(jù)乘法原理，就座方式總共有：P(8,5)P(8,4)P(7,5)28449792000（種）（2）因前排至少需坐6人，最多坐8人，后排也是如此?？煞殖扇N情況分別討論：①前排恰好坐②前排恰好坐③前排恰好坐6人，入座方式有C(14,6)P(8,6)P(8,8)；C(14,7)P(8,7)P(8,7)；C(14,8)P(8,8)P(8,6)；7人，入座方式有8人，入座方式有各類入座方式互相不同，由加法法則，總的入座方式總數(shù)為：C(14,6)P(8,6)P(8,8)C(14,7)P(8,7)P(8,7)C(14,8)P(8,8)P(8,6)10461394944000典型錯(cuò)誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個(gè)座C(14,6)P8,6C(8,4)P8,4P6,4種。但這樣計(jì)算無疑是有重復(fù)的，例如恰好選位。故總的入坐方式共有：6人坐前排，其余8人全坐后排，那么上式中的C(8,4)P8,4就有重復(fù)。第2頁(yè)（共10頁(yè)）習(xí)題一4．一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間，而且每天至少工作5小時(shí)，問共有多少種安排方案？解：用x表示第i天的工作時(shí)間，1,2,,7，則問題轉(zhuǎn)化為求不定方程iixxxxxxx50的整數(shù)解的組數(shù)，且567iyyyyyyy15的整數(shù)解的組數(shù)。1234567x5，于是又可以轉(zhuǎn)1234化為求不定方程該問題等價(jià)于：將15個(gè)沒有區(qū)別的球，放入7個(gè)不同的盒子中，每盒球數(shù)不限，即相異元素允許重復(fù)的組合問題。故安排方案共有：RC(,15)C(1571,15)54264（種）另解：y0，所以問題轉(zhuǎn)化為長(zhǎng)度為因?yàn)樵试Si加上前后兩個(gè)空，共16個(gè)空，在這1的15條線段中間有14個(gè)空，再16個(gè)空中放入6個(gè)“＋”號(hào)，每個(gè)空放置的“＋”號(hào)數(shù)不限，未放“＋”號(hào)的線段合成一條線段，求放法的總數(shù)。從而不定方程的整數(shù)解共有：RC(,6)C(1661,6)21201918171654264（組）654321即共有54264種安排方案。5．若某兩人拒絕相鄰而坐，問12個(gè)人圍圓周就坐有多少種方式？CP(12,12)11!種，甲和乙，將這兩個(gè)CP(11,11)10!種；由于甲乙相鄰而也可能是“乙甲”；所以則滿足條件的就坐方11!210!32659200種。解：12個(gè)人圍圓周就坐的方式有：設(shè)不愿坐在一起的兩人為人相鄰而坐，可看為1人，則這樣的就坐方式有：坐，可能是“甲乙”式有：6．有15名選手，其中5名只能打后衛(wèi)，8名只能打前鋒，2名只能打前鋒或后衛(wèi)，今欲選出11人組支球隊(duì)，而且需要7人打前鋒，4人打后衛(wèi)，試問選法？A、B、C分別代表5名打后衛(wèi)、8名打前鋒、2名可打前鋒或后衛(wèi)的集合，分為以下幾種情況：（1）7個(gè)前鋒從B中選取，有C種選法，根據(jù)乘法法則，這種選取方案有：成一有多少種解：用則可4個(gè)后衛(wèi)從A中選取，有C種，4578CC4種；785（2）7個(gè)前鋒從B中選取，從A中選取3名后衛(wèi)，從C中選1名后衛(wèi)，根據(jù)乘法法則，這種選取方案有：CCC1種；78352（3）7個(gè)前鋒從B中選取，從A中選取2名后衛(wèi)，C中2名當(dāng)后衛(wèi)，根據(jù)乘法法則，這種選取方案有：CC2種；785第3頁(yè)（共10頁(yè)）習(xí)題一（4）從B中選6個(gè)前鋒，從C中選1個(gè)前鋒，從A中選4個(gè)后衛(wèi)，根據(jù)乘法法則，這種選取方案有：種；CCC468125（5）從B中選6個(gè)前鋒，從C中選1個(gè)前鋒，從A中選3個(gè)后衛(wèi)，C中剩下的一個(gè)當(dāng)后衛(wèi)，選取方案有：種；5CCC68123（6）從B中選5個(gè)前鋒，C中2個(gè)當(dāng)前鋒，從A中選4個(gè)后衛(wèi)，選取方案有：種；CC5485根據(jù)加法法則，總的方案數(shù)為：CC4CCC1CC2CCC4CCC3CC414007878357868126812585255557．求xyzw2項(xiàng)的系數(shù)。(xy2zw)8展開式中222令ax,by,c2z,dw，則8解：(abcd)8中a2b2c2z2項(xiàng)的系數(shù)為8!22222!2!2!2!27，!即(xy2zw)8中，x(y)2(2z)2w2的系數(shù)，2因此，xyzw的系數(shù)為：7!2(1)2(2)210080。22228．求n4,t3，展開式共有44(xyz)4的展開式。解：RC(,4)C(431,4)15（項(xiàng)），所以，444(xyz)4xyzxyxz33014443400040004310444xyxzx211yz222222202024444xyxyzxy3xz322z130103112121444yz22022yz3yz3013031x4y4z44x3y4x3z4xy34xz34yz34y3z6x2y26x2z26y2z212x2yz12xyz212xy2z9．求xxx的系數(shù)。(xxxxx)10展開式中36123452341010!解：xxx6的系數(shù)為：8403234031603!1!6!11．證明nC(n1,r)(r1)C(n,r1)，并給出組合意義。第4頁(yè)（共10頁(yè)）習(xí)題一,)，現(xiàn)令，，則可得kr1l1證明：因?yàn)镃(n,k)C(k,l)C(n,l)C(nlkl，即(1,)(1)(,1)C(n,r1)C(r1,1)Cn(,C1)n(rnCnrrCnr組合意義：將n個(gè)元素分為3堆，1堆1個(gè)元素，1堆r個(gè)元素，1堆nr1個(gè)元素?？梢杂邢旅鎯煞N不同的分法：（1）先從nr1n個(gè)元素中選出r1個(gè)元素，剩下的個(gè)作為堆；再將1選出的r1個(gè)元素分為兩堆，1堆1個(gè)，1堆r個(gè)。（2）先從n個(gè)元素中選出1人作為1堆，再?gòu)氖Ｏ碌膎1個(gè)中選出r個(gè)作為1堆，剩下的1作為堆。nr1顯然，兩種分法是等價(jià)的，所以等式成立。12．證明kC(n,k)n2。nn1k1證明：采用殊途同歸法。組合意義一：考慮從n個(gè)人中選出1名正式代表和若干名列席代表的選法（列席代表人數(shù)不限，可以為0）?？梢杂幸韵聝煞N不同的選法：（1）先選定正式代表，有Cn種選法；然后從n1人中選列席代表，這n11n個(gè)人都有選和不選的兩種狀態(tài)，共有2種選法；n1根據(jù)乘法法則，共有n2n1（2）可以先選出k1(k0,1,2,,n1)人，然后再?gòu)闹羞x出k人作為列席代表，對(duì)于每個(gè)k，這樣的選法有：CC，種選法；1名正式代表，其余k11k1nn1nn從而總選法有：C(n,k1)C(k1,1)C(n,k)C(k,1)kC(n,k)k0k1k1顯然，兩種選法是等價(jià)的，所以等式成立。組合意義二：將n個(gè)不同的球放入標(biāo)號(hào)為A、B、C的3個(gè)盒子，其中要求A盒只放1個(gè)球，其余兩盒的球數(shù)不限。那么，有兩種不同的放法：（1）先從n個(gè)不同的球中選出1個(gè)，放入A盒，再將其余另n1個(gè)球放入外兩盒，有C2n2n1種放法；1n1n（2）先從n個(gè)球中選出k個(gè)(k1,2,,n)，再?gòu)乃x的k個(gè)球中選出C盒，1個(gè)放入A盒，將其余的k1個(gè)球放入B盒，剩下的nk個(gè)球放入根據(jù)乘法法則，對(duì)于不同的k，有CCCnkkCk種放法。k1nknkn當(dāng)k1,2,,n時(shí)，各種情況互不重復(fù)，且包含了所有放法，第5頁(yè)（共10頁(yè)）習(xí)題一n根據(jù)加法法則，總的放法有：kC(n,k)。k1顯然兩種放法是等價(jià)的，故等式成立。另法：根據(jù)二項(xiàng)式定理：(1x)n1C(n,1)xC(n,2)x2C(n,n1)xn1C(n,n)xn，兩邊求導(dǎo)，得：n(1x)C(n,1)C2n(,x2)n(C1)nn(,x1)nCn(n,x)，n1n2n1令x1，即得kC(n,k)n2n1nk114．六個(gè)引擎分列兩排，要求引擎的點(diǎn)火次序兩排交錯(cuò)開來，試求從某一特定引擎開始點(diǎn)火有多少種方案？解：第一次點(diǎn)火僅有一種選擇，即點(diǎn)某個(gè)特定引擎的火；第二次點(diǎn)另一組某個(gè)引2種,??。13221112（種）擎的火，有三種選擇；第三次有所以方案數(shù)為：如果只指定從第一排先開始點(diǎn)火，不指定某一個(gè)，則方案數(shù)為33221136（種）如果第一個(gè)引擎任意選，只要求點(diǎn)火過程是交錯(cuò)的，則方案數(shù)為632211（7種）16．n個(gè)男n個(gè)女排成一男女相間的隊(duì)伍，試問有多少種不同的方案？若圍成一圓桌坐下，又有多少種不同的方案？解：排成男女相間的隊(duì)伍：先將n個(gè)男的排成1行，共有P種排法；nn再將n個(gè)女的往n個(gè)空里插，有P種排法；由于可以先男后女，也可以先nn女后男，因此共有n2P種排法；n根據(jù)乘法法則，男女相間的隊(duì)伍共有：2PPn2n!n!種方案。nnn若圍成一圓周坐下，同理先將n個(gè)男的圍成一圓周，共有CP(n,n)種排法，再將n個(gè)女的往n個(gè)空中插，有P種排法，nn根據(jù)乘法法則，圍成圓周坐下，總的方案數(shù)有：CP(n,n)Pnn!(n1)!種。n17．n個(gè)完全一樣的球，放到r個(gè)有標(biāo)志的盒子，nr，要求無一空盒，第6頁(yè)（共10頁(yè)）習(xí)題一n1試證其方案數(shù)為。r1個(gè)球，再將剩余的nr球放入r個(gè)盒子中，沒有空盒，可先每盒放入一證明：因?yàn)榧磳r個(gè)無區(qū)別的球，放入r個(gè)不同的盒子中，每盒的球數(shù)不受限制，(1,1)。因此方案數(shù)有：(1,)(1,)CrnrnrCnnrCnr另法：插空法。：n個(gè)球排成1行，球與球之間形成n1個(gè)空，再在這n1個(gè)空中，插入r1個(gè)隔板，這樣就可形成r個(gè)盒子，每盒球不空的方案，其方案(1,1)。問題可看為Cnr數(shù)為18．設(shè)npppk，p,p,,p是k個(gè)素?cái)?shù)，12kk1212試求能整除盡數(shù)n的正整數(shù)數(shù)目。解：能整除數(shù)n的正整數(shù)即n的正約數(shù)，其個(gè)數(shù)為：(1)(1)(1)。k1219．試求n個(gè)完全一樣的骰子能擲出多少種不同的方案？解：每個(gè)骰子有六個(gè)面，每個(gè)面的點(diǎn)數(shù)可以是1,2,,6中的一種。由于n個(gè)骰子完全一樣，故這樣相當(dāng)于將n個(gè)完全一樣的球放到6個(gè)不同的盒子中，每盒球數(shù)不限。故方案數(shù)有C(n61,n)C(n5,5)51!(n5)(n4)(n3)(n2)(n1)（種）21．試證一整數(shù)n是另一整數(shù)的平方的充要條件是除盡n的正整數(shù)的數(shù)目為奇數(shù)。pak，pn，且p為素?cái)?shù)，1，kiii證明：必要性：整數(shù)n可表示為nppa1則除盡n的正整數(shù)個(gè)數(shù)為：(a1)(a1)(a1)，a21212k若(a1)(a1)(a1)為偶數(shù)，則必存在為奇數(shù)，2則n不可能寫成令一個(gè)數(shù)的平方。1ki所以n是另一整數(shù)的平方的必要條件是除盡n的正整數(shù)數(shù)目為奇數(shù)。充分性：若除盡n的正整數(shù)的數(shù)目為奇數(shù)，則(i1,2,,k)均為偶數(shù)，i2aa22aaa2aknpppakp21pp21pp2則222p2kka1a22212k112k可寫成另一整數(shù)的平方。證畢。22．統(tǒng)計(jì)力學(xué)需要計(jì)算r個(gè)質(zhì)點(diǎn)放到n個(gè)盒子里去，并分別服從下列假定之一，第7頁(yè)（共10頁(yè)）習(xí)題一問有多少種不同的圖像？假設(shè)盒子始終是不同的。（1）Maxwell-Boltzmann假定：r個(gè)質(zhì)點(diǎn)是不同的，任何盒子可以放任意個(gè)；（2）Bose-Einstein假定：r個(gè)質(zhì)點(diǎn)完全相同（3）Fermi-Dirac假定：r個(gè)質(zhì)點(diǎn)都完全相同1）問題即：將r個(gè)不同的質(zhì)點(diǎn)放到n個(gè)不同的盒子不受限制，即相異元素允許重復(fù)排列，其方案數(shù)有RP(,r)rn（2）問題即：將r個(gè)沒有區(qū)別的質(zhì)點(diǎn)放到n個(gè)不同的盒子，每一個(gè)盒子可以放任意個(gè)。，每盒不得超過一個(gè)。解：（，每個(gè)盒子放的質(zhì)點(diǎn)數(shù)：，每個(gè)盒子方的質(zhì)點(diǎn)數(shù)不受限制，即相異元素允許重復(fù)組合，其方案數(shù)有：RC(,r)Cn(rr1,()rn!(nr11))!!（3）問題即：將r個(gè)沒有區(qū)別的質(zhì)點(diǎn)放到n個(gè)不同的盒子，每盒不超過一個(gè)，即相異元素不允許重復(fù)的組合，其方案數(shù)有：n!C(n,r)r!(nr)!23．從26個(gè)英文字母中取出6個(gè)字母組成一問分別可構(gòu)成多少解：母音指元音，即a，e，i，o，u（1）有2個(gè)元音。先從5個(gè)元音中取出2個(gè)，再?gòu)氖Ｏ碌?1個(gè)字母中選出4個(gè)，再將6個(gè)字母進(jìn)行全排列，則可構(gòu)成的C2C4P6430920（0個(gè)0）字，若其中有2或3個(gè)母音，個(gè)字（不允許重復(fù)）？字總共有：5216（2）有4個(gè)，再將6個(gè)字母進(jìn)行全排列，則可構(gòu)成的C3C3P69567000（個(gè)）3個(gè)元音。先從5個(gè)元音中取出3個(gè)，再?gòu)氖Ｏ碌?1個(gè)字母中選出字總共有：5216(2n)!和(3n)!28．（1）用組合方法證明都是整數(shù)。2n3n2n（2）證明(n2)!是整數(shù)。(n!)n11）考慮2n個(gè)有證明：（區(qū)別的球放入n個(gè)不同的盒子里，每盒兩個(gè)，盒中球不第8頁(yè)（共10頁(yè)）習(xí)題一(2n)!(2n)!2!2n計(jì)順序，則方案數(shù)為：，2!2!n個(gè)(2n)!方案數(shù)是整數(shù)，所以是整數(shù)。2n同理，考慮3n個(gè)有區(qū)別的球放入n個(gè)不同的盒子里，每盒3個(gè)，盒(3n)!中球不計(jì)順，則方案數(shù)為：，3!3!3!23(3n)!nnn個(gè)(3n)!方案數(shù)是整數(shù)，所以是整數(shù)。23nn（2）考慮n2個(gè)不同的球放入n個(gè)相同的盒子，每盒n個(gè)，盒中球不計(jì)順序的方案。(2n)!先假設(shè)盒子是不同的，則這樣的方案數(shù)為：，n!n!n!(n!)n(n)!2n個(gè)又盒子是相同的，所以方案數(shù)應(yīng)為：(n2)!(n)!2，(n!)(n!)(n!)nn1(n)!2方案數(shù)必然是整數(shù)，所以是整數(shù)。(n!)n129．（1）在