定义
排列
从 $n$ 个不同的元素中，任取 $m$ 个元素按照一定的顺序构成一个序列的方案数，叫做从 $n$ 个元素中取出 $m$ 个元素的排列数。
排列数记为 $A(n,m)$ 或 $A_{n}^{m}$。
组合
从 $n$ 个不同的元素中，任取 $m$ 个元素无序构成一个集合的方案数，叫做从 $n$ 个元素中取出 $m$ 个元素的组合数。
组合数记为 $C(n,m)$ 或 $C_{n}^{m}$，最常用的是 $n\choose m$。
计算公式
$$ A_{n}^{m}=n\times (n-1)\times (n-2)\times (n-m+1)=\prod_{i=n-m+1}^{n}{i}=\dfrac{n!}{(n-m)!}\\ {n\choose m}=\dfrac{A_{n}^{m}}{A_{m}^{m}}=\dfrac{\dfrac{n!}{(n-m)!}}{m!}=\dfrac{n!}{m!\,(n-m)!} $$
常见公式
$$ {n\choose m}={n\choose n-m} $$
数学证明
$$ {n\choose m}=\dfrac{n!}{m!\,(n-m)!}=\dfrac{n!}{(n-m)!\,m!}={n\choose n-m} $$
组合意义证明
从 $n$ 个人中选取 $m$ 个人留下，等同于 $n$ 个人中选取 $n-m$ 个人让他们离开。
$$ {n\choose m}={n-1\choose m}+{n-1\choose m-1} $$
数学证明
$$ \begin{aligned} {n-1\choose m}+{n-1\choose m-1}&=\dfrac{(n-1)!}{m!\,(n-m-1)!}+\dfrac{(n-1)!}{(m-1)!\,(n-m)!}\\ &=\dfrac{(n-1)!\,(n-m)}{m!\,(n-m)!}+\dfrac{(n-1)!\,m}{m!\,(n-m)!}\\ &=\left(\dfrac{n-m}{n}+\dfrac{m}{n}\right)\dfrac{n!}{m!\,(n-m)!}\\ &={n\choose m} \end{aligned} $$
组合意义证明
从 $n$ 个人中选取 $m$ 个人留下，可以分两类讨论：
- 第 $n$ 个人被选中了：此时还要从剩下的 $n-1$ 人中选取 $m-1$ 个人，故方案数为 ${n-1\choose m-1}$。
- 第 $n$ 个人没被选中：此时还要从剩下的 $n-1$ 人中选取 $m$ 个人，故方案数为 ${n-1\choose m}$。
综上，总方案数 ${n\choose m}={n-1\choose m-1}+{n-1\choose m}$。
$$ \sum\limits_{i=0}^{n}{n\choose i}=2^{n} $$
证明
考虑从 $n$ 个人中选出任意个留下（可以不选），询问有多少种方案。
- 对于每个人考虑，每个人有留下或者不留下两种情况，所以总方案数为 $2^n$。
- 对于选的人考虑，枚举选出的人数 $i\in[0,n]$，总情况数就是 $\sum_{i=0}^{n}{n\choose i}$。
综上， 可得 $\sum_{i=0}^{n}{n\choose i}=2^n$。
二项式定理：
$$
(x+y)^{n}=\sum\limits_{i=0}^{n}{n\choose i}x^{i}y^{n-i}
$$
证明
式子的含义是对于 $\forall\,i\in[0,n]$，求 $x^iy^{n-i}$ 的系数。
这相当于从 $n$ 个物品中选 $i$ 个给 $x$，选 $n-i$ 个给 $y$ 的方案数，所以其系数为 ${n\choose i}$。
由于该式子的存在，组合数也常被成为二项式系数。
应用
用二项式定理求证 $\sum_{i=0}^{n}{n\choose i}=2^{n}$。
证明：
$$ \begin{aligned} 2^n&=(1+1)^n\\ &=\sum\limits_{i=0}^{n}{n\choose i}1^i1^{n-i}\\ &=\sum\limits_{i=0}^{n}{n\choose i} \end{aligned} $$
$$ \sum\limits_{i=0}^{n}{n\choose i}(-1)^i=0 $$
证明
$$ \begin{aligned} 0&=(-1+1)^n\\ &=\sum\limits_{i=0}^{n}{n\choose i}(-1)^i 1^{n-i}\\ &=\sum\limits_{i=0}^{n}{n\choose i}(-1)^i \end{aligned} $$
应用
该公式提醒我们，在杨辉三角内，对于同一行的组合数，奇数位置的和与偶数位置的和相等。
即
$$
\sum\limits_{2\,\mid\,i}{n\choose i}=\sum\limits_{2\,\nmid\,i}{n\choose i}
$$
公式集合
$$ \begin{cases} {n\choose m}={n\choose n-m}\\ {n\choose m}={n-1\choose m}+{n-1\choose m-1}\\ \sum\limits_{i=0}^{n}{n\choose i}=2^{n}\\ (x+y)^{n}=\sum\limits_{i=0}^{n}{n\choose i}x^{i}y^{n-i}\\ \sum\limits_{i=0}^{n}{n\choose i}(-1)^i=0\\ \end{cases} $$