离散数学计数原理笔记

计数原理专题笔记 / Counting Principles Notes#

主线说明 / Main line:
本笔记按离散数学教材常见顺序整理计数原理：有限集合基数规则、基本计数法、排列组合、二项式与多项式、容斥、鸽巢、星棒法、多重集合、错排、满射与 Stirling 数、递推、生成函数、Catalan 数和生日问题。
This note follows the standard textbook path: finite cardinality rules, basic counting rules, permutations and combinations, binomial and multinomial coefficients, inclusion-exclusion, pigeonhole principle, stars and bars, multisets, derangements, onto functions and Stirling numbers, recurrences, generating functions, Catalan numbers, and the birthday principle.

0. 计数题总策略 / General Strategy for Counting#

0.1 计数题的本质 / What Counting Really Means#

核心思想 / Core idea

计数不是“套公式”，而是先明确被数对象是什么，再找到一种不会漏、不会重的编码方式。

Counting is not just applying formulas. The first step is to identify the objects being counted, then encode them in a way that neither misses nor repeats objects.

标准问题 / Standard questions

1. 被数对象是什么？/ What are the objects?
2. 顺序是否重要？/ Does order matter?
3. 是否允许重复？/ Are repetitions allowed?
4. 是否有禁止条件？/ Are there forbidden cases?
5. 是否每个对象被数了多次？/ Is each object counted multiple times?
6. 是否能与另一个更容易数的集合建立双射？/ Can we build a bijection to an easier set?

0.2 常用方法表 / Method Checklist#

1. 有限集合与基数 / Finite Sets and Cardinality#

1.1 定义 / Definitions#

Finite set / 有限集合

若集合 $A$ 与 $\{1,2,\ldots,n\}$ 存在双射，则称 $A$ 是有限集合，且 $|A|=n$。

A set $A$ is finite if there is a bijection between $A$ and $\{1,2,\ldots,n\}$. In that case, $|A|=n$.

Cardinality / 基数

$|A|$ 表示集合 $A$ 中元素的个数。

$|A|$ denotes the number of elements in $A$.

1.2 双射原则 / Bijection Principle#

Theorem / 定理

若有限集合 $A$ 与 $B$ 之间存在双射 $f:A\to B$，则：

Proof / 证明

双射意味着每个 $A$ 中元素恰好对应一个 $B$ 中元素，并且每个 $B$ 中元素恰好被一个 $A$ 中元素对应。因此两个集合元素数量相同。

A bijection pairs every element of $A$ with exactly one element of $B$, and every element of $B$ is paired with exactly one element of $A$. Therefore the two sets have the same size.

Use / 怎么用

很多计数题可以转化为“数另一个集合”。例如长度为 $n$ 的二进制串与集合 $\{1,\ldots,n\}$ 的子集一一对应：第 $i$ 位为 $1$ 表示选中 $i$。

1.3 有限集合基数公式 / Cardinality Formulas#

Basic rules / 基本规则

若 $A,B$ 有限，则：

若 $A\cap B=\varnothing$，则：

笛卡尔积满足：

幂集满足：

Proof of power set formula / 幂集公式证明

设 $|A|=n$。构造 $A$ 的一个子集时，每个元素有两个选择：选入或不选入。因此一共有：

个子集。

To form a subset, each element has two choices: included or not included. By the product rule, there are $2^n$ subsets.

Example / 例题

一个集合 $A$ 有 $8$ 个元素，则它有多少个子集？有多少个非空真子集？

Solution / 解法

子集总数为：

非空真子集排除空集和全集：

2. 基本计数原则 / Basic Counting Principles#

2.1 加法原则 / Sum Rule#

Theorem / 定理

若选择可以分成互不重叠的 $k$ 类 $A_1,A_2,\ldots,A_k$，则总数为：

Proof / 证明

因为这些情况两两不相交，每个对象只出现在一个类别中，所以把每类数量相加不会重复计数，也不会漏计。

Since the cases are disjoint, every object appears in exactly one case. Adding the sizes counts each object once.

Example / 例题

从 $3$ 本数学书和 $5$ 本计算机书中选一本书，有多少种选法？

Solution / 解法

选数学书有 $3$ 种，选计算机书有 $5$ 种，两类互斥，所以：

2.2 乘法原则 / Product Rule#

Theorem / 定理

若一个过程分成 $k$ 步，第 $i$ 步有 $n_i$ 种选择，则总数为：

更一般地，如果第 $i$ 步的选择数依赖于前面选择，也可以把每条分支的选择数相乘，再对分支求和。

