清华版组合数学(第二版)第二章习题答案

组合数学第2章答案2.1 求序列{0，1，8，27，…3n …}的母函数。

解：()()++++++=++++++=nn n x n x x x x G x a x a x a x a a x G 3323322102780()46414321313=+-+--==-----n n n n n n n a a a a a n a n a左右同乘再连加：464:0464:0464:0464:4321543211123455012344=+-+-=+-+-=+-+-=+-+-----------n n n n n n n n n n n n a a a a a x a a a a a x a a a a a x a a a a a x母函数：()()42162036-+-=x x x x G2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。

解：1(1)nx -的第k 项为：11()k n n +-- ，对于本题，n=4， ∴母函数为：41(1)x -2.3 已知母函数G （X ）=25431783x x x--+,求序列{ n a }解：G （X ）=)61)(91(783x x x +-+=)61()91(x Bx A ++-从而有： ⎩⎨⎧-==⇒⎩⎨⎧=-=+4778963B A B A B A G （X ）=)61(4)91(7x x +-+-G （X ）=7)999x (13322 ++++x x -4))6((-6)(-6)x (13322 +-+++x xn a =7*n )6(*49n -- 2.4．已知母函数239156xx x ---，求对应的序列{}n a 。

解：母函数为239()156x G x x x -=--39(17)(18)xx x -=+- A BG(x)17x 18xA(18x)B(17x)39x=++--++=-令 A B 38A +7B =9+=⎧⎨--⎩解得：A=2 B=1所以 ii i 0i 021G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑n n n a 2*(7)8=-+2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。

第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 2⨯5⨯P(8,2)+3⨯4⨯P(8,2)6. (n+1)!-17. 用数学归纳法易证。

8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn k , 则n 2的除数个数为 ( 2p 1+1) (2p 2+1) …(2p k+1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。

11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。

当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。

故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。

2.1题（陈兴）求序列{ 0，1，8，27，3n }的母函数。

解：由序列可得到32333()23n G x x x x n x =+++++因为23111n x x x x x =++++++- 2311()'12341n x x x nx x-=++++++-设 2311()()'23(1)1n np x x x x x n x nx x-==++++-+-2222221[()]'123(1)n n p x x x x n x n x --=+++++-+设 2223212()[()]'23(1)n nq x x p x x x x n x n x -==++++-+3323231[()]'123(1)n n q x x x n x n x --=++++-+ 3233313[()]'23(1)n n x q x x x x n x n x -=+++-+ 由以上推理可知[()]'x q x =,[7*94*(6)],n n +-所以可通过求得[()]'x q x 得到序列的母函数：32()4G x x x x =++2321()()[34(3)]6n H x F x dx x x n x +==++++⎰2.2题（陈兴）已知序列343,,,,333n ⎧+⎛⎫⎛⎫⎛⎫⎫⎨⎬ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎭⎩，求母函数 解： 3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1nn n n G x x +++=+++=1[3.2.1 4.3.2(3)(2)(1)]6n x n n n x ++++++211()()[3.2 4.3(3)(2)]6n F x G x dx x x n n x +==+++++⎰ 2321()()[34(3)]6n H x F x dx x x n x +==++++⎰3431()()[]6n I x H x dx x X x ++==++⎰因为23111n x x x x+=+++++-所以211()(1)61I x x x x=----所以31()[]'''61x G x x=-就是所求序列的母函数。

2.1 求序列{0，1，8，27，…3n …}的母函数。

解：()()++++++=++++++=nn n x n x x x x G x a x a x a x a a x G 3323322102780()046414321313=+-+--==-----n n n n n n n a a a a a n a n a左右同乘再连加：464:0464:0464:0464:4321543211123455012344=+-+-=+-+-=+-+-=+-+-----------n n n n n n n n n n n n a a a a a x a a a a a x a a a a a x a a a a a x母函数：()()42162036-+-=x x x x G2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。

解：1(1)nx -的第k 项为：11()k n n +-- ，对于本题，n=4， ∴母函数为：41(1)x - 2.3 已知母函数G （X ）= 25431783x x x--+,求序列{ n a }解：G （X ）=)61)(91(783x x x +-+=)61()91(x Bx A ++-从而有： ⎩⎨⎧-==⇒⎩⎨⎧=-=+4778963B A B A B AG （X ）=)61(4)91(7x x +-+-G （X ）=7)999x (13322 ++++x x -4))6((-6)(-6)x (13322 +-+++x xn a =7*n )6(*49n -- 2.4．已知母函数239156xx x---，求对应的序列{}n a 。

解：母函数为239()156x G x x x -=--39(17)(18)xx x -=+- A BG(x)17x 18xA(18x)B(17x)39x=++--++=-令 A B 38A +7B =9+=⎧⎨--⎩解得：A=2 B=1所以 ii i 0i 021G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑n n n a 2*(7)8=-+2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。

第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。

满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。

满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。

1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。

将女生插入，有5!种方案。

故按乘法原理，有：7!×58C ×5!=33868800(种)方案。

(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≢n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。

习题二（母函数及其应用）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 +- 。