# 算法讲义：排列组合与二项式定理全汇总

## 1. 组合数基础知识

### 1.1 组合数的阶乘表示
从 $n$ 个不同物品中选取 $k$ 个物品的方案数，记作 $C\_n^k$ 或 $\binom{n}{k}$。
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
**推导：** 选取第一个物品有 $n$ 种选法，第二个有 $n-1$ 种……第 $k$ 个有 $n-k+1$ 种。由于选出的 $k$ 个物品内部无序，需除以其全排列 $k!$。

### 1.2 递推公式（杨辉三角）
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
**代码实现（预处理）：**
```cpp
const int mod = 10007;
const int N = 1010;
int c[N][N];

void init() {
    for (int i = 0; i < N; i++) {
        c[i][0] = 1; // 边界：选0个物品方案为1
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
        }
    }
}
```

---

## 2. 二项式定理

### 2.1 定理内容
$$(a+b)^n = \sum\_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$
**直观理解：** 在 $(a+b)(a+b)\dots(a+b)$ 这 $n$ 个括号中，每个括号要么选 $a$ 要么选 $b$。若选了 $k$ 个 $b$，则必然选了 $n-k$ 个 $a$，对应的项即为 $a^{n-k}b^k$，其系数是从 $n$ 选 $k$ 的组合数。

### 2.2 常见变形
1.  **所有系数和：** $\sum\_{k=0}^{n} \binom{n}{k} = 2^n$ （令 $a=1, b=1$）
2.  **奇偶项系数和相等：** $\sum\_{i \text{ is odd}} \binom{n}{i} = \sum\_{i \text{ is even}} \binom{n}{i} = 2^{n-1}$ （令 $a=1, b=-1$）
3.  **单项为1：** $(1+x)^n = \sum\_{k=0}^n \binom{n}{k} x^k$

---

## 3. 组合数常见变形与证明

### 3.1 吸收律 (Absorption Identity)
$$k \binom{n}{k} = n \binom{n-1}{k-1}$$
*   **证明：** $\text{左边} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = \text{右边}$。

### 3.2 进阶变形（平方求和项）
$$k^2 \binom{n}{k} = n \binom{n-1}{k-1} + n(n-1) \binom{n-2}{k-2}$$
*   **证明（组合意义）：** 一个班级 $n$ 个人，选出 $k$ 个候选人，再从候选人中选一名班长和一名副班长（一人可兼二职）。
    *   **左边：** 先选 $k$ 个候选人，再选班长（$k$ 种），再选副班长（$k$ 种）。
    *   **右边：** 分类讨论：
        1. 班长副班长是同一个人：选 1 人当班长兼副班长（$n$ 种），再选剩下 $k-1$ 个候选人 $\binom{n-1}{k-1}$。
        2. 班长副班长是不同的人：先选 2 人（$n(n-1)$ 种），再选剩下 $k-2$ 个候选人 $\binom{n-2}{k-2}$。

### 3.3 范德蒙德卷积 (Vandermonde's Identity)
$$\sum\_{i=0}^k \binom{n}{i} \binom{m}{k-i} = \binom{n+m}{k}$$
*   **证明：** 从 $n$ 个男生和 $m$ 个女生中选出 $k$ 个人，等价于总共 $n+m$ 个人中选 $k$ 个人。

---

## 4. 经典放球模型与排列

### 4.1 隔板法（球同，盒异）
1.  **盒子不能为空：** $n$ 个球 $n-1$ 个空隙插 $m-1$ 个板。
    *   方案：$\binom{n-1}{m-1}$
2.  **盒子可以为空：** 假设多借 $m$ 个球，每盒先放一个，再用不为空的公式。
    *   方案：$\binom{n+m-1}{m-1}$

### 4.2 错位排列 (Derangement)
每个数都不在自己位置的排列，记为 $D\_n$。
*   **递推公式：** $D\_n = (n-1)(D\_{n-1} + D\_{n-2})$
*   **证明：** 假设 $n$ 放在位置 $k$（$n-1$ 种情况）。
    1. 若 $k$ 回到了 $n$ 的位置：剩下 $n-2$ 个数错排，$D\_{n-2}$。
    2. 若 $k$ 不在 $n$ 的位置：将 $n$ 的位置看作 $k$ 的“禁区”，剩下 $n-1$ 个数错排，$D\_{n-1}$。

### 4.3 圆排列
$n$ 个人坐一圆桌，旋转相同视为同一种。
*   公式：$\frac{n!}{n} = (n-1)!$

---

## 5. 多重集合的排列与组合

### 5.1 多重集合的排列（全排列）
设 $n$ 个物体中，第 $i$ 类物体有 $n\_i$ 个，且 $\sum n\_i = n$。
*   公式：$\frac{n!}{n\_1! n\_2! \dots n\_k!}$
*   **证明：** 先看作全排列 $n!$，由于同类物体交换顺序不产生新方案，需除以各类的内部排列数。

### 5.2 多重集合的组合
从 $n$ 种元素中选 $k$ 个（每种元素无限多，允许重复）。
*   公式：$\binom{n+k-1}{k}$
*   **等价模型：** 将 $k$ 个相同的球放入 $n$ 个不同的盒子（允许为空）。

### 5.3 举例说明
**问题：** 假设有 3 种对象 $\{A, B, C\}$，要从中选择 3 个（允许重复）。
**计算：** 这里 $n=3$（种类）, $k=3$（选择数）。
依据公式：$\binom{n+k-1}{k} = \binom{3+3-1}{3} = \binom{5}{3} = 10$。
**具体方案枚举：**
1. 全同：{AAA, BBB, CCC} (3种)
2. 两同：{AAB, AAC, BBA, BBC, CCA, CCB} (6种)
3. 全异：{ABC} (1种)
**合计：** 10 种。正确。

算法讲义：排列组合与二项式定理全汇总

1. 组合数基础知识

1.1 组合数的阶乘表示

从 $n$ 个不同物品中选取 $k$ 个物品的方案数，记作 $C_n^k$ 或 $\binom{n}{k}$。 $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ 推导： 选取第一个物品有 $n$ 种选法，第二个有 $n-1$ 种……第 $k$ 个有 $n-k+1$ 种。由于选出的 $k$ 个物品内部无序，需除以其全排列 $k!$。

1.2 递推公式（杨辉三角）

$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$ 代码实现（预处理）：

const int mod = 10007;
const int N = 1010;
int c[N][N];

void init() {
    for (int i = 0; i < N; i++) {
        c[i][0] = 1; // 边界：选0个物品方案为1
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
        }
    }
}

2. 二项式定理

2.1 定理内容

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$$ 直观理解： 在 $(a+b)(a+b)\dots(a+b)$ 这 $n$ 个括号中，每个括号要么选 $a$ 要么选 $b$。若选了 $k$ 个 $b$，则必然选了 $n-k$ 个 $a$，对应的项即为 $a^{n-k}b^k$，其系数是从 $n$ 选 $k$ 的组合数。

2.2 常见变形

所有系数和： $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ （令 $a=1, b=1$）
奇偶项系数和相等： $\sum_{i \text{ is odd}} \binom{n}{i} = \sum_{i \text{ is even}} \binom{n}{i} = 2^{n-1}$ （令 $a=1, b=-1$）
单项为1： $(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$

3. 组合数常见变形与证明

3.1 吸收律 (Absorption Identity)

$$k \binom{n}{k} = n \binom{n-1}{k-1}$$ * 证明： $\text{左边} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} = \text{右边}$。

3.2 进阶变形（平方求和项）

$$k^2 \binom{n}{k} = n \binom{n-1}{k-1} + n(n-1) \binom{n-2}{k-2}$$ * 证明（组合意义）： 一个班级 $n$ 个人，选出 $k$ 个候选人，再从候选人中选一名班长和一名副班长（一人可兼二职）。 * 左边： 先选 $k$ 个候选人，再选班长（$k$ 种），再选副班长（$k$ 种）。 * 右边： 分类讨论： 1. 班长副班长是同一个人：选 1 人当班长兼副班长（$n$ 种），再选剩下 $k-1$ 个候选人 $\binom{n-1}{k-1}$。 2. 班长副班长是不同的人：先选 2 人（$n(n-1)$ 种），再选剩下 $k-2$ 个候选人 $\binom{n-2}{k-2}$。

3.3 范德蒙德卷积 (Vandermonde's Identity)

$$\sum_{i=0}^k \binom{n}{i} \binom{m}{k-i} = \binom{n+m}{k}$$ * 证明： 从 $n$ 个男生和 $m$ 个女生中选出 $k$ 个人，等价于总共 $n+m$ 个人中选 $k$ 个人。

4. 经典放球模型与排列

4.1 隔板法（球同，盒异）

盒子不能为空： $n$ 个球 $n-1$ 个空隙插 $m-1$ 个板。
- 方案：$\binom{n-1}{m-1}$
盒子可以为空： 假设多借 $m$ 个球，每盒先放一个，再用不为空的公式。
- 方案：$\binom{n+m-1}{m-1}$

4.2 错位排列 (Derangement)

每个数都不在自己位置的排列，记为 $D_n$。 * 递推公式： $D_n = (n-1)(D_{n-1} + D_{n-2})$ * 证明： 假设 $n$ 放在位置 $k$（$n-1$ 种情况）。 1. 若 $k$ 回到了 $n$ 的位置：剩下 $n-2$ 个数错排，$D_{n-2}$。 2. 若 $k$ 不在 $n$ 的位置：将 $n$ 的位置看作 $k$ 的“禁区”，剩下 $n-1$ 个数错排，$D_{n-1}$。

4.3 圆排列

$n$ 个人坐一圆桌，旋转相同视为同一种。 * 公式：$\frac{n!}{n} = (n-1)!$

5. 多重集合的排列与组合

5.1 多重集合的排列（全排列）

设 $n$ 个物体中，第 $i$ 类物体有 $n_i$ 个，且 $\sum n_i = n$。 * 公式：$\frac{n!}{n_1! n_2! \dots n_k!}$ * 证明： 先看作全排列 $n!$，由于同类物体交换顺序不产生新方案，需除以各类的内部排列数。

5.2 多重集合的组合

从 $n$ 种元素中选 $k$ 个（每种元素无限多，允许重复）。 * 公式：$\binom{n+k-1}{k}$ * 等价模型： 将 $k$ 个相同的球放入 $n$ 个不同的盒子（允许为空）。

5.3 举例说明

问题： 假设有 3 种对象 ${A, B, C}$，要从中选择 3 个（允许重复）。 计算： 这里 $n=3$（种类）, $k=3$（选择数）。依据公式：$\binom{n+k-1}{k} = \binom{3+3-1}{3} = \binom{5}{3} = 10$。 具体方案枚举： 1. 全同：{AAA, BBB, CCC} (3种) 2. 两同：{AAB, AAC, BBA, BBC, CCA, CCB} (6种) 3. 全异：{ABC} (1种) 合计： 10 种。正确。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com