杨辉三角

二项式展开式

可以发现杨辉三角正好和二项式展开式的系数相吻合。

二项式定理

二项式定理的计数解释：从a和b两种物品中取n个，正好取k个a的概率数是C(n,k)。

给定n，如何求出(a+b)^n所有项的系数呢？一个方法是递推，根据杨辉三角中不难发现的规律，可写出以下程序：

1. int n;

2. ll c[maxn][maxn];

3. void init(){

4.     for(int i = 0;i <= n;i++){

5.         c[i][0] = 1;

6.         for(int j = 1;j <= i;j++){

7.             c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;

8.         }

9.     }

10. }

时间复杂度O（n^2）

还有一个O（n）算法

运用性质：

，可以算出指定n的C(n,k)。

1. int n;

2. ll c[maxn];

3. void init(){

4. c[0] = 1;

5. for(int i = 1;i <= n;i++){

6. c[i] = c[i-1]*(n-i+1)/i;

7. }

8. }

根据以上所述可以得出二项式概率公式：P（X=k)=C(n,k)（p^k）*(1-p)^(n-k) n是试验次数，k是指定事件发生的次数，p是指定事件在一次试验中发生的概率。

经典例题：uva1639（注意精度处理）