习 题 二2-1 求下列数列的母函数（n ＝0,1,2，…）：（1）()⎭⎬⎫⎩⎨⎧⎪⎪⎭⎫ ⎝⎛-n n α1 ； （2）{ n ＋5 }（3）{ n (n －1) } ； （4）{ n (n ＋2) }（解）（1）()x G ＝()∑∞=⎪⎪⎭⎫ ⎝⎛-01n n nx n α＝()∑∞=-⎪⎪⎭⎫ ⎝⎛0n nx n α＝()αx -1 （2）()x G ＝()∑∞=+05n nx n ＝()∑∑∞=∞=++041n n n nx x n＝()x x n n -+'∑∞=+1401＝xx n n -+'⎪⎪⎭⎫ ⎝⎛∑∞=+1401＝x x -+'⎪⎭⎫⎝⎛--14111＝()x x -+-14112＝()2145x x--（3）()x G ＝()∑∞=-01n nxn n ＝()∑∞=--++222100n n xn n x＝()()∑∞=++0212n nxn n x＝()∑∞=+"022n n x x＝"⎪⎪⎭⎫ ⎝⎛∑∞=+022n n x x ＝"⎪⎪⎭⎫ ⎝⎛-x x x 122＝()3212x x - （4）()x G ＝()∑∞=+02n nxn n ＝()()()∑∑∑∞=∞=∞=-+-++0121n n n nn nx x n xn n＝()()x x x n n n n --'-"∑∑∞=+∞=+1112＝x x x n n n n --'⎪⎪⎭⎫ ⎝⎛-"⎪⎪⎭⎫ ⎝⎛∑∑∞=+∞=+110102＝x x x x x --'⎪⎭⎫⎝⎛--"⎪⎪⎭⎫ ⎝⎛-11112 ＝()()x x x -----11111223＝()3213x x x --组合数学 22-2 证明序列C (n ，n )，C (n ＋1，n )，C (n ＋2，n )，…的母函数为()111+-n x（证）已知集合{}n e e e S ⋅∞⋅∞⋅∞=，，， 21的r-组合的母函数为()∑∞=⎪⎪⎭⎫ ⎝⎛-+=-0111r r nx r r n x 所以序列()n n C ,，()n n C ,1+，()n n C ,2+，……的母函数为()x G ＝ +⎪⎪⎭⎫ ⎝⎛+++⎪⎪⎭⎫ ⎝⎛++⎪⎪⎭⎫ ⎝⎛++⎪⎪⎭⎫ ⎝⎛rx n r n x n n x n n x n n 21021 ＝∑∞=⎪⎪⎭⎫ ⎝⎛+0r rx r r n ＝()∑∞=⎪⎪⎭⎫ ⎝⎛-++011r rx r r n ＝()111+-n x2-3 设S ＝{}4321,,,e e e e ⋅∞⋅∞⋅∞⋅∞，求序列{}n a 的母函数，其中a n 是S 的满足下列条件的n 组合数：（1） S 的每个元素都出现奇数次； （2） S 的每个元素出现3的倍数次； （3） e 1不出现，e 2至多出现一次；（4） e 1只出现1、3或11次，e 2只出现2、4或5次； （5） S 的每个元素至少出现10次。

（解）（1）()x G ＝()453+++x x x ＝()4241x x -；（2）()x G ＝()49631 ++++x x x ＝()4311x -；（3）()x G ＝()()23211 +++++x x x x ＝()211x x-+；（4）()x G ＝()()()2325421131 ++++++++x x x x x x x x x＝()216151********x x x x x x x x x -+++++++；（5）()x G ＝()4121110+++x x x＝()4401x x -。

第二章 母函数及其应用 32-4 投掷两个骰子，点数之和为r (2≤r ≤12)，其组合数是多少？ 2-5 投掷4个骰子，其点数之和为12的组合数是多少？2-6 红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？（解）设从中取r 个的不同取法有r a 种，那么，数列r a 的母函数为()x G ＝()3832x x x x ++++＝()16109843278732x x x x x x x ++++++++()832x x x x ++++⋅ ＝24109854335282163x x x x x x x ++++++++因此所求方案数为9a ＝28另法：原问题等价于从集合S ＝{}c b a ⋅⋅⋅888,,中取出9个元素，且每个元素至少取一个。

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

又由于每个元素的个数大于6，故从1S 中取6个元素与从集合2S ＝{}c b a ⋅∞⋅∞⋅∞,,中取出6个元素的组合数一样多，从而知不同的取法为28286163==-+C C2-7 将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？（解）这是求正整数n 的分项只能等于1、2、5的分拆数。

设n 的分拆数为 n a ，则n a 的母函数为()x G ＝()()()+++++++++105422111x x x x x x＝⎪⎪⎭⎫ ⎝⎛+⎥⎥⎤⎢⎢⎡++++++++ nx n x x x x x 21332215432 ()+++⋅1051x x＝ ++++++++2054322943221x x x x x x所以，共有20a ＝29种兑换方法。

2-8 有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端。

