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

2020-04-03 11:10

P160

2. 任意100人中,至少有多少人的生日在同一个月? 解:?100/12?=9

少数学生计算错误:8

4. 设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元 解:

(1) C123=220 (2) P123=1320 正确

14. n个元素排成一个圆形,叫做环排列。计算n个不同元素的环排列数。 解:

把环从某个点剪开的话就是一般的直线排列了,全排列公式是An=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 解:

(1) 满足条件的解相当于下面的3元多重集的16组合:第一种元素至少有1个,这种

组合又相当于3元多重集的15组合,因此有C(15+3-1,15) =C(17,15)=136个。 (2) 满足条件的解相当于下面的3元多重集的16组合:第一种元素至少有2个,第二

n

种元素至少有2个,第三种元素至少有2个,这种组合又相当于3元多重集的10组合,因此有C(10+3-1,10) =C(12,10)=66个。

(3) 满足条件的解相当于下面的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?…?An) n为偶数时,

|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-1)/2!)

选做率80%基本正确,个别学生在最后一项时套用书中例题,出现错误 补充:

1. 含n个变量的命题公式有多少可能的个不同的真值表?

解:

含n个变量的命题的真值表有2n行,n+1列,前n列给出n个变量的取值的所有可能的组合,最后一列给出命题的真值。若按照相同的规则排列这n个变量的取值的所有可能的组合,则对于任何含n个变量的命题,其真值表的前n列都相同,不同的真值表仅在最后一列有所不同。最后一列有2n个真值,每个有2种可能的取值,所以,由乘法法则,不同的真值表共2n

大部分学生错答为2

2nn-2)/2

个。

2. 一个碗里有10个红球和10个篮球。一个女士不看着球而随机地选取。 (1)她必须选多少个球才能保证至少有3个球是同色的? (2)她必须选多少个球才能保证至少有3个球是蓝色的?

解:

(1) 5个

(2) 13个 正确

n

3. 在(x1+x2+…+xm)的展开式中,合并同类项以后有多少个不同的项?

解:

C(n+m-1,n)

大部分正确,部分学生错答为C(n+m-1,m), C(n+m-1,m-1)等 4. 在关于10个集合的容斥原理的公式中有多少个项?

解:

|A1?A2???A10?1?i?10?|Ai|?1?i?j?10?|Ai?Ai|?1?i?j?k?10?|Ai?Ai?Ak|???|A1?A2???A10|i1210 第i个?个中共有C10个项,C10+C10+…+C10=210-1=1023,即共有1023个项。

选做率60%,计算错误:2

5. 把8个不同的球放入3个不同的罐子,每个罐子至少有1个球。问有多少种方法? 解:

8个不同的球放入到3个不同的罐子中的方法数等于从8个元素的集合到3个元素的集合的函数的数目,按定理1,这个数目是

n8

m10

?C(n,1)(n?1)8

85

m?C(n,2)(n?2)m???(?1)n?1C(n,n?1)1

m3-C(3,1)2+C(3,2)1=6561-1536+3*1=5796种. 错误较多。A(8,3)3或A(8,3)C(7,2)等

1. 一给出下列序列的一个递推关系: 2

(1){n+3n} n

(2){1+(-1)}

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= 1

1. 写出序列{1,0,1,0,1,0,…}的生成函数。

2. 计算广义二项式系数 和 的值。

3. 一钱罐里有大量1角、2角、3角和5角的硬币,从中任取r个。请给出不同取法数

的生成函数,并求取5个硬币的方法数。

4. 某计算机系统用八进制数字串作为码字,若数字串中含有的0、2、4、6的个数为奇数,1、3、5、7的个数为偶数,则认为该串是有效码字,设an是长度为n(n=0,1,2,…)的有效码字的个数。请写出数列an的指数型生成函数,并给出an的计算公式。 解: G(x)?(11!x?113!x??)(3410!x?012!x??)?(24e?e2x?x)(4e?e2x?x)?4128(e2x?e?2x)4


华东师范大学离散数学章炯民课后习题第9章答案.doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:高中数学必修3第一次月考数学

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: