习题2与答案

习题二第1页（共14页）习题二（母函数及其应用）1．求下列数列的母函数(0,1,2,)n（1）(1)nan；（2）{5}n；（3）{(1)}nn；（4）{(2)}nn；解：（1）母函数为：00()(1)()(1)nnnannaaGxxxxnn；（2）母函数为：22000554()(5)5(1)1(1)nnnnnnxxGxnxnxxxxx；方法二：0001022()(5)14414111114541(1)1nnnnnnnnGxnxnxxxxxxxxxx（3）母函数为：2323000222()(1)(1)2(1)(1)(1)nnnnnnxxxGxnnxnnxnxxxx；方法二：2202222002222023()(1)00121121nnnnnnnnnnGxnnxxnnxxnnxxxxxxxxxx（4）母函数为：习题二第2页（共14页）232300023()(2)(1)(1)(1)(1)nnnnnnxxxxGxnnxnnxnxxxx。方法二：00002121000023223()(2)1211111121111111131nnnnnnnnnnnnnnnnGxnnxnnxnxxxxxxxxxxxxxxxxxxx2．证明序列(,),(1,),(2,),CnnCnnCnn的母函数为11(1)nx。证明：因为(,)(1,)(1,1)CnknCnknCnkn令230()(,)(,)(1,)(2,)(3,)knkGxCnknxCnnCnnxCnnxCnnx，则23()(,)(1,)(2,)nxGxCnnxCnnxCnnx，231()(1,1)(,1)(1,1)(2,1)nGxCnnCnnxCnnxCnnx而1(1)()()0nnxGxGx故1202111111nnnnGxGxGxGxxxx又23023()(0,0)(1,0)(2,0)(3,0)111GxCCxCxCxxxxx所以111nnxxG方法二：已知12nSeee，，，的k-组合数为(1,)Cnkk，习题二第3页（共14页）其母函数为：23011()(1)(1)nknknkAxxxxxkx序列(,),(1,),(2,),CnnCnnCnn的母函数为230001()(,)(1,)(2,)(3,)(,)(,)(11,)1(1)kkkkkknGxCnnCnnxCnnxCnnxCnknxCnkkxCnkkxx3．设1234{,,,}Seeee，求序列{}na的母函数。其中，na是S的满足下列条件的n组合数。（1）S的每个元素都出现奇数次；（2）S的每个元素都出现3的倍数次；（3）1e不出现，2e至多出现一次；（4）1e只出现1、3或11次，2e只出现2、4或5次；（5）S的每个元素至少出现10次。解：（1）4352142()()1rxGxxxxxx（2）4363431()(1)1rGxxxxx（3）23221()(1)(1)(1)xGxxxxxx（4）3112452323112453567813151622()()()(1)()()2(1)(1)Gxxxxxxxxxxxxxxxxxxxxxxxxxx（5）41010114()()1xGxxxx4．投掷两个骰子，点数之和为r(212)r，其组合数是多少？解：用ix表示骰子的点数为i，（1）若两个骰子不同，则问题等价于r的特殊有序2-分拆1216,1,2irrrri习题二第4页（共14页）故相应的母函数为23456223456789101112()()234565432Gxxxxxxxxxxxxxxxxxx则点数之和为r的方案总数就是rx的系数(212)r。（2）若两个骰子相同，则问题等价于r的特殊无序2-分拆121261rrrrr而此问题又可转化为求r的最大分项等于2，且项数不超过6的分拆数，即求方程121212120,1,6xxrxxxx的非负整数解的个数。相应的母函数为225223423456232222223456789101112()111112233323Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx其中点数之和为r的方案数就是rx的系数。5．投掷4个骰子，其点数之和为12的组合数是多少？解：参考第4题。（第二版第5题）居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有n个家庭，现从中选出r人，问：（1）设每个家庭都是3口之家，有多少种不同的选法？当n=50时，选法有多少种？（2）设n个家庭中两家有4口人，其余家庭都是3口人，有多少种选法？解：（1）12233()nGxCxCx（2）221221223344()nGxCxCxCxCx（第二版第6题）把n个相同的小球放入编号为1,2,3,,m的m个盒子中，使得每个盒子内的球数不小于它的编号数。已知22mmn，求不同的放球方法数(,)gnm。解：对应母函数为：习题二第5页（共14页）(1)2323412(1)23(1)()()()()(1)(1)(1)(2)(11!2!3!(1)[(1)1][(1)]!mmmmmmmmnmmxGxxxxxxxxxxxmmmmmmxxxxmmmnmmxnmm故2(1)[(1)1](1)(1)(,)[(1)]![(1)]!mmmnmmmmnmgnmnmmnmm6．红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？解：对应的母函数为：23456783323456733234567891011121314234567()()(1)(12345678765432)(1)Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx从中取9个对应的组合数为9x的系数，即1121314151617128（种）方法二：原问题等价于从集合8,8,8Sabc中取出9个元素，且每个元素至少取一个。现在先把元素a、b、c各取一个，然后再随意选出6个，则问题转变为从集合17,7,7Sabc中取出6个元素，且每个元素个数不限，求重复组合的方案数。又由于每个元素的个数大于6，故从1S中取6个元素与从集合1,,Sabc中取出6个元素的组合数一样多，因此不同的取法为62361828CC（种）7．将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？解：该题用1分、2分、5分的硬币组成20分。是可重复的无序拆分：习题二第6页（共14页）其母函数为：224510510251025100005100()(1)(1)(1)1(1)(1)(1)111111(1)41412(1)111(1)(1)(1)44211(1)2(1)(14iiiiiiiiiiGxxxxxxxxxxxxxxxxxxixxxixxx)则不同的兑换方法为20x的系数，即2015105011(1)2(201)11(1)2(151)141(1)2(101)11(1)2(51)11(1)2(01)129即有29种兑换方法。8．有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端，能称几种重量的物品？有多少种不同的称法？解：该题属于有限重复的无序拆分问题。对应的母函数为：224651015234567891011121314151617181920212223()(1)(1)(1)1222332223322233222Gxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx所以能称1～23克等23种重量的物品。总共的称法为母函数的各项系数之和，再减去常数项，即总共有(1)1344147G（种）不同的称法。其中，称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)Gxyzxxyyyzzz项55511222'''''''(,',''0nnnnnnnniiixxyyyzzznnni或）即为称1222555''''''nnnnnnnn克重量的一种方案。9．证明不定方程12nxxxr的正整数解组的个数为(1,1)Crn。习题二第7页（共14页）解：该问题即，求正整数r的n有序分拆。问题可转换为：将r个无区别的球，放入n个不同的盒子中，每盒至少1个的组合问题。可以先在每个盒子中放1球，再将rn个无区别的球，放入n个不同的盒子中，每盒球数不限，则其方案数为：(()1,)(1,1)CnrnrnCrn故该不定方程的正整数解组的个数为(1,1)Crn。方法二：问题可以视为将r个相同的1放入n个盒子。由于将ix之间的值互换，对应不同的解，所以盒子不同。设共有ra个解，则ra的母函数为231111100001nnnrrrnrknknknrnrkkrrkkxGxxxxxxCxCxCxCx所以1,1raCrn10．求方程24xyz的大于1的整数解的个数。解：该题相当于将24的3有序分拆，并且要求每个分项大于1。其母函数为：322335530121()()(1)12(1)2kkxxGxxxxxkkxxx所求的整数解的个数即为24x的系数：119(191)1902。11．设0(,2)nnkaCnkk，0(,21)nnkbCnkk，其中01a，00b。试证：（1）11nnnaab，1nnnbab；（2）求出{}na、{}nb的母函数()Ax，()Bx。习题二第8页（共14页）证明：（1）11011111100101(1,2)(