组合数学习题解答实用教案

1、会计学1组合数学习题组合数学习题(xt)解答解答第一页，共40页。1.5,求3000到8000之间的奇整数的数目(shm)，而且没有相同的数字。 解： C(5,1)C(10,1)C(10,1)C(5,1)=2500 1.6,计算(j sun)11!+22!+33!+nn! 解： (n+1)!-1,迭代(di di)。 1.7,试证(n+1)(n+2).(2n)能被2n除尽。 解： =(2n)!(2n-1)!/n!=2nn!(2n-1)!/n! =2n(2n-1)! C(3,1)C(4,1)C(8,1)C(7,1)+ C(2,1)C(5,1)C(8,1)C(7,1) =672+560=1232第

2、1页/共40页第二页，共40页。 1.8、求1040和2030的公因数数目(shm)。 解： 等价(dngji)于求(25)40和(225)30 的公因数数目。 C(40,1)+C(40,1)C(30,1)+C(30,1)+1=40+1200+30=1271 C(41,1)C(31,1)=1271 1.9、试证n2的整除(zhngch)数的数目是奇数。ammaapppn.2211ammaapppn22221212.所有的组合数都是偶数，最后再加上1，偶数加1是奇数第2页/共40页第三页，共40页。1.10 证明任一正整数n可惟一(wiy)地表示成：111,0, !iiiaiian先证可表示性：

3、当n=0,1时，命题成立。假设对小于n的非负整数(zhngsh)，命题成立。对于n,设k!n(k+1)!,即0n-k!kk!由假设对n-k!,命题成立，设n-k!=aii!，其中akk-1,n=aii!+k!，命题成立。第3页/共40页第四页，共40页。再证表示(biosh)的唯一性：设n=aii!=bii!,。bajbjajibiabaijjjjjjiijiiii矛盾也就是得余数两边同时除以令, !,)!1(!min第4页/共40页第五页，共40页。1.11 证明(zhngmng)下式，并给出组合解释) 1,() 1(), 1(rnCrrnnC组合(zh)意义： 从n个不同的球中取出的r+1

4、个，要求指定第一个球，有两种方式： 1、等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个； 2、等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。 显然两种方案数相同。第5页/共40页第六页，共40页。1.12 试证等式(dngsh)：nknnknkC112),(用多项式(1+x)n证明(zhngmng)，求导第6页/共40页第七页，共40页。 1.13、有n个不同的整数，从中取出两组来，要求(yoqi)第1组的最小数大于另一组的最大数。设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小

5、取a个作为第一组,剩余的为第二组。此时方案数为 C(n,m)。从m个数中取第一组数共有(n yu)m-1中取法。总的方案数为nmnnmnCm2112),()1(第7页/共40页第八页，共40页。 习题：1.14六个引擎分列两排，要求引擎的点火的次序两排交错(jiocu)开来，试求从一特定引擎开始点火有多少种方案。 第1步从特定(tdng)引擎对面的3个中取1个有C(3,1)种取法；第2步从特定引擎(ynqng)一边的2个中取1个有C(2,1)种取法； 第3步从特定引擎对面的2个中取1个有C(2,1)中取法；剩下的每边1个取法固定。所以共有C(3,1)C(2,1)C(2,1)=12种方案。 解：

6、 第8页/共40页第九页，共40页。习题(xt)：1.15试求从1到1000000的整数中，0出现的次数。 解：先将1到999999的整数都看作6位数,例如(lr)2就看作是 000002，这样从000000到999999。0出现了多少次呢？6105，某一位取0，其它(qt)各位任取。0出现在最前面的次数应该从中去掉000000到999999中最左1位的0出现了105次，000000到099999中左数第2位的0出现了104次，000000到009999左数第3位的0出现了103次,000000到000999左数第4位的0出现了102次,000000到000099左数第5位的0出现了10次,0

7、00000到000009左数第6位的0出现了1次。 因此不合法的0的个数为105+104+103+102+101+1=111111，不合法的应该去掉，再加整数1000000中的6个0，这样，从1到1000000的整数中0出现的次数为6105-111111+6=488895。 问题：在去掉多余的零的过程中，多减去了一部分，例如：000000这种情况在每次减的过程中都出现。第9页/共40页第十页，共40页。 1.16、n个完全一样的球放到r个有标志的盒中，无一空盒，试问(shwn)有多少种方案？ 取r个球每盒放一个，然后n-r个放入r个不同盒中，同充许空盒的放法。 C(r+n-r-1,n-r)=C

8、(n-1,n-r)=C(n-1,r-1)第10页/共40页第十一页，共40页。 1.18、8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻(xin ln)，问有多少种排列方案？ 5!654 1.19、n+m位由m个0，n个1组成的符号串，其中(qzhng)nm+1,试问不存在两个1相邻的符号串的数目？ (m+1)*m*.*(m-n+2)/n!=C(m+1,n) 1.20、甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中(qzhng)甲单位占4人，面且7人中男同志5位，试问有多少种方案？ 按甲单位： C(10,

9、4)C(15,1)C(10,2)+C(10,3)C(4,1)C(15,2)C(10,1)+ C(10,2)C(4,2)C(15,3)第11页/共40页第十二页，共40页。 1.20、甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个(y )7人的代表团，要求其中甲单位占4人，面且7人中男同志5位，试问有多少种方案？ 按甲单位： C(10,4)C(15,1)C(10,2)+C(10,3)C(4,1)C(15,2)C(10,1)+ C(10,2)C(4,2)C(15,3) 1.22、(a)C(5,2)C(8,3),(b) C(5,2)C(7,3), (c)C(5,

10、2)C(4,1)C(4,2),(d)C(13,5)- C(5,2)C(7,3)第12页/共40页第十三页，共40页。 1.23、令s=1,2,.,n+1,n2,nknCnCkTzyzxszyxzyxT12)3, 1(2)2, 1(:,),(试证 1、z可选2,3,4,.,n+1,相对(xingdu)应的x,y都有1,2,3,.,n种选择，因此共有：nkkT12 2、可分成x与y相同与不相同两种情况来处理(chl) a、相同时与从n+1中选2个，大的作为z,小的作为x与y, b、不相同时与从n+1个中选3个，最大的作为z两个小的排列作为x与y,排列数为2，两种方式结果相同：nknCnCkT12)

