雙射法

雙射法是組合數學中的一種重要的證明方法，用來證明兩個有限集合A和B的元素數目相等。證明的思路是構造一個雙射映射f : A → B，於是根據雙射的性質，A和B的元素數目就是相等的。這個證明是構造法證明的一種。由於雙射法是給出具體的映射構造，而不是分別點算兩個集合，所以不需要知道兩個集合的元素個數。這種證明可以用於難以直接對兩個集合或其中一個集合進行計數的情況。此外，雙射法也可以用來計算一個集合（難以直接計算時），方法是將它映射到一個可以拆分或比較容易計算的集合。而作為構造性證明，雙射法用到的f也許可以用來更深刻地分析集合本身的性質。

例子[編輯]

證明二項式係數的對稱性質[編輯]

二次項係數具有一定的對稱性：

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

證明：這個等式可以視為兩個集合的元素個數。考慮以下n個元素的集合： $S=\{a_{1},a_{2},\cdots ,a_{n}\}$ ，那麼以下兩個集合：

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

集合A的元素個數是 ${n \choose k}$ ，集合B的元素個數是 ${n \choose n-k}$ . 現在構造一個從集合A到集合B的映射：

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

對A中的每個元素C（包含集合S中的 $k$ 個元素），映射f把C映射到它在S中的補集（有S中的 $n-k$ 個元素），因此在集合B中。可以驗證，這個映射是雙射。所以集合A的元素個數等於B的元素個數。也就是說

{n \choose k}={n \choose 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},\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\}

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\}.

對集合 $A_{n}$ 中的一個元素 $(x_{1},x_{2},\cdots ,x_{m})$ ，假設其中有至少一個數為2，令 $x_{i_{1}}=x_{i_{2}},\cdots =x_{i_{k}}=2$ （其中的下標 $1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant m$ ），其餘的等於1。如果 $i_{k}<m$ ，那麼下面設 $k+1$ 個數：