《組合數(shù)學(xué)》姜建國(guó)著(第二版)課后習(xí)題答案完全版94頁(yè)

《《組合數(shù)學(xué)》姜建國(guó)著(第二版)課后習(xí)題答案完全版94頁(yè)》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)》姜建國(guó)著(第二版)課后習(xí)題答案完全版94頁(yè)（97頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、組合數(shù)學(xué)組合數(shù)學(xué)(第第 2 版版)-姜建國(guó)姜建國(guó),岳建國(guó)岳建國(guó)習(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è)；15P （2）選 2 個(gè)，即構(gòu)成兩位數(shù)，共有個(gè)；25P （3）選 3 個(gè)，即構(gòu)成 3 位數(shù)，共有個(gè)；35P （4）選 4 個(gè)，即構(gòu)成 4 位數(shù)，共有個(gè)；45P 由加法法則可知，所求的整數(shù)共有：個(gè)。12345555205PPPP2比 5400 小并具有下列性質(zhì)的正整數(shù)有多少個(gè)？（1）每

2、位的數(shù)字全不同；（2）每位數(shù)字不同且不出現(xiàn)數(shù)字 2 與 7；解：（1）比 5400 小且每位數(shù)字全不同的正整數(shù)； 按正整數(shù)的位數(shù)可分為以下幾種情況： 一位數(shù)，可從 19 中任取一個(gè)，共有 9 個(gè)； 兩位數(shù)。十位上的數(shù)可從 19 中選取，個(gè)位數(shù)上的數(shù)可從其余 9 個(gè)數(shù)字中選取，根據(jù)乘法法則，共有個(gè)；9 981 三位數(shù)。百位上的數(shù)可從 19 中選取，剩下的兩位數(shù)可從其余 9 個(gè)數(shù)中選 2 個(gè)進(jìn)行排列，根據(jù)乘法法則，共有個(gè)；299648P 四位數(shù)。又可分三種情況：千位上的數(shù)從 14 中選取，剩下的三位數(shù)從剩下的 9 個(gè)數(shù)字中選3 個(gè)進(jìn)行排列，根據(jù)乘法法則，共有個(gè)；3942016P千位上的數(shù)取 5，百

3、位上的數(shù)從 13 中選取，剩下的兩位數(shù)從剩下的 8 個(gè)數(shù)字中選 2 個(gè)進(jìn)行排列，共有個(gè)；283168P千位上的數(shù)取 5，百位上的數(shù)取 0，剩下的兩位數(shù)從剩下的 8 個(gè)數(shù)字中選 2 個(gè)進(jìn)行排列，共有個(gè)；2856P 根據(jù)加法法則，滿足條件的正整數(shù)共有：個(gè)；981 6482016 168562978（2）比 5400 小且每位數(shù)字不同且不出現(xiàn)數(shù)字 2 與 7 的正整數(shù)；按正整數(shù)的位數(shù)可分為以下幾種情況：設(shè)0,1,3,4,5,6,8,9A 一位數(shù)，可從中任取一個(gè)，共有 7 個(gè)；0A 兩位數(shù)。十位上的數(shù)可從中選取，個(gè)位數(shù)上的數(shù)可從 A 中其余0A7 個(gè)數(shù)字中選取，根據(jù)乘法法則，共有個(gè)；7 749 三位數(shù)

4、。百位上的數(shù)可從中選取，剩下的兩位數(shù)可從 A 其余 70A個(gè)數(shù)中選 2 個(gè)進(jìn)行排列，根據(jù)乘法法則，共有個(gè)；277294P 四位數(shù)。又可分三種情況：千位上的數(shù)從 1，3，4 中選取，剩下的三位數(shù)從 A 中剩下的 7 個(gè)數(shù)字中選 3 個(gè)進(jìn)行排列，根據(jù)乘法法則，共有個(gè)；373630P千位上的數(shù)取 5，百位上的數(shù)從 0，1，3 中選取，剩下的兩位數(shù)從 A 中剩下的 6 個(gè)數(shù)字中選 2 個(gè)進(jìn)行排列，共有個(gè)；26390P 根據(jù)加法法則，滿足條件的正整數(shù)共有：個(gè)；7492946309010703一教室有兩排，每排 8 個(gè)座位，今有 14 名學(xué)生，問(wèn)按下列不同的方式入座，各有多少種做法？ （1）規(guī)定某 5 人

5、總坐在前排，某 4 人總坐在后排，但每人具體座位不指定； （2）要求前排至少坐 5 人，后排至少坐 4 人。解：（1）因?yàn)榫妥怯写涡虻?，所有是排列?wèn)題。5 人坐前排，其坐法數(shù)為，4 人坐后排，其坐法數(shù)為，(8,5)P(8,4)P 剩下的 5 個(gè)人在其余座位的就坐方式有種，(7,5)P 根據(jù)乘法原理，就座方式總共有：（種）(8,5)(8,4)(7,5)28 449 792 000PPP （2）因前排至少需坐 6 人，最多坐 8 人，后排也是如此。可分成三種情況分別討論： 前排恰好坐 6 人，入座方式有；(14,6) (8,6) (8,8)CPP 前排恰好坐 7 人，入座方式有；(14,7) (

6、8,7) (8,7)CPP 前排恰好坐 8 人，入座方式有；(14,8) (8,8) (8,6)CPP各類入座方式互相不同，由加法法則，總的入座方式總數(shù)為： (14,6) (8,6) (8,8)(14,7) (8,7) (8,7)(14,8) (8,8) (8,6)10 461394944 000CPPCPPCPP典型錯(cuò)誤典型錯(cuò)誤：先選 6 人坐前排，再選 4 人坐后排，剩下的 4 人坐入余下的 6 個(gè)座位。故總的入坐方式共有：種。 (14,6)8,6(8,4)8,46,4CPCPP但這樣計(jì)算無(wú)疑是有重復(fù)的，例如恰好選 6 人坐前排，其余 8 人全坐后排，那么上式中的就有重復(fù)。(8,4)8,4

7、CP4一位學(xué)者要在一周內(nèi)安排 50 個(gè)小時(shí)的工作時(shí)間，而且每天至少工作 5 小時(shí)，問(wèn)共有多少種安排方案？解：用表示第 i 天的工作時(shí)間，則問(wèn)題轉(zhuǎn)化為求不定方程ix1,2,7i 的整數(shù)解的組數(shù)，且，于是又可以轉(zhuǎn)123456750 xxxxxxx5ix 化為求不定方程的整數(shù)解的組數(shù)。123456715yyyyyyy該問(wèn)題等價(jià)于：將 15 個(gè)沒(méi)有區(qū)別的球，放入 7 個(gè)不同的盒子中，每盒球數(shù)不限，即相異元素允許重復(fù)的組合問(wèn)題。故安排方案共有： （種）( ,15)(157 1,15)54 264RCC另解：因?yàn)樵试S，所以問(wèn)題轉(zhuǎn)化為長(zhǎng)度為 1 的 15 條線段中間有 14 個(gè)空，再0iy 加上前后兩個(gè)空，

