等间距组合数的和的闭合公式

张汉雄

摘要：利用二项式定理和单位根，我们可以得到等间距的组合数的和的闭合公式。

关键词：组合数；二项式定理；单位根

中图分类号：G642.41 文献标志码：A 文章编号：1674-9324（2017）38-0209-02

一、二项式定理

设n是一个正整数，k是一个不超过n的自然数，我们用C表示从n个人中选出k个代表的方法总数，则我们有如下的恒等式：

（a+b）=Ca+Cab+Cab+…+Cb，

这就是牛顿的二项式定理。在上述等式中，我们取a=1，b=x，就得到了如下更简单的形式：

（1+x）=C+Cx+Cx+…+Cxn，

在上式中分别令x=1和x=-1，我们可以得到

2=C+C+C+…+C，0=C-C+C-…+（-1）C，

再将这两个式子相加并除以2，我们就得到了

C+C+C+…=2，

上式中出现的组合数的上标0，2，4，…是一个等差数列，我们把这样的组合数称为等间距的组合数，上式就是间距为2的组合数的和的闭合公式。

二、间距为3的组合数的和的闭合公式

我们自然希望推广上面的公式，得到更多等间距组合数的和的闭合公式。比如我们可以问：

C+C+C+…等于多少？是否等于2/3？

答案显然是否定的，因为组合数的和必然是整数，而2/3不是一个整数。但2/3这个答案并不离谱，数值计算表明，C+C+C+…除以2非常接近1/3。事实上，我们有如下的结果：

定理 C+C+C+…=（2+2cos）。

我们来做一点简单的分析：在证明C+C+C+…=2的时候，我们是在公式（1+x）=C+Cx+Cx2+…

+Cxn中分别令x=1和x=-1，然后再相加。1，-1是方程x=1的两个根，即二次单位根。因此在求C+C+C+…的时候，我们要考虑三次单位根，即方程x=1的三个根：1，w，w。这里w=-+i=cos+isin（i是虚数单位，i=-1）。当j是3的倍数时，1+w+w=3；当j不是3的倍数时，1+w+w=0。

证明：我们在（1+x）=C+C+Cx2+…+Cxn中分别令x=1，x=w和x=w，得到三个式子：

2=C+C+C+…+C，

（1+w）=C+Cw+Cw2+…+Cwn，

（1+w）=C+Cw2+Cw4+…+Cw2n，

将这三个式子相加得到：

2+（1+w）+（1+w）=3（C+C+C+…），

最后把1+w=+i=cos+isin，1+w=-i=cos+isin代入即可，证明完毕。

三、间距为4的组合数的和的闭合公式

利用四次单位根，即方程x=1的四個根：1，i，-1，-i，我们很容易得到间距为4的组合数的和的闭合公式。

定理 C+C+C+…=（2+2cos）。

证明：我们在（1+x）=C+Cx+Cx2+…+Cxn中分别令x=1，x=i，x=-1和x=-i，得到四个式子：

2=C+C+C+…+C，

（1+i）=C+Ci+Ci2+…+Cin，

0=C-C+C-…+C（-1），

（1-i）=C+C（-i）+C（-i）+…+C（-i），

将这四个式子相加得到：

2+（1+i）+（1-i）=4（C+C+C+…），

最后把1+i=（cos+isin）和

1-i=（cos+isin）代入即可，证毕。

这里有一个有意思的现象：当n模4余2的时候（比如n=2018），C+C+C+…=2/4=2，这是严格的相等，没有任何余项。

四、总结

利用r次单位根和二项式定理，我们很容易得到间距是r的组合数的和的闭合公式，也可以得到起始上标不是0的等间距组合数的和（比如C+C+C+…）的闭合公式，具体过程留给感兴趣的读者。

参考文献：

[1]南基洙.组合数学[M].北京：高等教育出版社，2008.endprint