组合数学复习题 的.doc

  1. 1、本文档共28页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
组合数学复习题 的

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的字符串中 (a)0出现偶数次的字符串有个; (b),其中 [证].(a)方法一:采用(串值)数学归纳法 [基始]当n=1时,0出现偶数次,长度为1的字符串有=2个(即1和2两个长度为1的字符串)。所证结论成立; [归纳假设]当n=m(1?m?k)时,假设所证结论成立。即,0出现偶数次,长度为m的字符串有个; [归纳]当n=k+1时,0出现偶数次,长度为k+1的字符串包括两部分: (1)给0出现偶数次,长度为k的字符串后面再增加一位不是0的数(只能是1或2),因此,按乘法原理,由归纳假设,此种字符串有?2=3k+1个; (2)给0出现奇数次,长度为k的字符串后面再增加一位是0的数,因此,按乘法原理,由归纳假设,此种字符串有?1=个; 所以,按加法原理,0出现偶数次,长度为k+1的字符串共有 (3k+1)+= 个。所证结论成立; 归纳完毕。 方法二:采用指数型母函数方法 设:an—0出现偶数次,长度为n的字符串的个数,则{an}的指数型母函数 所以,(规定a0=1)。 (b)利用组合意义法来证 考虑0出现偶数次,长度为n的字符串的个数。根据上面(a),已证其个数为; 另一方面,相当于先从n个位置中选取2m(0?2m?n)个(有种选择)放置上数0,再在剩下的n-2m个位置上放置数1或2(有2n-2m种放法),按乘法原理,是个,m=0,1,2,?,q ()的方案数。 按加法原理,此方案数为。因此,我们有 。 1-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)格点)。故这样的字符串有 -=C(2n,n)-C(2n,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个部分。 故 = = = = 且 ,,,, 从而有    于是    同理可得 故有 同理可得 故有 同理可得 故有 同理可得 故有 对应的特征方程为 即 r=1是5重根 所以 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

文档评论(0)

ayangjiayu3 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档