8、共 16 個(gè)空，在這 16 個(gè)空中放入 6 個(gè)“”號(hào)，每個(gè)空放置的“”號(hào)數(shù)不限，未放“”號(hào)的線段合成一條線段，求放法的總數(shù)。從而不定方程的整數(shù)解共有：（組）21 20 19 18 17 16( ,6)(166 1,6)54 2646 5 4 3 2 1RCC 即共有 54 264 種安排方案。5若某兩人拒絕相鄰而坐，問(wèn) 12 個(gè)人圍圓周就坐有多少種方式？解：12 個(gè)人圍圓周就坐的方式有：種，(12,12)11!CP設(shè)不愿坐在一起的兩人為甲和乙，將這兩個(gè)人相鄰而坐，可看為 1 人，則這樣的就坐方式有：種；由于甲乙相鄰而坐，可能是“甲乙”(11,11)10!CP也可能是“乙甲” ；所以則滿足條件的

9、就坐方式有：種。11! 2 10!32 659 200 6有 15 名選手，其中 5 名只能打后衛(wèi)，8 名只能打前鋒，2 名只能打前鋒或后衛(wèi)，今欲選出 11 人組成一支球隊(duì)，而且需要 7 人打前鋒，4 人打后衛(wèi)，試問(wèn)有多少種選法？解：用 A、B、C 分別代表 5 名打后衛(wèi)、8 名打前鋒、2 名可打前鋒或后衛(wèi)的集合，則可分為以下幾種情況： （1）7 個(gè)前鋒從 B 中選取，有種選法，4 個(gè)后衛(wèi)從 A 中選取，有種，78C45C 根據(jù)乘法法則，這種選取方案有：種；7485CC （2）7 個(gè)前鋒從 B 中選取，從 A 中選取 3 名后衛(wèi)，從 C 中選 1 名后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種；7

10、31852CCC （3）7 個(gè)前鋒從 B 中選取，從 A 中選取 2 名后衛(wèi)，C 中 2 名當(dāng)后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種；7285CC （4）從 B 中選 6 個(gè)前鋒，從 C 中選 1 個(gè)前鋒，從 A 中選 4 個(gè)后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種；614825CCC （5）從 B 中選 6 個(gè)前鋒，從 C 中選 1 個(gè)前鋒，從 A 中選 3 個(gè)后衛(wèi)，C 中剩下的一個(gè)當(dāng)后衛(wèi)，選取方案有：種；613825CCC （6）從 B 中選 5 個(gè)前鋒，C 中 2 個(gè)當(dāng)前鋒，從 A 中選 4 個(gè)后衛(wèi)， 選取方案有：種；5485CC 根據(jù)加法法則，總的方案數(shù)為：7473172614613

11、548585285825825851400CCCCCCCCCCCCCCC 7求展開(kāi)式中項(xiàng)的系數(shù)。8(2)xyzw2222x y z w解：令，則中項(xiàng)的系數(shù)為,2 ,ax by cz dw 8()abcd 2222a b c z ，即中，的系數(shù)，88!7!2 2 2 22!2!2!2!28(2)xyzw2222() ( 2 )xyzw因此，的系數(shù)為：。2222x y z w227! 2 ( 1)( 2)10 0808求的展開(kāi)式。4()xyz解：，展開(kāi)式共有（項(xiàng)） ， 所以，4,3nt( ,4)(43 1,4)15RCC 444433222223322344444()4 0 00 4 00 0 4

12、3103014442 2 02 0 2211444413010311212144013031xyzxyzx yx zx yx zx yzxyxzxyzxy zyz32244433333322222222240 2 2444444666121212y zy zxyzx yx zxyxzyzy zx yx zy zx yzxyzxy z9求展開(kāi)式中的系數(shù)。1012345()xxxxx36234x x x解：的系數(shù)為： 36234x x x1010!8400316 03! 1! 6!10試證任一整數(shù) n 可唯一表示成如下形式： 1!,0,1,2,iiinaiai i證明：（1）可表示性。令，顯然，1

13、221(,)|0,1,2,1mmiMaaa aai im!Mm ，顯然，0,1,2,! 1Nm!Nm定義函數(shù)，:fMN，12211221(,)(1)!(2)!2!1!mmmmf aaa aamamaa顯然，122100 (1)! 0 (2)!0 2! 0 1!(1)!(2)!2!1!(1)(1)! (2)(2)!2 2! 1 1! (1)! (1)! (2)!3! 2! 2! 1! 1mmmmamamaammmmmmmmm即，12210(,)! 1mmf aaa am由于 f 是用普通乘法和普通加法所定義的，故 f 無(wú)歧義，肯定是一個(gè)函數(shù)。從而必有一確定的數(shù)，使得，(0! 1)KKm1221(

14、,)mmKf aaa a為了證明 N 中的任一數(shù) n 均可表示成的形式，1!iinai只需證明 f 是滿射函數(shù)即可。又因?yàn)?f 是定義在兩個(gè)有限且基數(shù)相等的函數(shù)上，因此如果能證明 f 單射，則 f 必是滿射。假設(shè) f 不是單射，則存在，12211221(,),(,)mmmmaaa abbb bM，且有，使得12211221(,)(,)mmmmaaa abbb b0KN012211221(,)(,)mmmmKf aaa af bbb b由于，故必存在，使得12211221(,)(,)mmmmaaa abbb b1jm。不妨設(shè)這個(gè) j 是第一個(gè)使之不相等的，即，jjab(1,1)iiab imj且

15、，jjabjjab因?yàn)?2211221(1)!(2)!2!1!(1)!(2)!2!1!mmmmamamaabmbmbb所以， 122112211122111122110(1)!(2)!2!1!(1)!(2)!2!1!() ! ()(1)!() 2! () 1!(1)!2!1!(1) (1)!2 2! 1 1!mmmmjjjjjjbmbmbbamamaabajbajbabajbajbabajjjj( ! 1)1j產(chǎn)生矛盾，所以 f 必是單射函數(shù)。因?yàn)?，所?f 必然也是滿射函數(shù)，!MNm故對(duì)任意的，都存在，使得nN1221(,)mmaaa aM1221(1)!(2)!2!1!mmnamamaa

16、這說(shuō)明對(duì)任意的整數(shù)，都可以表示成的形式。1!iinai （2）唯一性。 由于函數(shù)是一個(gè)單射，也是滿射，即 f 是雙射函數(shù)，:fMN故，對(duì)任意的，都存在唯一的，使得nN1221(,)mmaaa aM。1221(1)!(2)!2!1!mmnamamaa否則，若存在另一個(gè)，使得1221(,)mmbbb bM1221(1)!(2)!2!1!mmnbmbmbb將與 f 是單射函數(shù)矛盾。證畢。 11證明，并給出組合意義。(1, )(1) ( ,1)nC nrrC n r證明：因?yàn)?，現(xiàn)令，則可得( , ) ( , )( , ) (,)C n k C k lC n l C nl kl1kr1l ，即( ,1)

17、 (1,1)( ,1) (1, )C n rC rC nC nr(1, )(1) ( ,1)nC nrrC n r組合意義組合意義：將 n 個(gè)元素分為 3 堆，1 堆 1 個(gè)元素，1 堆 r 個(gè)元素，1 堆個(gè)1nr 元素?？梢杂邢旅鎯煞N不同的分法： （1）先從 n 個(gè)元素中選出個(gè)元素，剩下的個(gè)作為 1 堆；再將1r 1nr 選出的個(gè)元素分為兩堆，1 堆 1 個(gè)，1 堆 r 個(gè)。1r （2）先從 n 個(gè)元素中選出 1 人作為 1 堆，再?gòu)氖Ｏ碌膫€(gè)中選出 r 個(gè)1n作為 1 堆，剩下的作為 1 堆。1nr 顯然，兩種分法是等價(jià)的，所以等式成立。12證明 。11( , )2nnkkC n kn證明：

