双射法

双射法是组合数学中的一种重要的证明方法，用来证明两个有限集合A和B的元素数目相等。证明的思路是构造一个双射映射f : A → B，于是根据双射的性质，A和B的元素数目就是相等的。这个证明是构造法证明的一种。由于双射法是给出具体的映射构造，而不是分别点算两个集合，所以不需要知道两个集合的元素个数。这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况。此外，双射法也可以用来计算一个集合（难以直接计算时），方法是将它映射到一个可以拆分或比较容易计算的集合。而作为构造性证明，双射法用到的f也许可以用来更深刻地分析集合本身的性质。

例子

证明二项式系数的对称性质

二次项系数具有一定的对称性：

(\binom{n}{k}) = (\binom{n}{n - k}) .

证明：这个等式可以视为两个集合的元素个数。考虑以下n个元素的集合： $S = {a_{1}, a_{2}, \dots, a_{n}}$ ，那么以下两个集合：

A = {C \subset S, | C | = k}, B = {C \subset S, | C | = n - k}

集合A的元素个数是 $(\binom{n}{k})$ ，集合B的元素个数是 $(\binom{n}{n - k})$ . 现在构造一个从集合A到集合B的映射：

\begin{matrix} f & : A \to B \\ C \mapsto C_{S}^{c} \end{matrix}

对A中的每个元素C（包含集合S中的 $k$ 个元素），映射f把C映射到它在S中的补集（有S中的 $n - k$ 个元素），因此在集合B中。可以验证，这个映射是双射。所以集合A的元素个数等于B的元素个数。也就是说

(\binom{n}{k}) = (\binom{n}{n - k}) .

证明两种分解方法数相等

对一个大于2的自然数n，首先考虑将它写成若干个1和2的和，和项顺序不同认为是不同的写法，所有的方法数记作 $a_{n}$ ，例如当n=4的时候，所有的写法是：

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2 .

所以 $a_{4} = 5$ . 再考虑将它写成若干个大于等于2的自然数的和，和项顺序不同认为是不同的写法，所有的方法数记作 $b_{n}$ 。则有 $a_{n} = b_{n + 2} .$ 这个性质也可以用双射法证明：

证明：考虑集合

A_{n} = {(x_{1}, x_{2}, \dots, x_{m}), m ⩾ 1, \forall 1 ⩽ j ⩽ m, x_{j} \in {1, 2}, x_{1} + x_{2} + \dots + x_{m} = n}

B_{n + 2} = {(y_{1}, y_{2}, \dots, y_{k}), k ⩾ 1, \forall 1 ⩽ j ⩽ k, y_{j} ⩾ 2, y_{1} + y_{2} + \dots + y_{k} = n + 2} .

对集合 $A_{n}$ 中的一个元素 $(x_{1}, x_{2}, \dots, x_{m})$ ，假设其中有至少一个数为2，令 $x_{i_{1}} = x_{i_{2}}, \dots = x_{i_{k}} = 2$ （其中的下标 $1 ⩽ i_{1} < i_{2} < \dots < i_{k} ⩽ m$ ），其余的等于1。如果 $i_{k} < m$ ，那么下面设 $k + 1$ 个数：

\begin{matrix} y_{1} & = x_{1} + \dots + x_{i_{1}}, \\ y_{2} & = x_{i_{1} + 1} + \dots + x_{i_{2}}, \\ ⋮ ⋮ \\ y_{k} & = x_{i_{k - 1} + 1} + \dots + x_{i_{k}}, \\ y_{k + 1} & = x_{i_{k} + 1} + \dots + x_{m} + 2 . \end{matrix}

如果 $i_{k} = m$ 则 $y_{k + 1} = 2$ 。如果 $x_{1} = x_{2} = \dots = x_{m} = 1$ ，那么设 $y_{1} = n + 2$ 。

那么由于各个y元素的和必然是 $n + 2$ ，所以将 $(x_{1}, x_{2}, \dots, x_{m})$ 映射到 $(y_{1}, y_{2}, \dots, y_{k + 1})$ 的映射f是一个从 $A_{n}$ 到 $B_{n + 2}$ 的映射。从构造方式可以看出，f是一个单射。

对于 $B_{n + 2}$ 中每一个元素 $(y_{1}, y_{2}, \dots, y_{k})$ ，将其中的每一个 $y_{j}$ 换成 $y_{j} - 2$ 个1和一个2，然后删去最后一个2，就得到 $A_{n}$ 中的一个元素，所以f也是一个满射。

也就是说，f是一个双射。这就证明了 $a_{n} = b_{n + 2} .$

參見

其他組合技巧，如：
- 算兩次
- 抽屜原理

参考

Loehr, Nicholas A. (2011). Bijective Combinatorics Template:Webarchive. CRC Press Template:Wayback. ISBN 143984884X, ISBN 978-1439848845.

双射法

目录

例子

证明二项式系数的对称性质

证明两种分解方法数相等

參見

参考

导航菜单

双射法

例子

证明二项式系数的对称性质

证明两种分解方法数相等

參見

参考

导航菜单

搜索