#C07L02P01. C07.L02.组合数学之加法与乘法原理

C07.L02.组合数学之加法与乘法原理

1 加法原理

若具有性质 A 的事件有 m 个,具有性质 B 的事件有 n 个,则具有性质 A 或性质 B 的事件有 m + n 个。

  • 例子:从广州到上海可以做飞机,也可以做高铁。广州到上海的航班一共有 10 个,高铁有 7 趟列车。则坐飞机或者高铁从广州到上海有 10 + 7 个可供选择的方案。

设集合 S 被划分成两两不相交的部分 S1S_1S2S_2 ....SmS_m 。则 S 的对象数目可以通过确定它的每一个部分的对象数目并如此相加而得到:

|SS| = |S1S_1| + |S2S_2| + ... + |SmS_m|

2 乘法原理

若具有性质 A 的事件有 m 个,具有性质 B 的事件有 n 个,则具有性质A及性质B的事件有 m * n 个。

  • 例子:从广州到北京有 20 个交通方案,从北京到纽约有 3 个交通方案,则从广州先到北京再到纽约的方案一共有 20 * 3 = 60 个。

3 减法原理

令 A 是一个集合,而 U 是包含 A 的更大集合。设

Aˉ\bar A = UA U - A = {xU:xA{x \in U: x \notin A } }

  • 例子: 从广州到上海要么是做飞机,要么是坐火车,只有这两种方法可以选择。则从广州坐火车到上海的方案 = 从广州到上海的交通方案 排除 从广州坐飞机到上海的方案。

Aˉ\bar AAAUU 中的补集。那么 AA 中的对象数目 | AA | 由下列法则给出:

| AA | = | UU | - | Aˉ\bar A |

  • 例子: 从广州到上海要么是做飞机,要么是坐火车,只有这两种方法可以选择。则从广州坐火车到上海的方案数 = 从广州到上海的交通方案总数 - 从广州坐飞机到上海的方案数。

4 除法原理

SS 是一个有限集合,把它划分成 k 个部分使得每一部分包含的对象数目相同。于是,此划分中的部分的数目有下述公式给出:

kk = S在一个部分中的对象数目\large {\frac {|S|} {在一个部分中的对象数目}}