18、采用殊途同歸法。組合意義一組合意義一：考慮從 n 個(gè)人中選出 1 名正式代表和若干名列席代表的選法（列席代表人數(shù)不限，可以為 0） ?？梢杂幸韵聝煞N不同的選法：（1）先選定正式代表，有種選法；然后從人中選列席代表，這1nCn1n 個(gè)人都有選和不選的兩種狀態(tài)，共有種選法；1n12n根據(jù)乘法法則，共有 種選法；12nn（2）可以先選出人，然后再?gòu)闹羞x出 1 名正式代表，1(0,1,2,1)kkn其余 k 人作為列席代表，對(duì)于每個(gè) k，這樣的選法有：，111knkCC從而總選法有： 1011( ,1) (1,1)( , ) ( ,1)( , )nnnkkkC n kC kC n k C kkC n

19、k 顯然，兩種選法是等價(jià)的，所以等式成立。組合意義二：組合意義二：將 n 個(gè)不同的球放入標(biāo)號(hào)為 A、B、C 的 3 個(gè)盒子，其中要求 A 盒只放 1個(gè)球，其余兩盒的球數(shù)不限。那么，有兩種不同的放法：（1）先從 n 個(gè)不同的球中選出 1 個(gè)，放入 A 盒，再將其余個(gè)球放入1 n另外兩盒，有種放法；11122nnnCn（2）先從 n 個(gè)球中選出 k 個(gè)，再?gòu)乃x的 k 個(gè)球中選出 1 個(gè)(1,2, )kn放入 A 盒，將其余的個(gè)球放入 B 盒，剩下的個(gè)球放入 C 盒，1k nk根據(jù)乘法法則，對(duì)于不同的 k，有種放法。1kn kknkn knCCCkC當(dāng)時(shí)，各種情況互不重復(fù)，且包含了所有放法，1,2

20、,kn根據(jù)加法法則，總的放法有：。1( , )nkkC n k 顯然兩種放法是等價(jià)的，故等式成立。另法：另法：根據(jù)二項(xiàng)式定理：，21(1)1( ,1)( ,2)( ,1)( , )nnnxC nxC nxC n nxC n n x 兩邊求導(dǎo)，得： ，121(1)( ,1)2 ( ,2)(1) ( ,1)( , )nnnnxC nC nxnC n nxnC n n x令，即得1x 11( , )2nnkkC n kn13有 n 個(gè)不同的整數(shù)，從中取出兩組來(lái)，要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)，問(wèn)有多少種方案？解：設(shè)這 n 個(gè)不同的數(shù)為，12naaa若假定第一組取個(gè)數(shù)，第二組取個(gè)數(shù)，并且令，

21、1k2k12(2)mkkm則要求第一組數(shù)里的最小數(shù)大于第二組里的最大數(shù)，我們可以這樣來(lái)選：先從 n 個(gè)數(shù)中任選 m 個(gè)數(shù)出來(lái)，有種選法；再?gòu)倪@ m 個(gè)數(shù)中從大到( ,)C n m小取個(gè)數(shù)作為第一組數(shù)，有種取法；再將其余的個(gè)1k11,2,1km1m2k數(shù)作為第二組數(shù)。故總方案數(shù)有：22211(1) ( ,)( ,)( ,)2(21)(2)21nnnmmmnnnmC n mmC n mC n mnnnn14六個(gè)引擎分列兩排，要求引擎的點(diǎn)火次序兩排交錯(cuò)開(kāi)來(lái)，試求從某一特定引擎開(kāi)始點(diǎn)火有多少種方案？解：第一次點(diǎn)火僅有一種選擇，即點(diǎn)某個(gè)特定引擎的火；第二次點(diǎn)另一組某個(gè)引擎的火，有三種選擇；第三次有 2

22、種,。所以方案數(shù)為：（種）1 3 2 2 1 112 如果只指定從第一排先開(kāi)始點(diǎn)火，不指定某一個(gè)，則方案數(shù)為（種）3 3 2 2 1 136 如果第一個(gè)引擎任意選，只要求點(diǎn)火過(guò)程是交錯(cuò)的，則方案數(shù)為 （種）6 3 2 2 1 172 15試求從 1 到 1 000 000 的整數(shù)中，0 出現(xiàn)了幾次？解：分別計(jì)算 0 出現(xiàn)在各個(gè)位上的次數(shù)。 （1）0 出現(xiàn)在個(gè)位，此時(shí)符合條件的 2 位數(shù)有 9 個(gè)；3 位數(shù)有個(gè)；9 104 位數(shù)有個(gè)；5 位數(shù)有個(gè)；6 位數(shù)有個(gè)；29 1039 1049 10 （2）0 出現(xiàn)在十位，此時(shí)符合條件的 3 位數(shù)有個(gè)；4 位數(shù)有個(gè)；9 1029 105 位數(shù)有個(gè)；6 位

23、數(shù)有個(gè)；39 1049 10 （3）0 出現(xiàn)在百位，此時(shí)符合條件的 4 位數(shù)有個(gè)；5 位數(shù)有個(gè)；29 1039 106 位數(shù)有個(gè)；49 10 （4）0 出現(xiàn)在千位，此時(shí)符合條件的 5 位數(shù)有個(gè)；6 位數(shù)有個(gè)；39 1049 10 （5）0 出現(xiàn)在萬(wàn)位，此時(shí)符合條件的 6 位數(shù)有個(gè)；49 10 另外 1 000 000 中有 6 個(gè) 0。 所以，從 1 到 1 000 000 的整數(shù)中，0 出現(xiàn)的次數(shù)總共有： （次）23492 9 103 9 104 9 105 9 106488895 另法：另法：先不考慮 1 000 000 本身，那么任一個(gè) 000 000999 999 之間的數(shù)都可以表示成

24、如下形式：，其中每個(gè)是 0 到 9 的數(shù)字。123456d d d d d did因?yàn)槊课粩?shù)字可以有 10 種選擇，根據(jù)乘法法則，共有個(gè)“6 位數(shù)” ，610又每個(gè)“6 位數(shù)”由 6 個(gè)數(shù)字組成（包括無(wú)效 0） ，所以共有個(gè)數(shù)字，6106 又每個(gè)數(shù)字出現(xiàn)的概率相等， 所以 0 出現(xiàn)的次數(shù)應(yīng)是，5106 但習(xí)慣上在計(jì)算 0 的個(gè)數(shù)時(shí)，不包括無(wú)效 0（即高位的 0） ，因而要從中去掉無(wú)效 0，其中：（1）1 位數(shù)有 9 個(gè)（不包括 0） ，其無(wú)效 0 共有個(gè)（即95 00000） ；id（2）2 位數(shù)有 90 個(gè)，其無(wú)效 0 共個(gè)。904 依次類推，無(wú)效 0 的總數(shù)為 5 94 903 9002

25、9000 1 90000111 105 因?yàn)槿珵?0 時(shí)的 6 個(gè) 0 和 1 000 000 本身的 6 個(gè) 0 相互抵消，123456d d d d d d所以 1 到 1 000 000 之間的自然數(shù)中 0 出現(xiàn)的次數(shù)為（次）56 10111105488895注意：1 出現(xiàn)的次數(shù)為（要考慮 1 000 000 這個(gè)數(shù)的首位 1） ，11065 2，3，9 各自出現(xiàn)的次數(shù)為。5106 16n 個(gè)男 n 個(gè)女排成一男女相間的隊(duì)伍，試問(wèn)有多少種不同的方案？若圍成一圓桌坐下，又有多少種不同的方案？解：排成男女相間的隊(duì)伍：先將 n 個(gè)男的排成 1 行，共有種排法；nnP再將 n 個(gè)女的往 n 個(gè)空

