雙射法

雙射法是組合數學中的一種重要的證明方法，用來證明兩個有限集合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.