二项式定理与杨辉三角 - NOI提高级教程

📖 组合数学：杨辉三角与二项式展开

二项式定理 (Binomial Theorem) 指出了任意正整数次幂的二项式展开形式，而杨辉三角 (Pascal's Triangle) 则是这一项项展开系数的几何排列。

📐 二项式定理公式

对于任意整数 $n \ge 0$，$(a+b)^n$ 展开的代数形式为：

$(a + b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \cdots + \binom{n}{n}b^n$

其第 $k$ 项（从0起计）的系数正是组合数 $\binom{n}{k} = C(n, k)$。

📐 杨辉三角递推关系

杨辉三角的每一行代表 $(a+b)^n$ 的展开系数。其边界值均为 1，内部每一个数都是它肩上两个数之和。对应的组合递推公式为：

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

用鼠标悬停或点击下方杨辉三角的数字单元，观察它上方的两个加数连线及对应的二项式展开式。

当前行 n (指数) 4

当前列 k (项序) 2

组合数值 C(n, k) 6

递推递推式 C(4, 2) = C(3, 1) + C(3, 2)

🔺 杨辉三角二项式系数矩阵 (Pascal's Triangle Matrix)

(a + b)⁴ = ...

// 动态规划二维数组递推预处理组合数 (N = 10)
long long C[11][11];
void precomputeCombinations() {
    for (int i = 0; i <= 10; i++) {
        C[i][0] = 1; // 边界：任何数选0个都只有1种方法
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j]; // 肩上两数之和
        }
    }
}

📋 递推分析日志