26、里插，有種排法；由于可以先男后女，也可以先nnP女后男，因此共有種排法；2nnP根據(jù)乘法法則，男女相間的隊(duì)伍共有：種方案。22 ! !nnnnPPn n若圍成一圓周坐下，同理先將 n 個(gè)男的圍成一圓周，共有種排法，( , )CP n n再將 n 個(gè)女的往 n 個(gè)空中插，有種排法，nnP根據(jù)乘法法則，圍成圓周坐下，總的方案數(shù)有：種。( , )!(1)!nnCP n nPn n17n 個(gè)完全一樣的球，放到 r 個(gè)有標(biāo)志的盒子，要求無(wú)一空盒，nr試證其方案數(shù)為。11nr證明：因?yàn)闆](méi)有空盒，可先每盒放入一個(gè)球，再將剩余的球放入 r 個(gè)盒子nr中， 即將個(gè)無(wú)區(qū)別的球，放入 r 個(gè)不同的盒子中，每盒的球數(shù)

27、不受限制，nr 因此方案數(shù)有：。(1,)(1,)(1,1)C rnrnrC nnrC nr 另法：插空法。問(wèn)題可看為：n 個(gè)球排成 1 行，球與球之間形成個(gè)空，再在這個(gè)空1n1n中，插入個(gè)隔板，這樣就可形成 r 個(gè)盒子，每盒球不空的方案，其方案1r 數(shù)為。(1,1)C nr18設(shè)，是 k 個(gè)素?cái)?shù)，1212kknp pp12,kp pp試求能整除盡數(shù) n 的正整數(shù)數(shù)目。解：能整除數(shù) n 的正整數(shù)即 n 的正約數(shù)，其個(gè)數(shù)為： 。12(1)(1)(1)k19試求 n 個(gè)完全一樣的骰子能擲出多少種不同的方案？解：每個(gè)骰子有六個(gè)面，每個(gè)面的點(diǎn)數(shù)可以是中的一種。1,2,6由于 n 個(gè)骰子完全一樣，故這樣相

28、當(dāng)于將 n 個(gè)完全一樣的球放到 6 個(gè)不同的盒子中，每盒球數(shù)不限。故方案數(shù)有（種）) 1)(2)(3)(4)(5(! 51)5 , 5(), 16(nnnnnnCnnC20凸十邊形的任意三個(gè)對(duì)角線不共點(diǎn)，試求這凸十邊形的對(duì)角線交于多少個(gè)點(diǎn)？又把所有的對(duì)角線分割成多少段？解：（1）從一個(gè)頂點(diǎn)可引出 7 條對(duì)角線，這 7 條對(duì)角線和其他頂點(diǎn)引出的對(duì)角線的交點(diǎn)情況如下：從右到左，和第一條對(duì)角線的交點(diǎn)有： 個(gè)，和第二條的交點(diǎn)有，和第三條的交點(diǎn)有條，故和一1 72 63 5個(gè)頂點(diǎn)引出的 7 條線相交的點(diǎn)為：，故和從 10 點(diǎn)引出的對(duì)角線交的點(diǎn)1 72 63 54 45 36 27 184有個(gè)，但每個(gè)點(diǎn)重

29、復(fù)了四次（因?yàn)槊總€(gè)點(diǎn)在兩條線上，而每條線又84 10840有兩個(gè)端點(diǎn)） ，故凸十邊形對(duì)角線交于個(gè)點(diǎn)。840 4210也可以直接這樣看也可以直接這樣看：因?yàn)橐粋€(gè)交點(diǎn)需要兩條對(duì)角線相交，而兩條對(duì)角線又需要多邊形的四個(gè)點(diǎn)構(gòu)成一四邊形。反之，從 n 個(gè)頂點(diǎn)中任取四個(gè)頂點(diǎn)，連成一四邊形，而四邊形的兩條對(duì)角線必須確定唯一的一個(gè)交點(diǎn)，故凸十邊形的對(duì)角線的交點(diǎn)共有：（個(gè)）410210C（前提：任三個(gè)對(duì)角線不共點(diǎn)，否則，一個(gè)交點(diǎn)不能對(duì)應(yīng) n 邊形的唯一四個(gè)頂點(diǎn)）（2）由（1）知，一個(gè)點(diǎn)引出的 7 條對(duì)角線中，第一條線上有 7 個(gè)點(diǎn)，故將該線段分成 8 段；第二條線上有 12 個(gè)點(diǎn)，故將該線段分成 13 段，故從

30、一個(gè)點(diǎn)出發(fā)的 7 條線上的段數(shù)為：。8 13 16 17 16 13891現(xiàn)有 10 個(gè)點(diǎn)。故總的段數(shù)為：。但每段重復(fù)計(jì)算了 2 次（因91 10910為每條線有 2 個(gè)端點(diǎn)）故總的段數(shù)應(yīng)為：。910 2455另法：一個(gè)交點(diǎn)給相交的兩條對(duì)角線各增加 1 段，所以對(duì)角線總的段數(shù)為： 對(duì)角線數(shù)2 倍交點(diǎn)數(shù) （段）10(103)2 2104552 21試證一整數(shù) n 是另一整數(shù)的平方的充要條件是除盡 n 的正整數(shù)的數(shù)目為奇數(shù)。證明：必要性：整數(shù) n 可表示為，且為素?cái)?shù)，1212kaaaknp ppipnip，1i則除盡 n 的正整數(shù)個(gè)數(shù)為：，12(1)(1)(1)kaaa若為偶數(shù)，則必存在為奇數(shù)，1

31、2(1)(1)(1)kaaai則 n 不可能寫(xiě)成令一個(gè)數(shù)的平方。所以 n 是另一整數(shù)的平方的必要條件是除盡 n 的正整數(shù)數(shù)目為奇數(shù)。充分性：若除盡 n 的正整數(shù)的數(shù)目為奇數(shù)，則均為偶數(shù)，(1,2, )iik則 1212122222222222121212kkkaaaaaaaaakkknp pppppppp可寫(xiě)成另一整數(shù)的平方。證畢。22統(tǒng)計(jì)力學(xué)需要計(jì)算 r 個(gè)質(zhì)點(diǎn)放到 n 個(gè)盒子里去，并分別服從下列假定之一，問(wèn)有多少種不同的圖像？假設(shè)盒子始終是不同的。 （1）Maxwell-Boltzmann 假定：r 個(gè)質(zhì)點(diǎn)是不同的，任何盒子可以放任意個(gè)； （2）Bose-Einstein 假定：r 個(gè)質(zhì)點(diǎn)

32、完全相同，每一個(gè)盒子可以放任意個(gè)。 （3）Fermi-Dirac 假定：r 個(gè)質(zhì)點(diǎn)都完全相同，每盒不得超過(guò)一個(gè)。解：（1）問(wèn)題即：將 r 個(gè)不同的質(zhì)點(diǎn)放到 n 個(gè)不同的盒子，每個(gè)盒子放的質(zhì)點(diǎn)數(shù)不受限制，即相異元素允許重復(fù)排列，其方案數(shù)有： ( , )rRPrn （2）問(wèn)題即：將 r 個(gè)沒(méi)有區(qū)別的質(zhì)點(diǎn)放到 n 個(gè)不同的盒子，每個(gè)盒子方的質(zhì)點(diǎn)數(shù)不受限制，即相異元素允許重復(fù)組合，其方案數(shù)有： (1)!( , )(1, )!(1)!nrRCrC nrrr n （3）問(wèn)題即：將 r 個(gè)沒(méi)有區(qū)別的質(zhì)點(diǎn)放到 n 個(gè)不同的盒子，每盒不超過(guò)一個(gè)，即相異元素不允許重復(fù)的組合，其方案數(shù)有： !( , )!()!nC

