双射法

维基百科,自由的百科全书
跳转至: 导航搜索

双射法组合数学中的一种重要的证明方法,用来证明两个有限集合AB的元素数目相等。证明的思路是构造一个双射映射f : AB,于是根据双射的性质,AB的元素数目就是相等的。这个证明是构造法证明的一种。由于双射法是给出具体的映射构造,而不是分别点算两个集合,所以不需要知道两个集合的元素个数。这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况。此外,双射法也可以用来计算一个集合(难以直接计算时),方法是将它映射到一个可以拆分或比较容易计算的集合。而作为构造性证明,双射法用到的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{align}
f &: \, \, A \rightarrow B \\
&  \, \, \,  C \,  \, \,  \mapsto \, \, C_S^{c}
\end{align}

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=5的时候,所有的写法是:

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), \, \, \, m \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个数:

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

如果 i_k = m  y_{k+1}= 2 。如果 x_1 = x_2 = \cdots = x_m = 1 ,那么设 y_{1}= n+2 。那么由于各个y元素的和必然是 n+2 ,所以将(x_1, x_2, \cdots , x_m) 映射到 (y_1, y_2, \cdots , y_{k+1}) 的映射f是一个从 A_n  B_{n+2} 的映射。从构造方式可以看出,f是一个单射。对于 B_{n+2} 中每一个元素(y_1, y_2, \cdots , y_{k}) ,将中的每一个 y_j 换成 y_j - 2 个1和一个2,然后删去最后一个2,就得到 A_n 中的一个元素,所以f也是一个满射。也就是说,f是一个双射。这就证明了 a_n = b_{n+2}.

参考[编辑]