能称几种重量的物品？有多少种不同的称法？（解）设秤r 克重的物体有r a 种秤法，那么数列{{}r a 的母函数是()()()()151056422111x x x x x x x x x G +++⋅+++++=展开后得组合数学 4()1110987654323222332221x x x x x x x x x x x x G +++++++++++=222120191817161514131223242323x x x x x x x x x x x +++++++++++因此，能称1～22克共22种重量的物品，所有不同的称法总数为()1G ＝3×4×4＝482-9 证明不定方程n x x x +++ 21＝r 的正整数解组的个数为 ()11--n r C ,。

（证）问题可以视为将r 个相同的1放入n 个盒子。

由于将i x 之间的值互换，对应不同的解，所以盒子不同。

设共有r a 个解，则由式（2.1.1）知r a 的母函数为()x G ＝()nx x x +++32＝nx x ⎪⎭⎫⎝⎛-1＝∑∞=-+01r rrr n nx Cx ＝∑∞=+-+01r rn r r n x C ＝∑∞=--01k knk k x C＝∑∞=--011k kn k x C 所以r a ＝()11--n r C ,2-10 求方程z y x ++＝24 的大于1的整数解的个数。

（解）原方程即 ⎩⎨⎧=≥=++.,,,,321224321i x x x x i，令1-=i i x y ()321,,=i ，可得等价方程⎩⎨⎧=≥=++.,,,,321121321i y y y y i 由上题知后者共有()13121--,C ＝190组正整数解，从而知原不定方程的大于1的整数解的个数为190。

2-11 设a n ＝()∑=+n k k k n C 02,，b n＝()∑=++nk k k n C 012,其中a 0＝1，b 0＝0，（1） 试证a n ＋1＝a n ＋b n ＋1， b n ＋1＝a n ＋b n ； （2） 求出{ a n }，{ b n }之母函数A (x )，B (x )。

（解）（1）由序列的定义1+n a ＝∑+=++1021n k k k n C ＝∑+=++++112101n k kk n n C C第二章 母函数及其应用 5＝∑∑+=-++=++++111211201n k k k n n k k kn n C CC＝∑∑=+++=+++nk k k n nk k k n nC CC 0121120＝∑∑+=+++=++112102n k k k n nk kkn C C1+n b ＝∑+=+++10121n k k kn C＝()()112120121+++=++++∑n n nk k k n C C ＝∑∑=++=++n k k k n nk k kn C C1202 ＝n n b a +（2）由母函数的定义及（1）中所知数列n a 和n b 的关系知()x A ＝∑∞=0n nn xa ＝()∑∞=-++110n n n n x b a a＝∑∑∞=∞=--++11111n n n n n n x b x a x＝∑∑∞=∞=++01n nn n nn x b x a x＝()()x B x xA ++1()x B ＝∑∞=0n nn xb ＝()∑∞=--++1110n nn n x b a b ＝∑∑∞=--∞=--++1111110n n n n n n x b x xa x＝()()x xB x xA+组合数学 6即函数()x A 和()x B 满足方程()()()()()()⎩⎨⎧+=++=x xB x xA x B x B x xA x A 1 解之得()x A ＝2311x x x +--，()xB ＝231x x x+- 2-12 设S ＝{}k e e e ⋅∞⋅∞⋅∞,,,21 ，求序列{}n p 的母函数，其中p n 是S 的满足下列条件的n 排列数：（1）S 的每个元素都出现奇数次； （2）S 的每个元素至少出现4次； （3）e i 至少出现i 次（i ＝1,2, …,k ）； （3） e i 至多出现i 次（i ＝1,2, …,k ）。

（解）（1）()x G e ＝kx x x ⎪⎪⎭⎫ ⎝⎛+++ !!!53153＝kx x e e ⎪⎪⎭⎫⎝⎛--2； （2）()x G e ＝kx x x ⎪⎪⎭⎫ ⎝⎛+++ !!!654654＝kx x x x e ⎪⎪⎭⎫⎝⎛----!!32132；（3）()x G e ＝()()∏=++⎪⎪⎭⎫ ⎝⎛+++++ki i i i i x i x i x 12121 !!!＝()∏=-⎪⎪⎭⎫ ⎝⎛------ki i x i x x x e 112121!! ； （4）()x G e ＝∏=⎪⎪⎭⎫⎝⎛++++ki i i x x x 12211!!!2-13 把23本书分给甲、乙、丙、丁四人，要求这四个人得到的书的数量分别不得超过9本、8本、7本、6本，问（1） 若23本书相同，有多少种不同的分法？ （2） 若23本书都不相同，又有多少种不同的分法？2-14 8台计算机分给3个单位，第一个单位的分配量不超过3台，第二单位不超过4台，第三单位不超过5台，问共有几种分配方案？（解）设分配n 台计算机的分配方案有n a 种，则n a 的母函数为第二章 母函数及其应用 7()x G ()()()543243232111x x x x x x x x x x x x ++++++++++++＝1＋876543214171817141063x x x x x x x x +++++++＋12111093610x x xx +++所以分配8台计算机共有8a ＝14种方案。