排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切

加乘原理

加法原理：一个任务有 $n$ 种方法完成，第 $i$ 种方法有 $a_{i}$ 种选择，那么完成任务的方式一共有 $\sum_{i} a_{i}$ 种。

乘法原理：一个任务有 $n$ 步，第 $i$ 步有 $a_{i}$ 种方法，那么完成任务的方式一共有 $\prod_{i} a_{i}$ 种。

排列数和组合数

阶乘

阶乘是组合数学中经常用到的运算。对于 正整数 $n$ 而言，它的阶乘定义为：

$n! = 1 \times 2 \times . . . \times n = \prod_{i = 1}^{n} i$

阶乘的概念也可以延拓到整个实数域上，其中一种称为 伽玛函数 （ $Γ$ 函数），但这超出了组合数学的讨论范围。

排列数

组合数学的一个基础问题是，从 $n$ 个互不相同的元素中选出 $m$ 个出来进行排列，一共有多少种可能？这是一个非常常见的问题，因此我们用 $A_{n}^{m}$ 来表示这个问题的答案，以便在未来使用。我们称 $A_{n}^{m}$ 为 排列数 。

为了解决这个问题，不妨从第一个位置开始考虑。对于这个位置，一共有 $n$ 个元素可以选择；而对于第二个位置，因为在上一步已经选择了一个元素，因此这个位置还有 $n - 1$ 个元素可以选择；以此类推，第 $i$ 个位置有 $n - i + 1$ 种选择。

根据乘法原理，总的排列的数量就是每个位置的选择数的乘积。因此我们得到了：

$A_{n}^{m} = n * (n - 1) * . . . * (n - m + 1) = \frac{n!}{(n - m)!}$

从这个公式也可以看出，当 $n = m$ 时， $A_{n}^{m} = n!$ ，因此 $n!$ 的意义是将 $n$ 个数全部进行排列的方法数，这种排列称为 全排列。

组合数

组合数学的另一个基础问题是，从 $n$ 个互不相同元素中选 $m$ 个元素，一共有多少种方法。出于同样的原理，我们记这个问题的答案为 $(\binom{n}{m})$ 或 $C_{n}^{m}$ ，称为 组合数 ，也称 二项式系数。称为后者的原因会在后文提到。 $C_{n}^{m}$ 这种记法在中学教科书中更常使用。

将组合数与排列数相比较，可以发现组合数相当于一个不考虑顺序的排列数：在排列数中，我们先选了 $m$ 个元素，然后对它们进行了排列；而在组合数中，我们只进行了前一步，而没有排序。所以根据乘法原理，可以列出这样一个式子：

$排列数 = 组合数 * 将 m 个元素全排列的数量$

所以不难得到：

$(\binom{n}{m}) = \frac{A_{n}^{m}}{m!} = \frac{n!}{m! (n - m)!}$

组合恒等式

下面介绍一些常见的和组合数有关的恒等式：

$(\binom{n}{k}) = (\binom{n}{n - k})$ ：从 $n$ 个元素中选 $k$ 个，相当于从 $n$ 个元素中选 $n - k$ 个不要。
$(\binom{n + 1}{m}) = (\binom{n}{m}) + (\binom{n}{m - 1})$ ：考虑第 $n + 1$ 个元素选不选，选的情况下是 $(\binom{n}{m - 1})$ ，不选的情况下是 $(\binom{n}{m})$ 。这个公式也是 杨辉三角 （帕斯卡三角）的计算公式
$\sum_{i = 0}^{n} (\binom{n}{i}) = 2^{n}$ ：相当于考虑每个元素选不选，因此一共是 $2^{n}$ 中可能。
$(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{m - 1})$ ：由公式不难得到。
$\sum_{i = 0}^{m} (\binom{n}{i}) (\binom{m}{k - i}) = (\binom{m + n}{k})$ ：相当于将可以选择的元素分成了两部分，然后依次考虑每个部分选几个。这个式子称为 范德蒙恒等式 。

组合恒等式还有很多，读者可以自行拓展。

捆绑法和插板法

处理组合问题时，有两个基本的技巧可以使用：捆绑法和插板法。

捆绑法

捆绑法是用来解决一类要求部分元素相邻问题的技巧，也称“大元素法”。例如，一共有 $n$ 类水果，第 $i$ 类水果有 $a_{i}$ 个，问如果要求同一类水果必须相邻，有多少种排列的方法。

因为水果必须相邻，不妨把同一类水果看成一个“大元素”。然后，对这些大元素进行排列，然后再考虑各个大元素内部如何排列。

因为一共有 $n$ 类水果，因此大元素排列的数目就是 $n!$ 。对于每个大元素，其中元素的排列的数目是 $a_{i}$ ，因此总数是 $n! * \sum_{i = 1}^{n} a_{i}!$ 。

插板法

插板法是用于解决给若干相同元素分组的技巧。例如，现有 $n$ 个 完全相同 的元素，要求将其分为 $k$ 组，保证每组至少有一个元素，一共有多少种分法？

考虑拿 $k - 1$ 块板子插入到 $n$ 个元素两两形成的 $n - 1$ 个空里面。

因为元素是完全相同的，所以答案就是 $(\binom{n - 1}{m - 1})$ 。

二项式定理

二项式定理解决了下面这样一个多项式展开后各项的系数问题：

$(a + b)^{n} = \sum_{i = 0}^{n} (\binom{n}{i}) a^{i} b^{n - i}$

为了证明这个结论，不妨将原式的幂指数展开：

$(a + b)^{n} = (a + b) (a + b) . . . (a + b)$

为了进一步展开这个式子，我们可以进行下面的操作：从第一个 $(a + b)$ 中选择 $a$ 或 $b$ ，然后从第二个式子选，以此类推，一共进行了 $n$ 次选择，最后将这 $n$ 次选择的结果相乘，就得到了完全展开后的其中一项，而这样的项一共有 $2^{n}$ 个。

而在完全展开的结果中，如果最后得到了 $a^{i} b^{n - i}$ ，相当于要在上式的 $n$ 个 $(a + b)$ 中选 $i$ 个 $a$ ，因此总的选法就是 $(\binom{n}{i})$ 。因此， $a^{i} b^{n - i}$ 的系数就是 $(\binom{n}{i})$ 。