Proof / 证明

两步情形中，每个第一步选择都能搭配 $n_2$ 个第二步选择，所以有 $n_1n_2$ 个有序对。多步情形由归纳法得到。

For two steps, each first choice can be paired with $n_2$ second choices, giving $n_1n_2$ ordered pairs. The general case follows by induction.

Example / 例题

一个密码由 $2$ 个大写字母后接 $3$ 个数字组成，允许重复。共有多少个密码？

Solution / 解法

每个字母位置有 $26$ 种，每个数字位置有 $10$ 种：

2.3 减法原则与补集 / Subtraction Rule and Complements#

Theorem / 定理

若总集合为 $U$，坏集合为 $B$，好集合为 $G=U-B$，则：

Proof / 证明

$U$ 被分成互不相交的好对象和坏对象，所以：

移项得结论。

Example / 例题

长度为 $6$ 的二进制串中，至少有一个 $1$ 的有多少个？

Solution / 解法

总数为 $2^6$。没有 $1$ 的只有 $000000$ 一个，所以：

2.4 除法原则 / Division Rule#

Theorem / 定理

若某种计数方法把每个目标对象恰好数了 $d$ 次，则真实数量为：

Proof / 证明

设真实对象数为 $N$。若每个对象恰好产生 $d$ 个表示，则表示总数为 $dN$，故：

Example / 例题

$n$ 个不同的人围成一圈，旋转视为同一种座法，有多少种圆排列？

Solution / 解法

线性排列有 $n!$ 种。每个圆排列从 $n$ 个位置切开都得到不同线性排列，所以每个圆排列被数了 $n$ 次：

3. 排列 / Permutations#

3.1 排列定义 / Definition of Permutation#

Permutation / 排列

从 $n$ 个不同对象中按顺序选出 $r$ 个，称为 $r$-permutation。

An $r$-permutation of $n$ distinct objects is an ordered selection of $r$ objects from the $n$ objects.

3.2 无重复排列 / Permutations Without Repetition#

Theorem / 定理

从 $n$ 个不同对象中选出并排列 $r$ 个，数量为：

Proof / 证明

第 $1$ 个位置有 $n$ 种选择，第 $2$ 个位置有 $n-1$ 种，依此类推，第 $r$ 个位置有 $n-r+1$ 种。由乘法原则：

补上剩余因子可得：

Example / 例题

从 $10$ 名学生中选出班长、副班长、学习委员各一人，不能兼任，有多少种方式？

Solution / 解法

三个职位不同，所以顺序重要：

3.3 可重复序列 / Sequences With Repetition#

Theorem / 定理

从 $n$ 个对象中构造长度为 $r$ 的有序序列，允许重复，数量为：

Proof / 证明

每个位置都有 $n$ 种选择，共 $r$ 个位置，由乘法原则得 $n^r$。

Example / 例题

长度为 $8$ 的小写英文字母串有多少个？

Solution / 解法

每个位置 $26$ 种：

3.4 有重复元素的排列 / Permutations of Multisets#

Theorem / 定理

若一个多重集合共有 $n$ 个元素，其中第 $i$ 类重复 $n_i$ 次，且：

则不同排列数为：

Proof / 证明

先把所有相同元素临时标号，使它们都变成不同对象。此时共有 $n!$ 个排列。
但第 $i$ 类内部的 $n_i!$ 种标号交换不会改变最终字符串，因此每个真实排列被数了：

次。由除法原则得到公式。

Example / 例题

单词 MISSISSIPPI 的不同排列数是多少？

Solution / 解法

字母数量为：

所以：

3.5 圆排列 / Circular Permutations#

Theorem / 定理

$n$ 个不同对象围成一圈，若旋转视为相同，则圆排列数为：

Proof / 证明

普通线性排列有 $n!$ 种。每个圆排列可以从 $n$ 个不同位置切开成为线性排列，因此被重复计数 $n$ 次。故：

Remark / 备注

若翻转也视为相同，例如项链问题，则当 $n\ge3$ 时通常还要再除以 $2$，得到：

但若有重复颜色或特殊对称，需要更高级的 Burnside 引理，本笔记不展开。

4. 组合 / Combinations#

4.1 组合定义 / Definition of Combination#

Combination / 组合

从 $n$ 个不同对象中无顺序地选出 $r$ 个，称为 $r$-combination。

An $r$-combination of $n$ distinct objects is an unordered selection of $r$ objects.

4.2 组合公式 / Combination Formula#

Theorem / 定理

从 $n$ 个不同对象中选 $r$ 个，数量为：

