李凡长版 组合数学课后习题答案 习题3
更新时间:2023-09-23 03:17:02 阅读量: 人文社科 文档下载
- 李凡长 苏州大学推荐度:
- 相关推荐
第三章 递推关系
1. 在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限
区域数记为f(n),求f(n)满足的递推关系. 解: f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n.
2. n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求
f(n)满足的递推关系. 解:设an-1an-2?a1是满足条件的n-1位三进制数序列,则它的个数可以用f(n-1)表示。
an可以有两种情况:
1) 不管上述序列中是否有2,因为an的位置在最左边,因此0 和1均可选;
2)当上述序列中没有1时,2可选; 故满足条件的序列数为
f(n)=2f(n-1)+2n-1 n?1, 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)/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”的序列数,同时同时排除了在n-2位第一次出现“00”的可能;
依此类推,有
17
f(n)+f(n-1)+f(n-2)+?+f(2)=2n-2 f(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-6到n-4位第一次出现010的个数(因为 在第n-3位可以取0或1);
同理,k?3时,第n-k-2到n-k位第一次出现010的个数为 k-3
2f(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 n?6 f(3)=1,f(4)=2,f(5)=3.
7. 有多少个长度为n的0,1序列,在这些序列中,既不包含“010”,也不包
含“101”?
解:设满足条件的序列数为f(n)
考虑n-1位时最左边的情况:
1) 最左边为1,则左边可选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(n?2)的字符串可分成如下四类:
1) 最左字符为b; 2) 最左字符为c;
3) 最左两个字符为ab; 4) 最左两个字符为ac;
前两类字符串分别有f(n-1)个,后两类字符串分别有f(n-2)个。容易求出f(1)=3,f(2)=8。从而得到 f(n)=2f(n-1)+2f(n-2) (n?3) f(1)=3,f(2)=8. 9. 求解下列递推关系:
?f(n)?2f(n?1)?2f(n?2)(1)?;
?f(1)?3,f(2)?8解:先求这个递推关系的通解,它的特征方程为x2-2x-2=0
18
解这个方程,得x1?1?3,x2?1?3.
所以,通解为f(n)?c1(1?3)n?c2(1?3)n. 代入初值来确定c1和c2,得c1??2?32?3,c2?.
2323 因此,f(n)?2?3?2?3(1?3)n?(1?3)n. 2323(2)??f(n)?4f(n?1)?4f(n?2);
?f(0)?1,f(1)?3
解:此递推关系的特征方程为x2-4x+4=0 解这个方程,得x1=x2=2. 所以通解为f(n)=c12n+c2n2n.
代入初值来确定c1和c2,得c1=1,c2=1/2. 因此,f(n)=2n+2n-1n.
?f(n)??f(n?1)?3f(n?2)?5f(n?3)?2f(n?4)(3)?;
?f(0)?1,f(1)?0,f(2)?1,f(3)?2解:该递推关系的特征方程为x4+x3-3x2-5x-2=0, 解得特征根为x1=x2=x3=-1,x4=2.
所以通解为f(n)=c1(-1)n+c2n(-1)n+c3n2(-1)n+c42n.
代入初值,得c1?,c2??,c3?0,c4?.
939712因此,f(n)?(?1)n79?(?1)n13n?29?2.
n?f(n)?4f(n?1)?4f(n?2)?n?2n(4)?;
?f(0)?0,f(1)?1解:由于2是特征方程的二重根,所以该递推关系的特解为
f?(n)=n2(b1n+b0)·2n.
将它代入递推关系化简,得到 6b1=1, -6b1+2b0=0
解得b0?12
,b1?16.
而相应齐次递推关系的通解为(c0+c1n)·2n,从而非齐次递推关系的通解为
f(n)?(c0?c1n)?n????2?n?1???2n.
??62???
代入初值可得c0?0,c1??.
619
1 于是f(n)?(n3?3n2?n)?2n.
61?f(n)?nf(n?1)?n! (n?1)(5)?;
?f(0)?2解: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).
?f(n)?(n?2)f(n?1) (n?1)(6)?;
f(0)?1?解:f(n)=(n+2)f(n-1)=(n+2)(n+1)f(n-2)=? =(n+2)(n+1)?3·f(0)=(n+2)!/2.
10. 在一圆周上取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)+C(n-4). 11. 设有n条椭圆曲线,两两相交于两点,任意3条椭圆曲线不相交于一点.
问这样的n个椭圆将平面分割成多少部分?
解:设f(n)表示n个椭圆将平面分割成的部分的个数,则有:一个椭圆将平面分成内、外两个部分,两个椭圆将平面分成4个部分。第二个椭圆的周界被第一个椭圆分成两部分,这恰恰是新增加的域的边界。依此类推,第三个椭圆曲线被前面两个椭圆分割成4部分,将平面分割成4+4=8个部分。若n-1个椭圆将平面分割成f(n-1)个部分,第n个椭圆和前n-1个椭圆两两相交于两点,共2(n-1)个交点,即新增加的域有2(n-1)个。故有 f(n)=f(n-1)+2(n-1) f(1)=2
解得f(n)=n(n-1)+2
12. 求n位十进制正数中出现偶数个5的数的个数.
解:设f(n)表示n位十进制正数中出现个5的数的个数,d=d1d2?dn-1表示n-1位十进制数,则若d含有偶数个5,则dn取5以外的任何一个数;若d含有奇数个5,则dn取5。另n-1位十进制的数共有9×10n-2个,故递推关系为
f(n)=9f(n-1)+ 9×10n-2-f(n-1)= 9×10n-2+8f(n-1) f(1)=8. 20
13. 在一个平面上画一个圆,然后一条一条地画n条与圆相交的直线.当r是
大于1的奇数时,第r条直线只与前r-1条直线之一在圆内相交.当r是偶数时,第r条直线与前r-1条直线都在圆内相交.如果无3条直线在圆内共点,这n条直线把圆分割成多少个不重叠的部分?
解:当r是奇数时,它只与原来r-1条直线之一相交,因此多了两个部分; 当r是偶数时,它与原来的r-1条都相交,因此多了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算是相邻的数,并在此假定下从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) 求它所满足的递推关系;
?n?rk?r?2) 证明fr(n,k)???,n?r?k(r?1)
k??解:可将本题转换为构造相应的0-1串的问题。将这样的n位0-1串与1
到n的正整数对位,与1相应的整数选取,与0相应的不取。一个0-1串对应一个选取方案。这也对应将相同的球放入不同的盒子的方案数。
k???????????10...010...01......10...01??? rrr?k?1?n?k?r(k?1)?1??n?r(k?1)?所以fr(n,k)??????。 n?k?r(k?1)k????11??Fn?116. 试证:?????F10???nnFn?
?Fn?1?证明:可用数学归纳法证明
11?,右边=?11?,成立。 1) 当n=1时,左边= ??????10??10?11??Fk?12) 假设n=k时,等式成立,则有?????F10???kkFk??. Fk?1?n=k+1时,有
21
正在阅读:
李凡长版 组合数学课后习题答案 习题309-23
如何加密某一文件夹03-20
心想事成性格能量书九型人格心灵密码学04-08
关于财务报表中相关数据的计算公式01-25
你认为中国应该如何应对美国重返亚太战略05-15
LED小常识 - 图文05-09
乳腺癌基本知识问卷调查表05-08
四季之美课堂实录王崧舟08-01
中西档案信息公开制度比较研究06-13
阿里面试题10-03
- 粮油储藏基础知识
- 论文范文(包括统一封面和内容的格式)
- 经典解题方法
- 综合部后勤办公用品管理办法+领用表
- 学生宿舍突发事件应急预案
- 16秋浙大《生理学及病理生理学》在线作业
- 四分比丘尼戒本(诵戒专用)
- 浙江财经大学高财题库第一章习题
- 九大员岗位职责(项目经理、技术负责人、施工员、安全员、质检员、资料员、材料员、造价员、机管员)
- 旅游财务管理习题(学生版)
- 德阳外国语高二秋期入学考试题
- 投资学 精要版 第九版 第11章 期权市场
- 控制性详细规划城市设计认识
- bl03海运提单3国际贸易答案
- 2010-2011学年湖北省武汉市武珞路中学七年级(上)期中数学试卷
- VB程序填空改错设计题库全
- 教师心理健康案例分析 - 年轻班主任的心理困惑
- 民间借贷司法解释溯及力是否适用?
- 三联书店推荐的100本好书
- 《化工原理》(第三版)复习思考题及解答
- 习题
- 李凡
- 组合数学
- 课后
- 答案
- 关于基层党校如何打造精品课程的几点思考
- 这样才叫职业化答案
- 第三篇 组织答案
- 动生作业习题
- amber实战
- 中国当代文学史考试笔记(重点)
- 化工工艺学课程总结及复习
- 2016-2022年中国亚克力(PMMA)行业投资前景咨询研究报告 - 图文
- SignalTapII及SignalProbe使用指南
- 化学反应工程文献报告
- 物流设施与设备期末试题
- 2016-2017学年江苏省泰州市泰兴市西城中学八年级数学上双休日作业(10)(无答案).doc
- 架空光缆施工教学 - 图文
- 哲学与人生 第十四课
- 中国狗扣市场发展研究及投资前景报告(目录) - 图文
- 2014-2015学年江苏省苏州市高二下学期期末调研语文试卷(带解析)
- 常见的金融术语 - 金融业从业基础知识
- 国际航运业务英语与函电 复习整理(国航)
- 浅谈钙钛矿太阳能电池技术与发展
- 肺栓塞指南20151