33、 n rr nr23從 26 個(gè)英文字母中取出 6 個(gè)字母組成一字，若其中有 2 或 3 個(gè)母音，問(wèn)分別可構(gòu)成多少個(gè)字（不允許重復(fù)）？解：母音指元音，即 a，e，i，o，u （1）有 2 個(gè)元音。先從 5 個(gè)元音中取出 2 個(gè)，再?gòu)氖Ｏ碌?21 個(gè)字母中選出4 個(gè)，再將 6 個(gè)字母進(jìn)行全排列，則可構(gòu)成的字總共有： （個(gè)）246521643092 000C C P （2）有 3 個(gè)元音。先從 5 個(gè)元音中取出 3 個(gè)，再?gòu)氖Ｏ碌?21 個(gè)字母中選出4 個(gè)，再將 6 個(gè)字母進(jìn)行全排列，則可構(gòu)成的字總共有： （個(gè)）33652169567 000C C P 24給出的11221011220nrnrnr

34、nmrmnrmmmmm 組合意義。證明：組合意義一：組合意義一：從個(gè)元素中取出個(gè)元素的組合數(shù)為：(1)nr 1,2,1nr (1)nrm ，且，其(1,1)(1,)C nrnrmC nrm 1211rrn rmiiiii 中第位置上的元素可取，1r 1ri1,2,1rrrm 當(dāng)取時(shí)（） ，前邊的 r 個(gè)數(shù)可在1ri(1)rk 0,1,km12, ,ri ii這個(gè)數(shù)中取，故有種取法；后邊的1,2,1 (1)rk rk kkrrkr個(gè)數(shù)可在(1)(1)nrmrnm 231,rrn rmiii 這個(gè)數(shù)中取，故有11,1rknr (1)(1)nrrknk 種取法。kmknmnkn根據(jù)乘法法則，當(dāng)時(shí)，這

35、樣的組合數(shù)為：11rirk kkrkmknkkrkmkn1 再根據(jù)加法法則，對(duì)進(jìn)行求和，就有0,1,km。 mrnmmrmnrmnrmnrmn10222211110組合意義二：（格路方法）組合意義二：（格路方法）等式左端：從點(diǎn)到點(diǎn)（） ，直接經(jīng)過(guò)點(diǎn)(1,0)Ar ( 1, )Ck0,1,km再到點(diǎn)的路徑數(shù)。(0, )Dk(,)B nm m從 A 到 C 的路徑數(shù)為：，1 (1)00rkrkkk 從 D 到 B 的路徑數(shù)為：，0nmmknkmkmk根據(jù)乘法法則和加法法則，從 A 到 B 的路徑數(shù)有：。0mkrknkkmk等式右端：從點(diǎn)到點(diǎn)的路徑數(shù)為：(1,0)Ar (,)B nm m (1)01

36、0nmrmnrmm 25給出的組合意義。1211rrrnnrrrrr 證明：（1）等式右端：從個(gè)元素中，任選個(gè)元素的組1n121,nna aa a1r 合方案數(shù)為：。11nr （2）等式左端：從不同元素中選取個(gè)元素，一1n121,nna aa a1r 定選元素，但不選元素1(0,1,2,)r kaknr 的方案數(shù)。根據(jù)乘法法則，當(dāng) k 值取定21,r knnaa a 時(shí)，這樣的方案數(shù)為從其余的個(gè)元素中任取 r 個(gè)的rk方案數(shù)，即，再根據(jù)加法法則，總的方案數(shù)有：rkr0n rkrkr26證明 。120110nmmmmmmnmnnnn證明：考慮從 m 雙互不相同的鞋中取出 n 只，要求其中沒(méi)有任何

37、兩只nm是成對(duì)的，求方案數(shù)。 一方面，先從 m 雙鞋中選取 n 雙，共有種選法，再?gòu)拇?n 雙中每雙mn抽掉一只，有種取法，由乘法原理，總的方案數(shù)為：2n。2nmn 另一方面，先取出只左腳的鞋，再在其余的雙中取出(0,1, )k knmk只右腳的鞋，則總的方案數(shù)為：nk10110mmmmmmnnnn 所以，。120110nmmmmmmnmnnnn另法：根據(jù) （） （）rnnmrnrmrmnr0,1,2,rn從而有： 1011001012nmmmmmmnnnnmnmnmnnnnnmnnnnnmn 27對(duì)于給定的正整數(shù) n，證明在所有中，當(dāng)( , ) (1,2, )C n rrn 時(shí)，取得最大值。

38、11,222nnnknn為奇數(shù)，為偶數(shù)( , )C n r證明：取與進(jìn)行比較。，( , )C n k( ,1)C n k ( , )1( ,1)C n knkC n kk 當(dāng)時(shí)，即，2nk 11nkk( , )( ,1)C n kC n k 當(dāng)時(shí)，即，2nk 11nkk( , )( ,1)C n kC n k 因此，只有當(dāng)或最接近時(shí)，取得最大值。2nk 2n( , )C n k28 （1）用組合方法證明 和 都是整數(shù)。(2 )!2nn(3 )!23nnn （2）證明是整數(shù)。21()!( !)nnn證明：（1）考慮個(gè)有區(qū)別的球放入 n 個(gè)不同的盒子里，每盒兩個(gè)，盒中球2n不計(jì)順序，則方案數(shù)為：，

39、(2 )!(2 )!2! 2!2!2nnnn個(gè)方案數(shù)是整數(shù)，所以是整數(shù)。(2 )!2nn同理，考慮個(gè)有區(qū)別的球放入 n 個(gè)不同的盒子里，每盒 3 個(gè)，盒3n中球不計(jì)順，則方案數(shù)為：，(3 )!(3 )!3! 3!3!23nnnnn個(gè)方案數(shù)是整數(shù)，所以是整數(shù)。(3 )!23nnn （2）考慮個(gè)不同的球放入 n 個(gè)相同的盒子，每盒 n 個(gè)，盒中球不計(jì)順2n序的方案。 先假設(shè)盒子是不同的，則這樣的方案數(shù)為：，2(2 )!()!( !)nnnnnnnn個(gè) 又盒子是相同的，所以方案數(shù)應(yīng)為：，221()!()!( !)( !)( !)nnnnnnn 方案數(shù)必然是整數(shù)，所以是整數(shù)。21()!( !)nnn2

40、9 （1）在 2n 個(gè)球中，有 n 個(gè)相同，求從這 2n 個(gè)球中選取 n 個(gè)的方案數(shù)。 （2）在個(gè)球中，有 n 個(gè)相同，求從這個(gè)球中選取 n 個(gè)的方案數(shù)。31n31n解：（1）問(wèn)題即：從集合中，選取 n 個(gè)的方案數(shù)，121,nnSn e ee e 即多項(xiàng)式中的系數(shù)，即2(1)(1)nnxxxxnx 101112nnnnnnCCC 從這 2n 個(gè)球中選取 n 個(gè)的方案數(shù)為種。2n （2）問(wèn)題即：從集合中，選取 n 個(gè)的方案數(shù)，1222122,nnnSn e eeee 即多項(xiàng)式中的系數(shù)，即221(1)(1)nnxxxxnx 1021212121210111224nnninnnnnniCCCC 30

