Stage 2：二项式系数、恒等式与双计数

欢迎进入 Stage 2。先说一句和你刚交那份卷子直接相关的话：你的计算肌肉已经很强，缺的是”把理由写到纸上”——而 Stage 2 的核心恰好是一门强制你写论证的功夫（双计数）。一个组合证明，如果你不写出”这个集合是什么、两种数法分别是什么”，它就根本不成立，没有”只写数值蒙混”的退路。所以这一站对你不是新负担，而是用你最擅长的’数数’去练你最欠缺的’写证明’。

按 Stage 1 的习惯，先给整站的内核。Stage 2 看着是一堆恒等式，但全是三条思想的产物：

$(k n)$ 是一个计数对象（ $1, \dots, n$ 的 $k$ 元子集数），不是死公式——任何恒等式都能”翻译回计数”。
双计数是证恒等式的主武器：设一个集合 $S$ ，用两种方式数 $∣ S ∣$ ，两数必相等。
同一组系数横跨三个世界：代数（二项式展开的系数）、计数（子集数）、数论（模 $p$ 的行为由 Lucas / Kummer 决定）。

一、二项式定理：它本身就是一个组合论证

$(x + y)^{n} = \sum_{k = 0}^{n} (k n) x^{k} y^{, n - k} .$

为什么（这就是一个组合证明，请体会）： 把左边写成 $n$ 个因子相乘 $(x + y) (x + y) \dots (x + y)$ 。展开时，每个因子要么贡献 $x$ 、要么贡献 $y$ 。要凑出 $x^{k} y^{n - k}$ ，就得在 $n$ 个因子里选 $k$ 个出 $x$ （其余出 $y$ ），选法有 $(k n)$ 种。所以 $x^{k} y^{n - k}$ 前的系数就是 $(k n)$ 。∎

换句话说：二项式系数之所以叫”系数”，是因为它本来就在数”选哪些因子出 $x$ “的方案数。 这是代数与计数的第一座桥。

多项式定理（推广）： 同理， $(x_{1} + \dots + x_{m})^{n} = \sum_{a_{1} + \dots + a_{m} = n} (a _{1} , \dots , a _{m} n) \times x_{1}^{a_{1}} \dots x_{m}^{a_{m}}, (a _{1} , \dots , a _{m} n) = \frac{n !}{a _{1} ! \dots a _{m} !} .$ 右边那个多项式系数，正是你 Stage 1 学过的多重集排列数——又一处回扣。

二、杨辉三角与帕斯卡法则

$111413126131411$

每个数等于它”肩上”两数之和，这就是帕斯卡法则： $(k n) = (k - 1 n - 1) + (k n - 1) .$

组合证明（第一次完整示范）：

设集合： $S = 1, \dots, n$ 的全体 $k$ 元子集， $∣ S ∣ = (k n)$ 。
盯住元素 $n$ ：每个 $k$ 子集要么含 $n$ （再从前 $n - 1$ 个里选 $k - 1$ 个， $(k - 1 n - 1)$ 种），要么不含 $n$ （从前 $n - 1$ 个里选 $k$ 个， $(k n - 1)$ 种）。
这两类互斥且穷尽（加法原理），所以 $(k n) = (k - 1 n - 1) + (k n - 1)$ 。∎

注意这跟你 Stage 1 §十做的分类讨论是同一套，只是落在了一个恒等式上。

三、★ 核心武器：组合论证 / 双计数（本站的灵魂，重点）

原理一句话：如果两个表达式在数同一个有限集 $S$ 的元素个数，它们必然相等。

写组合证明必须写全这三步（这正是你习惯性跳过的）：

设集合：明确一个有限集 $S$ 。

数法 A：用第一种方式数 $∣ S ∣$ → 得到等式的一边。

数法 B：用第二种方式数 $∣ S ∣$ → 得到等式的另一边。

两次数的是同一个 $S$ ，故两边相等。∎

下面用四个经典范例把套路打透。请把这四种”数法”当作工具记住。

范例 1（逐元素法）： $k = 0 \sum n (k n) = 2^{n}$ 。设 $S = 1, \dots, n$ 的全体子集。数法 A（按大小分类）：大小为 $k$ 的子集有 $(k n)$ 个，求和得 $\sum_{k} (k n)$ 。数法 B（逐元素决定）：每个元素”选或不选”共 2 种， $n$ 个元素得 $2^{n}$ 。同一个 $S$ ，故相等。∎ —— 这就是你 Stage 1 §十一例 2 的思路，现在它有了正式名字。

