习习题2与答案

1、1习题二（母函数及其应用）习题二（母函数及其应用）1求下列数列的母函数(0,1,2,)n （1）；( 1)nan （2）；5n （3）； (1)n n（4）； (2)n n解：（1）母函数为：；00( )( 1)()(1)nnnannaaG xxxxnn （2）母函数为：；22000554( )(5)5(1)1(1)nnnnnnxxG xnxnxxxxx 方法二：方法二： 0001022( )(5)14414111114541(1)1nnnnnnnnG xnxnxxxxxxxxxx （3）母函数为：；2323000222( )(1)(1)2(1)(1)(1)nnnnnnxxxG xn nxn

2、nxnxxxx 方法二：方法二： 2202222002222023( )(1)00121121nnnnnnnnnnG xn nxxn nxxnnxxxxxxxxxx （4）母函数为：2。232300023( )(2)(1)(1)(1)(1)nnnnnnxxxxG xn nxn nxnxxxx 方法二：方法二：00002121000023223( )(2)1211111121111111131nnnnnnnnnnnnnnnnG xn nxnnxnxxxxxxxxxxxxxxxxxxx2证明序列的母函数为 。( , ),(1, ),(2, ),C n n C nn C nn11(1)nx证明：因为

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-组合数为，12nSeee ，(1, )C nkk3其母函数为：23011( )(1)(1)nknknkA xxxxxkx序列的母函数为( , ),(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设，求序列的母函数。1234,Seeee na其中，是 S 的满足下列条件的 n 组合数。na（1）S 的每个元素都出现奇数次；（2）S 的每个元

5、素都出现 3 的倍数次；（3）不出现，至多出现一次；1e2e（4）只出现 1、3 或 11 次，只出现 2、4 或 5 次；1e2e（5）S 的每个元素至少出现 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投掷两个骰子，点数之和为 r，其组合数是多少(

6、212)r解：用表示骰子的点数为 i， ix（1）若两个骰子不同，则问题等价于 r 的特殊有序 2-分拆1216,1,2irrrri4故相应的母函数为23456223456789101112( )()234565432G xxxxxxxxxxxxxxxxxx则点数之和为 r 的方案总数就是的系数。rx(212)r（2）若两个骰子相同，则问题等价于 r 的特殊无序 2-分拆121261rrrrr而此问题又可转化为求 r 的最大分项等于 2，且项数不超过 6 的分拆数，即求方程的非负整数解的个数。121212120,1,6xxrxxxx 相应的母函数为 2252234234562322222234

7、56789101112( )111112233323G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx其中点数之和为 r 的方案数就是的系数。rx5投掷 4 个骰子，其点数之和为 12 的组合数是多少解： 参考第 4 题。（第二版第 5 题）居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有 n 个家庭，现从中选出 r 人，问：（1）设每个家庭都是 3 口之家，有多少种不同的选法当 n=50 时，选法有多少种（2）设 n 个家庭中两家有 4 口人，其余家庭都是 3 口人，有多少种选法解：（1） 12233( )nG xC xC x （2） 221221223344( )

8、nG xC xC xC xC x（第二版第 6 题）把 n 个相同的小球放入编号为的 m 个盒子中，使得每个盒子内1,2,3,m的球数不小于它的编号数。已知，求不同的放球方法数。22mmn( ,)g n m解：对应母函数为：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红、黄、蓝三色的球各 8 个，从中取

9、出 9 个，要求每种颜色的球至少一个，问有多少种不同的取法解：对应的母函数为：2345678 3323456733234567891011121314234567( )()(1)(12345678765432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 从中取 9 个对应的组合数为的系数，即9x （种） 1 12 1 3 14 1 5 1 6 1 7 128 方法二：方法二：原问题等价于从集合中取出 9 个元素，且每个元素8,8,8Sabc至少取一个。现在先把元素 a、b、c 各取一个，然后再随意选出 6 个，则问题转变为从集合中取出 6 个元素，

10、且每个元素个数不限，17,7,7Sabc求重复组合的方案数。又由于每个元素的个数大于 6，故从中取 6 个元素与1S从集合中取出 6 个元素的组合数一样多，因此不同的1,Sabc 取法为（种）623 6 1828CC 7将币值为 2 角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法解：该题用 1 分、2 分、5 分的硬币组成 20 分。是可重复的无序拆分：6 其母函数为： 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 ) 则不同的兑换方法为的系数，即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 个砝码只许放在天平的一端，能称几种重量的物品有多少种不同的称法解：该题属于有限重复的无序拆分问题。对应的母函数为： 224651015234567891011121314151617181920212223( )(1)(1)(1)1

12、222332223322233222G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 所以能称 123 克等 23 种重量的物品。 总共的称法为母函数的各项系数之和，再减去常数项，即总共有（种）不同的称法。(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 种乘法；若要枚举出各种方案，则可作母函数：224651015( , , )(1)(1)(1)G x y zxxyyyzzz项即为5551

13、1222( ,0nnnnnnnniiix xy yyz zzn nni 或）称克重量的一种方案。1222555nnnnnnnn79证明不定方程的正整数解组的个数为。12nxxxr(1,1)C rn解：该问题即，求正整数 r 的 n 有序分拆。 问题可转换为：将 r 个无区别的球，放入 n 个不同的盒子中，每盒至少 1个的组合问题。可以先在每个盒子中放 1 球，再将个无区别的球，放rn入 n 个不同的盒子中，每盒球数不限，则其方案数为：() 1,)(1,1)C nrnrnC rn故该不定方程的正整数解组的个数为。(1,1)C rn 方法二：方法二：问题可以视为将 r 个相同的 1 放入 n 个盒

14、子。由于将之间的值互换，对ix应不同的解，所以盒子不同。设共有个解，则的母函数为rara 231111100001nnnrrrn rk nknkn rn rkkrrkkxG xxxxxxCxCxCxCx 所以 1,1raC rn10求方程的大于 1 的整数解的个数。24xyz解：该题相当于将 24 的 3 有序分拆，并且要求每个分项大于 1。 其母函数为： 322335530121( )()(1)12(1)2kkxxG xxxxxk kxxx 所求的整数解的个数即为的系数：。24x119 (19 1)190211设，其中，。试证：0(,2 )nnkaC nkk0(,21)nnkbC nkk01

15、a 00b （1），；11nnnaab1nnnbab （2）求出、的母函数，。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） 因为 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 解联立方程组 ，即可得(1) ( )( )1( )(1) ( )0 xA xB xxA xxB x ，21( )1 3xA xxx2( )1 3xB xxx12设，求序列的

17、母函数，12,kSeee np其中是 S 的满足下列条件的 n 排列数：np（1）S 的每个元素都出现奇数次；（2）S 的每个元素至少出现 4 次；（3）至少出现 i 次；ie(1,2, )ik（4）至多出现 i 次；ie(1,2, )ik解：（1）母函数为：；35( )1!3!5!2kkxxexxxeeG x （2）母函数为：；45623( )14!5!6!2!3!kkxexxxxxG xex （3）母函数为：；2111( )1!2!1 !jikkxej iiixxxG xexji （4）母函数为：；2011( )1!1!2!jikkiejiixxxxG xji13把 23 本书分给甲乙丙丁

18、四人，要求这四个人得到的书的数量分别不超过 9本、8 本、7 本、6 本，问：（1）若 23 本书相同，有多少种不同的分法（2）若 23 本书都不相同，又有多少种不同的分法解：（1）对应的母函数为：292827262345678910111213141523456789101112131415( )(1)(1)(1)(1)(123456777765432)(123456788765432)G xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx所求的分法数就是的系数，即23x （种）7 1 7 26 35 44 53 62 7 1 811910 （2）对应的母

19、函数为：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 所求的分法数就是的系数，即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 台计算机分给 3 个单位，第一个单位的分配量不超过 3 台，第二个单位不超过 4 台，第三个单位不超过 5 台，问共有几种分配方案解：对应的母函数为：11 2323423452345672345( )(1)(1)(1)(1234432)(1)G xxxxxxxxxxxxxxxxxxxxxxxxx 所求的分配方案数即的系数，即分配方案数为：8x （种）4 14 1 3 12 1 1 11415用母函数证明下列等式成立： （1）；222201nnnnnn （2）。111nnnmnmnnnn 证明：（1） 方法一方法一：根据范德蒙恒等式01

22、10mnnmnmnmrrrr 令，即得mrn2222011001nnnnnnnnnnnnnnn 方法二方法二：因为，两边展开得2(1)(1)(1)nnnxxx 22222201201nnnnnnnnnnxxxxxnnn 比较次方的系数，即得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 因为，23(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比较两边的系数，即可得：。nx111nnnmnmnnnn 方法三（组合意义法）方法三（组合意义法）等式右端：相当于从个不同的球中取个

24、球的组合，1nm1n其组合方案数为；(1,1)C nmn等式左端：把这个球编号为，按取出的球中最小的1nm1,2,1nm编号，可分为如下的 m+1 类：如果取出的个球中最小编号是 1，其余 n 个球要从去掉 1 号球后1n剩下的个球中选取，此类组合方案数为；nm(, )C nm n如果取出的个球中最小编号是 2，则 1 不能被选取，其余 n 个球1n要从去掉 1，2 号球后剩下的个球中选取，此类组合方案数为1nm；，依次类推，(1, )C nmn如果取出的个球中最小编号是 m，则不能被选取，其1n1,2,1m余 n 个球要从去掉号球后剩下的个球中选取，此类组1,2,1,mm1n合方案数为；(1, )C nn如果取出的个球中最小编号是，则不能被选取，1n