离散数学第七章 计数

离散数学

第七章 计数

离散数学

7.1 基本计数原理1.加法原理 2.乘法原理

离散数学

加法原理加法原理又称为和计数原理，也称和规则，存在三种表 述形式，其本质是说，整体等于其部分之和。 ① 若集合X是不相交非空子集S1,S2,…,Sm的并，则 |X|= m

| Si 1

i

|

② 若E1,E2,…,Em是彼此互斥事件，并且E1发生有e1 种方式，E2发生有e2种方式，…,Em发生有em种方式， 则E1或E2或…或Em发生有e1+e2+…+em种方式。 应该指出的是，事件E1和E2互斥是说，E1和E2发生但两 者不能同时发生。

离散数学

③ 如果选择事物O1有n1种方法，选择事物O2 有n2种方法，…,选择事物Om有nm种方法， 并且选择诸事物方法不重叠，则选取O1或O2 或…或Om有n1+n2+…+nm种方法。

离散数学

加法原理

例7.1.1 一个学生想选修一门数学课或一门生 物学课，但不能同时选修两门课。如果该生对 5门数学课和3门生物学课具有选课条件，试问 该生有多少方式来选修课程？

离散数学

乘法原理

乘法原理又称有序计数原理，也称积规则，类 似加法原理，也有三种表述形式。 ① 若S1,S2,…,Sm是非空集合，则笛卡尔 m 积S1 S2 … Sm的元素个数是 | Si | i 1 ② 若事件E1,E2,…,Em发生分别有e1, e2,…,em种方式，并且诸事件是独立的，则 事件E1或E2或·· m依次发生有e1 e2 … em ·或E 种方式。

离散数学

乘法原理

③ 如果选取事物O1,O2,…,Om分别有n1, n2,…,nm种方法，并且选取诸事物方法不重 叠，则事物O1与O2与…与Om依次选取有 n1 n2 … nm种方法。

离散数学

乘法原理

例7.1.2 一个学生要选修两门课，第一门课在 上午4小时内任选1小时，第二门课在下午3小 时内也可任选1小时，试问该生有多少种可能 的时间安排？

离散数学

乘法原理

例7.1.3 计数因特网地址。在由计算机的物理网络 互连而构成的因特网中，每台计算机的网络连接 被分配一个因特网地址。在网际协议版本IPV4中， 一个地址是32位的位串，它以网络标识netid开始， 后跟随主机标识hostid,该标识把一个计算机认定 为某个指定网络成员。

离散数学

乘法原理

根据网络标识和主机标识位数的不同目前使用3类地 址形式： 用于最大规模网络的A类地址，由0后跟7位网络标识 和24位的主机标识构成。 用于中等规模网络的B类地址，由位串10后跟14位的 网络标识和16位的主机标识构成。 用于最小规模网络的C类地址，由位串110后跟21位的 网络标识和8位的主机标识构成。 此外，又规定位串1111111在A类的网络标识中是无 效的，全0和全1组成的主机标识对任何网络都是无效 的。试计数因特网上的计算机有多少不同的有效IPV4 地址？

离散数学

乘法原理

令D是因特网上计算

机的有效地址数， DA,DB,DC分别表示A类B类和C类的有效地址， 根据加法原理D= DA+DB+DC A类的网络标识有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-2) D= DA+DB+DC=3737091842

离散数学

7.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天学习时 数，t3是前3天学习时数…… 因为每天至少学习1小时，所以t1≥1,数列 t1,t2,……,t37是严格单调递增的： t1<t2<……<t37 复习的时间不超过60个小时,所以t37≤60 数列t1+13,……t37+13也是严格递增的，并且 t37+13 ≤73

离散数学

鸽洞原理

因此74个数t1,t2,……,t37,t1+13,……t37+13 都位于1和73之间，根据鸽洞原理，它们之中 必有两个数相等 由于前37个数和后37个数都是彼此不相等的， 故存在两个数i和j,使得ti=tj+13 于是j+1,j+2,……,i这些天中，该生恰好学 习13小时

离散数学

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

离散数学

7.3 容斥原理有限集合中的容斥定理,在无限集合中不一定成立.

2个集合的情形：|A∪B| = |A| + |B| – |A∩B|

3个集合的情形：|A∪B∪C| = |A| + |B|+|C| – |A∩B| – |A∩C| – |B∩C|+ |A∩B∩C|一般情形：1 i n

| A1 A2 An |

| A | | A Ai 1 i j n i

j

|

1 i j k n

| A Ai

j

Ak |

( 1) n 1 | A1 A2 An |

离散数学

设S为全集，又因为 | A | | S | | A | 则有 | A1 A2 An | | S | | A1 A2 An | | S | | Ai | 1 i n 1 i j n

| A Ai

j

|

1 i j k n

| A Ai

j

Ak |

( 1) n | A1 A2 An |

2个集合的情形： | A B | = |S| – (|A| + |B|) + |A∩B| 3个集合的情形： | A B C | = |S| – (|A| + |B|+|C|) + (|A∩B| + |A∩C| + |B∩C|) – |A∩B∩C|

离散数学

例 一个班里有50个学生，在第一次考试中有26 人得5分，在第二次考试有21人得5分.如果两次 考试中都没得5分的有17人，那么两次考试都得5 分的有多少人？ 解 设A,B分别表示在第一次和第二次考试中得5 分的学生的集合，那么有 |S|=50, |A|=26, |B|=21, | A B | =17 由 | A B | = |S| – (|A| + |B|) + |A∩B|,得 |A∩B| = | A B | – |S| + (|A| + |B|) = 17 – 50 + 26 + 21=14

有14人两次考试都得5分.

离散数学

7.4 排列与组合我们以前讨论的排列称为线排列更为确 切，因为它隐含着将所选择的r元素排成在一 直线上，若使线排列的首末元素相邻就得了 “圆排列”。 定义7.4.2 从n元集S中有序选择r个元素并 排成一个圆周称为S的一个r圆排列，不同的r r 圆排列总数记为K(n,r)或 K n 。

本文来源：https://www.bwwdw.com/article/1on1.html