离散数学第七章计数.ppt

《离散数学第七章计数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章计数7.1基本计数原理1.加法原理2.乘法原理加法原理加法原理又称为和计数原理，也称和规则，存在三种表述形式，其本质是说，整体等于其部分之和。①若集合X是不相交非空子集S1，S2，…，Sm的并，则

2、X

3、=②若E1，E2，…，Em是彼此互斥事件，并且E1发生有e1种方式，E2发生有e2种方式，…，Em发生有em种方式，则E1或E2或…或Em发生有e1+e2+…+em种方式。应该指出的是，事件E1和E2互斥是说，E1和E2发生但两者不能同时发生。③如果选择事物O1有n1种方法，选择事物O2有n2种方法，…，选择事

4、物Om有nm种方法，并且选择诸事物方法不重叠，则选取O1或O2或…或Om有n1+n2+…+nm种方法。加法原理例7.1.1一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。如果该生对5门数学课和3门生物学课具有选课条件，试问该生有多少方式来选修课程？乘法原理乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。①若S1，S2，…，Sm是非空集合，则笛卡尔积S1S2…Sm的元素个数是②若事件E1，E2，…，Em发生分别有e1，e2，…，em种方式，并且诸事件是独立的，则事件E1或E2

5、或···或Em依次发生有e1e2…em种方式。乘法原理③如果选取事物O1，O2，…，Om分别有n1，n2，…，nm种方法，并且选取诸事物方法不重叠，则事物O1与O2与…与Om依次选取有n1n2…nm种方法。乘法原理例7.1.2一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？例7.1.3计数因特网地址。在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位的

6、位串，它以网络标识netid开始，后跟随主机标识hostid，该标识把一个计算机认定为某个指定网络成员。乘法原理乘法原理根据网络标识和主机标识位数的不同目前使用3类地址形式：用于最大规模网络的A类地址，由0后跟7位网络标识和24位的主机标识构成。用于中等规模网络的B类地址，由位串10后跟14位的网络标识和16位的主机标识构成。用于最小规模网络的C类地址，由位串110后跟21位的网络标识和8位的主机标识构成。此外，又规定位串1111111在A类的网络标识中是无效的，全0和全1组成的主机标识对任何网络都是无效的。试计数

7、因特网上的计算机有多少不同的有效IPV4地址？乘法原理令D是因特网上计算机的有效地址数，DA,DB,DC分别表示A类B类和C类的有效地址，根据加法原理D=DA+DB+DCA类的网络标识有27-1=127个（1111111无效），主机标识224-2=16777214（全0和全1组成的主机标识无效），根据乘法原理，DA=127*16777214乘法原理B类的网络标识有214个，主机标识216-2个，根据乘法原理，DB=214*（216-2）C类的网络标识有221个，主机标识28-2个，根据乘法原理，DB=221*（28

8、-2）D=DA+DB+DC=37370918427.2鸽洞原理若n+1只鸽子入住n个鸽洞，则至少有1个鸽洞里至少有2只鸽子。例7.2.1在任意一群366人中，至少有2人生日相同。例7.2.2抽屉里有3副手套，随意抽出4只手套，则其中至少有一副手套。鸽洞原理例7.2.3一个学生用37天准备考试。根据以往的经验他知道需要复习的时间不超过60个小时，他打算每天至少复习1小时，证明不管他如何安排学习时间表（假定每天学习时数为整数），必存在相继的若干天，他恰好共学习13小时。鸽洞原理设t1是第一天学习的时数，t2是前2天学习

9、时数，t3是前3天学习时数……因为每天至少学习1小时，所以t1≥1,数列t1,t2,……,t37是严格单调递增的：t1

10、小时鸽洞原理的推广设m1,m2,…,mn是正整数，并有m1+m2+…+mn-n+1只鸽子住进n个鸽洞，则或者第1个鸽洞至少有m1只鸽子，或者第2个鸽洞至少有m2只鸽子，…，或者第n个鸽洞至少有mn只鸽子。证明：反证法。假设第一个鸽洞住进的鸽子数少于m1只，第2个鸽洞住进鸽子数少于m2只……于是，鸽子总数不超过（m1-1）+（m2-1）+……+（mn-1)=m