Proof / 证明

先数有序选择，有：

每个无序 $r$ 元集合可以排列成 $r!$ 个有序序列，所以：

Example / 例题

从 $12$ 人中选 $5$ 人组成委员会，有多少种？

Solution / 解法

委员会内部无职位差别，所以：

4.3 组合数对称性 / Symmetry of Binomial Coefficients#

Theorem / 定理

Proof / 证明

从 $n$ 个元素中选 $r$ 个，等价于决定哪 $n-r$ 个不选。映射：

是从 $r$ 元子集到 $(n-r)$ 元子集的双射。

Use / 怎么用

当 $r$ 接近 $n$ 时，用对称性可简化计算，例如：

4.4 先选再排 / Choose Then Arrange#

Pattern / 常见模型

若先选出若干对象，再给它们安排不同角色，则常见形式为：

Example / 例题

从 $8$ 人中选 $3$ 人站成一排，有多少种？

Solution / 解法一 / Method 1

直接用排列：

Solution / 解法二 / Method 2

先选 $3$ 人，再排列：

两者相等。

5. 二项式系数与组合恒等式 / Binomial Coefficients and Combinatorial Identities#

5.1 Pascal 恒等式 / Pascal's Identity#

Theorem / 定理

Proof / 组合证明

从 $n$ 个元素中选 $r$ 个。固定一个特殊元素 $x$。

• 不选 $x$：从其余 $n-1$ 个中选 $r$ 个，有 $\binom{n-1}{r}$ 种。
• 选 $x$：还需从其余 $n-1$ 个中选 $r-1$ 个，有 $\binom{n-1}{r-1}$ 种。

两类互斥且覆盖所有选择，所以由加法原则得到结论。

Use / 怎么用

Pascal 恒等式是组合数递推、杨辉三角和很多归纳证明的基础。

5.2 子集总数恒等式 / Subset Identity#

Theorem / 定理

Proof / 组合证明

右边 $2^n$ 数的是 $n$ 元集合的所有子集。左边按子集大小分类：大小为 $r$ 的子集有 $\binom{n}{r}$ 个，对 $r=0,\ldots,n$ 求和。

Example / 例题

一个 $10$ 元集合有多少个偶数大小的子集？

Solution / 解法

偶数大小子集数为：

由：

和：

可知偶数项和奇数项相等，均为：

5.3 Vandermonde 恒等式 / Vandermonde's Identity#

Theorem / 定理

Proof / 组合证明

从 $m+n$ 个人中选 $r$ 人。把人分成两组，第一组 $m$ 人，第二组 $n$ 人。
若从第一组选 $k$ 人，则必须从第二组选 $r-k$ 人，有：

种。对所有 $k$ 求和得左边。直接从 $m+n$ 人中选 $r$ 人得右边。

Use / 怎么用

看到形如：

的卷积，就优先想到 Vandermonde。

5.4 曲棍球杆恒等式 / Hockey-Stick Identity#

Theorem / 定理

Proof / 组合证明

从集合 $\{0,1,2,\ldots,n\}$ 中选 $r+1$ 个数。按最大元素分类。
若最大元素是 $k$，其余 $r$ 个必须从 $0,1,\ldots,k-1$ 中选，所以有：

种。对 $k=r,\ldots,n$ 求和得左边。直接选 $r+1$ 个数得右边。

5.5 带权计数恒等式 / Weighted Counting Identity#

Theorem / 定理

Proof / 组合证明

数“一个委员会和一个队长”的方式，其中委员会非空且队长在委员会中。

左边：先选大小为 $r$ 的委员会，有 $\binom{n}{r}$ 种，再从其中选队长，有 $r$ 种。

右边：先选队长，有 $n$ 种；其余 $n-1$ 人每人可选入或不选入委员会，有 $2^{n-1}$ 种。

所以：

6. 二项式定理与多项式定理 / Binomial and Multinomial Theorems#

6.1 二项式定理 / Binomial Theorem#

Theorem / 定理

Proof / 证明

展开：

时，每个括号中选择 $x$ 或 $y$。若要得到 $x^{n-k}y^k$，需要从 $n$ 个括号中选 $k$ 个贡献 $y$，其余贡献 $x$。这样的选择有 $\binom{n}{k}$ 种。

Example / 例题

求 $(2x-3)^5$ 中 $x^3$ 的系数。

Solution / 解法

写成 $(2x+(-3))^5$。要得到 $x^3$，需要选 $2x$ 三次，选 $-3$ 两次：

系数为：

