排列数与组合数
首先是定义
组合数：从 \(n\) 个不同元素中，任取 \(m(m \le n)\) 个元素并成一组，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合；\(C_{n}^{m}\) 表示从 \(n\) 个不同元素中取出 \(m(m \le n)\) 个元素的所有组合的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数。
例如，从 \(\left\{1, 2, 3 \right\}\) 这3个不同元素中，取出2个元素的所有组合就是 \(\left\{1, 2\right\}\), \(\left\{1, 3\right\}\) 和 \(\left\{2, 3 \right\}\) ， 因此组合数 \(C_{3}^{2} = 3\) 。
排列数：表示从 \(n\) 个不同元素中，任取 \(m(m \le n)\) 个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做从\(n\)个不同元素中取出 \(m\) 个元素的一个排列。 \(P_{n}^{m}\) 表示从 \(n\) 个不同元素中取出 \(m\) 个元素的所有排列的个数，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的排列数。
例如，从 \(\left\{1, 2, 3 \right\}\) 这3个不同元素中，取出2个元素的所有排列就是\(\left\{1, 2\right\}\), \(\left\{2, 1\right\}\)，\(\left\{1, 3\right\}\), \(\left\{3, 1\right\}\) , \(\left\{2, 3 \right\}\) , \(\left\{3, 2\right\}\) 因此排列数 \(P_{3}^{2} = 6\) 。
排列与元素的顺序有关，组合与顺序无关。
下面是一些计算排列数与组合数的常用公式：
-
\[P_{a}^{b} = a(a - 1)...(a - b + 1) = \frac{a!}{(a - b)!} \]
很容易理解，取第一个元素时有 \(a\) 种取法，取第二个元素时有 \((a - 1)\) 种取法...一直到第 \(b\) 个元素时有 \((a - b + 1)\) 种取法， 相乘即可得。
-
\[C_{a}^{b} = \frac{P_{a}^{b}}{b!} = \frac{a(a - 1)...(a - b +1)}{b!} = \frac{a!}{b!(a - b)!} \]
同样也很容易理解：先从求出从 \(a\) 个元素中取 \(b\) 个元素的排列数，然后对于取出的 \(b\) 个元素，它们的 \(P_{b}^{b}\) 种排列的元素都是同一个组合的，因此除去 $ P_{b}^{b} $ , 即 \(b!\)。
-
\[C_{a}^{b} = C_{a - 1}^{b} + C_{a - 1}^{b - 1} \]
这个就有点动态规划的思想了，假设从 \(a\) 个苹果中选 \(b\) 个苹果，那么所有的组合就一定能够不重不漏地分成2类：不取第 \(a\) 个苹果的组合和取第 \(a\) 个苹果的组合。不取第 \(a\) 个苹果的组合数等同于从剩下 $a - 1 $个苹果中取出 \(b\) 个苹果的组合数， 即 \(C_{a - 1}^{b}\)。取第 \(a\) 个苹果的组合数就等同于先将第 \(a\) 个苹果拿走，再从剩下的 \(a - 1\) 个苹果中取出 \(b - 1\) 个苹果的组合数， 即 \(C_{a - 1}^{b - 1}\) 。于是从 \(a\) 个苹果中选 \(b\) 个苹果的组合数就是这两种组合数的和， 即 \(C_{a}^{b} = C_{a - 1}^{b} + C_{a - 1}^{b - 1}\)。
-
\[C_{n}^{0} + C_{n}^{1} + C_{n}^{2} + ...+C_{n}^{n} = 2^n \]
这个就是要从实际含义来考虑，$ C_{n}^{0} + C_{n}^{1} + C_{n}^{2} + ...+C_{n}^{n} $ 实际上就相当于求从 \(n\) 个元素中取任意多个元素 \((\le n)\) 的组合数，那么对于每个元素，都有取或不取 \(2\) 种可能，所以一共 \(n\) 个元素就有 \(2^n\) 种可能，每种可能对应了一种组合，由此可得该恒等式。（恒等式证明常常都是从等式的实际含义考虑）。