---
title: "组合数学进阶"
description: "容斥原理、卡特兰数、错排列、圆排列、鸽巢原理与二项式定理。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 组合数学进阶

![](https://img.dailyup.xyz/optimized/8207672311838-59d12621-8f9b-4a07-816a-14398c7572b9.jpg)

入门级的计数题靠排列组合公式就能解决。到了提高级，题目开始出现「至少」「不重复」「相邻不能相同」这类限制，光靠公式不够了，需要容斥、错排列、卡特兰数这些工具。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| NOI 提高级 | 2.5.3 离散与组合数学：多重集合、等价关系与等价类、多重集上的排列与组合、错排列、圆排列、鸽巢原理、二项式定理、容斥原理、卡特兰数 | 全章 |

## 二项式定理

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

展开式中 $a^{n-k}b^k$ 的系数就是 $\binom{n}{k}$。这个定理把「展开」和「组合计数」连了起来：系数之所以是组合数，是因为从 $n$ 个括号里选 $k$ 个取 $b$ 的方案数就是 $\binom{n}{k}$。

几个常用的变形：

- 令 $a = b = 1$：$\sum_{k=0}^{n} \binom{n}{k} = 2^n$。$n$ 个元素的子集总数是 $2^n$，互相印证。
- 令 $a = 1, b = -1$：$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$，奇数项系数和等于偶数项系数和。
- $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots = 2^{n-1}$（$n \ge 1$）。

## 多重集的排列与组合

**多重集**是允许元素重复的集合，比如 $\{a, a, b\}$。

若 $n$ 个元素中有 $n_1$ 个第一类、$n_2$ 个第二类，一直到 $n_k$ 个第 $k$ 类，且 $n_1 + \cdots + n_k = n$，则全排列的种数是：

$$\frac{n!}{n_1! \, n_2! \cdots n_k!}$$

分母除掉的是每一类内部重复的排列。比如 `aab` 的排列数是 $3!/(2!1!) = 3$，正好是 `aab`、`aba`、`baa`。

**多重集的组合**是另一回事：从 $k$ 类元素中一共选 $n$ 个，每类可以重复选，方案数是

$$\binom{n + k - 1}{k - 1}$$

这正是《离散与组合数学》里隔板法的公式。$n + k - 1$ 个位置里选 $k - 1$ 个放隔板，就得到 $k$ 组的分配方案。

## 圆排列

$n$ 个人围成一圈，有多少种坐法？

排成一排是 $n!$，但围成一圈时，整体旋转不算新方案。每一个圆排列在直线排列里被数了 $n$ 次，所以圆排列数是

$$(n-1)!$$

比如 4 个人围坐一桌，有 $3! = 6$ 种坐法。如果题目还区分顺时针和逆时针（比如项链翻转也算同一种），答案还要再除以 2。

## 错排列

$n$ 个元素的全排列中，所有元素都不在自己位置上的排列，叫**错排列**，记作 $D_n$。

前几项：$D_1 = 0$，$D_2 = 1$，$D_3 = 2$，$D_4 = 9$，$D_5 = 44$，$D_6 = 265$。

递推式是：

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

理解方式：先把第 1 个元素放到第 $k$ 个位置（有 $n-1$ 种选择）。此时看第 $k$ 个元素，如果它放到第 1 个位置，剩下 $n-2$ 个元素构成错排列，有 $D_{n-2}$ 种；如果它不放到第 1 个位置，那么「第 1 个位置不能放第 $k$ 个元素」和原来的约束等价，剩下 $n-1$ 个元素构成错排列，有 $D_{n-1}$ 种。

```cpp
long long D[25];
D[1] = 0; D[2] = 1;
for (int i = 3; i <= 20; i++) D[i] = (i - 1) * (D[i-1] + D[i-2]);

还有一个直接公式：$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$，当 $n$ 稍大时 $D_n$ 约等于 $n!/e$。

## 鸽巢原理

把 $n+1$ 只鸽子放进 $n$ 个笼子，至少有一个笼子里有两只以上鸽子。

推广形式：把 $n$ 个物体放进 $k$ 个盒子，至少有一个盒子里有不少于 $\lceil n/k \rceil$ 个物体。

竞赛里的用法通常是反着说：如果某种状态的数量超过了可能的种类数，就一定存在两个状态相同。比如 367 个人里一定有两个人同一天生日（一年最多 366 天）。

## 容斥原理

求若干个集合的并集大小时，不能直接把各个集合相加，因为重叠部分被多算了。容斥原理给出了修正方法。

两个集合：$|A \cup B| = |A| + |B| - |A \cap B|$。

三个集合：

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

一般形式是「奇加偶减」：所有单个的交，减去所有两两的交，加上所有三个的交，依此类推。

**例**：$1$ 到 $100$ 中，能被 2 或 3 或 5 整除的数有多少个？

- 单个：$\lfloor 100/2 \rfloor = 50$，$\lfloor 100/3 \rfloor = 33$，$\lfloor 100/5 \rfloor = 20$
- 两两：$\lfloor 100/6 \rfloor = 16$，$\lfloor 100/10 \rfloor = 10$，$\lfloor 100/15 \rfloor = 6$
- 三个：$\lfloor 100/30 \rfloor = 3$

$$(50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74$$

**容斥的经典应用：求 $1$ 到 $n$ 中与 $m$ 互质的数的个数。**

与 $m$ 不互质，等价于能被 $m$ 的某个质因数整除。把 $m$ 质因数分解，设质因数为 $p_1, \dots, p_k$，用容斥对「能被 $p_i$ 整除」这 $k$ 个集合求并集，再用 $n$ 减去它。

```cpp
// 枚举所有质因数的子集，用容斥统计不互质的个数
long long notCoprime = 0;
for (int mask = 1; mask < (1 << k); mask++) {
    long long prod = 1;
    int bits = 0;
    for (int i = 0; i < k; i++) {
        if (mask >> i & 1) {
            prod *= p[i];
            bits++;
        }
    }
    if (bits & 1) notCoprime += n / prod;
    else notCoprime -= n / prod;
}
long long coprime = n - notCoprime;

子集大小是 $2^k$，而 $m \le 10^{18}$ 的不同质因数最多 15 个，$2^{15}$ 完全可以接受。

## 卡特兰数

卡特兰数出现在大量「成对匹配」的计数问题里，通项是：

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}$$

