习题二（母函数及其应用）1．求下列数列的母函数(0,1,2,)n =（1）(1)n a n ⎧⎫⎛⎫-⎨⎬ ⎪⎝⎭⎩⎭；（2）{5}n +； （3）{(1)}n n -； （4）{(2)}n n +；解：（1）母函数为：00()(1)()(1)nn n a n n a a G x x x x n n ∞∞==⎛⎫⎛⎫=-=-=- ⎪ ⎪⎝⎭⎝⎭∑∑；（2）母函数为：22554()(5)5(1)1(1)nnn n n n x xG x n x nx x x x x ∞∞∞===-=+=+=+=---∑∑∑； ♦ 方法二：()()()001022()(5)14414111114541(1)1nnnn n n n n G x n x n x x x x x x x x x x ∞∞∞===∞+==+=++''⎛⎫=+=-+⎪---⎝⎭-=+=---∑∑∑∑ （3）母函数为：2323000222()(1)(1)2(1)(1)(1)nnnn n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ♦ 方法二：()()()()()2202222002222023()(1)00121121nn n n nn n n n n G x n n x xn n xxn n x xx x x x x x x x ∞∞-==∞∞+==∞+==-=++-"=++=""⎛⎫⎛⎫== ⎪⎪-⎝⎭⎝⎭=-∑∑∑∑∑（4）母函数为：232300023()(2)(1)(1)(1)(1)nnnn n n x x x x G x n n x n n x nx x x x ∞∞∞===-=+=++=+=---∑∑∑。

♦ 方法二：()()()()()()()()00212100023223()(2)1211111121111111131nnnnn n n n n n n n n n n n G x n n x n n x n x x x x x x x xx x x x x x x x x x x ∞∞∞∞====∞∞∞∞++++=====+=++-+-"'"'⎛⎫⎛⎫=--=-- ⎪ ⎪--⎝⎭⎝⎭"'⎛⎫⎛⎫=--=-- ⎪ ⎪----⎝⎭--⎝⎭-=-∑∑∑∑∑∑∑∑2．证明序列(,),(1,),(2,),C n n C n n C n n ++ 的母函数为 11(1)n x +- 。

证明：因为 (,)(1,)(1,1)C n k n C n k n C n k n +=+-++--令230()(,)(,)(1,)(2,)(3,)k n k G x C n k n x C n n C n n x C n n x C n n x ∞==+=+++++++∑ ，则 23()(,)(1,)(2,)n x G x C n n x C n n x C n n x =+++++ ，231()(1,1)(,1)(1,1)(2,1)n G x C n n C n n x C n n x C n n x -=--+-++-++-+ 而 1(1)()()0n n x G x G x ---= 故 ()()()()()()1202111111n n n nG x G x G x G x x x x --=⋅=⋅=⋅⋅⋅⋅⋅⋅=⋅--- 又23023()(0,0)(1,0)(2,0)(3,0)111G x C C x C x C x x x x x=++++=++++=-所以 ()()111+-=n n x x G♦ 方法二：已知{}12n S e e e =∞⋅∞⋅∞⋅ ，，，的k-组合数为(1,)C n k k +-，其母函数为：23011()(1)(1)nk nk n k A x x x x x k x ∞=+-⎛⎫=++++== ⎪-⎝⎭∑ 序列(,),(1,),(2,),C n n C n n C n n ++ 的母函数为23001()(,)(1,)(2,)(3,)(,)(,)(11,)1(1)kkk k kk n G x C n n C n n x C n n x C n n x C n k n x C n k k x C n k k xx ∞∞==∞=+=+++++++=+=+=++-=-∑∑∑3．设1234{,,,}S e e e e =∞∞∞∞ ，求序列{}n a 的母函数。

其中，n a 是S 的满足下列条件的n 组合数。

（1）S 的每个元素都出现奇数次； （2）S 的每个元素都出现3的倍数次； （3）1e 不出现，2e 至多出现一次；（4）1e 只出现1、3或11次，2e 只出现2、4或5次； （5）S 的每个元素至少出现10次。