6.2 多项式定理 / Multinomial Theorem#

Theorem / 定理

Proof / 证明

展开时共有 $n$ 个括号。要得到：

必须有 $k_i$ 个括号选择 $x_i$。选择这些位置的方式数为：

Example / 例题

求 $(x+y+z)^{10}$ 中 $x^2y^3z^5$ 的系数。

Solution / 解法

由多项式定理，系数为：

7. 容斥原理 / Inclusion-Exclusion Principle#

7.1 两集合容斥 / Two-Set Inclusion-Exclusion#

Theorem / 定理

Proof / 证明

$|A|+|B|$ 中，属于 $A\cap B$ 的元素被数了两次，因此需要减去一次。

In $|A|+|B|$, every element in $A\cap B$ is counted twice, so we subtract it once.

Example / 例题

$1$ 到 $100$ 中能被 $2$ 或 $5$ 整除的数有多少个？

Solution / 解法

设：

则：

所以：

7.2 一般容斥 / General Inclusion-Exclusion#

Theorem / 定理

对有限集合 $A_1,A_2,\ldots,A_n$：

Proof / 证明

考虑某个元素 $x$ 恰好属于 $r$ 个集合。右边对它的贡献为：

由：

可得：

所以每个属于并集的元素被数一次，不属于并集的元素被数零次。

Use / 怎么用

容斥特别适合“至少一个条件发生”或“排除若干坏事件”。

7.3 容斥计数补集 / Counting by Excluding Bad Events#

Theorem / 定理

若全集为 $U$，坏事件集合为 $A_1,\ldots,A_n$，则没有坏事件发生的对象数为：

展开得：

其中 $J=\varnothing$ 时交集理解为 $U$。

Example / 例题

长度为 $5$ 的十进制数字串中，每个数字 $0,1,2$ 都至少出现一次的有多少个？

Solution / 解法

全集 $U$ 为所有长度 $5$ 数字串：

设 $A_i$ 表示数字 $i$ 没有出现，$i=0,1,2$。要求没有任何 $A_i$ 发生。

单个数字缺失：每个有 $9^5$ 种，共 $3\cdot9^5$。
两个指定数字缺失：每个有 $8^5$ 种，共 $\binom{3}{2}8^5$。
三个都缺失：有 $7^5$ 种。

答案：

8. 鸽巢原理 / Pigeonhole Principle#

8.1 基本鸽巢原理 / Basic Pigeonhole Principle#

Theorem / 定理

若把 $n+1$ 个对象放入 $n$ 个盒子，则至少有一个盒子含有至少 $2$ 个对象。

If $n+1$ objects are placed into $n$ boxes, at least one box contains at least two objects.

Proof / 反证法

假设每个盒子至多含有 $1$ 个对象，则 $n$ 个盒子最多容纳 $n$ 个对象，与有 $n+1$ 个对象矛盾。

8.2 广义鸽巢原理 / Generalized Pigeonhole Principle#

Theorem / 定理

若把 $N$ 个对象放入 $k$ 个盒子，则至少有一个盒子含有至少：

个对象。

Proof / 证明

若每个盒子最多有 $\left\lceil N/k\right\rceil-1$ 个对象，则总对象数最多为：

矛盾。

Example / 例题

任取 $13$ 个人，证明至少有两个人出生月份相同。

Solution / 解法

对象是 $13$ 个人，盒子是 $12$ 个月。由鸽巢原理，至少一个月份含有至少：

个人。

8.3 鸽巢构造技巧 / How to Design Boxes#

Key idea / 核心

鸽巢题的难点不是公式，而是“盒子”怎么设计。

Common boxes / 常见盒子

• 余数类 / residue classes
• 子集大小 / sizes of subsets
• 首字母、生日月份、颜色 / labels such as initials, months, colors
• 图中的邻居数或边颜色 / degrees or edge colors in graphs
• 区间分段 / intervals

Example / 例题

任取 $n+1$ 个整数，证明其中有两个整数对 $n$ 同余。

Proof / 证明

对象是 $n+1$ 个整数。盒子是模 $n$ 的 $n$ 个余数类：

由鸽巢原理，至少两个整数落入同一个余数类，所以它们模 $n$ 同余。

8.4 Ramsey 例子 / Ramsey Example#

Theorem / 定理

也就是说，任意 $6$ 个人中，必有 $3$ 个人两两认识，或 $3$ 个人两两不认识。

In any group of six people, there are either three mutual acquaintances or three mutual strangers.

Proof / 证明

