分步乘法计数原理

乘法原理是组合计数的基本计数原理。简而言之，“若有 $a$ 种方法做某事， $b$ 种方法做另一事，则合共有 ${a \cdot b}$ 种方法做此两件事。”

例子

有一个集合 $A= \{a_1,a_2,a_3\}$ ,一个集合 $B= \{b_1,b_2\}$ ,现从分别从集合 $A,B$ 中取一个元素,形成一个新的集合 $C$ ,问 $C$ 有多少种可能性?

    ┌───► a1
    │
a ──┼───► a2
    │
    └───► a3

    ┌───► b1
b ──┤
    └───► b3

注意前提条件: 集合 $A \cap B = \varnothing$ 即两次选择中，没有选项重复出现

整个问题可以等同于选取一个有序对 $(a,b)$ ,其中 $a \in A,b \in B$ , $a$ 有 $3$ 种取法, $b$ 有 $2$ 种取法,则共有 $3 \times 2 = 6$

使用集合来描述这个种问题

\left. \begin{array} {c} C = \{(a,b) \mid a \in A , b \in B \} \\ A \cap B = \varnothing \\ \end{array} \right\} \Rightarrow |C| = |A| \times |B|

有 $n$ 个不同球,编号为 $1,2,\cdots,n$ ,放到 $n$ 个不同的盒子里,有多少种不同的放法?

设 $f(n)$ 表示n个数据时的方案数. $f(n) = n \times f(n-1)$

核心:

放的顺序不影响结果(需要证明).
- 所以可以先放第n个球.
- 这说明这是一个面对集合的问题,而不是面对一个序列的问题!
第n个球放完后,相当于减少了一个位置,问题就变成了 $f(n-1)$ .这说明:无论第n个球放哪个位置,所形成的子问题的答案都是一样的,所以一定是把这些子问题加起来(加法原理),也就是 $N \times f(n-1)$

证明:放的顺序不影响结果, 本质是一种映射关系. 顺序放法 $put_1$ 与放法 $put_2$ ,都可以得到答案集合里的任意一个元素. 也就是说 $put_1$ , $put_2$ 都可以得到所有的答案.

总结: 第一步有n种可能性(放法),第二步放编号为n-1的球,有n-1个可能性,… 最后答案就把这些可能性乘以起来

f(n) = n! = n \times (n-1) \times (n-2) \times \cdots 1

TODO