华东师范大学离散数学章炯民课后习题第9章答案

P1602.任意100人中，至少有多少人的生日在同一个月？解：é100/12ù=9少数学生计算错误：84.设a1,a2,…,an是n个整数。证明：存在k和l（n³l>k³0），使得ak+1+ak+2+…+al被n整除。证明：构造序列：0,a1,a1+a2,a1+a2+a3,…，a1+a2+a3+…+an,共有n+1个元素«鸽巢，对每个元素模n求余，余数分别为0,1,2,…,n-1共n种«鸽子，则必存在两个元素模n同余，其差被n整除，故存在k和l（n³l>k³1），使得ak+1+ak+2+…+al被n整除。约60%学生选做此题。均采用模n求余的方法。12.股评家推荐了12个股票，一股民欲购买其中的3个。问在下列各种条件下，分别有多少种不同的投资方式？（1）每个股票各投资3000元（2）3个股票分别投资5000元、3000元和1000元解：C123=220P123=1320正确14.n个元素排成一个圆形，叫做环排列。计算n个不同元素的环排列数。解：把环从某个点剪开的话就是一般的直线排列了，全排列公式是Ann=n!.然后考虑到同一个环排列从不同个点剪开得到的是不同的排列，也就是一个环排列可以得到n个排列，所以是n！/n=（n-1）！基本正确。个别为：n！18.用组合的方法证明：对任意正整数n，C(r,r)＋C(r+1,r)＋…＋C(n,r)＝C(n＋1,r+1)。证明：C(n＋1,r+1)表示n＋1位长的二进制串，包含r+1个1。其中，考虑最后一个1可能位置的相关情况：最后一个1一定出现在位置r+1，r+2，…,或者n+1。如果最后一个1出现在第k位，那么一定有r个1出现在前k-1位，这样的二进制串有C(k-1,r)个，对所有的k求和，其中r+1≤k≤n+1，共有C(r,r)＋C(r+1,r)＋…＋C(n,r)个n位二进制串恰含有r+1个1。得证。大部分学生利用公式C(n,r)=C(n-1,r-1)+C(n-1,r)证明23.16支互不同颜色的蜡笔平分给4个孩子，有多少种不同的分法？解：C(16,4)C(12,4)C(8,4)C(4,4)正确24.求方程x1+x2+x3=16分别满足下列条件的非负整数解的个数：（1）x1≥1（2）xi≥2，i=1,2,3（3）10≥x3≥2解：满足条件的解相当于下面的3元多重集的16组合：第一种元素至少有1个，这种组合又相当于3元多重集的15组合，因此有C(15+3-1,15)＝C(17,15)=136个。满足条件的解相当于下面的3元多重集的16组合：第一种元素至少有2个，第二种元素至少有2个，第三种元素至少有2个，这种组合又相当于3元多重集的10组合，因此有C(10+3-1,10)=C(12,10)=66个。满足条件的解相当于下面的3元多重集的16组合：x3≥2，第三种元素至少有2个，这种组合又相当于3元多重集的14组合，因此有C(14+3-1,14)个。x3≥11，第三种元素至少有11个，这种组合又相当于3元多重集的5组合，因此有C(5+3-1,5)个，满足10≥x3≥2条件的个数为C(14+3-1,14)-C(5+3-1,5)=C(16,14)-C(7,5)=99.基本正确。部分学生第三题错。少数学生计算错误。27.某学校有2504个计算机科学专业的学生，其中1876人选修了C语言，999人选修了Fortran语言，345人选修了JAVA，876人选修了C语言和Fortran语言，231人选修了Fortran和JAVA，290人选修了C和JAVA，189个学生同时选了C、Fortran和JAVA。问没有选这3门程序设计语言课中的任何一门的学生有多少个？解：A表示选修了C语言，B表示选修了Fortran语言，C表示选修了JAVA|AÈBÈC|=|A|+|B|+|C|-|AÇB|-|BÇC|-|CÇA|+|AÇBÇC|=1876+999+345-876-231-290+189=2012则没有选这3门程序设计语言课中的任何一门的学生：2504-2012=492正确29.某设集合S={1,2,3,…,n}，求偶数都不在其自然位置上的S的全排列的个数。解：U：{1,2,…,n}的全排列的集合Ai：偶数i在第i个位置上的全排列的集合P：错排列的集合P=U-(A2ÈA4È…ÈAnn为偶数时，|P|=|U|-|A2ÈA4È…ÈAn=n!-(C(n/2,1)(n-1)!-C(n/2,2)(n-2)!+…+(-1)n/2C(n/2,n)(2/n)!n为奇数时，|P|=|U|-|A1ÈA2È…ÈAn=n!-(C((n-1)/2,1)(n-1)!-C((n-1)/2,2)(n-2)!+…+(-1)n-2)/2(n-1)/2!)选做率80%基本正确，个别学生在最后一项时套用书中例题，出现错误补充：含n个变量的命题公式有多少可能的个不同的真值表？解：含n个变量的命题的真值表有2n行，n+1列，前n列给出n个变量的取值的所有可能的组合，最后一列给出命题的真值。若按照相同的规则排列这n个变量的取值的所有可能的组合，则对于任何含n个变量的命题，其真值表的前n列都相同，不同的真值表仅在最后一列有所不同。最后一列有2n个真值，每个有2种可能的取值，所以，由乘法法则，不同的真值表共个。大部分学生错答为2n2.一个碗里有10个红球和10个篮球。一个女士不看着球而随机地选取。（1）她必须选多少个球才能保证至少有3个球是同色的？（2）她必须选多少个球才能保证至少有3个球是蓝色的？解：5个13个正确在(x1+x2+…+xm)n的展开式中，合并同类项以后有多少个不同的项？解：C(n+m-1,n)大部分正确，部分学生错答为C(n+m-1,m),C(n+m-1,m-1)等在关于10个集合的容斥原理的公式中有多少个项？解：第i个个中共有个项，++…+=210-1=1023，即共有1023个项。选做率60%，计算错误：210把8个不同的球放入3个不同的罐子，每个罐子至少有1个球。问有多少种方法？解：8个不同的球放入到3个不同的罐子中的方法数等于从8个元素的集合到3个元素的集合的函数的数目，按定理1，这个数目是38-C(3,1)28+C(3,2)18=6561-1536+3*1=5796种.错误较多。A(8,3)35或A(8,3)C(7,2）等1.一给出下列序列的一个递推关系：（1）{n2+3n}（2）{1+(-1)n}2.设含连续三个0的n位二进制串的数目是sn，请给出{sn}的递推关系和初始条件。3.设{1,2,…,n}的错排列数是Dn，请给出{Dn}的递推关系和初始条件。解：Dn=(n-1)(Dn-1+Dn-2)1.求初值问题的通项公式：an=10an-1-25an-2；a0=-7，a1=15。*2.求递推关系的一个特解：an＝8an-2-16an-4+n24n。*3.求初值问题的通项公式：hn=hn/2+2，n=2k，k≥1；h1=11.写出序列{1,0,1,0,1,0,…}的生成函数。2.计算广义二项式系数和的值。3.一钱罐里有大量1角、2角、3