InoueMoby's Blog

前言：从“选人”说起

“从 10 个人里选 3 个组成小组，有多少种选法？” ——你可能学过这是 $\binom{10}{3} = 120$ 。但在实际题目中，问题往往没有这么直接：

“把 10 块相同的糖分给 3 个小朋友，每人至少 1 块，有多少种分法？“（隔板法）
“100 个人参加考试，至少有一个人满分的可能情况有多少种？“（容斥原理）
” $n$ 对括号有多少种合法的嵌套方式？“（Catalan 数）

这些问题看似各不相同，但有一个共同的核心：计数——数出满足条件的方案有多少种。

这篇笔记的目标，是帮你建立起一套完整的计数工具箱。我们从最基本的排列组合出发，解释公式背后的直觉（而不只是死记公式），然后逐步引入更强大的工具：

排列与组合 —— 基本计数原理，以及几个常用的恒等式
隔板法 —— 解决”把相同的东西分到若干组”这类问题
容斥原理 —— 解决”至少满足一个条件”的计数问题，核心思路是”加了又减、减了又加”
Catalan 数 —— 一类非常经典的计数问题，括号匹配、二叉树形态等都是它

每个工具都会讲清楚”什么时候用”和”为什么这样算是对的”。最后用一道综合题，把隔板法和容斥原理配合使用。

一、排列与组合的基本概念

1.1 排列

从 $n$ 个不同元素中选 $k$ 个排成一列：

P(n, k) = A_n^k = \frac{n!}{(n-k)!}

直觉：第一个位置有 $n$ 种选法，第二个 $n-1$ 种……第 $k$ 个 $n-k+1$ 种，连乘。

1.2 组合

从 $n$ 个不同元素中选 $k$ 个（不关心顺序）：

\binom{n}{k} = C_n^k = \frac{n!}{k! \cdot (n-k)!}

排列除以 $k!$ 消除顺序—— $k$ 个元素的排列有 $k!$ 种，但组合只算一种。

1.3 基本恒等式

恒等式	直觉
$\binom{n}{k} = \binom{n}{n-k}$	选 $k$ 个留下 = 选 $n-k$ 个去掉
$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$	杨辉三角递推：元素 $n$ 要么不选，要么选
$\sum_{k=0}^{n}\binom{n}{k} = 2^n$	每个元素选或不选，共 $2^n$ 个子集
$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$	用于递推计算，避免大数阶乘

二、多重集的排列与组合

2.1 多重集排列

$n$ 个物品中有 $n_1$ 个 A、 $n_2$ 个 B、……、 $n_k$ 个 K（ $\sum n_i = n$ ），排列数为：

\frac{n!}{n_1! \cdot n_2! \cdots n_k!}

直觉：先当所有物品不同（ $n!$ ），然后同类物品互换不产生新排列，除以各自的阶乘。

2.2 多重集组合

从 $k$ 种物品中选 $n$ 个（每种无限供应）：

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

这就是隔板法的直接结果——下一节展开。

三、隔板法（Stars and Bars）

3.1 问题

将 $n$ 个不可区分的物品放入 $k$ 个可区分的组，每组至少 1 个，有多少种分法？

3.2 方法

把 $n$ 个物品排成一排，中间有 $n - 1$ 个间隙。插入 $k - 1$ 个隔板，把物品分成 $k$ 组：

\underbrace{\star \star}_{\text{组 1}} \mid \underbrace{\star}_{\text{组 2}} \mid \underbrace{\star \star \star}_{\text{组 3}}

从 $n - 1$ 个间隙中选 $k - 1$ 个放隔板：

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

3.3 允许空组的变体

很多时候，“每组至少 1 个”这个约束太强了。比如”把 $n$ 个苹果分给 $k$ 个小朋友，有人可以不分”就属于允许空组的情况。

如果组可以为空，先给每组预放 1 个物品（共 $k$ 个），剩余 $n + k$ 个物品分到 $k$ 组、每组至少 1 个：

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

这就是多重集组合的公式来源。

什么时候用隔板法？ 当问题是”把若干相同的东西分到若干组”时。关键在于”相同”和”分组”——如果物品不同，就是子集/排列问题；如果分组有额外约束，可能需要容斥。

四、容斥原理

4.1 直觉

要计数”满足至少一个条件的对象”——直接加会多算（满足多个条件的被重复计数），减回来，加回来……交替进行。

两个集合：

|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|

一般形式：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \ne S \subseteq \{1,\dots,n\}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|

4.2 补集形式（竞赛更常用）

上面的形式是”至少满足一个”。但很多题目问的是”全都不满足”——比如”每个人都不去自己原来的位置”（错排问题）。用全集减去并集：

\left|\overline{A_1} \cap \cdots \cap \overline{A_n}\right| = |U| - \left|\bigcup_{i=1}^{n} A_i\right| = \sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

这里 $S = \emptyset$ 时贡献 $|U|$ （全集大小）。

