習(xí)習(xí)題2與答案

1、1習(xí)題二（母函數(shù)及其應(yīng)用）習(xí)題二（母函數(shù)及其應(yīng)用）1求下列數(shù)列的母函數(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

2、nxnxxxx 方法二：方法二： 2202222002222023( )(1)00121121nnnnnnnnnnG xn nxxn nxxnnxxxxxxxxxx （4）母函數(shù)為：2。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)?/p>

3、 (, )(1, )(1,1)C nk nC nknC nkn令，230( )(, )( , )(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 所以 111

4、nnxxG 方法二：方法二：已知的 k-組合數(shù)為，12nSeee ，(1, )C nkk3其母函數(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è)元

5、素都出現(xiàn) 3 的倍數(shù)次；（3）不出現(xiàn)，至多出現(xiàn)一次；1e2e（4）只出現(xiàn) 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ù)是多少(

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

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

8、nG xC xC xC xC x（第二版第 6 題）把 n 個(gè)相同的小球放入編號為的 m 個(gè)盒子中，使得每個(gè)盒子內(nèi)1,2,3,m的球數(shù)不小于它的編號數(shù)。已知，求不同的放球方法數(shù)。22mmn( ,)g n m解：對應(yīng)母函數(shù)為：5(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、出 9 個(gè)，要求每種顏色的球至少一個(gè)，問有多少種不同的取法解：對應(yīng)的母函數(shù)為：2345678 3323456733234567891011121314234567( )()(1)(12345678765432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 從中取 9 個(gè)對應(yīng)的組合數(shù)為的系數(shù)，即9x （種） 1 12 1 3 14 1 5 1 6 1 7 128 方法二：方法二：原問題等價(jià)于從集合中取出 9 個(gè)元素，且每個(gè)元素8,8,8Sabc至少取一個(gè)?，F(xiàn)在先把元素 a、b、c 各取一個(gè)，然后再隨意選出 6 個(gè)，則問題轉(zhuǎn)變?yōu)閺募现腥〕?6 個(gè)元素，

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

11、 xxxxxxxxxxxxxxxxxxixxxixxx ) 則不同的兌換方法為的系數(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ù)的無序拆分問題。對應(yīng)的母函數(shù)為： 224651015234567891011121314151617181920212223( )(1)(1)(1)1

12、222332223322233222G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 所以能稱 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)即為5551

13、1222( ,0nnnnnnnniiix xy yyz zzn nni 或）稱克重量的一種方案。1222555nnnnnnnn79證明不定方程的正整數(shù)解組的個(gè)數(shù)為。12nxxxr(1,1)C rn解：該問題即，求正整數(shù) r 的 n 有序分拆。 問題可轉(zhuǎn)換為：將 r 個(gè)無區(qū)別的球，放入 n 個(gè)不同的盒子中，每盒至少 1個(gè)的組合問題。可以先在每個(gè)盒子中放 1 球，再將個(gè)無區(qū)別的球，放rn入 n 個(gè)不同的盒子中，每盒球數(shù)不限，則其方案數(shù)為：() 1,)(1,1)C nrnrnC rn故該不定方程的正整數(shù)解組的個(gè)數(shù)為。(1,1)C rn 方法二：方法二：問題可以視為將 r 個(gè)相同的 1 放入 n 個(gè)盒

14、子。由于將之間的值互換，對ix應(yīng)不同的解，所以盒子不同。設(shè)共有個(gè)解，則的母函數(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 nkk01

15、a 00b （1），；11nnnaab1nnnbab （2）求出、的母函數(shù)，。na nb( )A x( )B x8證明：（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)?0

16、10111111000( )1()11(0)1( )( )nnnnnnnnnnnnnnnnnnnnnnA 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 x9 解聯(lián)立方程組 ，即可得(1) ( )( )1( )(1) ( )0 xA xB xxA xxB x ，21( )1 3xA xxx2( )1 3xB xxx12設(shè)，求序列的

17、母函數(shù)，12,kSeee np其中是 S 的滿足下列條件的 n 排列數(shù)：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 本書分給甲乙丙丁

18、四人，要求這四個(gè)人得到的書的數(shù)量分別不超過 9本、8 本、7 本、6 本，問：（1）若 23 本書相同，有多少種不同的分法（2）若 23 本書都不相同，又有多少種不同的分法解：（1）對應(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 811910 （2）對應(yīng)的母

19、函數(shù)為：2928272623( )(1)(1)1!2!9!1!2!8!(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!111

20、1111119!1!8!2!7!3!6!4!5!5!4!6!3!6!8!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!

21、3!6!2!7!1!26 281939980582 148 臺計(jì)算機(jī)分給 3 個(gè)單位，第一個(gè)單位的分配量不超過 3 臺，第二個(gè)單位不超過 4 臺，第三個(gè)單位不超過 5 臺，問共有幾種分配方案解：對應(yīng)的母函數(shù)為：11 2323423452345672345( )(1)(1)(1)(1234432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxx 所求的分配方案數(shù)即的系數(shù)，即分配方案數(shù)為：8x （種）4 14 1 3 12 1 1 11415用母函數(shù)證明下列等式成立： （1）；222201nnnnnn （2）。111nnnmnmnnnn 證明：（1） 方法一方法一：根據(jù)范德蒙恒等式01

22、10mnnmnmnmrrrr 令，即得mrn2222011001nnnnnnnnnnnnnnn 方法二方法二：因?yàn)?，兩邊展開得2(1)(1)(1)nnnxxx 22222201201nnnnnnnnnnxxxxxnnn 比較次方的系數(shù)，即得nx 2222011001nnnnnnnnnnnnnnn （2） 方法一方法一：令，( , )(1, )(, )maC n nC nnC nm n 則 ，1(1, )(1,1)mmmaaC nmnaC nmm且，0( , )1aC n n令20120( )mmmA xa xaa xa x12則10( )1( )(1,1)mmA xxA xC nmmx 即23

23、(1) ( )1(1,1)(2,2)(3,3)x A xC nxC nxC nx 因?yàn)椋?3(1)1(1,1)(2,2)(3,3)(1)nC nxC nxC nxx所以，(1)(1) ( )(1)nx A xx故 2231( )(1)1(2,1)(3,2)(4,3)(1,)nmA xxC nxC nxC nxC nmm x 所以 。證畢。(1,)(1,1)maC nmmC nmn 方法二：方法二：11111111111111nnn mmnn mnxxxxxxxxx比較兩邊的系數(shù)，即可得：。nx111nnnmnmnnnn 方法三（組合意義法）方法三（組合意義法）等式右端：相當(dāng)于從個(gè)不同的球中取個(gè)

24、球的組合，1nm1n其組合方案數(shù)為；(1,1)C nmn等式左端：把這個(gè)球編號為，按取出的球中最小的1nm1,2,1nm編號，可分為如下的 m+1 類：如果取出的個(gè)球中最小編號是 1，其余 n 個(gè)球要從去掉 1 號球后1n剩下的個(gè)球中選取，此類組合方案數(shù)為；nm(, )C nm n如果取出的個(gè)球中最小編號是 2，則 1 不能被選取，其余 n 個(gè)球1n要從去掉 1，2 號球后剩下的個(gè)球中選取，此類組合方案數(shù)為1nm；，依次類推，(1, )C nmn如果取出的個(gè)球中最小編號是 m，則不能被選取，其1n1,2,1m余 n 個(gè)球要從去掉號球后剩下的個(gè)球中選取，此類組1,2,1,mm1n合方案數(shù)為；(1, )C nn如果取出的個(gè)球中最小編號是，則不能被選取，1n