把 $6$ 个人看成完全图 $K_6$ 的顶点。两人认识的边染红色，不认识的边染蓝色。

固定一个顶点 $v$。它与其余 $5$ 个顶点相连，有 $5$ 条边。由鸽巢原理，其中至少 $3$ 条边同色。

不妨设 $v$ 到 $a,b,c$ 的边都是红色。若 $a,b,c$ 中有一条红边，例如 $ab$，则 $v,a,b$ 构成红三角形。若 $a,b,c$ 之间没有红边，则三条边全是蓝边，$a,b,c$ 构成蓝三角形。

所以 $K_6$ 的任意红蓝染色都含有单色三角形。

9. 星棒法与整数解 / Stars and Bars#

9.1 非负整数解 / Nonnegative Integer Solutions#

Theorem / 定理

方程：

的非负整数解个数为：

Proof / 证明

把 $n$ 个相同物品看成 $n$ 个星星，用 $k-1$ 根隔板分成 $k$ 组。
例如 $k=4,n=7$ 时：

表示：

总共有 $n+k-1$ 个位置，其中选 $k-1$ 个放隔板，所以：

9.2 正整数解 / Positive Integer Solutions#

Theorem / 定理

方程：

的正整数解个数为：

Proof / 证明

令：

则：

由非负整数解公式，解数为：

Example / 例题

把 $12$ 个相同糖果分给 $4$ 个孩子，每个孩子至少 $1$ 个，有多少种？

Solution / 解法

求：

答案：

9.3 可重复组合 / Combinations With Repetition#

Theorem / 定理

从 $n$ 类对象中选 $r$ 个，允许重复且不看顺序，数量为：

Proof / 证明

设 $x_i$ 表示第 $i$ 类对象选了多少个，则：

由星棒法得到公式。

Example / 例题

从 $5$ 种口味冰淇淋中买 $8$ 个球，允许重复，顺序不重要，有多少种买法？

Solution / 解法

这是从 $5$ 类中可重复选 $8$ 个：

9.4 有上界的星棒法 / Stars and Bars With Upper Bounds#

Example / 例题

求非负整数解数量：

Solution / 解法

先忽略上界，非负解总数为：

设坏事件 $A_i$ 表示 $x_i\ge6$。若 $x_1\ge6$，令 $y_1=x_1-6\ge0$，则：

解数为：

三个变量对称，单个坏事件总数为 $3\cdot15$。两个变量同时至少 $6$ 不可能，因为总和只有 $10$。所以答案：

General method / 通用方法

有上界 $x_i\le u_i$ 时，先忽略上界，再对 $x_i\ge u_i+1$ 的坏事件做容斥。

10. 分配问题 / Distribution Problems#

10.1 四种基本分配模型 / Four Basic Distribution Models#

其中 $r$ 是物品数，$n$ 是盒子数。

10.2 不同球到不同盒 / Distinct Balls Into Distinct Boxes#

Theorem / 定理

$r$ 个不同球放入 $n$ 个不同盒子，允许空盒，数量为：

Proof / 证明

每个球独立选择一个盒子，有 $n$ 种选择，共 $r$ 个球，所以 $n^r$。

10.3 相同球到不同盒 / Identical Balls Into Distinct Boxes#

Theorem / 定理

$r$ 个相同球放入 $n$ 个不同盒子，允许空盒，数量为：

Proof / 证明

设 $x_i$ 是第 $i$ 个盒子中的球数，则：

由星棒法得结论。

11. 错排 / Derangements#

11.1 定义 / Definition#

Derangement / 错排

$n$ 个元素的一个排列中，若没有任何元素留在原位置，则称为错排。

A derangement is a permutation with no fixed points.

设 $D_n$ 表示 $n$ 个元素的错排数。

11.2 错排公式 / Derangement Formula#

Theorem / 定理

Proof / 容斥证明

全集 $U$ 是所有 $n$ 个元素的排列：

令 $A_i$ 表示第 $i$ 个元素固定不动。错排就是没有任何 $A_i$ 发生。

若指定 $k$ 个元素固定不动，其余 $n-k$ 个元素任意排列，有：

种。选择这 $k$ 个固定元素有 $\binom{n}{k}$ 种。由容斥：

化简：

所以：

11.3 错排递推 / Derangement Recurrence#

Theorem / 定理

Proof / 证明

考虑元素 $1$ 被放到位置 $j$，其中 $j\ne1$，有 $n-1$ 种选择。现在看位置 $1$ 上放什么。

若元素 $j$ 放到位置 $1$，则 $1$ 与 $j$ 交换，剩下 $n-2$ 个元素必须错排，有 $D_{n-2}$ 种。

