组合数学复习题

1-23.(a)在2n个球中，有n个相同。求从这2n个球中选取n个的方案数。

(b)在3n+1个球中，有n个相同。求从这3n+1个球中选取n个的方案数。 [解].(a)相当于从n个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出n-m个小球，m=0,1,2,?,n的方案数。

根据加法原理，这个方案数应该是：C(n,0)+ C(n,1)+?+ C(n,n)=2n。 同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。

(b)相当于从2n+1个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出n-m个小球，m=0,1,2,?,n的方案数。

根据加法原理，这个方案数应该是：C(2n+1,0)+ C(2n+1,1)+?+ C(2n+1,n)。

1-24.证明在由字母表{0,1,2}生成的长度为n的字符串中

3n?1(a)0出现偶数次的字符串有个；

2?n?n?n?n?2?n?n?q3n?1?n??????(b)?,其中2?2???2?q?2?0??2??q??2? 2????????[证].(a)方法一：采用（串值）数学归纳法

31?1［基始］当n=1时，0出现偶数次，长度为1的字符串有=2个（即1和2

2两个长度为1的字符串）。所证结论成立；

［归纳假设］当n=m(1?m?k)时，假设所证结论成立。即，0出现偶数次，长度为

3m?1m的字符串有个；

2［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：

(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能

3k?1是1或2），因此，按乘法原理，由归纳假设，此种字符串有?2=3k+1个；

2(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，

?k3k?1?3k?1按乘法原理，由归纳假设，此种字符串有??3?2???1=2个；

??所以，按加法原理，0出现偶数次，长度为k+1的字符串共有

3k?13k?1?1(3+1)+= 个。所证结论成立；

22k归纳完毕。

方法二：采用指数型母函数方法

设：an—0出现偶数次，长度为n的字符串的个数，则{an}的指数型母函数

xn A(x)??an?n!n?0?x2x4x6xx2x3?(1?????)(1?????)

2!4!6!1!2!3!ex?e?x2x??e

2e3x?ex ?213x(3x)2(3x)3xx2x3?[(1?????)?(1?????)] 21!2!3!1!2!3!1(3?1)x(32?1)x2(33?1)x3?[(1?1)?????] 21!2!3!3n?1所以，an?（规定a0=1）。

2(b)利用组合意义法来证

考虑0出现偶数次，长度为n的字符串的个数。根据上面(a)，已证其个数

3n?1为；

2另一方面，相当于先从n个位置中选取2m(0?2m?n)个（有???n???种选择）放2m??置上数0,再在剩下的n-2m个位置上放置数1或2（有2n-2m种放法），按乘法原理，是???n?n?2m?n??个，m=0,1,2,?,q (2q?2??2?)的方案数。 2m????nn?2n?q?????按加法原理，此方案数为?。因此，我们有 2?2???2???????n??0??n??2??n??q??n?n?n?n?2?n?n?q3n?1??0??2???2??2?????q??2?2。 ??????1-26.在由n个0及n个1构成的字符串中，

任意前k个字符中，0的个数不少于1的个(n+1,n+1) (n,n) 数的字符串有多少？

[解].转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对

角线。它可看作是从(0,1)到(n,n+1)的强领(0,1) 先条件（只能从对角线上方走，但不可以碰(0,0) (1,0) 第26题图1 到对角线）的格路问题。更进一步的，它可

看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点)。故这样的字符串有

?n?0?(n?1)?1??n?1?(n?1)?0????-?????=C(2n,n)-C(2n,n-1)个。 nn?1????(n,n+1)

1-27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？

[解].设：g(n,k)为从1~n中选取不同且互不相邻的k个数的方案数。

于是，按这k个数中有无数n而分为两种情况：(1)若选n，则必不能选n-1，故此种方案数为g(n-2,k-1)；(2)若不选n，则可以选n-1，故此种方案数为g(n-1,k)；所以，按加法原理，总的方案数g(n,k)=g(n-2,k-1)+g(n-1,k)。

且只有当n?2k-1时，g(n,k)?0；否则g(n,k)=0。因此，可给定初始值：

g(2k-1,k)=1，g(2k-2,k)=0。

2-18.在一圆周上取n个点，每一对顶点可做一弦。不存在三弦共点的现象，

求弦把圆分割成几部分？ [解].(参见 P98例6)

设an为过n个点的每两点作一条弦，且不存在三弦共点的现象，弦把圆分割成部分的个数。其中过n-1个点所作弦把圆分割成的部分为an-1，第n个点可以引出n-1条弦，第一条弦增加一个部分，第二条弦增加1?(n-3)+1个部分，第三条弦增加2?(n-4)+1个部分，……，第k条弦增加(k-1)?(n-k-1)+1个部分，……，第n-1条弦增加(n-1-1)?(n-(n-1)-1)+1=1个部分。

故 an?an?1?n?2v7

v1

v6

v2

v5

v3

第14题图

v4

k?2?(k?1)(n?k?1)?n?1

n?2n?2=an?1?(n?2)?(k?1)??(k?1)2?n?1

k?2k?2=an?1?(n?2)?k??k2?n?1

k?1k?1n?3n?3(n?2)2(n?3)1?(n?3)(n?2)(2n?5)?n?1 =an?1?261=an?1?(n?1)(n?2)(n?3)?n?1

6且 a2?2，a3?4，a4?8，a5?16，a6?31

1从而有 an?1?an?n(n?1)(n?2)?n

61于是 an?1?an?n(n?1)(n?2)?n

61同理可得 an?2?an?1?(n?1)n(n?1)?(n?1)

61故有 an?2?2an?1?an?n(n?1)?1

21同理可得 an?3?2an?2?an?1?(n?1)n?1

2故有 an?3?3an?2?3an?1?an?n 同理可得 an?4?3an?3?3an?2?an?1?n?1 故有 an?4?4an?3?6an?2?4an?1?an?1 同理可得 an?5?4an?4?6an?3?4an?2?an?1?1 故有 an?5?5an?4?10an?3?10an?2?5an?1?an?0 对应的特征方程为 r5?5r4?10r3?10r2?5r?1?0 即 (r?1)5?0 r=1是5重根 所以

an?A?B(n?2)?11C(n?2)(n?3)?D(n?2)(n?3)(n?4)2!3!1?E(n?2)(n?3)(n?4)(n?5)4!

n=2时，a2=A=2

n=3时，a3=A+B=4，?B=2 n=4时，a4=A+2B+C=8，?C=2 n=5时，a5=A+3B+3C+D=16，?D=2 n=6时，a6=A+4B+6C+4D+E=31，?E=1

故 an?2?2(n?2)?2??an?2?2(n?2)??n?2??n?2??n?2?????2???????? 234??????或

112(n?2)(n?3)?2(n?2)(n?3)(n?4)2!3!1?(n?2)(n?3)(n?4)(n?5)4!

或 an?

14(n?6n3?23n2?18n?24)。 242-19.求n位二进制数中相邻两位不出现11的数的个数。