组合数学

加法原理、乘法原理

加法原理：如果完成一个任务有 $m$ 类方法（每类方法都可以单独完成任务），第 $i$ 类方法有 $a_i$ 种不同的方法，那么完成这个任务一共有 $\sum a_i$ 种方法。

例如从 3 个红球和 2 个蓝球中选一个，有两类方法：选红或者选蓝。选红有 3 种选法，选蓝有 2 种选法，所以总共有 $2+3=5$ 种选法。

乘法原理相当于加法原理的推论：如果完成一个任务有 $n$ 步（有严格的先后顺序），第 $i$ 步有 $b_i$ 种不同的方法，那么完成这个任务一共有 $\prod b_i$ 种方法。

考虑有 2 步的情况，第一步有 $b_1$ 种方法，第二步有 $b_2$ 种方法，那么有多少类方法可以解决这个问题呢？我们把在第一步选择方法 $j\space(1\le j\le b_1)$ 看成是第 $j$ 类，那么对于第 $j$ 类问题，我们还要从第二步的方法中选一种，即这类方法有 $b_2$ 种方法。所以总方法数就是 $\sum_{i=1}^{b_1} b_2=b_1b_2=\prod b_i$。

例如从 3 个红球和 2 个蓝球中各选一个，红球有 3 种选法，蓝球有 2 中选法，所以总共有 $2\times3=6$ 种选法。

排列组合

• 线排列：从 $n$ 个数中不重复地取出 $k$ 个组成一个排列，排列的方案数记为 $A^k_n$：

  $$A^k_n=n(n-1)(n-2)\dots(n-k)=\frac{n!}{(n-k)!}.$$

• 圆排列：从 $n$ 个数中不重复地取出 $k$ 个数组成一个环，环的方案数记为 $Q^k_n$：

  $$Q^k_n=\frac{A^k_m}{k}=\frac{n!}{k(n-k)!}.$$

  因为这是一个环，相当于在线排列的基础上，循环右移 $m$ 个位置，得到的排列视为等价的，$m$ 可以取 $0,1,2,\dots,k-1$，所以要除以 $k$。

• 组合数：从 $n$ 个数中选 $k$ 种，选法总数记为 $C^k_n$ 或 $\binom{n}{k}$：

  $$C^k_n=\binom{n}{k}=\frac{A^k_m}{A^k_k}=\frac{n!}{k!(n-k)!}.$$

  我比较喜欢 $\binom{n}{k}$ 这种写法。

鸽巢原理 / 抽屉原理

我比较喜欢用抽屉来描述：

• 基本：有 $n+1$ 个物品放到 $n$ 个抽屉里，那么至少有一个抽屉里有 $2$ 或以上个物品。

• 推广：有 $nk+1$ 个物品放到 $n$ 个抽屉里，那么至少有一个抽屉里有 $k+1$ 或以上个物品。

应用的基本思路是插入法：即往若干个抽屉里放物品，考虑覆盖情况。我们需要考虑 “抽屉” 是什么（怎么建模）。