双射法

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

例子

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

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

${\displaystyle {n \choose k}={n \choose n-k}.}$

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

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

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

${\displaystyle {\begin{aligned}f&:\,\,A\rightarrow B\\&\,\,\,C\,\,\,\mapsto \,\,C_{S}^{c}\end{aligned}}}$

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

${\displaystyle {n \choose k}={n \choose n-k}.}$

证明两种分解方法数相等

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

${\displaystyle 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2.}$

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

证明：考虑集合

${\displaystyle A_{n}=\{(x_{1},x_{2},\cdots ,x_{m}),\,\,\,m\geqslant 1,\,\,\forall 1\leqslant j\leqslant m,x_{j}\in \{1,2\},\,\,x_{1}+x_{2}+\cdots +x_{m}=n\}}$

${\displaystyle B_{n+2}=\{(y_{1},y_{2},\cdots ,y_{k}),\,\,\,k\geqslant 1,\,\,\forall 1\leqslant j\leqslant k,y_{j}\geqslant 2,\,\,y_{1}+y_{2}+\cdots +y_{k}=n+2\}.}$

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

${\displaystyle {\begin{aligned}y_{1}&=x_{1}+\cdots +x_{i_{1}},\\y_{2}&=x_{i_{1}+1}+\cdots +x_{i_{2}},\\&\vdots \quad \quad \quad \vdots \\y_{k}&=x_{i_{k-1}+1}+\cdots +x_{i_{k}},\\y_{k+1}&=x_{i_{k}+1}+\cdots +x_{m}+2.\end{aligned}}}$

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

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

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

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

参见

• 其他组合技巧，如：
  • 算两次
  • 抽屉原理

参考

• Loehr, Nicholas A. (2011). Bijective CombinatoricsArchive-It的存档，存档日期2015-10-23. CRC Press（页面存档备份，存于互联网档案馆）. ISBN 143984884X, ISBN 978-1439848845.