基础原理与排列组合
计数原理
组合数学的核心在于计数，主要依赖两个基本原理：
- 加法原理（分类计数）：完成一件工程有 $n$ 类办法，第 $i$ 类办法有 $a_i$ 种不同方法（$i \in [1, n]$）。则完成该工程的总方法数为各类方法之和： $$\sum_{i=1}^{n} a_i$$
- 乘法原理（分步计数）：完成一件工程需要 $n$ 个步骤，第 $i$ 步有 $a_i$ 种不同方法（$i \in [1, n]$）。则完成该工程的总方法数为各步方法之积： $$\prod_{i=1}^{n} a_i$$
排列数 ($A_n^m$)
定义：从 $n$ 个不同元素中，选择 $m$ 个元素组成排列的个数。
推导：基于乘法原理，第 1 个位置有 $n$ 种选择，第 2 个位置有 $n-1$ 种选择，以此类推，第 $m$ 个位置有 $n-m+1$ 种选择，故相乘得证。
公式：
$$A_n^m = n \cdot (n-1) \cdot (n-2) \cdots (n-m+1) = \frac{n!}{(n-m)!}$$- 全排列：当 $m=n$ 时，$A_n^n = n!$，即 $n$ 个元素的全排列。
组合数 ($C_n^m$ 或 $\binom{n}{m}$)
定义：从 $n$ 个不同元素中，取出 $m$ 个元素组成集合（不考虑顺序）的个数。
公式：
$$C_n^m = \binom{n}{m} = \frac{A_n^m}{A_m^m} = \frac{n!}{m!(n-m)!}$$组合数的性质
以下是组合数的一些重要性质及其解释：
对称性：
$$\binom{n}{m} = \binom{n}{n-m}$$解释：从 $n$ 个元素中选取 $m$ 个元素，相当于从 $n$ 个元素中“不选” $n-m$ 个元素。
帕斯卡公式（递推公式）：
$$\binom{n+1}{m} = \binom{n}{m} + \binom{n}{m-1}$$解释：考虑第 $n+1$ 个元素，分为“不选该元素”（从剩下列 $n$ 个中选 $m$ 个）和“选该元素”（从剩下 $n$ 个中选 $m-1$ 个）两种情况。
边界条件：
$$\binom{n}{0} = 1, \quad \binom{n}{n} = 1$$特别规定：当 $m > n$ 时，$\binom{n}{m} = 0$。
分组问题与插板法
插板法是解决“相同元素分组”问题的核心方法。
插板法（正整数解）
问题：将 $n$ 个相同元素分为 $m$ 组，每组至少有 1 个元素，有多少种分法？
思路：在 $n$ 个元素形成的 $n-1$ 个空隙中，插入 $m-1$ 个隔板。
公式：
此问题等价于求方程 $\sum_{i=1}^m x_i = n$ （$x_i \ge 1$）的整数解个数。
插板法（非负整数解）
问题：将 $n$ 个相同元素分为 $m$ 组，每组可以为空（即 $\ge 0$ 个元素），有多少种分法？
思路（借元法）：先给每组额外“借” 1 个元素（共 $m$ 个），问题转化为将 $n+m$ 个元素分为 $m$ 组，每组至少 1 个。等分配完后再从每个组抽出一个元素就能符合原问题了。
公式：
此问题等价于求方程 $\sum_{i=1}^m x_i = n$ （$x_i \ge 0$）的整数解个数。
插板法（不定方程解的个数）
问题：将 $n$ 个相同元素分为 $m$ 组，第 $i$ 组至少有 $a_i$ 个元素，$\sum a_i \le n$，有多少种分法？
思路：从 $n$ 个元素中拿出 $\sum a_i$ 个元素，给每个组分 $a_i$ 个元素，接下来再从剩下 $n-\sum a_i$ 个元素分为 $m$ 组，每组可以为 $0$，等同于上一个问题。
公式：
此问题等价于求方程 $\sum_{i=1}^m x_i = n$ （$x_i \ge a_i$）的整数解个数。
不相邻组合
问题：从 $n$ 个相同元素中选取 $m$ 个，要求这 $m$ 个元素互不相邻的组合数。
思路（插空法）（逆向思考）：
- 既然选出的 $m$ 个元素不能相邻，我们可以先处理不被选中的 $n-m$ 个元素。
- 将这 $n-m$ 个元素排成一列，它们之间以及两端会产生 $(n-m) + 1$ 个空位。
- 要保证选出的元素不相邻，只需将这 $m$ 个选中的元素插入到上述不同的空位中即可。 公式： $$\binom{n-m+1}{m}$$
二项式定理
公式：
$$(a+b)^n = \sum_{i=0}^{n} \binom{n}{i} a^{n-i} b^i$$证明思路（数学归纳法）：
- 验证 $n=1$ 时成立。
- 假设 $n=k$ 时成立。
- 当 $n=k+1$ 时，利用 $(a+b)^{k+1} = (a+b)(a+b)^k$，展开后利用 $\binom{k}{i} + \binom{k}{i-1} = \binom{k+1}{i}$ 即可得证。
如何直观理解（组合意义）？
我们以 $b$ 的幂为参考，当 $b$ 的幂为 $i$ 时相当于从 $n$ 个括号式子中选出了 $i$ 个 $b$ 进行相乘，这就有 $\binom{n}{i}$ 种情况，因此是 $\binom{n}{i} a^{n-i}b_i$
推广：
$$ (x_1 + \cdots + x_t)^n = \sum_{n_1 + \cdots + n_t = n} \frac{n!}{n_1! \cdots n_t!} x_1^{n_1} \cdots x_t^{n_t} $$$$ = \sum_{n_1 + \cdots + n_t = n} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1} \cdots x_t^{n_t} $$理解方式可以参考二项式定理
多重集 (Multiset)
定义：多重集 $S = {n_1 \cdot a_1, n_2 \cdot a_2, \dots, n_k \cdot a_k}$，总元素个数 $n = \sum n_i$。
多重集的排列数 | 多重组合数
公式：
$$ \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{n_1! n_2! \cdots n_k!} $$解释：多重集排列数即字面意思，每 $n_i$ 个 $a_i$ 就会产生 $n_i!$ 个排列，由此便推出公式。此式子同时也是多重组合数，即把 $n$ 个元素分成 $k$ 份， 第 $i$ 份有 $n_i$ 个元素，其实也可以用来解释普通的组合数，$\binom{n}{m}$ 其实就是把 $n$ 个元素分成 $2$ 份，一份包含 $m$ 个元素，一份包含 $n-m$ 个元素。
$$ \binom{n}{m}=\binom{n}{n-m}=\binom{n}{n,n-m} $$多重集的组合数
情况 1：无限制
从 $S$ 中取出 $r$ 个元素，且 $r$ 小于任意 $n_i$（即元素充足），等价于 $k$ 种元素选 $r$ 个的可重组合。问题可以转化为求解不定方程 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的个数
公式：
情况 2：有限制（容斥原理应用） 问题：求 $x_1 + x_2 + \cdots + x_k = r$ 的非负整数解个数，约束条件为 $0 \le x_i \le n_i$。 计算步骤：
- 全集 $U$：不考虑 $x_i \le n_i$ 的限制，只考虑 $x_i \ge 0$。由扩展插板法，总数为 $\binom{r+k-1}{k-1}$。
- 定义属性 $S_i$：表示 $0 \le x_i \le n_i$ 的解。
- 答案即为交集（我们使用 $\overline{S_i}$ 表示 $S_i$ 的补集）： $$ \left | \bigcap_{i=1}^{k} S_i \right |=|U|-\left | \bigcup_{i=1}^{k} \overline{S_i} \right | $$
公式表示：
$$Ans = \sum_{T \subseteq \{1, \dots, k\}} (-1)^{|T|} \binom{r - \sum_{i \in T}(n_i+1) + k - 1}{k-1}$$(注意：当组合数下标小于上标时，值为0)
圆排列
定义：$n$ 个人排成一圈形成的排列数。 公式：
$$Q_n^n = \frac{A_n^n}{n} = (n-1)!$$组合数的其他高级性质
- $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$。
- $\sum_{i=0}^n \binom{n}{i} = 2^n$。
- $\sum_{i=0}^n (-1)^i \binom{n}{i} = 0$。
鸽巢原理 (Pigeonhole Principle)
又称抽屉原理或狄利克雷原理。
基本形式
原理：将 $n+1$ 个物品放入 $n$ 个抽屉中，那么至少有一个抽屉里含有 2 个或 2 个以上的物品。
证明：使用反证法。假设每个抽屉里的物品都少于 2 个（即至多 1 个），那么所有抽屉的物品总数 $\le n \times 1 = n$，这与总共有 $n+1$ 个物品矛盾。
推广形式
原理：将 $n$ 个物品放入 $k$ 个抽屉中，那么至少有一个抽屉里含有 $\lceil \frac{n}{k} \rceil$ 个物品。
注：$\lceil x \rceil$ 表示对 $x$ 向上取整。