范例 2（主席法，最经典）： $k (k n) = n (k - 1 n - 1)$ 。设 $S =$ 从 $n$ 人中选一个 $k$ 人委员会、并在其中指定一名主席的全部方案 $(委员会, 主席)$ 。数法 A（先委员会后主席）：选 $k$ 人 $(k n)$ 种，再从中选主席 $k$ 种 → $k (k n)$ 。数法 B（先主席后其余）：先选主席 $n$ 种，再从剩下 $n - 1$ 人选 $k - 1$ 名委员 $(k - 1 n - 1)$ 种 → $n (k - 1 n - 1)$ 。故相等。∎ 验证 $n = 5, k = 2$ ： $2 (2 5) = 20 = 5 (1 4) = 20$ 。✓ “主席法”务必练到条件反射——它是双计数最高频的招。

范例 3（按颜色分类）——范德蒙德恒等式： $k \sum (k m) (q - k p) = (q m + p)$ 。设 $S =$ 一个有 $m$ 个红球、 $p$ 个蓝球（共 $m + p$ 个）的集合的全体 $q$ 元子集。数法 A（直接）： $(q m + p)$ 。数法 B（按取了几个红分类）：取 $k$ 个红有 $(k m)$ 种、配 $q - k$ 个蓝有 $(q - k p)$ 种，对 $k$ 求和。故相等。∎ 验证 $m = 3, p = 2, q = 2$ ： $(0 3) (2 2) + (1 3) (1 2) + (2 3) (0 2) = 1 + 6 + 3 = 10 = (2 5)$ 。✓

范例 4（按最大元素分类）——曲棍球棒 / 朱世杰恒等式： $i = r \sum n (r i) = (r + 1 n + 1)$ 。设 $S = 1, \dots, n + 1$ 的全体 $(r + 1)$ 元子集。数法 A（直接）： $(r + 1 n + 1)$ 。数法 B（按最大元素分类）：若最大元素是 $i + 1$ ，则其余 $r$ 个取自 $1, \dots, i$ ，有 $(r i)$ 种； $i$ 从 $r$ 到 $n$ 求和。故相等。∎ 验证 $r = 2, n = 4$ ： $(2 2) + (2 3) + (2 4) = 1 + 3 + 6 = 10 = (3 5)$ 。✓ 遇到”一串组合数连续求和等于一个组合数”，先想”按最大元素分类”。

另外两个一眼能看出的（留给你自己用双射 / 双计数补证，对应 Stage 1）：对称 $(k n) = (n - k n)$ （取补集的双射），交错和 $\sum_{k} (- 1)^{k} (k n) = 0$ （你在 P5(b) 用 toggle 对合证过——那就是它的组合证明！）。

四、二项式系数的数论面（编程支线的”数学化”）

同一个 $(k n)$ ，它模一个质数 $p$ 的行为由两条漂亮定理刻画。

Lucas 定理： 设 $p$ 为质数，把 $n, k$ 写成 $p$ 进制 $n = (n_{t} \dots n_{0})_{p}, k = (k_{t} \dots k_{0})_{p}$ ，则 $(k n) \equiv \prod_{i = 0}^{t} (k _{i} n _{i}) (mod p) .$ 直觉：模 $p$ 下，二项式系数”各位互不干扰”，整体等于各 $p$ 进制位上小二项式系数的乘积。推论：只要某一位 $k_{i} > n_{i}$ ，那位 $(k _{i} n _{i}) = 0$ ，于是整个 $(k n) \equiv 0 (mod p)$ 。例（非零，看清机制）： $(4 13) mod 3$ 。 $13 = (111)_{3}, 4 = (011)_{3}$ ，故 $(4 13) \equiv (1 1) (1 1) (0 1) = 1 (mod 3)$ 。验证 $(4 13) = 715 = 3 \cdot 238 + 1 \equiv 1$ 。✓ 例（出现 0）： $(3 10) mod 2$ 。 $10 = (1010)_{2}, 3 = (0011)_{2}$ ；最低位 $(1 0) = 0$ ，故 $(3 10) \equiv 0 (mod 2)$ 。验证 $(3 10) = 120$ 是偶数。✓

Kummer 定理： $v_{p} ((n m + n))$ （即 $(n m + n)$ 里含 $p$ 的幂次） $=$ 在 $p$ 进制下做加法 $m + n$ 时的进位次数。直觉：把” $(k n)$ 里藏了多少个 $p$ “变成纯粹的”数进位”游戏——和你数论里的 Legendre / $v_{p}$ 公式同源。例： $(3 6) = 20$ ，看 $p = 2$ 。写成 $(3 3 + 3)$ ，二进制 $1 1_{2} + 1 1_{2}$ ：最低位 $1 + 1 = 0$ 进 1，次位 $1 + 1 + 1 = 1$ 进 1，得 $11 0_{2} = 6$ ，共 2 次进位。故 $v_{2} (3 6) = 2$ ，即 $4 ∣ 20$ 而 $8 ∤ 20$ 。验证 $20 = 4 \cdot 5$ 。✓