若元素 $j$ 不放到位置 $1$，则可以把位置 $j$ 视为元素 $1$ 的“禁止位置”已经处理掉，剩下结构等价于 $n-1$ 个元素的错排，有 $D_{n-1}$ 种。

所以：

Example / 例题

四个人随机拿四顶帽子，没人拿到自己的帽子有多少种？

Solution / 解法

12. 满射函数与第二类 Stirling 数 / Onto Functions and Stirling Numbers of the Second Kind#

12.1 满射函数计数 / Counting Onto Functions#

Theorem / 定理

从 $n$ 元集合到 $k$ 元集合的满射数量为：

Proof / 容斥证明

所有函数共有 $k^n$ 个。令 $A_j$ 表示陪域中第 $j$ 个元素没有被命中。满射就是没有任何 $A_j$ 发生。

若指定 $i$ 个陪域元素没被命中，则每个定义域元素只能映到剩下的 $k-i$ 个元素，有：

个函数。选择这 $i$ 个没被命中的元素有 $\binom{k}{i}$ 种。由容斥得到：

Example / 例题

从 $5$ 个学生到 $3$ 个项目组的分配中，每个项目组至少有一个学生，有多少种？

Solution / 解法

学生不同，项目组不同，每个组非空。这是从 $5$ 元集合到 $3$ 元集合的满射：

12.2 第二类 Stirling 数 / Stirling Numbers of the Second Kind#

Definition / 定义

$S(n,k)$ 表示把 $n$ 个有标号元素分成 $k$ 个非空无标号块的数量。

$S(n,k)$ is the number of ways to partition $n$ labeled elements into $k$ nonempty unlabeled blocks.

12.3 Stirling 递推 / Stirling Recurrence#

Theorem / 定理

边界条件：

Proof / 证明

观察元素 $n$。

第一种情况：元素 $n$ 单独成一块。剩下 $n-1$ 个元素分成 $k-1$ 个非空块，有 $S(n-1,k-1)$ 种。

第二种情况：元素 $n$ 加入已有的某个块。先把前 $n-1$ 个元素分成 $k$ 块，有 $S(n-1,k)$ 种；再选择 $n$ 加入哪一块，有 $k$ 种。因此有 $kS(n-1,k)$ 种。

两种情况互斥且完整，所以递推成立。

12.4 满射与 Stirling 数关系 / Relation Between Onto Functions and Stirling Numbers#

Theorem / 定理

从 $n$ 元集合到 $k$ 元集合的满射数为：

Proof / 证明

一个满射会把定义域分成 $k$ 个非空原像块。若忽略陪域标签，就是一个 $k$ 块划分，有 $S(n,k)$ 种。
然后把这 $k$ 个无标号块分配给 $k$ 个有标号陪域元素，有 $k!$ 种。

因此满射数为：

结合容斥公式可得：

13. 递推计数 / Counting With Recurrences#

13.1 递推关系定义 / Definition of Recurrence Relation#

Recurrence relation / 递推关系

递推关系用前面若干项定义后续项。例如：

A recurrence relation defines later terms using earlier terms.

Initial conditions / 初始条件

递推必须配合初始条件才能确定唯一序列。例如 Fibonacci 数：

13.2 用递推建模 / Modeling by Recurrences#

Strategy / 策略

1. 定义 $a_n$ 是什么。/ Define what $a_n$ counts.
2. 按第一个位置、最后一步、是否包含某元素等分类。/ Split by first position, last step, or whether a special element is used.
3. 把大问题化成小问题。/ Reduce the problem to smaller cases.
4. 写初始条件。/ Give initial conditions.

Example / 例题：无连续 1 的二进制串

设 $a_n$ 为长度 $n$ 且没有连续 $1$ 的二进制串数量。求递推式。

Solution / 解法

按最后一位分类。

若最后一位是 $0$，前 $n-1$ 位可以是任意合法串，有 $a_{n-1}$ 种。

若最后一位是 $1$，倒数第二位必须是 $0$，前 $n-2$ 位可以是任意合法串，有 $a_{n-2}$ 种。

所以：

初始条件：

13.3 一阶线性递推 / First-Order Linear Recurrences#

Standard form / 标准形式

若 $c\ne1$，则展开得：

若 $c=1$，则：

Example / 例题

解：

Solution / 解法

展开：

13.4 常系数齐次线性递推 / Linear Homogeneous Recurrences#

Theorem / 定理

若：

尝试解 $a_n=r^n$，得到特征方程：