解：（1）4352142()()1r x G x x x x xx +⎛⎫=+++++= ⎪-⎝⎭（2）4363431()(1)1r G x x x x x ⎛⎫=+++++= ⎪-⎝⎭ （3）23221()(1)(1)(1)xG x x x x x x +=+++++=- （4）3112452323112453567813151622()()()(1)()()2(1)(1)G x x x x x x x x x x x x x x x x x x x x x x x x x x =+++++++++++++++++++==-- （5）41010114()()1x G x x x x ⎛⎫=++= ⎪-⎝⎭4．投掷两个骰子，点数之和为r (212)r ≤≤，其组合数是多少？ 解：用i x 表示骰子的点数为i ，（1）若两个骰子不同，则问题等价于r 的特殊有序2-分拆1216,1,2i r r r r i =+⎧⎨≤≤=⎩故相应的母函数为23456223456789101112()()234565432G x x x x x x x x x x x x x x x x x x=+++++=++++++++++则点数之和为r 的方案总数就是r x 的系数(212)r ≤≤。

（2）若两个骰子相同，则问题等价于r 的特殊无序2-分拆121261r r r r r =+⎧⎨≥≥≥⎩ 而此问题又可转化为求r 的最大分项等于2，且项数不超过6的分拆数，即求方程121212120,1,6x x rx x x x ⋅+⋅=⎧⎨≥≥+≤⎩的非负整数解的个数。

相应的母函数为()()()()()()()()()()225223423456232222223456789101112()111112233323G x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x =+++++++++++++++++++=++++++++++ 其中点数之和为r 的方案数就是r x 的系数。

5．投掷4个骰子，其点数之和为12的组合数是多少？解： 参考第4题。

（第二版第5题）居民小区组织义务活动，号召每家出一到两个人参加。

设该小区共有n 个家庭，现从中选出r 人，问：（1）设每个家庭都是3口之家，有多少种不同的选法？当n=50时，选法有多少种？（2）设n 个家庭中两家有4口人，其余家庭都是3口人，有多少种选法？解：（1） ()12233()nG x C x C x =+ （2） ()()221221223344()n G x C x C x C x C x -=++（第二版第6题）把n 个相同的小球放入编号为1,2,3,,m 的m 个盒子中，使得每个盒子内的球数不小于它的编号数。

已知22m m n +≥，求不同的放球方法数(,)g n m 。

解：对应母函数为：(1)2323412(1)23(1)()()()()(1)(1)(1)(2)(11!2!3!(1)[(1)1][(1)]!m m m m m mm m n m m x G x x x x x x x x xxx m m m m m m x x x x m m m n m m x n m m ++++-+=+++++++++=-+++=++++++-+-++-+故2(1)[(1)1](1)(1)(,)[(1)]![(1)]!m m m n m m m m n m g n m n m m n m m ++-+-+--==-+-+6．红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？解：对应的母函数为：23456783323456733234567891011121314234567()()(1)(12345678765432)(1)G x x x x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x =+++++++=+++++++=+++++++++++++++++++++从中取9个对应的组合数为9x 的系数，即11213141516171⨯+⨯+⨯+⨯+⨯+⨯+⨯=（种）♦ 方法二：原问题等价于从集合{}8,8,8S a b c = 中取出9个元素，且每个元素至少取一个。

现在先把元素a 、b 、c 各取一个，然后再随意选出6个，则问题转变为从集合{}17,7,7S a b c = 中取出6个元素，且每个元素个数不限，求重复组合的方案数。

又由于每个元素的个数大于6，故从1S 中取6个元素与从集合{}1,,S a b c =∞∞∞ 中取出6个元素的组合数一样多，因此不同的取法为62361828C C +-==（种）7．将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？解：该题用1分、2分、5分的硬币组成20分。

是可重复的无序拆分：其母函数为：()224510510251025100005100()(1)(1)(1)1(1)(1)(1)111111(1)41412(1)111(1)(1)(1)44211(1)2(1)(14i i ii i i i i i i G x x x x x x x x x x x x x x x x x x i x x x i x x x ∞∞∞===∞==+++++++++=+++--⎡⎤=+++++⎢⎥-+-⎣⎦⎡⎤=+-+++++⎢⎥⎣⎦=+-++++∑∑∑∑ )+ 则不同的兑换方法为20x 的系数，即2015105011(1)2(201)11(1)2(151)141(1)2(101)11(1)2(51)11(1)2(01)129⎡⎡⎤⎡⎤+-++++-+++⎣⎦⎣⎦⎣⎤⎡⎤⎡⎤⎡⎤++-++++-++++-++⎣⎦⎣⎦⎣⎦⎦= 即有29种兑换方法。