【算法竞赛】杨辉三角

杨慧三角是二项式系数在三角形中的一种集合排列!!

换一种说法: 杨辉三角是二项式系数, 通过数据三角形表示, 发现的数学规律.

定义: 在数学里, 二项式系数, 或组合数, 是定义为形如 ( 1 + x ) n (1 + x)^n (1+x)n展开后x的系数(其中n为自然数, k为整数)

那么一般二项式 ( x + y ) n (x + y)^n (x+y)n 的幂可用二项式系数记为 C n r C^r_n Cnr​

通常来讲，二项式系数代表的是从n件物品中，无序地选取k件的方法总数.

假设n = 4, k = 2. 通过组合数公式可以得到组合数为 6.

假如我们把 ( 1 + x ) 4 (1 + x)^4 (1+x)4 展开并标记每一个x, 就会得到:

( 1 + x 1 ) ( 1 + x 2 ) ( 1 + x 3 ) ( 1 + x 4 ) (1+x_1)(1+x_2)(1+x_3)(1+x_4) (1+x1​)(1+x2​)(1+x3​)(1+x4​)上式等于: ( 1 + x 1 ) ⋯ ( 1 + x 4 ) = ⋯ + x 1 x 2 + x 1 x 3 + x 1 x 4 + x 2 x 3 + x 2 x 4 + x 3 x 4 + ⋯ (1+x_1)⋯(1+x_4)=⋯+x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4+⋯ (1+x1​)⋯(1+x4​)=⋯+x1​x2​+x1​x3​+x1​x4​+x2​x3​+x2​x4​+x3​x4​+⋯

假如把标记去掉, 那么 x 2 x^2 x2的系数正好是等于6, 与 C 4 2 C_4^2 C42​相符合

也就证明了： ( 1 + x ) n (1+x)^n (1+x)n中 x k x^k xk的系数正好等于从n个元素中选取k个元素的组合数（ C n k C^k_n Cnk​）.

C [ i ] [ j ] = C [ i − 1 ] [ j ] + C [ i − 1 ] [ j − 1 ] ; C[i][j]=C[i−1][j]+C[i−1][j−1]; C[i][j]=C[i−1][j]+C[i−1][j−1];

递推: