离散数学
离散数学
第
第
5
5
章 计数
章 计数
离散数学 第 5 章 计数
5.1
5.1
计数基本原理
计数基本原理
5.2
5.2
排列与组合
排列与组合
5.3
5.3
重集的排列与组合
重集的排列与组合
第
第
5
5
章 计数
章 计数
5.4
5.4
递归式及其应用
递归式及其应用
离散数学 第 5 章 计数
5.1.1
5.1.1
加法原理和乘法原理
加法原理和乘法原理
5.1 计数基本原理
加法原理:
加法原理:
若对象或事件的有限集合 S=S
1
∪S
2
… ∪ ∪S
n
且 S
1
,…,S
n
两两不
相交,那么 |S|=|S
1
|+|S
2
| +… + |S
n
|
另一个说法:
另一个说法:
n 个独立事件分别有 a
1
,…, a
n
种方式发生,那么这 n 个事件
之一发生的方式总计为 a
1
+ … +a
n
种。
离散数学 第 5 章 计数
5.1.1
5.1.1
加法原理和乘法原理
加法原理和乘法原理
5.1 计数基本原理
乘法原理:
乘法原理:
若对象或事件的有限集合 S 是依次取自有限集合 S
1
, S
2
,…,S
n
中事件的序列的集合,那么 |S|=|S
1
|•|S
2
| •… •|S
n
|
另一个说法:
另一个说法:
n 个独立事件分别有 a
1
,…, a
n
种不同发生方式,那么这 n
个
事件同时发生的方式总计为 a
1
•…•a
n
种。
离散数学 第 5 章 计数
5.1.1
5.1.1
加法原理和乘法原理
加法原理和乘法原理
5.1 计数基本原理
例
例
5.1
5.1
(1)
(1) 从上海直达天津可以乘坐汽车、火车和飞机旅行。已知每天
汽车有 3 个班次,火车有 8 个班次,飞机有 4 个班次,问每天
从上海直达到天津有多少种不同的旅行方式?
(2)
(2) 从上海直达天津可以乘坐汽车、火车和飞机旅行,已知汽车
有 3 个班次,火车有 8 个班次,飞机有 4 个班次。从天津直达
大连可以乘坐轮船和飞机旅行,已知轮船有 2 个班次,飞机
有 3 个班次。问从上海经天津到大连有多少种旅行方式?
解
解
(1)
(1) 3 + 8 + 4 = 15 种 ( 加法原理 ) 。
(2)
(2) 15·(2 + 3)= 75 种 ( 加法原理和乘法原理 )