41、證明在由字母表生成的長(zhǎng)度為 n 的字符串中，0,1,2 （1）0 出現(xiàn)偶數(shù)次的字符串有個(gè)；312n （2），其中 。231222022nnnn qnnnq 22nq 證明：（1）采用數(shù)學(xué)歸納法當(dāng)時(shí)，0 出現(xiàn)偶數(shù)次（0 次） ，長(zhǎng)度為 1 的字符串為“1”和1n “2”兩個(gè)字符串，而，故結(jié)論成立。13122假設(shè)當(dāng)時(shí)，結(jié)論成立，(1)nk k即 0 出現(xiàn)偶數(shù)次，長(zhǎng)度為 k 的字符串有個(gè)，312k當(dāng)時(shí)，0 出現(xiàn)偶數(shù)次，長(zhǎng)度為的字符串包括兩部分：1nk1k 在 0 出現(xiàn)偶數(shù)次，長(zhǎng)度為 k 的字符串后面再增加一位不是 0 的數(shù)（只能是 1 或 2） ，因此，這樣的字符串有個(gè)。312312kk 給 0 出

42、現(xiàn)奇數(shù)次，長(zhǎng)度為 k 的字符串后面再增加一個(gè) 0， 因此，這樣的字符串有：。3131322kkk根據(jù)加法法則，0 出現(xiàn)偶數(shù)次，長(zhǎng)度為的字符串共有：1k ，即時(shí)，結(jié)論也成立。31313122kk+1k 1nk 所以，根據(jù)數(shù)學(xué)歸納法，結(jié)論成立。（2）由（1）知，右端表示 0 出現(xiàn)偶數(shù)次的字符串?dāng)?shù)。 而左端代表的組合問(wèn)題是：長(zhǎng)度為 n 的字符串中，有 0 個(gè) 0 的字符串?dāng)?shù)有：，20nn 有 2 個(gè) 0 的字符串?dāng)?shù)有：，222nn ， 有 q 個(gè) 0 的字符串?dāng)?shù)有：，2n qnq 根據(jù)加法法則，可知，左端代表的是長(zhǎng)度為 n 的字符串中 0 出現(xiàn)偶數(shù)次的字符串?dāng)?shù)，因此231222022nnnn qnn

43、nq 315 臺(tái)教學(xué)儀器供 m 個(gè)學(xué)生使用，要求使用第 1 臺(tái)和第 2 臺(tái)的人數(shù)相等，有多少種分配方案？解： 方法一：方法一：先從 m 個(gè)學(xué)生中選取 k 個(gè)使用第 1 臺(tái)機(jī)器，再?gòu)氖Ｏ碌膫€(gè)學(xué)生中選mk取 k 個(gè)使用第 2 臺(tái)機(jī)器，其余個(gè)學(xué)生可以任意使用剩下的 3 臺(tái)機(jī)器，2mk按乘法原理，其組合數(shù)為，這里，23mkmmkkk0,1,2,()2mkq q于是，按加法原理，共有種使用方案。203qmkkmmkkk方法二方法二：先從 m 個(gè)學(xué)生種選出 2k 個(gè)，再將選出 2k 個(gè)學(xué)生平均分到 1、2 臺(tái)機(jī)器上，其余的個(gè)學(xué)生可以任意使用剩下的 3 臺(tái)機(jī)器，2mk按乘法法則，其組合數(shù)為，這里2232mk

44、mkkk0,1,2,()2mkq q于是，按加法原理，共有種使用方案。 20232qmkkmkkk32由 n 個(gè) 0 及 n 個(gè) 1 組成的字符串，其任意前 k 個(gè)字符中，0 的個(gè)數(shù)不少于1 的個(gè)數(shù)的字符串有多少？解：（參見(jiàn) P21，例 1.8.8）轉(zhuǎn)化為格路問(wèn)題。即從點(diǎn)到，只能從對(duì)(0,0)( , )n n角線上方走，但可以碰到對(duì)角線的所有最短路徑數(shù)。顯然，第一步必然要走到點(diǎn)，因此可以轉(zhuǎn)換為從點(diǎn)到的所有滿足條件的路徑數(shù)，(0,1)(0,1)( , )n n進(jìn)一步，可以轉(zhuǎn)換為從點(diǎn)到，只能從對(duì)角線上方走，但不可(0,1)( ,1)n n以碰到對(duì)角線的所有路徑數(shù)，因?yàn)閺狞c(diǎn)到的所有經(jīng)過(guò)對(duì)角線(0,1

45、)( ,1)n n的路徑數(shù)與從點(diǎn)到點(diǎn)的所有路徑數(shù)是一一對(duì)應(yīng)的，因此，所(1,0)( ,1)n n求的字符串有：（個(gè)）0(1) 11 (1)0(2 , )(2 ,1)1nnnnCn nCn nnn 方法二：方法二：由 n 個(gè) 1 和 n 個(gè) 0 組成的 2n 位二進(jìn)制數(shù)共有個(gè)(2n 個(gè)不盡相2(2 )!( !)nn異元素的全排列)，設(shè)所求的二進(jìn)制數(shù)共有個(gè)，不符合要求的數(shù)有個(gè)。而不合要求的數(shù)的nbnr特征是從左向右掃描時(shí)，必然在某一位首次出現(xiàn) 0 的個(gè)數(shù)小于 1 的個(gè)數(shù)，即從左向右累計(jì)到第 2k1 位時(shí)出現(xiàn) k 個(gè) 0 和個(gè) 1。此時(shí)，后位上有1k 2() 1nk個(gè) 1，個(gè) 0。將后部分的 0 改

46、寫(xiě)為 1，1 改寫(xiě)為 0。結(jié)果整個(gè)數(shù)變成1nknk由個(gè)和個(gè) 0 組成的 2n 位數(shù) z。即一個(gè)不合要求的數(shù)唯一對(duì)應(yīng)于這樣的1n1n一個(gè)數(shù) z。反之，給定一個(gè)由個(gè) 1 和個(gè) 0 組成的 2n 位數(shù) z由于 1 比 0 多 21n1n個(gè)，故一定在某一位首次出現(xiàn) 0 的累計(jì)數(shù)少于 1 的累計(jì)數(shù)。依同法將此位后的0 與 1 互換，使 z 變成由 n 個(gè) 1 和 n 個(gè) 0 組成的 2n 位數(shù)。所以，這兩種二進(jìn)制數(shù)一一對(duì)應(yīng)。即 !1!1!2nnnrn故 。 2222!2!2!2!112 ,1 !1 !11!nnnnnnbrCn nnnnnnnn習(xí)題二（母函數(shù)及其應(yīng)用）習(xí)題二（母函數(shù)及其應(yīng)用）1求下列數(shù)列

47、的母函數(shù)(0,1,2,)n （1）；( 1)nan （2）；5n （3）； (1)n n（4）； (2)n n解：（1）母函數(shù)為：；00( )( 1)()(1)nnnannaaG xxxxnn （2）母函數(shù)為：；22000554( )(5)5(1)1(1)nnnnnnxxG xnxnxxxxx方法二：方法二： 0001022( )(5)14414111114541(1)1nnnnnnnnG xnxnxxxxxxxxxx （3）母函數(shù)為：；2323000222( )(1)(1)2(1)(1)(1)nnnnnnxxxG xn nxn nxnxxxx方法二：方法二： 2202222002222023

