《李凡长版 组合数学课后习题答案 习题3》由会员分享，可在线阅读，更多相关《李凡长版 组合数学课后习题答案 习题3（9页珍藏版）》请在金锄头文库上搜索。
1、17第三章 递推关系1. 在平面上画 n 条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为 f(n),求 f(n)满足的递推关系.解： f(n)=f(n-1)+2f(1)=2,f(2)=4解得 f(n)=2n.2. n 位三进制数中,没有 1 出现在任何 2 的右边的序列的数目记为 f(n),求 f(n)满足的递推关系.解：设 an-1an-2a1是满足条件的 n-1 位三进制数序列，则它的个数可以用f(n-1)表示。an可以有两种情况：1） 不管上述序列中是否有 2，因为 an的位置在最左边，因此 0和 1 均可选；2）当上述序列中没有 1 时，2 可选；故满足条件的序列数为f
2、(n)=2f(n-1)+2n-1 n1,f(1)=3解得 f(n)=2n-1(2+n).3. n 位四进制数中,2 和 3 出现偶数次的序列的数目记为 f(n),求 f(n)满足的递推关系.解：设 h(n)表示 2 出现偶数次的序列的数目，g(n)表示有偶数个 2 奇数个3 的序列的数目，由对称性它同时还可以表示奇数个 2 偶数个 3 的序列的数目。则有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的 h(n)=(2n+4n)/2 代入（2） ，可得f(n+1)= (2n+4n)/
3、2-2f(n),f(1)=2.4. 求满足相邻位不同为 0 的 n 位二进制序列中 0 的个数 f(n).解：这种序列有两种情况：1)最后一位为 0，这种情况有 f(n-3)个；2)最后一位为 1，这种情况有 2f(n-2)个；所以f(n)=f(n-3)+2f(n-2)f(1)=2,f(2)=3,f(3)=5.5. 求 n 位 0,1 序列中“00”只在最后两位才出现的序列数 f(n).解：最后两位是“00”的序列共有 2n-2个。f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在 n-1位第一次出现“00”的可能；f(n-1)表示在第 n-1 位第一次出现“00”的序列数，同时
4、同时排除了在n-2 位第一次出现“00”的可能；18依此类推，有f(n)+f(n-1)+f(n-2)+f(2)=2n-2f(2)=1,f(3)=1,f(4)=2.6. 求 n 位 0,1 序列中“010”只出现一次且在第 n 位出现的序列数 f(n).解：最后三位是“010”的序列共有 2n-3个。包括以下情况：f(n)包含了在最后三位第一次出现 010 的个数，同时排除了从n-4 到 n-2 位第一次出现 010 的可能；f(n-2)包含了从 n-4 到 n-2 位第一次出现 010 的个数；f(n-3)包含了从 n-5 到 n-3 位第一次出现 010 的个数；2f(n-4)包含了从 n-
5、6 到 n-4 位第一次出现 010 的个数（因为在第 n-3 位可以取 0 或 1） ；同理，k3 时，第 n-k-2 到 n-k 位第一次出现 010 的个数为2k-3f(n-k)(因为第 n-k 位n-3 位中间的 k-3 位可以取 0、1，所以有 2k-3种状态)。所以满足条件的递推关系为f(n)+f(n-2)+f(n-3)+2n-6f(3)=2n-3 n6f(3)=1,f(4)=2,f(5)=3.7. 有多少个长度为 n 的 0,1 序列,在这些序列中,既不包含“010”,也不包含“101”？解：设满足条件的序列数为 f(n)考虑 n-1 位时最左边的情况：1) 最左边为 1，则左边
6、可选 0 或 1 生成满足要求的序列，这种情况有2f(n-2)个；2) 最左边为 01，则左边只能选 1 才能满足要求，这种情况有f(n-3)个；f(n)=2f(n-2)+f(n-3)f(2)=1,f(3)=1,f(4)=2.8. 在信道上传输 a,b,c 三个字母组成的长为 n 的字符串,若字符串中有两个 a 连续出现,则信道就不能传输.令 f(n)表示信道可以传输的长为 n的字符串的个数,求 f(n)满足的递推关系.解：信道上能够传输的长度为 n（n2）的字符串可分成如下四类：1) 最左字符为 b；2) 最左字符为 c；3) 最左两个字符为 ab；4) 最左两个字符为 ac；前两类字符串分
7、别有 f(n-1)个，后两类字符串分别有 f(n-2)个。容易求出 f(1)=3,f(2)=8。从而得到f(n)=2f(n-1)+2f(n-2) (n3)f(1)=3,f(2)=8.9. 求解下列递推关系：（1） ；()21)(2)3,8fnffn19解：先求这个递推关系的通解，它的特征方程为 x2-2x2=0解这个方程，得 , .13x21x所以，通解为 .()(3)nnfncc代入初值来确定 c1和 c2，得 ， .123因此， .233()()()nnfn（2） ；412(0),(fff解：此递推关系的特征方程为 x2-4x+4=0解这个方程，得 x1=x2=2.所以通解为 f(n)=c
8、12n+c2n2n.代入初值来确定 c1和 c2，得 c1=1，c 2=1/2.因此，f(n)=2 n+2n-1n.（3） ；()3()5(3)(4)0,(,fffffn解：该递推关系的特征方程为 x4+x3-3x2-5x-2=0,解得特征根为 x1=x2=x3=-1,x4=2.所以通解为 f(n)=c1(-1)n+c2n(-1)n+c3n2(-1)n+c42n.代入初值，得 .2347,0,99cc因此， .()1()nnnf（4） ；42)(0),()fff解：由于 2 是特征方程的二重根，所以该递推关系的特解为f(n)=n2(b1n+b0)2n.将它代入递推关系化简，得到6b1=1,-6
9、b1+2b0=0解得 ， .02b16而相应齐次递推关系的通解为(c 0+c1n)2n，从而非齐次递推关系的通解为20.2011()6nfncn代入初值可得 ， .01于是 .321()6nfn（5） ；(! (1)0)ff解：f(1)=f(0)+1!f(2)=2f(1)+2!=2f(0)+2*2!=2!(f(0)+2)f(3)=3f(2)+3!=6f(0)+3*3!=3!(f(0)+3)f(n)=n!(f(0)+n)=n!(n+1).（6） ；()2)(1 )0fnfn解：f(n)=(n+2)f(n-1)=(n+2)(n+1)f(n-2)=(n+2)(n+1)3f(0)=(n+2)!/2.1
10、0. 在一圆周上取 n 个点,过每对点作一弦,且任何三条弦不在圆内共点,试求这些弦把圆分成的区域的个数.解：n-1 个点把圆分为 f(n-1)部分，在加第 n 个点则对于前 n-1 个点来说，每选 3 个点都有 3 条弦构成了一个三角形。而中间的一点和第 n 点的连线把中间和第 n 点间的弦分成了 2 个部分，增加了 1 一个域。第 n 个点和其它 n-1 个点的连线又把第 1，n-1，n 点构成的三角形分为 n 个域。故满足条件的递推关系为f(n)=f(n-1)+C(n-1,3)+n-1，f(0)=1,f(1)=1,f(2)=2,f(3)=4,f(4)=8.解得 f(n)=1+C(n,2)+
11、C(n-4).11. 设有 n 条椭圆曲线，两两相交于两点，任意 3 条椭圆曲线不相交于一点.问这样的 n 个椭圆将平面分割成多少部分?解：设 f(n)表示 n 个椭圆将平面分割成的部分的个数，则有：一个椭圆将平面分成内、外两个部分，两个椭圆将平面分成 4 个部分。第二个椭圆的周界被第一个椭圆分成两部分，这恰恰是新增加的域的边界。依此类推，第三个椭圆曲线被前面两个椭圆分割成 4 部分，将平面分割成 448 个部分。若 n1 个椭圆将平面分割成 f(n-1)个部分，第 n 个椭圆和前 n1个椭圆两两相交于两点，共 2（n1）个交点，即新增加的域有 2（n1）个。故有 f(n)=f(n-1)+2(
12、n-1)f(1)=2解得 f(n)=n(n-1)+22112. 求 n 位十进制正数中出现偶数个 5 的数的个数.解：设 f(n)表示 n 位十进制正数中出现个 5 的数的个数，d=d 1d2dn-1表示n-1 位十进制数，则若 d 含有偶数个 5，则 dn取 5 以外的任何一个数；若 d含有奇数个 5，则 dn取 5。另 n-1 位十进制的数共有 910n-2个，故递推关系为f(n)=9f(n-1)+ 910n-2-f(n-1)= 910n-2+8f(n-1)f(1)=8.13. 在一个平面上画一个圆,然后一条一条地画 n 条与圆相交的直线.当 r 是大于 1 的奇数时,第 r 条直线只与前
13、 r1 条直线之一在圆内相交.当 r是偶数时,第 r 条直线与前 r1 条直线都在圆内相交.如果无 3 条直线在圆内共点,这 n 条直线把圆分割成多少个不重叠的部分？解：当 r 是奇数时，它只与原来 r1 条直线之一相交，因此多了两个部分；当 r 是偶数时，它与原来的 r1 条都相交，因此多了 r 个交点；故有f(n)=f(n-1)+2 n 为奇数；f(n)=f(n-1)+n n 为偶数；14. 从 1 到 n 的自然数中选取 k 个不同且不相邻的数,设此选取的方案数位f(n,k).1) 求 f(n,k)满足的递推关系；2) 用归纳法求 f(n,k)；3) 若设 1 与 n 算是相邻的数,并在
14、此假定下从 1 到 n 的自然数中选取k 个不同且不相邻的数的方案数位 g(n,k),试利用 f(n,k)求 g(n,k).解：1）有两类：选 n 为 f(n-2,k-1)；不选 n 为 f(n-1,k).所以f(n,k)=f(n-2,k-1)+f(n-1,k).2)f(n,k)=C(n-k+1,k).3)f(n,k)=C(n-k+1,k-1)*n/k.15. 从 1 到 n 的自然数中选取两两之差均大于 r 的 k 个数1) 求它所满足的递推关系；2) 证明 (,),(1)rrkfn解：可将本题转换为构造相应的 01 串的问题。将这样的 n 位 01 串与1 到 n 的正整数对位，与 1 相
15、应的整数选取，与 0 相应的不取。一个 01串对应一个选取方案。这也对应将相同的球放入不同的盒子的方案数。 .1krr所以 。1(1)()(,)rknnfnkk16. 试证： 10nnF22证明：可用数学归纳法证明1) 当 n=1 时，左边= ，右边= ，成立。10102) 假设 n=k 时，等式成立，则有 .1kkFn=k+1 时，有 1 121100kk kkkFF 由 1)、2）可得等式成立。17. 设 , , ,用 Fibonacci 数来表示 和 .n02nka102nkbnab解： 1100 0 02112212nn n nkk k ka 1nb同理可得 。na由此可得两个序列的生成函数为 。()()1,()BxAxAx联立解可得 。22()1(),331BAxx由 Fibonacci 数定义可知，f(n)=f(n-1)+f(n-2)，其生成函数为。2()1Fx令 ，可得01()()(2),n nnnPfxQfx22()1(),33xx所以 f(2n), f(2n-1).nanb18. 某人有 n 元钱,他每天
