查看“︁双射法”︁的源代码

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

==例子==
=== 证明[[二项式系数]]的对称性质 ===
二次项系数具有一定的对称性：
:<math> {n \choose k} = {n \choose n-k}. </math>
'''证明'''：这个等式可以视为两个集合的元素个数。考虑以下''n''个元素的集合：<math>S =\{a_1, a_2, \cdots , a_n\}</math>，那么以下两个集合：
:<math>A =\{ C \subset S , \, |C| = k\}, \qquad \, B = \{ C \subset S , \, |C| = n - k\}</math> 
集合'''A'''的元素个数是<math> {n \choose k} </math>，集合'''B'''的元素个数是<math> {n \choose n-k} </math>. 现在构造一个从集合'''A'''到集合'''B'''的映射：
:<math>\begin{align}
f &: \, \, A \rightarrow B \\
&  \, \, \,  C \,  \, \,  \mapsto \, \, C_S^{c}
\end{align}</math>  
对'''A'''中的每个元素C（包含集合S中的<math>k</math>个元素），映射''f''把C映射到它在S中的补集（有S中的<math>n-k</math>个元素），因此在集合'''B'''中。可以验证，这个映射是双射。所以集合'''A'''的元素个数等于'''B'''的元素个数。也就是说 
:<math> {n \choose k} = {n \choose n-k}. </math> 

=== 证明两种分解方法数相等 ===
对一个大于2的自然数n，首先考虑将它写成若干个1和2的和，和项顺序不同认为是不同的写法，所有的方法数记作<math>a_n</math>，例如当n=4的时候，所有的写法是：
:<math>4 = 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1 = 2+2.</math>
所以<math>a_4 = 5</math>. 再考虑将它写成若干个大于等于2的[[自然数]]的和，和项顺序不同认为是不同的写法，所有的方法数记作<math>b_n</math>。则有<math>a_n = b_{n+2}.</math> 这个性质也可以用双射法证明：

'''证明'''：考虑集合
:<math>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\}</math>
:<math>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\}.</math> 
对集合<math> A_n </math>中的一个元素<math>(x_1, x_2, \cdots , x_m) </math>，假设其中有至少一个数为2，令<math>x_{i_1}=x_{i_2}, \cdots =x_{i_k}=2</math>（其中的下标<math>1 \leqslant i_1 < i_2 < \cdots < i_k \leqslant m</math>），其余的等于1。如果<math> i_k < m</math>，那么下面设<math>k+1</math>个数：
:<math>\begin{align}
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{align}
</math>  
如果<math> i_k = m</math>则<math>  y_{k+1}= 2 </math>。如果 <math>x_1 = x_2 = \cdots = x_m = 1 </math>，那么设<math> y_{1}= n+2 </math>。

那么由于各个y元素的和必然是<math> n+2 </math>，所以将<math>(x_1, x_2, \cdots , x_m) </math>映射到 <math>(y_1, y_2, \cdots , y_{k+1}) </math>的映射''f''是一个从<math> A_n </math>到<math> B_{n+2} </math>的映射。从构造方式可以看出，''f''是一个单射。

对于<math> B_{n+2} </math>中每一个元素<math>(y_1, y_2, \cdots , y_{k}) </math>，将其中的每一个<math> y_j </math>换成<math> y_j - 2 </math>个1和一个2，然后删去最后一个2，就得到<math> A_n </math>中的一个元素，所以''f''也是一个满射。

也就是说，''f''是一个双射。这就证明了 <math>a_n = b_{n+2}.</math>

==參見==
*其他[[組合技巧]]，如：
**[[算兩次]]
**[[抽屜原理]]

==参考==
* Loehr, Nicholas A. (2011).  [http://www.math.vt.edu/people/nloehr/bijbook.html Bijective Combinatorics]{{Webarchive|url=https://wayback.archive-it.org/all/20151023194824/http://www.math.vt.edu/people/nloehr/bijbook.html |date=2015-10-23 }}.  [http://www.crcpress.com CRC Press]{{Wayback|url=http://www.crcpress.com/ |date=20200407041251 }}. ISBN 143984884X, ISBN 978-1439848845.

[[Category:组合计数]]
[[Category:包含证明的条目]]
[[Category:证明]]