若有两个不同根 $r_1,r_2$，则通解为：

Proof idea / 证明思路

代入 $a_n=r^n$：

当 $r\ne0$ 时除以 $r^{n-2}$，得到特征方程。线性递推的线性组合仍是解，所以不同根对应的解可线性组合。常数由初始条件确定。

Example / 例题

解：

Solution / 解法

特征方程：

即：

通解：

由 $a_0=2$ 得：

由 $a_1=3$ 得：

解得 $\beta=1,\alpha=1$，所以：

13.5 计数递推与闭式公式 / Recurrence Versus Closed Form#

Use / 怎么用

递推本身通常已经是有效答案，尤其在算法计数或动态规划中。若题目要求 explicit formula / closed form，才进一步求闭式。

Counting recurrences are often already useful answers, especially in algorithms and dynamic programming. Find a closed form only when needed.

14. 生成函数 / Generating Functions#

14.1 普通生成函数定义 / Ordinary Generating Function#

Definition / 定义

序列 $a_0,a_1,a_2,\ldots$ 的普通生成函数是：

The ordinary generating function of a sequence is the formal power series whose coefficient of $x^n$ is $a_n$.

14.2 基本生成函数 / Basic Generating Functions#

常用公式：

14.3 生成函数用于限制计数 / Generating Functions as Translators#

Rule / 规则

若变量 $x_i$ 可取集合 $S_i$ 中的值，则对应因子为：

所有变量共同限制的解数等于乘积中目标次数项的系数。

Example / 例题

求方程：

的解数，其中：

Solution / 解法

对应生成函数：

答案是其中 $x^{10}$ 的系数：

由于最高次数为 $2+4+4=10$，要得到 $10$ 只能选 $x^2,x^4,x^4$，所以答案为 $1$。

14.4 生成函数解星棒法 / Stars and Bars by Generating Functions#

Example / 例题

求非负整数解：

Solution / 解法

每个变量可取 $0,1,2,\ldots$，对应因子：

总生成函数：

答案为：

这与星棒法一致。

14.5 生成函数解递推 / Solving Recurrences by Generating Functions#

Example / 例题：Fibonacci 生成函数

设：

令：

对递推乘以 $x^n$ 并对 $n\ge2$ 求和：

左边为：

右边为：

所以：

整理：

Use / 怎么用

生成函数把递推变成代数方程，把计数限制变成系数提取。

Generating functions turn recurrences into algebraic equations and counting restrictions into coefficient extraction.

15. Catalan 数 / Catalan Numbers#

15.1 定义 / Definition#

Catalan numbers / Catalan 数

等价形式：

前几项为：

15.2 Catalan 数计数对象 / Objects Counted by Catalan Numbers#

$C_n$ 常计数以下对象：

• $n$ 对括号的合法匹配方式 / valid parenthesizations of $n$ pairs of parentheses
• 从 $(0,0)$ 到 $(n,n)$ 且不越过对角线 $y=x$ 的路径 / lattice paths that do not cross the diagonal
• $n+1$ 个叶子的满二叉树形状 / full binary trees with $n+1$ leaves
• 凸 $(n+2)$ 边形的三角剖分 / triangulations of a convex $(n+2)$-gon

15.3 反射法证明 / Reflection Principle Proof#

Theorem / 定理

从 $(0,0)$ 到 $(n,n)$，每步向右 $R$ 或向上 $U$，且从不越过直线 $y=x$ 的路径数为：

Proof / 证明

所有从 $(0,0)$ 到 $(n,n)$ 的路径共有：

条，因为要在 $2n$ 步中选 $n$ 步向上。

坏路径是第一次到达 $y=x+1$ 的路径。对坏路径中从起点到第一次越过对角线的部分做反射，把 $R$ 和 $U$ 互换。这样得到一条从 $(-1,1)$ 到 $(n,n)$ 的路径，等价于从 $(0,0)$ 到 $(n+1,n-1)$ 的路径。

坏路径数为：

所以好路径数为：

化简：

于是：

Example / 例题

$4$ 对括号有多少种合法匹配方式？

Solution / 解法

答案是：

15.4 Catalan 递推 / Catalan Recurrence#

Theorem / 定理

Proof / 证明

考虑一个合法括号串。第一个左括号与某个右括号匹配。设其内部有 $i$ 对括号，外部剩下 $n-i$ 对括号。内部可以用 $C_i$ 种方式合法匹配，外部可以用 $C_{n-i}$ 种方式合法匹配。对所有 $i$ 求和：

