等間距組合數的和的閉合公式

張漢雄

摘要：利用二項式定理和單位根，我們可以得到等間距的組合數的和的閉合公式。

關鍵詞：組合數；二項式定理；單位根

中圖分類號：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