双射法是组合数学中的一种重要的证明方法,用来证明两个有限集合A和B的元素数目相等。证明的思路是构造一个双射映射f : A → B,于是根据双射的性质,A和B的元素数目就是相等的。这个证明是构造法证明的一种。由于双射法是给出具体的映射构造,而不是分别点算两个集合,所以不需要知道两个集合的元素个数。这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况。此外,双射法也可以用来计算一个集合(难以直接计算时),方法是将它映射到一个可以拆分或比较容易计算的集合。而作为构造性证明,双射法用到的f也许可以用来更深刻地分析集合本身的性质。
双射法, 是组合数学中的一种重要的证明方法, 用来证明两个有限集合a和b的元素数目相等, 证明的思路是构造一个双射映射f, 于是根据双射的性质, a和b的元素数目就是相等的, 这个证明是构造法证明的一种, 由于是给出具体的映射构造, 而不是分别点算两个集合, 所以不需要知道两个集合的元素个数, 这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况, 此外, 也可以用来计算一个集合, 难以直接计算时, 方法是将它映射到一个可以拆分或比较容易计算的集合, 而作为构造性证明, 用到的f也许可以用来更深刻地分析集. 双射法是组合数学中的一种重要的证明方法 用来证明两个有限集合A和B的元素数目相等 证明的思路是构造一个双射映射f A B 于是根据双射的性质 A和B的元素数目就是相等的 这个证明是构造法证明的一种 由于双射法是给出具体的映射构造 而不是分别点算两个集合 所以不需要知道两个集合的元素个数 这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况 此外 双射法也可以用来计算一个集合 难以直接计算时 方法是将它映射到一个可以拆分或比较容易计算的集合 而作为构造性证明 双射法用到的f也许可以用来更深刻地分析集合本身的性质 目录 1 例子 1 1 证明二项式系数的对称性质 1 2 证明两种分解方法数相等 2 參見 3 参考例子 编辑证明二项式系数的对称性质 编辑 二次项系数具有一定的对称性 n k n n k displaystyle n choose k n choose n k nbsp 证明 这个等式可以视为两个集合的元素个数 考虑以下n个元素的集合 S a 1 a 2 a n displaystyle S a 1 a 2 cdots a n nbsp 那么以下两个集合 A C S C k B C S C n k displaystyle A C subset S C k qquad B C subset S C n k nbsp 集合A的元素个数是 n k displaystyle n choose k nbsp 集合B的元素个数是 n n k displaystyle n choose n k nbsp 现在构造一个从集合A到集合B的映射 f A B C C S c displaystyle begin aligned f amp A rightarrow B amp C mapsto C S c end aligned nbsp 对A中的每个元素C 包含集合S中的k displaystyle k nbsp 个元素 映射f把C映射到它在S中的补集 有S中的n k displaystyle n k nbsp 个元素 因此在集合B中 可以验证 这个映射是双射 所以集合A的元素个数等于B的元素个数 也就是说 n k n n k displaystyle n choose k n choose n k nbsp 证明两种分解方法数相等 编辑 对一个大于2的自然数n 首先考虑将它写成若干个1和2的和 和项顺序不同认为是不同的写法 所有的方法数记作a n displaystyle a n nbsp 例如当n 4的时候 所有的写法是 4 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2 displaystyle 4 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2 nbsp 所以a 4 5 displaystyle a 4 5 nbsp 再考虑将它写成若干个大于等于2的自然数的和 和项顺序不同认为是不同的写法 所有的方法数记作b n displaystyle b n nbsp 则有a n b n 2 displaystyle a n b n 2 nbsp 这个性质也可以用双射法证明 证明 考虑集合 A n x 1 x 2 x m m 1 1 j m x j 1 2 x 1 x 2 x m n 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 nbsp B n 2 y 1 y 2 y k k 1 1 j k y j 2 y 1 y 2 y k n 2 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 nbsp 对集合A n displaystyle A n nbsp 中的一个元素 x 1 x 2 x m displaystyle x 1 x 2 cdots x m nbsp 假设其中有至少一个数为2 令x i 1 x i 2 x i k 2 displaystyle x i 1 x i 2 cdots x i k 2 nbsp 其中的下标1 i 1 lt i 2 lt lt i k m displaystyle 1 leqslant i 1 lt i 2 lt cdots lt i k leqslant m nbsp 其余的等于1 如果i k lt m displaystyle i k lt m nbsp 那么下面设k 1 displaystyle k 1 nbsp 个数 y 1 x 1 x i 1 y 2 x i 1 1 x i 2 y k x i k 1 1 x i k y k 1 x i k 1 x m 2 displaystyle begin aligned y 1 amp x 1 cdots x i 1 y 2 amp x i 1 1 cdots x i 2 amp vdots quad quad quad vdots y k amp x i k 1 1 cdots x i k y k 1 amp x i k 1 cdots x m 2 end aligned nbsp 如果i k m displaystyle i k m nbsp 则y k 1 2 displaystyle y k 1 2 nbsp 如果 x 1 x 2 x m 1 displaystyle x 1 x 2 cdots x m 1 nbsp 那么设y 1 n 2 displaystyle y 1 n 2 nbsp 那么由于各个y元素的和必然是n 2 displaystyle n 2 nbsp 所以将 x 1 x 2 x m displaystyle x 1 x 2 cdots x m nbsp 映射到 y 1 y 2 y k 1 displaystyle y 1 y 2 cdots y k 1 nbsp 的映射f是一个从A n displaystyle A n nbsp 到B n 2 displaystyle B n 2 nbsp 的映射 从构造方式可以看出 f是一个单射 对于B n 2 displaystyle B n 2 nbsp 中每一个元素 y 1 y 2 y k displaystyle y 1 y 2 cdots y k nbsp 将其中的每一个y j displaystyle y j nbsp 换成y j 2 displaystyle y j 2 nbsp 个1和一个2 然后删去最后一个2 就得到A n displaystyle A n nbsp 中的一个元素 所以f也是一个满射 也就是说 f是一个双射 这就证明了 a n b n 2 displaystyle a n b n 2 nbsp 參見 编辑其他組合技巧 如 算兩次 抽屜原理参考 编辑Loehr Nicholas A 2011 Bijective CombinatoricsArchive It的存檔 存档日期2015 10 23 CRC Press 页面存档备份 存于互联网档案馆 ISBN 143984884X ISBN 978 1439848845 取自 https zh wikipedia org w index php title 双射法 amp oldid 68225342, 维基百科,wiki,书籍,书籍,图书馆,