加法原理和乘法原理
根据维基百科：
- 加法原理：若有a种方式做某事，b种方式做另一件事，但只能选其一，则共有$a+b$种选择。
- 乘法原理：若有a种方式做某事，b种方式做另一件事，则共有$a\times b$种方式做这两件事。
加法原理还是乘法原理？
取决于是否分步骤。分步则乘法，否则加法。
排列组合
排列
不可重复排列
从$n$个不同的元素中任取m（$1\le m \le n$）个不同的元素，按顺序排成一列，排列方式有$P^m_n$种
- 如果 $m \lt n$，那么 $P^m_n = A^m_n = n(n-1)...(n-m+1)$
- 如果 $m = n$，那么 $P^n_n = A^n_n = n(n-1)...1 = n!$
第二种情况称为全排列
可重复排列
从$n$个不同的元素中有放回地取m个元素，按顺序排成一列，则有 $n^m$ 种排列方式。
组合
从$n$个不同元素种取出$m$个不同元素，不管顺序排成一组，则有$C^m_n = \frac{P^m_n}{m!} = \frac{n(n-1)...(n-m+1)}{m!}$ 种组合方式。
这里要除以$m!$是为了去重。
注意：
- $0! = 1$
- $C^m_n = C^{n-m}_n$
- $C^m_n = C^{m-1}_{n-1} + C^m_{n-1}$
排列还是组合？
取决于是否按顺序排起来。按顺序则排列，否则是组合。