Skip to content

组合数学进阶

容斥原理、卡特兰数、错排列、圆排列、鸽巢原理与二项式定理。

Updated View as Markdown

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

本章的知识点与 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} 种。

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 减去它。

// 枚举所有质因数的子集,用容斥统计不互质的个数
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

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

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 杨辉三角

题库那题的范围是 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 更保险。

参考代码

练习 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,用快速幂就能求出。具体推导见《数论进阶》。

参考代码

练习 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 或者及时判断。

参考代码

练习 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 装得下。

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

参考代码

小结

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

  • 二项式定理把展开系数和组合数连起来,\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 互质的数的个数」。
  • 拿到一道初赛选择题,能判断它考的是哪一种计数模型。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close