证明二项式系数的对称性质
二次项系数具有一定的对称性:
-
证明:这个等式可以视为两个集合的元素个数。考虑以下n个元素的集合: ,那么以下两个集合:
-
集合A的元素个数是 ,集合B的元素个数是 . 现在构造一个从集合A到集合B的映射:
-
对A中的每个元素C(包含集合S中的 个元素),映射f把C映射到它在S中的补集(有S中的 个元素),因此在集合B中。可以验证,这个映射是双射。所以集合A的元素个数等于B的元素个数。也就是说
-
证明两种分解方法数相等
对一个大于2的自然数n,首先考虑将它写成若干个1和2的和,和项顺序不同认为是不同的写法,所有的方法数记作 ,例如当n=4的时候,所有的写法是:
-
所以 . 再考虑将它写成若干个大于等于2的自然数的和,和项顺序不同认为是不同的写法,所有的方法数记作 。则有 这个性质也可以用双射法证明:
证明:考虑集合
-
-
对集合 中的一个元素 ,假设其中有至少一个数为2,令 (其中的下标 ),其余的等于1。如果 ,那么下面设 个数:
-
如果 则 。如果 ,那么设 。
那么由于各个y元素的和必然是 ,所以将 映射到 的映射f是一个从 到 的映射。从构造方式可以看出,f是一个单射。
对于 中每一个元素 ,将其中的每一个 换成 个1和一个2,然后删去最后一个2,就得到 中的一个元素,所以f也是一个满射。
也就是说,f是一个双射。这就证明了