前几项：$1, 1, 2, 5, 14, 42, 132, 429, 1430$。

它出现的场景：

| 场景 | 对应 $n$ |
| --- | --- |
| $n$ 对括号的合法匹配方案数 | $C_n$ |
| $n$ 个元素的出入栈序列数 | $C_n$ |
| $n$ 个节点的不同二叉树形态数 | $C_n$ |
| 凸 $n+2$ 边形的三角剖分方案数 | $C_n$ |
| 从 $(0,0)$ 走到 $(n,n)$ 不越过对角线的路径数 | $C_n$ |

在模质数意义下计算用阶乘和逆元：

```cpp
long long catalan(int n) {
    return C(2 * n, n) * fastPow(n + 1, MOD - 2, MOD) % MOD;
}

看到 `1 1 2 5 14 42` 就要反应过来是卡特兰数。

## 等价关系与等价类

这个概念在并查集和计数题里都有用。

集合上的一个**关系**如果同时满足下面三条，就叫等价关系：

- **自反性**：每个元素和自己有关系。
- **对称性**：$a$ 和 $b$ 有关系，则 $b$ 和 $a$ 也有关系。
- **传递性**：$a$ 和 $b$ 有关系、$b$ 和 $c$ 有关系，则 $a$ 和 $c$ 也有关系。

等价关系把集合划分成若干个互不相交的**等价类**，每个元素恰好属于一个等价类。并查集维护的就是等价类：`find(x) == find(y)` 说明 $x$ 和 $y$ 属于同一个类。

## 常见易错点

- 容斥的符号搞反。记住「奇加偶减」，单元素集合是加。
- 圆排列忘记除以 $n$。$n$ 个人围成一圈是 $(n-1)!$，不是 $n!$。
- 多重集排列忘记除重复类别的阶乘。
- 错排列和「至少有一个错位」不是一回事。错排列要求**所有**位置都错。
- 卡特兰数的公式里是 $\dfrac{1}{n+1}$，不是 $\dfrac{1}{n}$。
- 求互质个数时，容斥枚举的是质因数的子集，不是所有的因数子集。

## 初赛选择题精选

下面 8 道题全部选自历年 CSP-J/S 第一轮和 GESP 八级的真题，题干保持原样，选项做了重新编排。建议先自己算一遍，再看答案与解析。

### 题 1（2024 CSP-J1）

某公司有 10 名员工，分为 3 个部门：A 部门有 4 名员工，B 部门有 3 名员工，C 部门有 3 名员工。现需要从这 10 名员工中选出 4 名组成一个工作组，且每个部门至少有 1 人。问有多少种选择方式？

A. 120　　B. 126　　C. 150　　D. 210

**答案：B**

**解析**：选 4 个人、每个部门至少 1 人，说明必然恰好有一个部门出 2 人。按「哪个部门出 2 人」分三类：

- A 出 2 人：$\binom{4}{2}\binom{3}{1}\binom{3}{1} = 6 \times 3 \times 3 = 54$
- B 出 2 人：$\binom{3}{2}\binom{4}{1}\binom{3}{1} = 3 \times 4 \times 3 = 36$
- C 出 2 人：$\binom{3}{2}\binom{4}{1}\binom{3}{1} = 3 \times 4 \times 3 = 36$

合计 $54 + 36 + 36 = 126$。坑在分类：容易漏掉「哪个部门多出一个人」这一层，也算不出用组合数而不是排列数。

### 题 2（2023 CSP-J1）

一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合？

A. 1420　　B. 1540　　C. 1770　　D. 2200

**答案：A**

**解析**：正向分类要分三种情况，不如用排除法。从 22 个人里任选 3 人共 $\binom{22}{3} = 1540$ 种，减掉「一个女生都没有」的 $\binom{10}{3} = 120$ 种，得 $1540 - 120 = 1420$。

这就是本章容斥思想在初赛里的常见形式：**不符合条件的情况单一，就从总数里减掉**。

### 题 3（2024 CSP-J1）

有 5 个男生和 3 个女生站成一排，规定 3 个女生必须相邻，问有多少种不同的排列方式？

A. 720　　B. 1440　　C. 4320　　D. 5040

**答案：C**

**解析**：捆绑法。把 3 个女生捆成一个整体，和 5 个男生一共相当于 6 个「元素」，全排列 $6! = 720$ 种；女生内部还有 $3! = 6$ 种站法。$720 \times 6 = 4320$。

忘了乘内部排列数是这道题最常见的错法，会错选 A。

### 题 4（2020 CSP-J1）

有 5 个小朋友并排站成一列，其中有两个小朋友是双胞胎。如果要求这两个双胞胎必须相邻，共有多少种不同的排列方法？

A. 24　　B. 48　　C. 96　　D. 120

**答案：B**

**解析**：同样是捆绑法。双胞胎捆成一个整体，和剩下 3 个人共 4 个「元素」，全排列 $4! = 24$；双胞胎内部 $2! = 2$。$24 \times 2 = 48$。

### 题 5（GESP 八级，2025 年 9 月）

有 4 个红球、3 个蓝球和 2 个绿球排成一排（相同颜色的球视为完全相同），则不同的排列方案有多少种？

A. 630　　B. 1260　　C. 2520　　D. 362880

**答案：B**

**解析**：多重集排列。一共 9 个球，若全部不同是 $9!$；同色的内部排列是重复的，除掉：

$$\frac{9!}{4! \, 3! \, 2!} = \frac{362880}{24 \times 6 \times 2} = \frac{362880}{288} = 1260$$

$9! = 362880$ 是选 D 的原因，那是把它们全当成不同颜色算的结果。

### 题 6（GESP 八级，2026 年 3 月）

在杨辉三角中，从第 0 行开始计数，第 10 行的所有数之和为（ ）。

A. 512　　B. 1024　　C. 2048　　D. 4096

**答案：B**

**解析**：第 $n$ 行的数就是 $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$，由二项式定理令 $a = b = 1$，它们的和是 $2^n$。所以第 10 行之和是 $2^{10} = 1024$。

### 题 7（GESP 八级，2025 年 6 月）

有 3 位学长、3 位学姐排成一排拍照，要求男生不相邻、女生不相邻。共有多少种拍照方案？

A. 36　　B. 72　　C. 144　　D. 720

**答案：B**

**解析**：男女各 3 人，要求同类不相邻，只能是男女交替排列。开头可以是男生也可以是女生，2 种模式；每种模式下男女各自全排列，$3! \times 3! = 36$。所以一共 $2 \times 36 = 72$。

### 题 8（GESP 八级，2025 年 9 月）

小杨点奶茶时还差 5 元起送，于是决定加点小料。可选小料为：珍珠 1 元、椰果 2 元、奶冻 3 元、奶盖 4 元，每种最多点 1 份。共有多少种满足起送条件的点法？

A. 16　　B. 10　　C. 9　　D. 7

**答案：C**

**解析**：4 种小料每种选或不选，一共 $2^4 = 16$ 种组合。把总价不到 5 元的减掉：总价 0 元 1 种，1 元 1 种，2 元 1 种，3 元 2 种（珍珠+椰果、奶冻），4 元 2 种（奶盖、珍珠+奶冻），共 7 种。$16 - 7 = 9$。

看上去是枚举题，其实用的是「总数减反面」，和题 2 一个思路。

## 练习

### 练习 1：杨辉三角

在线评测练习：[P1283 杨辉三角](https://dailyup.run/tasks/367)

> 题库那题的范围是 $1 \le N < 10$，本题放宽到 $n \le 30$，需要用 `long long`。

#### 题目描述

输出杨辉三角的前 $n$ 行。

#### 输入格式

一个整数 $n$。

#### 输出格式

输出 $n$ 行，第 $i$ 行有 $i$ 个数，同一行内相邻数字用一个空格隔开。

#### 数据范围

- $1 \le n \le 30$。

#### 输入输出样例

输入

```
5