16. 概率中的计数：生日问题 / Counting in Probability: Birthday Principle#

16.1 等可能模型 / Equally Likely Model#

Rule / 规则

若样本空间中每个结果等可能，则：

计数概率题的第一步是写清样本空间 $\Omega$。

16.2 生日问题 / Birthday Problem#

Problem / 问题

假设一年有 $365$ 天且生日均匀独立。$n$ 个人中至少两人生日相同的概率是多少？

Solution / 解法

用补集。总样本数为：

所有人生日互不相同的方式数为：

所以至少两人生日相同的概率为：

当 $n=23$ 时，这个概率已经超过 $1/2$。

Connection / 联系

生日问题是“补集 + 排列 + 概率”的典型组合。

17. 证明模板 / Proof Templates#

17.1 组合证明模板 / Combinatorial Proof Template#

Template / 模板

要证明两个表达式相等：

可以这样写：

1. 定义一个集合 $S$。/ Define a set $S$.
2. 说明左边 $L$ 是按一种方式计数 $S$。/ Explain that $L$ counts $S$ in one way.
3. 说明右边 $R$ 是按另一种方式计数 $S$。/ Explain that $R$ counts $S$ in another way.
4. 因为两边都数同一个集合，所以 $L=R$。/ Since both sides count the same set, $L=R$.

Example / 例题

证明：

Proof / 证明

令 $S$ 为 $n$ 元集合的所有子集。右边 $2^n$ 通过“每个元素选或不选”计数 $S$。左边按子集大小分类计数 $S$。因此两边相等。

17.2 容斥证明模板 / Inclusion-Exclusion Template#

Template / 模板

1. 写全集 $U$。/ Define the universe $U$.
2. 写坏事件 $A_i$。/ Define bad events $A_i$.
3. 判断要求的是 $|A_1\cup\cdots\cup A_n|$ 还是 $|U-(A_1\cup\cdots\cup A_n)|$。/ Decide whether to count the union or its complement.
4. 计算单交、双交、三交等。/ Count intersections.
5. 交替加减。/ Alternate signs.

17.3 递推建模模板 / Recurrence Modeling Template#

Template / 模板

1. 设 $a_n$ 为目标数量。/ Let $a_n$ be the desired number.
2. 按最后一步或第一个元素分类。/ Classify by the last step or first element.
3. 把每类化成较小规模的 $a_i$。/ Express each case using smaller $a_i$.
4. 写递推式。/ Write the recurrence.
5. 写初始条件。/ State initial conditions.

17.4 生成函数模板 / Generating Function Template#

Template / 模板

1. 每个变量限制翻译成一个多项式或幂级数。/ Translate each variable restriction into a polynomial or power series.
2. 把因子相乘。/ Multiply the factors.
3. 取目标次数系数。/ Extract the target coefficient.

符号：

表示 $A(x)$ 中 $x^n$ 的系数。

18. 常见易错点 / Common Pitfalls#

18.1 加法原则误用 / Misusing the Sum Rule#

加法原则要求情况互斥。如果情况不互斥，要用容斥。

The sum rule requires disjoint cases. If cases overlap, use inclusion-exclusion.

18.2 排列组合混淆 / Confusing Permutations and Combinations#

看“角色是否不同”而不是只看“人是否不同”。
班长、副班长不同，是排列；委员会成员无职位，是组合。

Look for whether roles are distinct. President and vice president are ordered roles; committee members are not.

18.3 重复是否允许 / Whether Repetition Is Allowed#

密码、字符串、函数通常允许重复；抽牌、选人通常不允许重复。

Passwords, strings, and functions usually allow repetition. Drawing cards or choosing people usually does not.

18.4 除法原则的前提 / Condition for Division Rule#

只有每个目标对象被数了相同次数 $d$，才能直接除以 $d$。

You may divide by $d$ only when every target object is counted exactly $d$ times.

18.5 容斥中的交集 / Intersections in Inclusion-Exclusion#

双交不是把两个单独数量相乘，而是同时满足两个条件的对象数量。

An intersection count is not usually the product of two separate counts. It counts objects satisfying both conditions.

19. 公式索引 / Formula Index#

19.1 基本计数 / Basic Counting#

19.2 排列组合 / Permutations and Combinations#

19.3 二项式 / Binomial#

19.4 容斥 / Inclusion-Exclusion#

19.5 星棒法 / Stars and Bars#

19.6 错排、满射、Stirling / Derangements, Onto Functions, Stirling#

19.7 Catalan / Catalan#

20. 中英术语表 / Bilingual Glossary#