48、( )(1)00121121nnnnnnnnnnG xn nxxn nxxnnxxxxxxxxxx （4）母函數(shù)為：。232300023( )(2)(1)(1)(1)(1)nnnnnnxxxxG xn nxn nxnxxxx方法二：方法二：00002121000023223( )(2)1211111121111111131nnnnnnnnnnnnnnnnG xn nxnnxnxxxxxxxxxxxxxxxxxxx2證明序列的母函數(shù)為 。( , ),(1, ),(2, ),C n n C nn C nn11(1)nx證明：因?yàn)?(, )(1, )(1,1)C nk nC nknC nkn令，23

49、0( )(, )( , )(1, )(2, )(3, )knkG xC nk n xC n nC nn xC nn xC nn x則 ，23( )( , )(1, )(2, )nx G xC n n xC nn xC nn x231( )(1,1)( ,1)(1,1)(2,1)nGxC nnC n nxC nnxC nnx而 1(1)( )( )0nnx G xGx故 1202111111nnnnGxGxGxGxxxx又 23023( )(0,0)(1,0)(2,0)(3,0)111G xCCxCxCxxxxx 所以 111nnxxG方法二：方法二：已知的 k-組合數(shù)為，12nSeee ，(1

50、, )C nkk其母函數(shù)為：23011( )(1)(1)nknknkA xxxxxkx序列的母函數(shù)為( , ),(1, ),(2, ),C n n C nn C nn 230001( )( , )(1, )(2, )(3, )(, )(, )(11, )1(1)kkkkkknG xC n nC nn xC nn xC nn xC nk n xC nk k xC nkk xx 3設(shè)，求序列的母函數(shù)。1234,Seeee na其中，是 S 的滿足下列條件的 n 組合數(shù)。na（1）S 的每個(gè)元素都出現(xiàn)奇數(shù)次；（2）S 的每個(gè)元素都出現(xiàn) 3 的倍數(shù)次；（3）不出現(xiàn)，至多出現(xiàn)一次；1e2e（4）只出現(xiàn)

51、1、3 或 11 次，只出現(xiàn) 2、4 或 5 次；1e2e（5）S 的每個(gè)元素至少出現(xiàn) 10 次。解：（1）4352142( )()1rxG xxxxxx （2）4363431( )(1)1rG xxxxx （3）23221( )(1)(1)(1)xG xxxxxx （4）3112452323112453567813151622( )()()(1)()()2(1)(1)G xxxxxxxxxxxxxxxxxxxxxxxxxx （5）41010114( )()1xG xxxx4投擲兩個(gè)骰子，點(diǎn)數(shù)之和為 r，其組合數(shù)是多少？(212)r解：用表示骰子的點(diǎn)數(shù)為 i， ix（1）若兩個(gè)骰子不同，則問(wèn)題

52、等價(jià)于 r 的特殊有序 2-分拆1216,1,2irrrri故相應(yīng)的母函數(shù)為23456223456789101112( )()234565432G xxxxxxxxxxxxxxxxxx則點(diǎn)數(shù)之和為 r 的方案總數(shù)就是的系數(shù)。rx(212)r（2）若兩個(gè)骰子相同，則問(wèn)題等價(jià)于 r 的特殊無(wú)序 2-分拆121261rrrrr而此問(wèn)題又可轉(zhuǎn)化為求 r 的最大分項(xiàng)等于 2，且項(xiàng)數(shù)不超過(guò) 6 的分拆數(shù)，即求方程的非負(fù)整數(shù)解的個(gè)數(shù)。121212120,1,6xxrxxxx 相應(yīng)的母函數(shù)為 225223423456232222223456789101112( )111112233323G xxxxxxxxx

53、xxxxxxxxxxxxxxxxxxxxx其中點(diǎn)數(shù)之和為 r 的方案數(shù)就是的系數(shù)。rx5投擲 4 個(gè)骰子，其點(diǎn)數(shù)之和為 12 的組合數(shù)是多少？解： 參考第 4 題。（第二版第 5 題）居民小區(qū)組織義務(wù)活動(dòng)，號(hào)召每家出一到兩個(gè)人參加。設(shè)該小區(qū)共有 n 個(gè)家庭，現(xiàn)從中選出 r 人，問(wèn)：（1）設(shè)每個(gè)家庭都是 3 口之家，有多少種不同的選法？當(dāng) n=50 時(shí)，選法有多少種？（2）設(shè) n 個(gè)家庭中兩家有 4 口人，其余家庭都是 3 口人，有多少種選法？解：（1） 12233( )nG xC xC x （2） 221221223344( )nG xC xC xC xC x（第二版第 6 題）把 n 個(gè)相同

54、的小球放入編號(hào)為的 m 個(gè)盒子中，使得每個(gè)盒子內(nèi)1,2,3,m的球數(shù)不小于它的編號(hào)數(shù)。已知，求不同的放球方法數(shù)。22mmn( ,)g n m解：對(duì)應(yīng)母函數(shù)為：(1)2323412(1)23(1)( )()()()(1)(1)(1)(2)(11!2!3!(1)(1) 1(1)!m mmmmmm mn m mxG xxxxxxxxxxxmm mm mmxxxxm mmnm mxnm m 故2(1)(1) 1(1)(1)( ,)(1)!(1)!m mmnm mm mnmg n mnm mnm m6紅、黃、藍(lán)三色的球各 8 個(gè)，從中取出 9 個(gè)，要求每種顏色的球至少一個(gè)，問(wèn)有多少種不同的取法？解：對(duì)應(yīng)

55、的母函數(shù)為：2345678 3323456733234567891011121314234567( )()(1)(12345678765432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 從中取 9 個(gè)對(duì)應(yīng)的組合數(shù)為的系數(shù)，即9x （種） 1 12 1 3 14 1 5 1 6 1 7 128 方法二：方法二：原問(wèn)題等價(jià)于從集合中取出 9 個(gè)元素，且每個(gè)元素8,8,8Sabc至少取一個(gè)?，F(xiàn)在先把元素 a、b、c 各取一個(gè)，然后再隨意選出 6 個(gè)，則問(wèn)題轉(zhuǎn)變?yōu)閺募现腥〕?6 個(gè)元素，且每個(gè)元素個(gè)數(shù)不限，17,7,7Sabc求重復(fù)組合的方案數(shù)。又由于

56、每個(gè)元素的個(gè)數(shù)大于 6，故從中取 6 個(gè)元素與1S從集合中取出 6 個(gè)元素的組合數(shù)一樣多，因此不同的1,Sabc 取法為（種）623 6 1828CC 7將幣值為 2 角的人民幣，兌換成硬幣（壹分、貳分和伍分）可有多少種兌換方法？解：該題用 1 分、2 分、5 分的硬幣組成 20 分。是可重復(fù)的無(wú)序拆分： 其母函數(shù)為： 224510510251025100005100( )(1)(1)(1)1(1)(1)(1)111111(1)4 14 12(1)111( 1)(1)(1)44211 ( 1)2(1)(14iiiiiiiiiiG xxxxxxxxxxxxxxxxxxixxxixxx ) 則不同

57、的兌換方法為的系數(shù)，即20 x 2015105011 ( 1)2(20 1)11 ( 1)2(15 1)141 ( 1)2(10 1)11 ( 1)2(5 1)11 ( 1)2(0 1)129 即有 29 種兌換方法。8有 1 克重砝碼 2 枚，2 克重砝碼 3 枚，5 克重砝碼 3 枚，要求這 8 個(gè)砝碼只許放在天平的一端，能稱幾種重量的物品？有多少種不同的稱法？解：該題屬于有限重復(fù)的無(wú)序拆分問(wèn)題。對(duì)應(yīng)的母函數(shù)為： 224651015234567891011121314151617181920212223( )(1)(1)(1)1222332223322233222G xxxxxxxxxxx

58、xxxxxxxxxxxxxxxxxxxxx 所以能稱 123 克等 23 種重量的物品。 總共的稱法為母函數(shù)的各項(xiàng)系數(shù)之和，再減去常數(shù)項(xiàng)，即總共有（種）不同的稱法。(1) 13 4 4 147G 其中，稱 1、3、20、22、23 克重量各有 1 種稱法； 稱 2、4、5、8、9、10、13、14、15、18、19、21 克重量各有 2 種稱法； 稱 6、7、11、12、16、17 克重量各有 3 種乘法；若要枚舉出各種方案，則可作母函數(shù)：224651015( , , )(1)(1)(1)G x y zxxyyyzzz項(xiàng)即為55511222( ,0nnnnnnnniiix xy yyz zzn

59、 nni 或）稱克重量的一種方案。1222555nnnnnnnn9證明不定方程的正整數(shù)解組的個(gè)數(shù)為。12nxxxr(1,1)C rn解：該問(wèn)題即，求正整數(shù) r 的 n 有序分拆。 問(wèn)題可轉(zhuǎn)換為：將 r 個(gè)無(wú)區(qū)別的球，放入 n 個(gè)不同的盒子中，每盒至少 1個(gè)的組合問(wèn)題。可以先在每個(gè)盒子中放 1 球，再將個(gè)無(wú)區(qū)別的球，放rn入 n 個(gè)不同的盒子中，每盒球數(shù)不限，則其方案數(shù)為：() 1,)(1,1)C nrnrnC rn故該不定方程的正整數(shù)解組的個(gè)數(shù)為。(1,1)C rn方法二：方法二：?jiǎn)栴}可以視為將 r 個(gè)相同的 1 放入 n 個(gè)盒子。由于將之間的值互換，對(duì)ix應(yīng)不同的解，所以盒子不同。設(shè)共有個(gè)解

