组合基础
排列与排列数
给定 \(n\) 个互不相同的元素 \(a_1,a_2,\cdots ,a_n\)，一个排列 \(p\) 就是它们的一个排序方式，例如 \(a_2,a_3,a_1\) 就是 \(a_1,a_2,a_3\) 的一个排列。举个例子：ABC三人拍照，他们的站位方式共有几种？从左到右看，可以是ABC、ACB、BAC、BCA、CAB、CBA，共有六种，这六个站位方式都是ABC的排列。
在讨论排列时，我们只关注元素的数量而并不关注每个元素具体是什么，因此我们可以认为 \(n\) 个元素的排列就是 \(1,2,\cdots ,n\) 的排列。
在上面的例子中，不同的排列数量共有 \(6\) 种，给定元素数量 \(n\)，如何计算其排列数？称最左边的位置为第一个位置，之后从左到右依次是第二个、第三个，......，第 \(n\) 个位置，那么第一个位置可以是 \(1,2,\cdots ,n\) 中的任意一个元素，共有 \(n\) 种选法，第二个位置不能和第一个位置相同，因此有 \(n-1\) 种选法，第三个位置不能与前两个位置相同，因此有 \(n-2\) 种选法，以此类推，第 \(n\) 个位置只有 \(1\) 种选法，乘法原理即可得到 \(n\) 个元素的排列数为 $$ n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 $$ 为了写作方便，定义 \(n!=n(n-1)(n-2)\cdots (2)(1)\)，称作 “\(n\) 的阶乘”，于是 \(n\) 个元素的排列数就是 \(n!\)。
更准确地，我们可以这样定义阶乘： $$ n!=\begin{cases} 1, &n=0\newline n \times (n-1)!, &n \ge 1 \end{cases} $$
一种等价的定义是 $$ n!=\prod_{i=1}^{n}i $$
注意上面我们规定了 \(0!=1\)，一个比较合理的理解是空排列有且仅有一种（就是空），这样子表示“空”的边界条件在后面会频繁出现。
做一个简单推广：从 \(n\) 个不同元素中选出 \(m\) 个元素组成的排列有多少种呢？显然就是 \(n \times (n-1) \times \cdots \times (n-m+1)\)，一共 \(m\) 项，它就等于 \(\frac{n!}{(n-m)!}\)。
还有一种表示方法叫做“下降幂”，记作 \(x^{\underline n}=\prod_{i=0}^{n-1}(x-i)\)。在 \(x\) 为正整数且 \(x \ge m\) 时，\(x^{\underline m}=\frac{x!}{(x-m)!}\)。发现什么了吗？阶乘的定义域为正整数但下降幂的底数可以是任意实数！高中数学课本中将 \(\frac{n!}{(n-m)!}\) 记作 \(A_n^m\)，表示从 \(n\) 个互异元素中选出 \(m\) 个组成排列的方案数，但这个记号在OI中很冷门，大家都喜欢用下降幂 \(n^{\underline m}\) 表示。
对于下降幂，有 \(n^{\underline 0}=1\)（注意这导出了 \(0^{\underline 0}=1\) 而非 \(0\)），\(n^{\underline 1}=n\)。若 \(m > n\)，则 \(n^{\underline m} = 0\)。
组合数
假如我们不关注选出元素的相对顺序，只考虑它们构成的集合，就得到的组合数。一般地，称从 \(n\) 个互异元素中选出 \(m\) 个元素组成的集合的方案数为 “\(n\) 选 \(m\)”，记作 \(\binom{n}{m}\)。
记号差异
高中数学课本中选用的是另一种记号 \(C_n^m\)，注意上下标是相反的。
一个大小为 \(m\) 的集合可以变为 \(m!\) 个排列，所以 \(\binom{n}{m}\) 就应该等于 \(n^{\underline m}\) 再除以 \(m!\)，即 $$ \binom{n}{m}=\frac{n^{\underline m}}{m!} $$
注意，假如我们将排列数 \(\frac{n!}{(n-m)!}\) 写成下降幂的形式，那么上标的定义域就可以扩展为 \(\mathbb{R}\)！假如采取阶乘的定义方式，定义域就是自然数，即 \(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)。
简单验证一下，\(\binom{n}{0}= \frac{n^{\underline 0}}{0!}=1\)（显然我们只有空集 \(\varnothing\) 这一种选法）， \(\binom{n}{1}=\frac{n^{\underline 1}}{1!}=n\)，\(\binom{n}{n}=1,\binom{n}{n+1}=0\)。