组合数学第一章习题解答

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1,从1,2,.,50中找一双数a,b,使其满足：,求这样的一对数的组合数。,分三部分，1-5，6-45，46-50,C(5,1)+C(40,1)2+C(5,1)/2,分三部分，1-5，6-45，46-50,5+6+7+8+9+C(40,1)10+9+8+7+6+5/2,1,1.3,m个男生，n个女生，排成一行，其中m,n都是正整数，若,(a)男生不相邻（mn+1)；,(b)n个女生形成一个整体；,(c)男生A与女生B排在一起。,解：,(a)首先女生的全排列有n!个，那么第一个男生有n+1个位置,可选第二个男生有n个位置，.，第m个男生有n-m+2个位置可选。,男生不相邻的排列数有n!(n+1)!/(n-m+1)!,(b)把n个女生作为一个整体来看待。n!(m+1)!,(c)男生A与B作为一个整体，(m+n-1)!*2,2,1.5,求3000到8000之间的奇整数的数目，而且没有相同的数字。,解：,C(5,1)C(10,1)C(10,1)C(5,1)=2500,1.6,计算11!+22!+33!+nn!,解：,(n+1)!-1,迭代。,1.7,试证(,n+1)(n+2).(2n)能被2,n,除尽。,解：,=(2n)!(2n-1)!/n!=2,n,n!(2n-1)!/n! =2,n,(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,3,1.8、求10,40,和20,30,的公因数数目。,解：,等价于求(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、试证n,2,的整除数的数目是奇数。,所有的组合数都是偶数，最后再加上1，偶数加1是奇数,4,1.10 证明任一正整数n可惟一地表示成：,先证可表示性：,当n=0,1时，命题成立。,假设对小于n的非负整数，命题成立。,对于n,设k!n(k+1)!,即0n-k!kk!,由假设对n-k!,命题成立，,设n-k!=aii!，其中akk-1,n=aii!+k!，命题成立。,5,再证表示的唯一性：,设n=aii!=bii!,6,1.11 证明下式，并给出组合解释,组合意义：,从n个不同的球中取出的r+1个，要求指定第一个球，有两种方式：,1、,等式左边：,n个不同的球，先任取出1个，再从余下的n-1个中取r个；,2、,等式右边：,n个不同球中任意取出r+1个，并指定其中任意一个为第一个。,显然两种方案数相同。,7,1.12 试证等式：,用多项式(1+x),n,证明，求导,8,1.13、有n个不同的整数，从中取出两组来，要求第1组的最,小数大于另一组的最大数。,设取的第一组数有a个,第二组有b个,而要求第一组数中最小,数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从,大到小取a个作为第一组,剩余的为第二组。此时方案数为,C(n,m)。从m个数中取第一组数共有m-1中取法。,总的方案数为,9,习题：1.14六个引擎分列两排，要求引擎的点火的次序两,排交错开来，试求从一特定引擎开始点火有多少种方案。,第1步从特定引擎对面的3个中取1个有C(3,1)种取法；,第2步从特定引擎一边的2个中取1个有C(2,1)种取法；,第3步从特定引擎对面的2个中取1个有C(2,1)中取法；,剩下的每边1个取法固定。所以共有C(3,1)C(2,1)C(2,1)=12种方案。,解： , ,10,习题：1.15试求从1到1000000的整数中，0出现的次数。,解：先将1到,999999的整数都看作6位数,例如2就看作是,000002，这样从000000到999999。0出现了多少次呢？,610,5,，某一位取0，其它各位任取。,0出现在最前面的次数应该从中去掉,000000到999999中最左1位的0出现了10,5,次，,000000到099999中左数第2位的0出现了10,4,次，,000000到009999左数第3位的0出现了10,3,次,000000到000999左数第4位的0出现了10,2,次,000000到000099左数第5位的0出现了10次,000000到000009左数第6位的0出现了1次。,因此不合法的0的个数为10,5,+10,4,+10,3,+10,2,+10,1,+1=111111，,不合法的应该去掉，再加整数1000000中的6个0，这样，从1到,1000000的整数中0出现的次数为610,5,-111111+6=488895。,问题：在去掉多余的零的过程中，多减去了一部分，例如：,000000这种情况在每次减的过程中都出现。,11,1.16、n个完全一样的球放到r个有标志的盒中，无一空盒，,试问有多少种方案？,取r个球每盒放一个，然后n-r个放入r个不同盒中，同充许空盒的放法。,C(r+n-r-1,n-r)=C(n-1,n-r)=C(n-1,r-1),12,1.18、8个盒子排成一列，5个有标志的球放到盒子中，每盒,最多放一个球，要求空盒不相邻，问有多少种排列方案？,5!654,1.19、n+m位由m个0，n个1组成的符号串，其中nm+1,试问,不存在两个1相邻的符号串的数目？,(m+1)*m*.*(m-n+2)/n!=C(m+1,n),1.20、甲单位有10个男同志，4个女同志，乙单位有15个男同,志，10个女同志，由他们产生一个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),13,1.20、甲单位有10个男同志，4个女同志，乙单位有15个男同,志，10个女同志，由他们产生一个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,2)C(4,1)C(4,2),(d)C(13,5)- C(5,2)C(7,3),14,1.23、令s=1,2,.,n+1,n2,1、z可选2,3,4,.,n+1,相对应的x,y都有1,2,3,.,n种选,择，因此共有：,2、可分成x与y相同与不相同两种情况来处理,a、相同时与从n+1中选2个，大的作为z,小的作为x与y,b、不相同时与从n+1个中选3个，最大的作为z两个小的排列,作为x与y,排列数为2，两种方式结果相同：,15,1.24、,(a)求x,y平面上以A作顶点的长方形的数目。,(b)求x,y平面上以A作顶点的正方形的数目。,16,1.25、平面上有15个点p,1,p,2,.,p,15,其中p,1,p,2,.,p,5,共线，,此外不存在三点共线。,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),17,1.26 S=1,2,.,1000,a,bS,使ab=0mod5,求数偶a,b,的数目。,解：偶数有500个，200个5的倍数，100个10的倍数。,单独是5的倍数不是10的倍数有100个，偶数中除去10的倍数有400个，,C(100,1)C(400,1)+C(100,1)(900,1),1.27 6位男宾，5位女宾围一圆桌而坐。,女宾不相邻有多少种方案？,所有女宾在一起有多少种方案？,一女宾A和两位男宾相邻又有多少种方案？,18,5!*6*5*4*3*2,6!5!,P(6,2)8!,1.28 k和n都是正整数，kn位来宾围着k张桌子而坐，试求其,方案数。,1.29 从n个对象中取r个作圆排列，求其方案数。,C(n,r)(r-1)!,19,1.30 试证下列等式,20,1.31 试证任意r个相邻数的连乘,(n+1)(n+2).(n+r)=(n+r)!/n!被r!除尽。,从n+r个元素中取r个的组合数，C(n+r,r)=(n+r)!/n!r!,1.32 在a,b,c,d,e,f,x,x,x,y,y的排列中，要求y必须夹在,两个x之间，问这样的排列数等于多少？,7！把xyxyx看作一个元素来看待。,1.33 已知r,n,k都是正整数，rnk,将r个无区别的球放在,n个有标志的盒子里，每盒至少k个球，试问有多少种方案？,C(n+r-nk-1,r-nk),21,1.34 在r,s,t,u,v,w,x,y,z的排列中，求y居x和z中间的排列数。,解：2*7！,1.35 凸十边形的任意三条对角线不共点，试求这凸十边形的对角线交于多少个点（交点指内部交点，顶点及外部交点除外）。,任意4点的两条对角线有一个交点，,C（10，4）,22,1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整(奇)数。,解：如果一个数能写成另一个整数的平方的形式。则,除尽m的数的个数是:,23,1.37 给出下式的组合意义,路径问题,24,1.38 给出下式的组合意义,解：,C(n+1,r+1)是指从n+1个元素a1, a2,an+1中任取r+1个,进行组合的方案数。左边：若一定要选an+1,则方案数为C(n,r).,若不选an+1,一定要选an,则方案数为C(n-1,r).,若不选an+1,an,ar+2,则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。,25,1.39 证明,证：,组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中,每个球都有两种放法,得到可能的方案数。左边：第i项的意义是,一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等,于右边。,26,1.40 从n个人中选r个围成一个圆圈，问有多少种不同的排列。,解：C(n,r)(r-1)!,27,1.43 对于给定的正整数n，证明，当k满足下式时，C(n,k)是,取大值。,证：,取C(n,k)和C(n,k-1)进行比较。,C(n,k)/C(n,k-1)=(n-k+1)/k。,要使C(n,k)C(n,k-1)，必须k(n+1)/2,取C(n,k)和C(n,k+1)进行比较。,C(n,k)/C(n,k-1)=(k+1)/(n-k)。,要使C(n,k)C(n,k+1)，必须k(n-1)/2,因此，当,(n-1)/2,k,(n+1)/2时取最大值。,28,1.44 (a)用组合方式证明下列式子都是整数。,(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案,数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个,球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计,算的次数，n个盒子内部的排列共重复计算了2,n,次。得到2n个不,同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2,n,若有3n个,不同的球,放入n个不同盒子,故同理得(3n)!/(3!),n,是整数。,29,1.44 (b)用组合方式证明下列式子都是整数。,有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，,方案数应该是一个整数。按前面(a)的方法，应该得到,(n,2,)!/(n!),n,是整数。另外由于n个盒子相同，放入不同的盒子,是没有区别的，应该把n个盒子的排列数n!除去。,因此得到(n,2,)!/(n!),n+1,是整数。,30,1.45 (a)在2n个球中，有n个相同。求从这2n个球中选取n个的方案数。,(b)在3n+1个球中，有n个相同。求从这3n+1个球中选取n个的方案数。,C(n,0)+C(n,1)+C(n,2)+.+C(n,n)=2,n,C(2n+1,0)+C(2n+1,1)+C(2n+1,2)+.+C(2n+1,n),相当于从,n,个不同的小球中分别取出,m,个小球,(0mn),，,再从,n,个相同的小球中取出,n-m,个小球。共有方案：,C(n,0)+C(n,1)+,C(n,n,)=2,n,种。,(b),相当于从,2n+1,个不同的小球中分别取出,m,个小球,(0mn),，,再从,n,个相同的小球中取出,n-m,个小球。共有方案：,C(2n+1,0)+C(2n+1,1)+C(2n+1,n),种。,31,1.46证明在由字母表0,1,2生成的长度为n的字符串中.,(a)0出现偶数次的字符串有(3,n,+1)/2个,证：,(a)归纳法：,当n=1时,0出现偶数次的字符串有(3,0,+1)/2=2个(即1,2),成立。,假设当n=k时,0出现偶数次的字符串有(3,k,+1)/2种。总的字符串,有3,k,种。0出现奇数次的字符串有(3,k,-1)/2种。当n=k+1时，0出,现偶数次的字符串包括两部分：n=k时,0出现偶数次再增加一位,不是0的，共有2(3,k,+1)/2种，0出现奇数次再增加一位0,共有(3,k,1)/2种。所以共有2(3,k,+1)/2+(3,k,1)/2=(3,k+1,+1)/2种，,证毕。,(b)等式左边第m项是0出现m次的字符串数，总和就是0出现偶数,次的字符串数，右边由(a)得是0出现偶数次的字符串数，,两边显然相等。,32,1.47 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？,解：,当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3,(m-2n),。所以,33,1.49 在1到n的自然数中选取不同且互不相邻的k个数，有多少,种选取方案？,C(n-k+1,k),34,1.50 (a)在由5个0，4个1组成的字符串中，出现01或10的总次数,为4的字符串，有多少个？,(b)在由m个0，n个1组成的字符串中，出现01或10的总次数,为k的字符串，有多少个？,(a),先将5个0排成一列：00000，1若插在两个0中间，“010”，则,出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出,现“01”,“10”总次数为4，有两种办法：,(1)把两个1插入0的空当内，剩下的1插入1的前面。,(2)把1个1插入0得空当内，再取两个1分别插入两端，,剩下的1插入1的前面。故总方案数为C(4,2)3+C(4,1)3=36.,35,1.50 (b)在由m个0，n个1组成的字符串中，出现01或10的总次数,为k的字符串，有多少个？,解：m个0产生m-1个空档，或k为奇数，则必有且只有1个“1”插,入头或尾，总方案数为：,若k为偶数。,36,1.51 从N=1,2,3,.,20中选出3个数，使得没有两个数相邻，,问有多少种方案？,C(20-3+1,3)=C(18,3),1.52 从N=1,2,3,.,n中选出k个数，使得没有两个数相邻，,问有多少种方案？,C(n-k+1,k),1.53 把n个无区别的球放进有标志1,2,3,.,n的n个盒子里，,每个盒子可放多于一个球，求有多少种方案？,C(n+n-1,n)=C(2n-1,n),37,1.56 (n-1)!n!,(n-1)!n(n-1).(n-m+1),1.57 n个人分别沿着两圆桌坐下，一张r个人，另一张n-r个人，试问有多种不同的方案。,C(n,r)(r-1)!(n-r-1)!,1.56 n个男人与n个女人沿一圆桌坐下，问两个女人之间坐一个男人的方案数，又m个女人n个男人，且mm.,(n+1)n(n-1)(n-2).(n-m+2)/m!,38,1.58 一圆周上n个点标以1,2,.,n。每一点与其他n-1个点连,以直线，试问这些直线交于圆内有多少点？,每4点的连线有且只有一个交点，,C(n,4),39,问题：一个n位密码，m个科学家，n能够被m正除，每位科,学家持有密码数相同且相互之间不重复，问共有多少密码分配方,式。,先易后难：设有6位密码1,2,3,4,5,6分给2人。,C(6,3)C(3,3),设k=n/m,C(n,k)C(n-k,k)C(k,k),= C(mk,k)C(mk-k,k)C(k,k),40,