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

组合数学第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 数。

7 1 a2 22. 1 1 b2 c2 a3 b3 c3 = = = = =
r3 −r1 r2 −r1
1 0
a2 b2 − a2
a3 c2 − a2 c3 − a3 1 a a2 = (b2 − a2 )(c3 − a3 ) − (c2 − a2 )(b3 − a3 )
0 c2 − a2
= (b − a)(c − a)[(b + a)(c2 + ac + a2 ) − (c + a)(b2 + ab + a2 )] = (b − a)(c − a)[bc2 + ac2 − b2 c − ab2 ] = (b − a)(c − a)(c − b)(ab + bc + ca) = (ab + bc + ca) 1 1 b c b2 c
2 0 . . . 0 0
0 . . . 0 0
= −2(n − 2)!
1 a 29. a . . . a
2
1 a−1 (a − 1) . . . (a − 1)
2
1 a−2 (a − 2) . . . (a − 2)
2
··· ··· ··· ··· ···
1 a−n (a − n)2 . . . (a − n)n
n(n+1) 2
n+1阶vandermonde = = = = = = = = = = = = = = 行列式
[(a − j ) − (a − i)]
0≤i<j ≤n1+2+···+n 1!2!3! · · · n! = (−1)
n k=1
k!
an 1 30. an 2 . . . an n+1

7! 2!(7−2)!
=
7! 2!5!
and C (7, 5) =
7! 5!(7−5)!
=
7! 5!2! ;
8 7(b). C (6, 4) =
6! 4!(6−4)!
Answers to Selected Exercises =
6! 4!2!
and C (6, 2) =
6! 2!(6−2)!
=
6! 2!4! ;
n+1 2
× 3 × 10−9 . × 3 × 10−11 .
8(a). n × 3 × 10−11 . 8(b).
n+1 2
Section 2.5 . 1(a). 3 · 2; 1(b). 5 · 4 · 3; 1(c). 8 · 7 · 6 · 5 · 4; 1(d). 0; 2(a). 63 ; 2(b). 6 · 5 · 4; 2(c). 1 · 6 · 6; 2(d). 1 · 5 · 4; 3(a). 84 ; 3(b). 8 · 7 · 6 · 5; 3(c). 1 · 8 · 8 · 8;
8. 1 7 21 35 35 21 7 1; 9. C (5, 3) =
5! 3!2!
= 10, C (4, 2) =
4! 2!2!
= 6, C (4, 3) =
4! 3!1!
= 4, and 10 = 6 + 4; = 6, and 21 = 15 + 6;
10. C (7, 5) =
7! 5!2!
4
Answers to Selected Exercises
Applied Combinatorics
by Fred S. Roberts and Barry Tesman

第一章答案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 种。

7.网络地址、主机地址8.分片、重组
9.ICMP10.类型、差错报告、ICMP控制报文、请求应答
11.静态路由、动态路由
二、选择题
1. A2. C3. C4. C5. C6. A
7. C8. D9. D10. C11. A12. CBBAA
三、问答题
5.
源结点
目的地
下一站
代价
C
A
D
4
B
B
4
C
0
D
D
2
2.网络的拓扑结构表示网络传输介质和结点的连接形式，通常有总线型、环形、星形和树形。
3.OSI将整个网络通信的功能划分为七个层次，由低到高分别是物理层、链路层、网络层、传输层、会话层、表示层和应用层。
4.利用通信设备和线路，将分布在地理位置不同的、功能独立的多个计算机系统连接起来，以功能完善的网络软件实现网络中资源共享和信息传递的系统，称为计算机网络。
第2章
一、填空题
1.基带、调制2.数字、模拟
3.频分多路复用、时分多路复用4.不归零编码、曼彻斯特编码
5.电信号、光信号6.变换器、信道、反变换器
7.同轴电缆、双绞线、光纤8.单模、多模
9.调制、解调10.光纤到户、FTTC、光纤到办公室
二、选择题
1.A2. D3. A4. C5. A
6. B7. A8. B9. C10. D
附录
第1章
一、填空题
1.面向终端的计算机网络、以分组交换为核心的计算机网络、以OSI为核心的计算机网络、以高速和多媒体应用为核心的计算机网络
2.ARPANET、分组交换3.计算机、通信
4.局域网、城域网、广域网5.网络协议
6.语义、语法7.计算机网络体系结构

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=-就是所求序列的母函数。