输出

```
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

#### 题目分析

用二维数组存一行一行的组合数，递推公式就是帕斯卡公式：

$$\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$$

边界是每行两端的 1。$n \le 30$ 时最大是 $\binom{30}{15} \approx 1.55 \times 10^8$，`int` 装得下，用 `long long` 更保险。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/combinatorics/index.md

### 练习 2：组合数取模

#### 题目描述

求 $\binom{n}{m} \bmod (10^9+7)$。

#### 输入格式

一行两个整数 $n$ 和 $m$。

#### 输出格式

输出一个整数，表示 $\binom{n}{m}$ 对 $10^9+7$ 取模的结果。

#### 数据范围

- $0 \le m \le n \le 10^6$。

#### 输入输出样例

输入

```
5 2

输出

```
10

#### 题目分析

$n \le 10^6$ 时杨辉三角的 $O(n^2)$ 递推已经不行了，要用阶乘和逆元：

$$\binom{n}{m} = n! \times (m!)^{-1} \times ((n-m)!)^{-1}$$

$10^9+7$ 是质数，由费马小定理 $a^{-1} \equiv a^{p-2} \pmod p$，用快速幂就能求出。具体推导见《数论进阶》。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/combinatorics/index.md

### 练习 3：与 m 互质的数的个数

#### 题目描述

求 $1$ 到 $n$ 中与 $m$ 互质的数的个数。

#### 输入格式

一行两个整数 $n$ 和 $m$。

#### 输出格式

输出一个整数，表示与 $m$ 互质的数的个数。

#### 数据范围

- $1 \le n \le 10^9$，$1 \le m \le 10^{18}$。

#### 输入输出样例

输入

```
10 6

