楊輝三角與二項式定理

這篇部落客要參考劉汝佳的《算法競賽入門經典》。

下面是一個楊輝三角：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

    我們再把(a+b)n展開，将得到一個關于x的多項式：

      (a+b)0 = 1

     (a+b)1 = a + b

     (a+b)2 = a2 + 2ab + b2

     (a+b)3 = a3 + 3a2b + 3ab2 + b3

     (a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4

     ……

    系數正好和楊輝三角一緻。一般地，我們有二項式定理：

這個不難了解：(a+b)n是n個括号連乘，每個括号裡任選一項乘起來都會對最後的結果又一個貢獻。如果選了k個a，就一定會選n-k個b，最後的項自然是an-kbk。而n個a中選k個（同時也相當于n個b裡選n-k個)有Ckn，這就是組合數的定義。

給定n，如何求出(a+b)n所有項的系數呢？一個方法是遞推，根據楊輝三角中不難發現的規律，可寫出以下程式：

1 memset(c, 0, sizeof(c));
2 for(i = 0; i <= n; i++)
3 {
4     c[i][0] = 1;
5     for(j = 1; j <=n; j++) 
6     {
7         c[i][j] = c[i-1][j-1] + c[i-1][j];
8     }
9 }      

但遺憾的是，這個算法的時間複雜度是O(n2)，盡管隻用了楊輝三角的第n行的n+1個元素，但是卻把全部n行的On2）個元素都計算了一遍

另一個方法是利用等式 

1 c[0]=1;
2 for(i = 1; i <= n; i++) 
3 {
4     c[i] = c[i-1]*(n-i+1)/i;
5 }      

 注意，先乘後除，因為c[i-1]/i可能不是整數。但這樣一來增加了溢出的可能性——即結果可能在int或long long 範圍之外，乘法也可能溢出。如果擔心這樣的情況發生，可以先約分，不過一般來說是不必要的。

作者：王陸