11、3, 1(2)2, 1(第13页/共40页第十四页，共40页。 1.24、50,90,),(bazbabaA(a)求x,y平面(pngmin)上以A作顶点的长方形的数目。(b)求x,y平面(pngmin)上以A作顶点的正方形的数目。第14页/共40页第十五页，共40页。 1.25、平面上有15个点p1,p2,.,p15,其中(qzhng)p1,p2,.,p5,共线，此外不存在三点共线。 1、求至少过15个点中两点的直线的数目。 2、求由15个点中3点组成的三角形的数目。 1、C(10,2)+(10,1)C(5,1)+1 2、C(10,3)+C(10,2)C(5,1)+C(10,1)C(5,2)

12、第15页/共40页第十六页，共40页。 1.26 S=1,2,.,1000,a,bS,使ab=0mod5,求数偶a,b的数目(shm)。 解：偶数有500个，200个5的倍数，100个10的倍数。 单独是5的倍数不是(b shi)10的倍数有100个，偶数中除去10的倍数有400个， C(100,1)C(400,1)+C(100,1)(900,1) 1.27 6位男宾，5位女宾围一圆桌而坐。 女宾不相邻有多少种方案(fng n)？ 所有女宾在一起有多少种方案(fng n)？ 一女宾A和两位男宾相邻又有多少种方案(fng n)？第16页/共40页第十七页，共40页。 5!*6*5*4*3*2 6

13、!5! P(6,2)8! 1.28 k和n都是正整数，kn位来宾(libn)围着k张桌子而坐，试求其方案数。 1.29 从n个对象(duxing)中取r个作圆排列，求其方案数。C(n,r)(r-1)!),(.),(),()!1(nnCnnknCnknCnk第17页/共40页第十八页，共40页。 1.30 试证下列(xili)等式nrrnCrnrnCa1),1, 1(),()()1, 1()!1()!()!1( )!1()!()!1(!)!(!),(rnCrnrrnnrnrrrnnnrrnnrnCnrrnCrrnrnCb1),1,(1),()()1,()!1()!1(!1 )!1()!)(1(!

14、)1(!)!(!),(rnCrnrrnnrrnrrrnrnnrnrrnnrnC第18页/共40页第十九页，共40页。nrrnCrnrnCc1),1, 1(),()(), 1(!)!1()!1( !)!1)()!1(!)!(!),(rnCrnnrrnnrnnrrnrnnnrrnnrnC第19页/共40页第二十页，共40页。 1.31 试证任意(rny)r个相邻数的连乘 (n+1)(n+2).(n+r)=(n+r)!/n!被r!除尽。从n+r个元素(yun s)中取r个的组合数，C(n+r,r)=(n+r)!/n!r! 1.32 在a,b,c,d,e,f,x,x,x,y,y的排列中，要求(yoqi

15、)y必须夹在两个x之间，问这样的排列数等于多少？7！把xyxyx看作一个元素来看待。 1.33 已知r,n,k都是正整数，rnk,将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？C(n+r-nk-1,r-nk)第20页/共40页第二十一页，共40页。 1.34 在r,s,t,u,v,w,x,y,z的排列(pili)中，求y居x和z中间的排列(pili)数。 解：2*7！ 1.35 凸十边形的任意三条对角线不共点，试求这凸十边形的对角线交于多少个点（交点指内部交点，顶点及外部(wib)交点除外）。任意(rny)4点的两条对角线有一个交点，C（10，4）第21页/共40页

16、第二十二页，共40页。 1.36 试证一整数是另一整数的平方的必要条件(b yo tio jin)是除尽它的数的数目是整(奇)数。 解：如果一个数能写成另一个整数(zhngsh)的平方的形式。则hhhhkkkkkkkm222212212.).(2121 除尽m的数的个数是:是奇数)12).(12)(12(21h第22页/共40页第二十三页，共40页。1.37 给出下式的组合(zh)意义), 1(),()0 ,(.)2 , 2()2, 2() 1 , 1() 1, 1()0 ,(),(mrnCmmrCmnCrCmnCrCmnCrCmnC路径(ljng)问题第23页/共40页第二十四页，共40页。

17、1.38 给出下式的组合(zh)意义) 1, 1(),(.), 2(), 1(),(rnCrnCrrCrrCrrC解：解：C(n+1,r+1)是指从是指从n+1个元素个元素a1, a2,an+1中任取中任取r+1个个进行进行(jnxng)组合的方案数。左边：若一定要选组合的方案数。左边：若一定要选an+1,则方案数为则方案数为C(n,r).若不选若不选an+1,一定要选一定要选an,则方案数为则方案数为C(n-1,r).若不选若不选an+1,an,ar+2,则方案数为则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。所有这些可能性相加就得到了总方案数。第24页/共40页第二十五页，

18、共40页。1.39 证明(zhngmng),(2) 0 ,(),(.) 1, 1() 1 ,(),() 0 ,(nmCnmCnmCnmCmCnmCmCn证：组合意义证：组合意义,右边：右边：m个球个球,从中取从中取n个个,放入两个盒子放入两个盒子,n个球中个球中每个球都有两种放法每个球都有两种放法,得到可能的方案得到可能的方案(fng n)数。左边：第数。左边：第i项的意义是项的意义是一个盒子中放一个盒子中放i个个,另一个盒子放另一个盒子放n-i个个,所有的方案所有的方案(fng n)数相加应该等数相加应该等于右边。于右边。ninnininininmCinCnmCnmCinininnmninm

19、innmimiimminimCimC00000),(2),(),(),()!( !)!)(!)!)()!(!)(!),(),(左边第25页/共40页第二十六页，共40页。1.40 从n个人中选(zhng xun)r个围成一个圆圈，问有多少种不同的排列。解：C(n,r)(r-1)!第26页/共40页第二十七页，共40页。1.43 对于(duy)给定的正整数n，证明，当k满足下式时，C(n,k)是取大值。是偶数若是奇数若或nnnnnk,2,2121证：取证：取C(n,k)和和C(n,k-1)进行进行(jnxng)比较。比较。C(n,k)/C(n,k-1)=(n-k+1)/k。要使要使C(n,k)C

20、(n,k-1)，必须，必须k(n+1)/2取取C(n,k)和和C(n,k+1)进行进行(jnxng)比较。比较。C(n,k)/C(n,k-1)=(k+1)/(n-k)。要使要使C(n,k)C(n,k+1)，必须，必须k(n-1)/2因此(ync)，当(n-1)/2k(n+1)/2时取最大值。第27页/共40页第二十八页，共40页。1.44 (a)用组合方式证明下列(xili)式子都是整数。nnnnn32)!3(2)!2(和(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这

21、些重复计算的次数(csh)，n个盒子内部的排列共重复计算了2n次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2n若有3n个不同的球,放入n个不同盒子,故同理得(3n)!/(3!)n是整数。第28页/共40页第二十九页，共40页。1.44 (b)用组合方式证明(zhngmng)下列式子都是整数。12)!()!(nnn有n个不同的球，放入n个相同的盒子(h zi)里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子(h zi)相同，放入不同的盒子(h zi)是没有区别的，应该把n个盒子(h zi)的排列数n

22、!除去。因此得到(n2)!/(n!)n+1是整数。第29页/共40页第三十页，共40页。 1.45 (a)在2n个球中，有n个相同。求从这2n个球中选取(xunq)n个的方案数。 (b)在3n+1个球中，有n个相同。求从这3n+1个球中选取(xunq)n个的方案数。 C(n,0)+C(n,1)+C(n,2)+.+C(n,n)=2n C(2n+1,0)+C(2n+1,1)+C(2n+1,2)+.+C(2n+1,n)(a)相当于从n个不同的小球中分别取出m个小球(0mn)，(b)再从n个相同(xin tn)的小球中取出n-m个小球。共有方案：(c)C(n,0)+C(n,1)+C(n,n)=2n种。

23、(d)(b)相当于从2n+1个不同的小球中分别取出m个小球(0mn)，(e)再从n个相同(xin tn)的小球中取出n-m个小球。共有方案：(f)C(2n+1,0)+C(2n+1,1)+C(2n+1,n)种。第30页/共40页第三十一页，共40页。1.46证明(zhngmng)在由字母表0,1,2生成的长度为n的字符串中.(a)0出现偶数次的字符串有(3n+1)/2个22,2132),(.2)2 ,(2)0 ,()(2nqqnCnCnCbnqnnn其中证：证：(a)归纳法：归纳法：当当n=1时时,0出现偶数次的字符串有出现偶数次的字符串有(30+1)/2=2个个(即即1,2),成立。成立。假设

24、当假设当n=k时时,0出现偶数次的字符串有出现偶数次的字符串有(3k+1)/2种。总的字符串种。总的字符串有有3k种。种。0出现奇数次的字符串有出现奇数次的字符串有(3k-1)/2种。当种。当n=k+1时，时，0出出现偶数次的字符串包括两部分：现偶数次的字符串包括两部分：n=k时时,0出现偶数次再增加一位出现偶数次再增加一位不是不是0的，共有的，共有2(3k+1)/2种，种，0出现奇数次再增加一位出现奇数次再增加一位0,共有共有(3k1)/2种。所以种。所以(suy)共有共有2(3k+1)/2+(3k1)/2=(3k+1+1)/2种，种，证毕。证毕。(b)等式左边第等式左边第m项是项是0出现出

25、现m次的字符串数，总和就是次的字符串数，总和就是0出现偶数出现偶数次的字符串数，右边由次的字符串数，右边由(a)得是得是0出现偶数次的字符串数，出现偶数次的字符串数，两边显然相等。两边显然相等。第31页/共40页第三十二页，共40页。 1.47 5台教学机器m个学生使用，使用第1台和第2台的人数相等(xingdng)，有多少种分配方案？ 解：当使用第1台机器的学生(xu sheng)为n个时，使用第2台机器的学生(xu sheng)也为n,从m个学生(xu sheng)中选出2n个使用这两台机器，剩余的学生(xu sheng)可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-

26、2n)。所以qnnmnnnmC023),2)(2,(2mq第32页/共40页第三十三页，共40页。1.49 在1到n的自然数中选取不同(b tn)且互不相邻的k个数，有多少种选取方案？C(n-k+1,k)第33页/共40页第三十四页，共40页。1.50 (a)在由5个0，4个1组成(z chn)的字符串中，出现01或10的总次数为4的字符串，有多少个？ (b)在由m个0，n个1组成(z chn)的字符串中，出现01或10的总次数为k的字符串，有多少个？(a),先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：(1)把两个1插入0的空当内，剩下(shn xi)的1插入1的前面。(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下(shn xi)的1插入1的前面。故总方案数为C(4,2)3+C(4,1)3=36.第34页/共40页第三十五页，共40页。1.50 (b)在由m个0，n个1组成的字符串中，出现(chxin)01或10的总次数为k的字符串，有多少个？解：m个0产生m-1个空档，或k为奇数(j sh)，则必有且只有1个“1”插入头或尾