n0
k 0
(c)an C(n 3,3), n {0,1,2,...}
n
(b)G 2 an xn , 其中an (k 1)(n 1 k )
n0
k 0
G2 (1 2x 3x2 ... (n 1)xn ...)(1 2x 3x2 ... (n 1)xn ...)
an 1 (n 1) 2 (n) ... (k 1) (n k 1) ...
G(x) 1 23 x 1 ...(n 1)3 xn 1 ...
1 x 1 x
1 x
1 (1 23 x ...(n 1)3 xn ...) 1 x
G(x)
1 1 x
1 4x x2 (1 x)4
1 4x x2 (1 x)5
2.16 用数学归纳法证明 C(m,m),C(m+1,m),C(m+2,m),...,C(m+n,m),...的母函数为 (1-x)-m-1
按叠加原理 an 4an1 3 4n 的特解为hn4n , 代入替推关系 hn4n 4h(n 1)4n1 3 4n , h 3 一般解为: r4n 3n4n 10 5n
2.28
an
a a 3
10
n 1
n2
两边求对数
ln an 3 ln an1 10 ln an2 令bn ln an bn 3bn1 10bn2 0, 特征根为 : r1 5, r 2 2,
1 ln 4
a [3n 3( 1)n ] 0
ln a a 1[3n (1)n ]
1[3n 3( 1)n ]
14
04
a a a 1[3n ( 1)n ]
1[3n 3( 1)n ]
n
14
04

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 +- 。

组合数学答案组合数学是一种研究数学对象的组合方式的学科。

它的一个主要内容是计算组合数。

组合数指从若干个元素中选出一些元素，这些元素没有顺序，也没有重复，求出可能的情况数。

在组合数学中，常用的计算方法是二项式定理和递推法。

那么如何得出组合数学的答案呢？下面我们来探讨一下这个问题。

一、二项式定理二项式定理是组合数学中最基本的一个公式，也是最常用的公式之一。

二项式定理可以表示为：$$(a+b)^n=\sum_{k=0}^{n}{C_n^k}a^{n-k}b^k$$ 其中，$C_n^k$表示从n个元素中选k个元素的组合数，也称为二项式系数。

在计算组合数的时候，可以通过递推公式或者杨辉三角求得。

在使用二项式定理时，需要对公式进行变形，得到我们需要的答案。

二、递推法递推法是组合数学中另一种常用的计算方法。

递推法的核心思想是通过已知的答案计算新的答案。

在计算组合数时，常用的递推公式有杨辉三角和组合数恒等式等。

递推法的优点是计算简单、易于理解，缺点是可能出现大量的重复计算，导致计算效率降低。

三、应用组合数学的应用广泛，其中最为常见的应用是在概率统计学中。

在概率统计学中，经常需要计算从一个大集合中选出一个子集的概率，这就需要用到组合数学中的组合数。

另一个重要的应用是在密码学中。

组合数学可以用来研究密码的强度和安全性，设计更加安全的密码。

四、总结组合数学是数学中一门非常重要的学科，它的应用广泛，不仅仅应用于数学领域，还渗透到了各个领域，如物理学、计算机科学、信息科学等。

在组合数学中，二项式定理和递推法是常用的计算方法，我们可以根据不同的问题选择不同的方法来求解答案。

在学习组合数学的时候，需要掌握这些基本方法，并且理解应用范围和意义，才能真正掌握组合数学的核心思想。

（种）
20．凸十边形的任意三个对角线不共点，试求这凸十边形的对角线交于多少个点？又把所有的对角线分割成多少段？
解：（1）从一个顶点可引出7条对角线，这7条对角线和其他顶点引出的对角线的交点情况如下：从右到左，和第一条对角线的交点有： 个，和第二条的交点有 ，和第三条的交点有 条，…，故和一个顶点引出的7条线相交的点为：
4位数有 个；5位数有 个；6位数有 个；
（2）0出现在十位，此时符合条件的3位数有 个；4位数有 个；5位数有 个；6位数有 个；
（3）0出现在百位，此时符合条件的4位数有 个；5位数有 个；6位数有 个；
（4）0出现在千位，此时符合条件的5位数有 个；6位数有 个；
（5）0出现在万位，此时符合条件的6位数有 个；
依次类推，无效0的总数为
因为 全为0时的6个0和1 000 000本身的6个0相互抵消，
所以1到1 000 000之间的自然数中0出现的次数为
（次）
注意：1出现的次数为 （要考虑1 000 000这个数的首位1），
2，3，…，9各自出现的次数为 。
16．n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？
解：12个人围圆周就坐的方式有： 种，
设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有： 种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲”；所以
则满足条件的就坐方式有： 种。
6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？
（2）要求前排至少坐5人，后排至少坐4人。
解：（1）因为就坐是有次序的，所有是排列问题。

