組合恆等式1 五個基本的組合恆等式 基礎與簡單例子

組合恆等式是組合學中一個非常有趣但也十分具有挑戰性的小分支，它常常以複雜的離散概率論問題的歸一性的基礎，或者數學競賽題目的形式出現。組合恆等式是無窮的，因此掌握組合恆等式的證明、計算技巧尤爲重要。這一講就從五個大家高中就學過的組合恆等式開始。

四個基本的組合恆等式

等式一 組合數的對稱性
$C_n^k = C_n^{n-k}$

等式二 楊輝三角
$C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$

等式三 多項式係數的唯一性
$C_n^kC_k^m = C_n^{m}C_{n-m}^{k-m} = C_n^{k-m}C_{n-k+m}^m,m\le k \le n$

這個等式表示多項式係數的唯一性，可以驗證這三項表示的都是$(n;m,k-m,n-k)$的多重組合數，即把$n$個白球中的$m$個塗紅、$k-m$個塗綠、$n-k$個塗黑的可能的方法數目：
$\frac{n!}{m!(k-m)!(n-k)!}$

在計數的時候，塗紅色/綠色/黑色的順序不影響總數，這就有了上面的恆等式，所以是多項式係數的唯一性。這個恆等式的一個特例也非常有用，假設$m=1$，
$kC_n^k = nC_{n-1}^{k-1}$

等式四 二項式定理
$(x+y)^n = \sum_{i=0}^n C_n^ix^iy^{n-i}$

特例，如果$x=y=1$，則
$\sum_{i=0}^n C_n^i = 2^n$

如果$x=1,y=-1$，則
$\sum_{i=0}^n (-1)^iC_n^i = 0$

這四個等式中，等式一的作用就是變換一下指標；等式二的作用主要是拆項遞推；等式三主要用來處理與組合數相乘的隨指標變化的因子；等式四的作用是提供原始的和式。

應用四個基本恆等式計算組合恆等式的例題

例1 計算$\sum_{k=0}^n (-1)^k\frac{C_n^k}{k+1}$
先觀察隨指標變換的部分，$C_n^k/(1+k)$，與組合數相乘的因子是一個分式。等式三簡單變形一下，$C_n^k/n = C_{n-1}^{k-1}/k$，所以$C_n^k/(1+k)=C_{n+1}^{k+1}/(n+1)$，
$\sum_{k=0}^n (-1)^k\frac{C_n^k}{k+1}= \frac{1}{n+1}\sum_{k=0}^n (-1)^kC_{n+1}^{k+1}$

-1的冪作爲因子與組合數相乘可以參考等式四的特例二，
$\sum_{i=0}^{n+1} (-1)^iC_{n+1}^i = 0 = (-1)^0C_{n+1}^0 + \sum_{i=1}^{n+1} (-1)^iC_{n+1}^i = 1 - \sum_{k=0}^{n+1} (-1)^{k}C_{n+1}^{k+1}$

結合這兩條推導，可以得到$\sum_{k=0}^n (-1)^k\frac{C_n^k}{k+1}=1/(1+n)$。

例2 計算$\sum_{k=0}^n k^2C_n^k$
同樣觀察隨指標變換的部分，$k^2C_n^k$，也是利用等式三先做一次變形，$k^2C_n^k=knC_{n-1}^{k-1}$。考慮$kC_{n-1}^{k-1}$，等式二與組合數的指數相同，所以這裏裂項，$kC_{n-1}^{k-1}=C_{n-1}^{k-1} + (k-1)C_{n-1}^{k-1}$，其中$(k-1)C_{n-1}^{k-1}=(n-1)C_{n-2}^{k-2}$
$\sum_{k=0}^n k^2C_n^k=n\sum_{k=0}^n C_{n-1}^{k-1} + n(n-1)\sum_{k=0}^n C_{n-2}^{k-2}$

剩下的兩個求和式可以用等式四的特例一
$\sum_{k=0}^n C_{n-1}^{k-1} = \sum_{i=0}^{n-1} C_{n-1}^i = 2^{n-1},\ \sum_{k=0}^n C_{n-2}^{k-2} = \sum_{j=0}^{n-2} C_{n-2}^j = 2^{n-2}$

結合這兩條推導，可以得到$\sum_{k=0}^n k^2C_n^k=n(n+1)2^{n-2}$。

例3 計算$\sum_{i=m}^n C_n^iC_i^m$和$\sum_{i=m}^n (-1)^iC_n^iC_i^m$
（1）隨指標變換的部分，$C_n^iC_i^m$，是兩個組合數的乘積，特點是左上和右下的兩個指標相同，這種特徵對應等式三，$C_n^iC_i^m = C_n^{m}C_{n-m}^{i-m}$，它可以消去一個組合數中變動的指標，
$\sum_{i=m}^n C_n^iC_i^m=C_n^{m}\sum_{i=m}^n C_{n-m}^{i-m}=C_n^{m}\sum_{k=0}^{n-m} C_{n-m}^{k}=C_n^m2^{n-m}$