60、，則的母函數(shù)為rara 231111100001nnnrrrn rk nknkn rn rkkrrkkxG xxxxxxCxCxCxCx 所以 1,1raC rn10求方程的大于 1 的整數(shù)解的個(gè)數(shù)。24xyz解：該題相當(dāng)于將 24 的 3 有序分拆，并且要求每個(gè)分項(xiàng)大于 1。 其母函數(shù)為： 322335530121( )()(1)12(1)2kkxxG xxxxxk kxxx 所求的整數(shù)解的個(gè)數(shù)即為的系數(shù)：。24x119 (19 1)190211設(shè)，其中，。試證：0(,2 )nnkaC nkk0(,21)nnkbC nkk01a 00b （1），；11nnnaab1nnnbab （2）求出、

61、的母函數(shù)，。na nb( )A x( )B x證明：（1）11011111100101(1,2 )(1,0)(1,2 )( ,0)(,2 )(,21)(,2 )(1,21)(1,22)0)(1,21)(11,23)0)nnknknnkknnkknnknnaC nkkC nC nkkC nC nkkC nkkC nkkC nkkC nnnaC nkkC nnnab 000101(,2 )(,21)(1,21)(1,21)(22,23)0)nnnnkknknknabC nkkC nkkC nkkC nkkCnnb （2） 因?yàn)?010111111000( )1()11(0)1( )( )nnnnn

62、nnnnnnnnnnnnnnnnnA xa xaa xab xaxb xa xb xbxA xB x 所以 (1) ( )( )1xA xB x 同理，01101111111100( )()( )( )nnnnnnnnnnnnnnnnnnnnnnB xb xbb xabxaxbxa xb xxA xxB x 所以，( )(1) ( )0 xA xxB x 解聯(lián)立方程組 ，即可得(1) ( )( )1( )(1) ( )0 xA xB xxA xxB x ，21( )1 3xA xxx2( )1 3xB xxx12設(shè)，求序列的母函數(shù)，12,kSeee np其中是 S 的滿足下列條件的 n 排列數(shù)

63、：np（1）S 的每個(gè)元素都出現(xiàn)奇數(shù)次；（2）S 的每個(gè)元素至少出現(xiàn) 4 次；（3）至少出現(xiàn) i 次；ie(1,2, )ik（4）至多出現(xiàn) i 次；ie(1,2, )ik解：（1）母函數(shù)為：；35( )1!3!5!2kkxxexxxeeG x （2）母函數(shù)為：；45623( )14!5!6!2!3!kkxexxxxxG xex （3）母函數(shù)為：；2111( )1!2!1 !jikkxej iiixxxG xexji （4）母函數(shù)為：；2011( )1!1!2!jikkiejiixxxxG xji13把 23 本書(shū)分給甲乙丙丁四人，要求這四個(gè)人得到的書(shū)的數(shù)量分別不超過(guò) 9本、8 本、7 本、6

64、本，問(wèn)：（1）若 23 本書(shū)相同，有多少種不同的分法？（2）若 23 本書(shū)都不相同，又有多少種不同的分法？解：（1）對(duì)應(yīng)的母函數(shù)為：292827262345678910111213141523456789101112131415( )(1)(1)(1)(1)(123456777765432)(123456788765432)G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx所求的分法數(shù)就是的系數(shù)，即23x （種）7 1 7 26 35 44 53 62 7 1 8119 （2）對(duì)應(yīng)的母函數(shù)為：2928272623( )(1)(1)1!2!9!1!2!8!

65、(1)(1)1!2!7!1!2!6!11111111111!1!2!1!1!2!3!1!2!2!1!3!11111118!1!7!2!6!3!5!4!4!5!3!6!2!exxxxxxG xxxxxxxxxx8152381519!6!11111111111!1!2!1!1!2!3!1!2!2!1!3!1111111118!1!7!2!6!3!5!4!4!5!3!6!2!7!1!8!7!xxxxxxx 所求的分法數(shù)就是的系數(shù)，即2323!x1111111123!8!1!7!2!6!3!5!4!4!5!3!6!2!8!7!1111111119!1!8!2!7!3!6!4!5!5!4!6!3!6!8

66、!7!7!1111111111!9!2!8!3!7!4!6!5!5!6!4!5!8!6!7!7!6!12!9! 111111113!8!4!7!5!6!6!5!4!8!5!7!6!6!7!5!1111111113!9!4!8!5!7!6!6!3!8!4!7!5!6!6!5!7!4!1111111114!9!5!8!6!7!2!8!3!7!4!6!5!5!6!4!7!3!115!9! 11111116!8!1!8!2!7!3!6!4!5!5!4!6!3!7!2!1111111116!9!8!1!7!2!6!3!5!4!4!5!3!6!2!7!1!26 281939980582 148 臺(tái)計(jì)算機(jī)分給 3 個(gè)單位，第一個(gè)單位的分配量不超過(guò) 3 臺(tái)，第二個(gè)單位不超過(guò) 4 臺(tái)，第三個(gè)單位不超過(guò) 5 臺(tái)，問(wèn)共有幾種分配方案？解：對(duì)應(yīng)的母函數(shù)為： 2323423452345672345( )(1)(1)(1)(1234432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxx 所求的分配方案數(shù)即的系數(shù)，即分配方案數(shù)為：8x （種）4 14 1 3 12 1 1 11415用母函數(shù)證明下列等