双射法

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

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

${\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.