（2）利用一樣的技巧，當$n>m$時
$\sum_{i=m}^n (-1)^iC_n^iC_i^m=C_n^{m}\sum_{i=m}^n (-1)^iC_{n-m}^{i-m}=(-1)^mC_n^{m}\sum_{k=0}^{n-m} (-1)^{k}C_{n-m}^{k}=0$

最後一步利用了等式四的特例二；當$n=m$時，和式只有一項，$(-1)^m$。綜合可得，
$\sum_{i=m}^n (-1)^iC_n^iC_i^m=(-1)^m\delta_{nm}$

$\delta_{nm}$是Kronecker符合，當僅當$m=n$爲1，否則爲0。

應用四個基本恆等式證明組合恆等式的例題

例4 證明$\sum_{i=0}^n (-1)^iC_n^i \frac{m}{m+i}= (C_{m+n}^n)^{-1}$
當$m=1$時，這個等式就是例1的結果。當$m>1$時，就要麻煩一點了，等式一三四顯然都是沒法用的，那就考慮一下等式二，$C_n^i=C_{n-1}^{i-1} + C_{n-1}^i$

$\sum_{i=0}^n (-1)^iC_n^i \frac{m}{m+i}=\sum_{i=0}^n (-1)^iC_{n-1}^i \frac{m}{m+i}+\sum_{i=0}^n (-1)^iC_{n-1}^{i-1} \frac{m}{m+i}$

這個等式的右邊第一項在$i=n$，第二項在$i=0$時都是沒有定義的，爲了讓這個式子有意義，需要把$i=0,n$單獨拿出來

$\sum_{i=0}^n (-1)^iC_n^i \frac{m}{m+i}=1+\sum_{i=1}^{n-1} (-1)^iC_{n-1}^i \frac{m}{m+i}+\sum_{i=1}^{n-1} (-1)^iC_{n-1}^{i-1} \frac{m}{m+i}+(-1)^n\frac{m}{m+n}$

記$a_n=\sum_{i=0}^n (-1)^iC_n^i \frac{m}{m+i}$，則$a_{n-1}=1+\sum_{i=1}^{n-1} (-1)^iC_{n-1}^i \frac{m}{m+i}$，處理剩下的兩項

$\sum_{i=1}^{n-1} (-1)^iC_{n-1}^{i-1} \frac{m}{m+i}+(-1)^n\frac{m}{m+n}=\sum_{i=1}^{n} (-1)^iC_{n-1}^{i-1} \frac{m}{m+i}$

觀察這個結果，它和$a_n$的形式非常相似，所以接下來的目標就是把它表示成$a_i$的樣子，$C_{n-1}^{i-1}$與$C_n^i$之間可以利用等式三特例來轉換，$C_{n-1}^{i-1}=\frac{i}{n}C_n^i$，

$\sum_{i=1}^{n} (-1)^iC_{n-1}^{i-1} \frac{m}{m+i}=\frac{m}{n}\sum_{i=1}^{n} (-1)^iC_{n}^{i} \frac{i}{m+i}=\frac{m}{n}\sum_{i=1}^{n} (-1)^iC_{n}^{i} \left( 1- \frac{m}{m+i} \right) \\ = \frac{m}{n}\sum_{i=1}^{n} (-1)^iC_{n}^{i} - \frac{m}{n}\sum_{i=1}^{n} (-1)^iC_{n}^{i}\frac{m}{m+i} = -\frac{m}{n}a_n$

結合上面的推導，可以得到一個遞推關係$a_n=a_{n-1}-\frac{m}{n}a_n$，也就是$a_n=\frac{n}{n+m}a_{n-1}$

$a_n = \frac{n}{n+m}a_{n-1} = \frac{n}{n+m}\frac{n-1}{n-1+m}a_{n-2} = \cdots =(C_{m+n}^n)^{-1}$

例5 證明$\sum_{i=1}^n (-1)^{i+1}C_n^i \frac{1}{i}= \sum_{i=1}^n \frac{1}{i}$
觀察隨指標變換的部分，與例1的區別就是分式中的分母是$i$而不是$i+1$，這種和基本恆等式的指標差一點的情況，我們用與例4類似的方法，記$b_n=\sum_{i=1}^n (-1)^{i+1}C_n^i \frac{1}{i}$，用等式二裂項，下面 下麪僅給出簡略步驟

$b_n=\sum_{i=1}^{n} (-1)^{i+1}C_{n-1}^{i-1} \frac{1}{i}+b_{n-1} = \frac{1}{n} \sum_{i=1}^{n} (-1)^{i+1}C_{n}^{i}+b_{n-1} =\frac{1}{n} +b_{n-1}$