一个把组合与费马连起来的小引理： 对质数 $p$ 与 $0 < k < p$ ，有 $(k p) \equiv 0 (mod p)$ 。证：由刚才的主席法恒等式 $k (k p) = p (k - 1 p - 1)$ ，右边含因子 $p$ ，故 $p ∣ k (k p)$ ；而 $0 < k < p$ 时 $p ∤ k$ ，所以 $p ∣ (k p)$ 。∎ 推论（新生之梦 / Freshman’s dream）： $(x + y)^{p} \equiv x^{p} + y^{p} (mod p)$ ——也是费马小定理组合证法的起点。

注意这一节漂亮在哪：上一节刚证的”主席法”，转身就成了数论引理的钥匙。这就是”同一组系数横跨三个世界”。

五、组合数系与阶乘数系：把”双射”接到整数上（进阶延伸）

组合数系 (combinatorial number system)： 固定阶 $k$ ，每个非负整数 $N$ 有唯一表示 $N = (k c _{k}) + (k - 1 c _{k - 1}) + \dots + (1 c _{1}), c_{k} > c_{k - 1} > \dots > c_{1} \geq 0,$ 贪心求法：每步取使 $(j c) \leq$ 当前余值的最大 $c$ 。例（ $k = 3, N = 5$ ）：最大 $(3 c _{3}) \leq 5$ 是 $(3 4) = 4$ （因 $(3 5) = 10 > 5$ ），余 $1$ ；最大 $(2 c _{2}) \leq 1$ 是 $(2 2) = 1$ ，余 $0$ ； $(1 c _{1}) = 0 \Rightarrow c_{1} = 0$ 。于是 $5 = (3 4) + (2 2) + (1 0)$ ，对应 3 元子集 $4, 2, 0$ 。意义：这是”非负整数”与” $k$ 元子集”之间的一个双射——竞赛编程里”排名 / 反排名 (ranking / unranking)“的数学本质就是它。和你 Stage 1 学的双射是同一条线，只是这次双射的另一端是整数。

阶乘数系 (factoradic)： 把整数按 $1!, 2!, 3!, \dots$ 的混合进制展开，对应到排列的 Lehmer 码（每个排列 ↔ 一个唯一整数）。它是”组合 ↔ 整数”双射在排列上的版本。（先知道有这回事即可。）

这一站的统一主线（请内化）

$(k n)$ 是计数对象（ $k$ 元子集数）——一切恒等式都能翻译回”数集合”。
双计数是证恒等式的主武器：设 $S$ ，两种数法数 $∣ S ∣$ ，必相等。写证明要写全”设集合 / 数法 A / 数法 B”三步。
同一组系数横跨代数、计数、数论三界：二项式定理给它代数面，子集计数给它组合面，Lucas / Kummer 给它数论面。

我的观点（直说）

你刚交的卷子证明了一件事：你不是不会写证明，而是习惯性不写——P5(b) 你无师自通地写出了 toggle 对合，那就是一个完整的组合 / 双射证明。Stage 2 的任务，就是把”我能讲清楚为什么”那种状态，从一道题复制到每一个恒等式上。所以我的硬建议是：本站每学一个恒等式，逼自己用三步模板手写一遍组合证明，哪怕你早会代数约分。代数证法证明”它对”，组合证法证明”它为什么对”——USAMO 要的是后者。

四个范例里，**“主席法”和”按最大元素分类”**是 90% 双计数题的套路来源，优先练到条件反射。

置信度与注意事项

置信度：约 0.95。 全部数值例子我逐一核对过（ $(4 13) = 715 \equiv 1 (mod 3)$ 、 $(3 6) = 20$ 含 $2^{2}$ 、范德蒙德与曲棍球棒实例均为 $10$ 、组合数系 $5 = (3 4) + (2 2)$ 等）。

注意事项：

Lucas / Kummer 我按”数学原理”讲（讲为什么、怎么手算），没写代码——符合我们把编程支线数学化的约定。若你要可运行的取模实现，告诉我即可（届时会附镜像安装命令，例如 pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple）。本回答不含 Python 代码，故未触发安装说明。
§五（组合数系 / factoradic）是本站的进阶延伸，USAMO 正赛很少直接考；放进来是为补全”组合 ↔ 整数的双射”这条线，别让它挤占双计数的主练时间。
多项式定理、 $q$ -类比等只点到为止；想深入某块单独说。

准备好后我就出 Stage 2 试卷。延续你上一份的反馈，这次我可以把评分栏改成更硬的口径——“组合证明没写全’设集合 / 数法 A / 数法 B’三步就扣分”——强制你把刚说的习惯练出来。要这个硬口径，还是先按常规出？

My Vault

Explorer

2 二项式