对应与配对

一句话

要数集合 $A$ ，如果能找到一个一一对应 $f : A \to B$ ，而 $B$ 好数，那么 $∣ A ∣ = ∣ B ∣$ 。

路径 ⟷ 向上的步的编号组成的子集, ∣ A ∣ = ∣ B ∣

配对是它的小兄弟：把对象两两配起来（ $k$ 与 $n - k$ ， $A$ 与 $∁ A$ ， $z$ 与 $\overset{z}{ˉ}$ ），每一对的和或积都相同，总和就一眼看出。对应与配对都要验证两件事：不重（单射）、不漏（满射）。

先猜后证

从 $(0, 0)$ 走到 $(4, 4)$ ，每步向右或向上一格，且路径从不走到直线 $y = x$ 的上方（可以碰到）。这样的路径有几条？

14

16

20

先选定答案，才能看到结论。

例：用翻折数“坏”路径（反射原理）

第 1 / 5 步

路径就是子集
一条从 $(0, 0)$ 到 $(4, 4)$ 的路径共 $8$ 步，由“哪 $4$ 步向上”完全决定。所以全部路径有 $(4 8) = 70$ 条。

$# 路径 = (4 8) = 70$
什么是坏路径
翻折
为什么一一对应
相减

第 1 站 · 映射与计数（卷二）

隔板法是最常用的对应：解 ↔ 隔板的位置。

例：x₁ + x₂ + x₃ + x₄ = 12 有多少组正整数解？

第 1 / 4 步

把数变成球
把 $12$ 写成 $12$ 个排成一行的球。一组解就是把这一行从左到右切成 $4$ 段，每段非空。

$\circ \circ \circ ∣ \circ \circ ∣ \circ \circ \circ \circ ∣ \circ \circ \circ \leftrightarrow (3, 2, 4, 3)$
切法就是选空隙
验证是一一对应
数

第 2 站 · 子集族（卷一）

${1, 2, \dots, n}$ 的 $2^{n}$ 个子集，把每个子集 $A$ 和它的补集 $∁ A$ 配成一对： $∣ A ∣ + ∣ ∁ A ∣ = n$ 。

一题多解

对 ${1, 2, \dots, n}$ 的所有子集 $A$ （含空集），求 $\sum ∣ A ∣$ 。

补集配对

$2^{n}$ 个子集恰好配成 $2^{n - 1}$ 对（ $A \neq = ∁ A$ 总成立），每对的元素个数之和为 $n$ ，所以 $\sum ∣ A ∣ = n \cdot 2^{n - 1}$ 。

代价一行；只需看出“每对的和都是 n”。

按大小分类

大小为 $k$ 的子集有 $(k n)$ 个， $\sum ∣ A ∣ = \sum_{k = 0}^{n} k (k n)$ 。用 $k (k n) = n (k - 1 n - 1)$ ，得 $n \sum_{k} (k - 1 n - 1) = n \cdot 2^{n - 1}$ 。

代价要算组合数恒等式。

第 3 站 · 数列求和（卷五）

高斯的首尾配对，在组合数求和里同样好用： $k$ 与 $n - k$ 配对，而 $(k n) = (n - k n)$ 。

例：求 S = Σ k·C(n, k)，k = 0, 1, …, n

第 1 / 3 步

倒着再写一遍
把 $k$ 换成 $n - k$ ，和不变；再利用 $(n - k n) = (k n)$ 。

$S = k = 0 \sum n (n - k) (k n)$
两式相加
结果

第 4 站 · 复数的共轭配对（卷四）

实系数多项式的虚根成对出现： $z$ 与 $\overset{z}{ˉ}$ 。每一对的和 $z + \overset{z}{ˉ} = 2 Re z$ 、积 $z \overset{z}{ˉ} = ∣ z ∣^{2}$ 都是实数。

例：x⁵ = 1 的四个虚根两两配对

第 1 / 3 步

列出根
$x^{5} = 1$ 的根是 $ω^{k}$ （ $k = 0, 1, 2, 3, 4$ ）， $ω = cos 7 2^{\circ} + i sin 7 2^{\circ}$ 。 $ω^{4} = \overset{ω}{ˉ}$ ， $ω^{3} = \overline{ω^{2}}$ 。

${ω, ω^{4}}, {ω^{2}, ω^{3}}$
每对配成实二次式
比较系数

练一练

练习 1基础

方程 $x_{1} + x_{2} + x_{3} + x_{4} = 10$ 有多少组正整数解？

练习 2基础

方程 $x + y + z = 8$ 有多少组非负整数解？

练习 3提高

对 ${1, 2, 3, 4, 5, 6}$ 的所有子集 $A$ ，求它们元素个数的总和 $\sum ∣ A ∣$ 。

练习 4挑战

由 $5$ 个“(”和 $5$ 个“)”组成的长度为 $10$ 的串中，括号能正确配对（从左往右读，任何时刻“)”的个数都不超过“(”的个数）的有多少个？

一句话

例：用翻折数“坏”路径（反射原理）

第 1 站 · 映射与计数（卷二）

例：x₁ + x₂ + x₃ + x₄ = 12 有多少组正整数解？

第 2 站 · 子集族（卷一）

补集配对

按大小分类

第 3 站 · 数列求和（卷五）

例：求 S = Σ k·C(n, k)，k = 0, 1, …, n

第 4 站 · 复数的共轭配对（卷四）

例：x⁵ = 1 的四个虚根两两配对

练一练

错误博物馆 · 本站展品

对应不是一一的

翻折时找错了线

这条线路经过的站