输出

```
3

$1$ 到 $10$ 中与 $6$ 互质的是 $1$、$5$、$7$，共 3 个。

#### 题目分析

正面统计很难，转成反面统计：与 $m$ **不**互质，等价于能被 $m$ 的某个质因数整除。

把 $m$ 质因数分解，设质因数为 $p_1, \dots, p_k$，用**容斥**求「能被至少一个 $p_i$ 整除」的数的个数，再用 $n$ 减掉。

枚举所有非空子集，子集里的质因数相乘得到 $prod$，它被 $\lfloor n/prod \rfloor$ 个数整除；子集大小为奇数就加、偶数就减。

$m \le 10^{18}$ 的不同质因数最多 15 个，$2^{15}$ 个子集完全可以枚举。注意 $prod$ 可能超过 `long long`，中途要用 `__int128` 或者及时判断。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/combinatorics/index.md

### 练习 4：多重集排列

#### 题目描述

给定一个只含小写字母的字符串，求它所有不同排列的个数。比如 `aab` 的不同排列有 `aab`、`aba`、`baa`，共 3 个。

#### 输入格式

一行一个只含小写字母的字符串。

#### 输出格式

输出一个整数，表示不同排列的个数。

#### 数据范围

- 字符串长度不超过 20。

#### 输入输出样例

输入

```
aab

输出

```
3

#### 题目分析

直接套多重集排列公式：

$$\frac{n!}{c_1! \, c_2! \cdots c_{26}!}$$

其中 $c_i$ 是第 $i$ 个小写字母出现的次数。长度不超过 20，$20! \approx 2.43 \times 10^{18}$，`long long` 装得下。

如果长度再大一点，阶乘就会溢出，那时要用高精度，或者按题目要求取模并改用逆元。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/combinatorics/index.md

## 小结

组合数学的题看着杂，其实只有两条主线：**把问题翻译成「选与不选」**（组合数、隔板法、多重集排列），以及**把不符合条件的减掉**（容斥、错排列、排除法）。

- 二项式定理把展开系数和组合数连起来，$\sum_k \binom{n}{k} = 2^n$ 是最常用的变形。
- 多重集排列除以各类内部的阶乘；多重集组合就是隔板法。
- 圆排列是 $(n-1)!$，错排列满足 $D_n = (n-1)(D_{n-1}+D_{n-2})$。
- 容斥原理「奇加偶减」，处理「至少一个」「不互质」这类问题。
- 卡特兰数 $C_n = \binom{2n}{n}/(n+1)$，出现在括号匹配、出入栈、二叉树形态等成对计数的场景。

学完这一章，下面这些事应该能独立完成：

- 说出「分类用加法、分步用乘法」，并区分排列和组合。
- 用捆绑法、插空法处理相邻与不相邻的约束。
- 写出错排列和卡特兰数的递推式，并解释它们的推导思路。
- 用容斥求「$1$ 到 $n$ 中与 $m$ 互质的数的个数」。
- 拿到一道初赛选择题，能判断它考的是哪一种计数模型。

Source: https://cppguide.xyz/maths/combinatorics/index.mdx