习题一（A ）1.设），（），（∞+∞=55-- A ，），310[-=B ，求)\(\\,,B A A B A B A B A 及 . 解 ),5()3,(+∞-∞= B A ；105AB [,)=--；105A\B (,)(,)=-∞-+∞；105A\(A\B )[,)=--.2. 设A 表示某大学学习英语的学生的集合，B 表示学习日语的学生集合， 则B A B A B A B A 及,,\,,各表示怎样的集合.解 A 表示该大学不学习英语的大学生集合；B 表示该大学不学习日语的大学生集合；B A \表示该大学学习英语但不学习日语的大学生集合；B A 表示该大学既不学习英语又不学习日语的大学生集合；B A 表示该大学不学习英语或不学日语的大学生集合.3. 求下列函数的定义域. （1）211x xy --=； （2））1tan(+=x y （3）)3arcsin(-=x y （4）xx y 1arctan3+-= （5）)1ln(2-=x y （6）xe y 1= 解 （1）1001[,)(,]-； （2） 10122x k ,k ,,,ππ≠+-=±±；（3）1|3|≤-x 即42≤≤x ； （4）3≤x 且0≠x ； （5）1||>x 即),1()1,(+∞--∞ ； （6）,0≠x 即),0()0,(+∞-∞ .4.设)(x f 的定义域]1,0[=D ，求下列函数的定义域： （1）)(sin x f ； （2）)0(),(>+a a x f （3）)0(),()(>-++a a x f a x f .解 （1）]1,0[sin ∈x ，即221012x [k ,(k )]k ,,,ππ∈+=±±.（2）]1,0[∈+a x ，即a x a -≤≤-1； （3）]1,0[∈+a x 且]1,0[∈-a x .所以当102a <≤时，定义域为]1,[a a -；当21>a 时，定义域为空集φ.5. 下列函数)(x f 和)(x g 是否相同？为什么？ （1）22ln 2)(,ln )(x x g x x f ==；（2）33341)(,)(-=-=x x x g x x x f ；（3）x x x g x f 22tan sec )(,1)(-==；（4）2)(|,|)(x x g x x f ==.解 (1) 两个函数不同,因为对应法则或表达式不同. (2)两个函数相同,因为定义域和对应法则都相同. (3)两个函数不同,因为它们的定义域不同.(4)这对函数是相同的。

2 n
( a )G
2
= (1 − x )
−4
= ∑ C ( n + 3,3) x n
n=0
∞
2.4 已知母函数 1 − x − 56 x 2，求对应的序列
注意到 1－x-56x2=(1-8x)(1+7x)， 用A/(1-8x)+B/(1+7x)的分子等于3-9x 待定A，B的方程组为： A + B = 3 7 A − 8 B = −9 解出A＝1，B＝2 G(x)=1/(1-8x)+2/(1+7x) 利用基本母函数1/(1-x) an=8n-7n
• 解：G(x)=/Sum{0,n}(anxn) • 参考p61，例2－13，2－14， • 参考p111， 例2－63
2.48有红、黄、蓝、白球各两个，绿、紫、黑球各3个， 问从中取出10个球，试问有多少种不同的取法？ 用指数型母函数，可得母函数 x x2 4 x x 2 x3 3 G ( x) = (1 + + ) ⋅ (1 + + + ) 1! 2! 1! 2! 3!
• 用多项式除法，解出a0，a1均为1
1− x + x
2
1 1
1 1 −x x2
2
• P68 x −x • 将(1-x+x2)分解因子，转化为基本母函数.引 用P59，定理2－1. 并参考p56例子2－11. • 这个题目整体都做的不错

2.18（1）课练，用母函数法求 an-6an-1+8an-2=0
注：这个题目中有同学使用的符号 n指代比较 混乱。虽然最后结果对，但过程中未体现出逻 辑的连贯性。 也有同学用积分和求导渐次推理得到正确结论。 十分可贵。不过有的人在最后写有一个 m次方， 令人困惑