组合与概率 2026-08-21 含解答

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

程国根 · 微信公众号「恩次方根」

正文文字 577 字公式 75 处

题目

给定正整数𝑘,𝑚,𝑛，满足1≤𝑘≤𝑚≤𝑛．求

∑_(𝑖=1)^(𝑛)(−1)^(𝑖)(1)/(𝑛+𝑘+𝑖)⋅((𝑚+𝑛+𝑖)!)/(𝑖!(𝑛−𝑖)!(𝑚+𝑖)!)

的值．

展开解答收起解答

补上𝑖=0项并乘𝑛!，得到

∑_(𝑖=0)^(𝑛)(−1)^(𝑖)((𝑛)/(𝑖))((𝑚+𝑛+𝑖)!)/((𝑚+𝑖)!(𝑛+𝑘+𝑖)).;(1)

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

竞赛班有𝑛名学生，第𝑗名学生手上有𝑚+𝑗道互不相同的个人题，其中𝑗=1,2,⋯,𝑛．教练手上另外还有𝑛道互不相同的公共题（与个人题也不同）．

今天，手上有𝑛+𝑘道个人题的学生（编号为𝑛+𝑘−𝑚∈[1,𝑛]∩ℤ）没有来．

现在固定𝑖．

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

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

((𝑛)/(𝑖))((𝑚+1+𝑖)(𝑚+2+𝑖)⋯(𝑚+𝑛+𝑖))/(𝑛+𝑘+𝑖);= ((𝑛)/(𝑖))((𝑚+𝑛+𝑖)!)/((𝑚+𝑖)!(𝑛+𝑘+𝑖));

故这恰好就是(1)中第𝑖项的绝对值．

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

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

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

对这个方案作如下变换：

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

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

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

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

∑_(𝑖=0)^(𝑛)(−1)^(𝑖)((𝑛)/(𝑖))((𝑚+𝑛+𝑖)!)/((𝑚+𝑖)!(𝑛+𝑘+𝑖))=0.

从而

∑_(𝑖=1)^(𝑛)(−1)^(𝑖)(1)/(𝑛+𝑘+𝑖)⋅((𝑚+𝑛+𝑖)!)/(𝑖!(𝑛−𝑖)!(𝑚+𝑖)!);= −(−1)^(0)(1)/(𝑛+𝑘+0)⋅((𝑚+𝑛+0)!)/(0!(𝑛−0)!(𝑚+0)!);= −(1)/(𝑛+𝑘)((𝑚+𝑛)/(𝑛)).;

在公众号查看原文 ↗ 反馈点公式可复制源码

正常留言提交后可直接显示，无需人工审核；仍会经过防刷与垃圾内容过滤。请不要留下手机号等私人信息。解法、疑问都可以说；公式用 LaTeX：行内 $…$ ，整行 $$…$$。