4.3 二进制枚举子集

理论公式写出来了，但怎么编程实现？如果有 $n$ 个条件，就要枚举 $2^n$ 个子集——每个子集可以用一个 $n$ 位二进制数表示，第 $i$ 位是 1 就代表”第 $i$ 个条件成立”。

long long inclusion_exclusion(int n) {
    long long ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long long cnt = count_intersection(mask);  // 满足 mask 中所有条件的对象数
        if (__builtin_popcount(mask) % 2 == 0)
            ans += cnt;   // 偶数个条件：加
        else
            ans -= cnt;   // 奇数个条件：减
    }
    return ans;
}

4.4 一个经典例子：错排

$n$ 个元素的排列，每个元素都不在原位的排列数 $D_n$ 。

用容斥：全集 $n!$ ， $A_i$ = “第 $i$ 个元素在原位”。

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

$\binom{n}{k} \cdot (n-k)! = n!/k!$ 是任意固定 $k$ 个位置在原位的排列数。

五、Catalan 数

5.1 定义

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

前几项： $1, 1, 2, 5, 14, 42, 132, \dots$

5.2 等价问题

$C_n$ 同时是以下问题的答案：

问题	描述
括号序列	$n$ 对括号的合法匹配方式数
Dyck 路径	从 $(0,0)$ 到 $(2n, 0)$ ，每步 $+1$ 或 $-1$ ，始终 $\ge 0$ 的路径数
二叉树	$n$ 个节点的不同形态二叉树数
出栈序列	$1, 2, \dots, n$ 依次入栈，合法出栈序列数
多边形三角剖分	凸 $n+2$ 边形的不同三角剖分数

5.3 推导（折线反射法）

这个公式怎么来的？以括号问题为例： $n$ 个 ( 和 $n$ 个 ) 排成一列，合法条件是任意前缀中 ( 不少于 )。

先不管合法性，总共有 $\binom{2n}{n}$ 种排列。其中不合法的排列，某个位置 ) 第一次比 ( 多。关键技巧是反射：从这个位置开始，把所有括号取反（( ↔ )）。这会把 $n$ 个 ( 和 $n$ 个 ) 变成 $n+1$ 个 ( 和 $n-1$ 个 )。而且这个变换是双射（一一对应），所以：

不合法数 = $n+1$ 个 ( 和 $n-1$ 个 ) 的排列数 = $\binom{2n}{n-1}$ 。

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

5.4 递推关系

C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}

直觉：以二叉树为例，根的左子树 $i$ 个节点、右子树 $n - i$ 个节点，遍历所有 $i$ 求和。

long long catalan[100];
catalan[0] = 1;
for (int n = 0; n < 99; n++)
    for (int i = 0; i <= n; i++)
        catalan[n + 1] += catalan[i] * catalan[n - i];

或直接用组合数公式： $C_n = \binom{2n}{n} - \binom{2n}{n+1}$ 。

六、实战：方程的非负整数解

求方程 $x_1 + x_2 + \cdots + x_k = n$ 的非负整数解的个数，满足 $x_i \le a_i$ （ $0 \le n, k, a_i \le 10^5$ ）。

不加约束的解数是 $\binom{n+k-1}{k-1}$ （隔板法，允许空组）。加上上界约束 $x_i \le a_i$ 后，用容斥：

令 $A_i$ = " $x_i > a_i$ "（即 $x_i \ge a_i + 1$ ），求的是”不满足任何 $A_i$ “的对象数。

对于子集 $S \subseteq \{1, \dots, k\}$ ，令 $x_i' = x_i - (a_i + 1)$ （对 $i \in S$ ），转化为无约束方程，剩余总量 $n - \sum_{i \in S}(a_i + 1)$ ，解数 $\binom{n - \sum_{i \in S}(a_i+1) + k - 1}{k-1}$ （当剩余量非负时，否则为 0）。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 800006;

long long fact[MAXN], inv_fact[MAXN];

long long qpow(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; }
    return res;
}

void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n || n < 0) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(k);
    for (int i = 0; i < k; i++) scanf("%d", &a[i]);

    init(n + k);

    long long ans = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        long long rem = n;
        int bits = 0;
        for (int i = 0; i < k; i++)
            if (mask >> i & 1) { rem -= a[i] + 1; bits++; }
        long long cnt = C(rem + k - 1, k - 1);
        if (bits % 2 == 0) ans = (ans + cnt) % MOD;
        else               ans = (ans - cnt + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

解析：隔板法给出无约束解数，容斥处理上界约束。每个子集 $S$ 对应”强制这些变量超过上界”的情况，减去（或加回）。当 $k$ 较小（ $\le 20$ ）时 $2^k$ 枚举完全可行； $k$ 较大时需要更精细的方法（如生成函数）。

组合数学 — 计数、隔板与容斥

竞赛计数问题的核心工具：排列组合、隔板法、容斥原理