一道组合恒等式的双射证法：2000年CTST第2题

题目

给定正整数，满足．求

的值．

解答

补上项并乘，得到

我们先用双射证明补项后的结果为．

赋予组合意义

竞赛班有名学生，第名学生手上有道互不相同的个人题，其中．教练手上另外还有道互不相同的公共题（与个人题也不同）．

今天，手上有道个人题的学生（编号为）没有来．

现在固定．

教练先从道公共题中选出道供学生选择，共有种选法．

对于第名到场学生，他可以从自己的个人题与教练选出的道公共题中任选一道，因此共有种选择．故总方案数为

故这恰好就是中第项的绝对值．

构造双射

下面构造双射，将为偶数的方案与为奇数的方案一一对应．

今天只有名学生到场，而一共有道公共题．每名学生最终只选择一道题，因此至少有一道公共题没有被任何学生选中．

对于任意一个方案，在所有没有被学生选中的公共题中，取编号最小的一道，记为．

对这个方案作如下变换：

• 如果原本被教练选出，就将它从教练选出的公共题中删去；
• 如果原本没有被教练选出，就将它加入教练选出的公共题中；
• 所有学生原先选择的题保持不变．

因为本来就没有被任何学生选择，所以无论将它加入还是删去，都不会影响任何学生原有的选择，因此变换后的方案仍然合法．

此外，这个变换前后，被学生实际选中的公共题完全没有改变．因此，编号最小的“没有被学生选中的公共题”仍然是于是再进行一次同样的变换，就会回到原方案．

所以这个变换是一个双射，并且它恰好使教练选出的公共题数增加或减少．因此，它把为偶数的方案与为奇数的方案一一对应。

于是，中每一个正号方案都与唯一一个负号方案配对，两者恰好抵消．因此

从而