《组合数学复习题.doc》由会员分享，可在线阅读，更多相关《组合数学复习题.doc（27页珍藏版）》请在金锄头文库上搜索。
1、1-23.(a)在2n个球中，有n个相同。求从这2n个球中选取n个的方案数。 (b)在3n+1个球中，有n个相同。求从这3n+1个球中选取n个的方案数。解.(a)相当于从n个不同的小球中取出m个小球(0mn),再从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个小球(0mn),再从n个相同的小球中取出n-m个小球，m=0,1,2,n的方案数。根据加法原理，这个方案数应该
2、是：C(2n+1,0)+ C(2n+1,1)+ C(2n+1,n)。1-24.证明在由字母表0,1,2生成的长度为n的字符串中(a)0出现偶数次的字符串有个；(b),其中证.(a)方法一：采用（串值）数学归纳法基始当n=1时，0出现偶数次，长度为1的字符串有=2个（即1和2两个长度为1的字符串）。所证结论成立；归纳假设当n=m(1mk)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有个；归纳当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有2=3k+1
3、个；(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，由归纳假设，此种字符串有1=个；所以，按加法原理，0出现偶数次，长度为k+1的字符串共有(3k+1)+= 个。所证结论成立；归纳完毕。方法二：采用指数型母函数方法设：an0出现偶数次，长度为n的字符串的个数，则an的指数型母函数所以，（规定a0=1）。(b)利用组合意义法来证考虑0出现偶数次，长度为n的字符串的个数。根据上面(a)，已证其个数为；另一方面，相当于先从n个位置中选取2m(02mn)个（有种选择）放置上数0,再在剩下的n-2m个位置上放置数1或2（有2n-2m种放法），按乘法原理，是个，m=0,1,
4、2,q ()的方案数。按加法原理，此方案数为。因此，我们有。(n+1,n+1)(0,1)(1,0)(n,n+1)(n,n)(0,0)第26题图11-26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？解.转化为格路问题（弱领先条件参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)的强领先条件（只能从对角线上方走，但不可以碰到对角线）的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点)。故这样的
5、字符串有-=C(2n,n)-C(2n,n-1)个。1-27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？解.设：g(n,k)为从1n中选取不同且互不相邻的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)。且只有当n2k-1时，g(n,k)0；否则g(n,k)=0。因此，可给定初始值：g(2k-1,k)=1，g(2k-2,k)=0。2-18.在一圆周上取n个
6、点，每一对顶点可做一弦。不存在三弦共点的现象，求弦把圆分割成几部分？v5v6v1第14题图v4v3v2v7解.(参见 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个部分。故 =且 ，从而有 于是 同理可得 故有 同理可得 故有 同理可得 故有 同理可得 故有 对应的特征
7、方程为 即 r=1是5重根所以n=2时，a2=A=2n=3时，a3=A+B=4，B=2n=4时，a4=A+2B+C=8，C=2n=5时，a5=A+3B+3C+D=16，D=2n=6时，a6=A+4B+6C+4D+E=31，E=1故 或 或 。2-19.求n位二进制数中相邻两位不出现11的数的个数。解.设：ann位二进制数种相邻两位不出现11的数的个数；n位二进制数种相邻两位不出现11的数的个数，可分为两个部分：(1)第n位是0，这时第n-1位既可以是0又可以是1，故从第1位到第n-1位形成n-1位二进制数中相邻两位不出现11的数，相应的数的个数为an-1；(2)第n位是1，这时第n-1位只能是
8、0，第n-2位既可以是0又可以是1，故从第1位到第n-2位形成n-2位二进制数中相邻两位不出现11的数，相应的数的个数为an-2；因此，按加法原理，n位二进制数中相邻两位不出现11的数的个数an= an-1+an-2 。初始条件a1=2，a2=3因此，显然有an=Fn+2所以，n位二进制数中相邻两位不出现11的数的个数是。2-20.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现三次，求这样的排列的数目。解.设：ak从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目；从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数
9、目，可分为两个部分：(1)第k位与第k-1位不相同，因此，在前k-1位已形成满足条件的k-1位排列时，第k位只能有n-1种选择，相应的排列个数为(n-1)ak-1；(2)第k位与第k-1位相同，因此，在前k-2位已形成满足条件的k-2位排列时，第k位与第k-1位一起只有n-1种选择，相应的排列个数为(n-1)ak-2；因此，按加法原理，从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目ak=(n-1)ak-1+(n-1)ak-2 。初始条件：a1=n，a2=n2，a3=n3-n特征方程为：r2-(n-1)r-(n-1)=0特征根为：，故递归方程的通解为：ak=A
10、ak+Bbk利用初始条件可得方程组： Aa+Bb=nAa2+Bb2=n2利用特征根a，b满足特征方程，可得方程组：解之，得所以，从n个文字中取k个文字作允许重复的排列，没有一个文字连续出现三次，这样的排列的数目。2.42. 设an满足an - an-1- an-2 = 0，bn满足bn - 2bn-1- bn-2 = 0，cn = an + bn，n =0, 1, 2, 3, ，试证序列cn满足一个四阶线性常系数齐次递推关系。解方法一：(特征系数法)由于序列an满足递推关系：an - an-1- an-2 = 0 j故显然也满足递推关系：(an - an-1- an-2) + A1(an-1
11、- an-2- an-3) + A2(an-2 - an-3- an-4) = 0这里A1，A2为任意常数整理为：an + (A1 - 1)an-1+ (A2 - A1 - 1)an-2 - (A1 + A2)an-3 - A2an-4 = 0 k由于序列bn满足递推关系：bn - 2bn-1- bn-2 = 0 故显然也满足递推关系：(bn - 2bn-1- bn-2) + B1(bn-1 - 2bn-2- bn-3) + B2(bn-2 - 2bn-3- bn-4) = 0这里B1，B1为任意常数整理为：bn + (B1 - 2)bn-1+ (B2 - 2B1 - 1)bn-2 - (B1
12、 + 2B2)bn-3 - B2bn-4 = 0 l 令：解之得：，将此解代入k和l，有：an - 3an-1 + 3an-3 + an-4 = 0 m bn - 3bn-1 + 3bn-3 + bn-4 = 0 n 将m+n，并注意到cn = an + bn，我们有：cn - 3cn-1 + 3cn-3 + cn-4 = 0 o 这就是序列cn所满足的四阶线性常系数齐次递推关系。方法二：(特征根法)序列an的递推关系：an - an-1- an-2 = 0 特征方程：g 2 - g - 1 = 0特征根：g1 =，g2 =故其通解为：bn = A()n + B()n序列bn的递推关系：bn
13、- 2bn-1- bn-2 = 0特征方程：g 2 - 2g - 1 = 0特征根：g1 =，g2 =故其通解为：bn = C()n + D()n 于是有：cn = an + bn = A()n + B()n + C()n + D()n因此序列cn所满足的线性常系数齐次递推关系的特征多项式为：(g -)(g -)g -()g -() = 0整理为：(g 2 - g - 1)(g 2 - 2g - 1) = 0再整理为：g 4 - 3g 3 + 3g + 1 = 0因此，对应的四阶线性常系数齐次递推关系为：cn - 3cn-1 + 3cn-3 + cn-4 = 0 。 2.43.在习题2.42中，若cn = anbn，试讨论之。解(特征根法)序列an的递推关系：an - an-1- an-2 = 0 特征方程：g 2 - g - 1 = 0特征根：g1 =，g2 =故其通解为：bn = A()n + B()n序列bn的递推关系：bn - 2bn-1- bn-2 = 0特征方程：g 2 - 2g - 1 = 0特征根：g1 =，g2 =故其通解为：bn = C()n + D()n 于是有：cn = anbn = A()n + B()n C()n + D()n = AC()n()n + AD()n()n + BC()n()n + BD(
