第62章杨辉三角

杨辉三角（又称帕斯卡三角，Pascal's Triangle）是组合数学中最重要的结构之一。它把"组合数"以三角形的形式排列出来，既能直观展示组合规律，也能通过递推在程序中高效求解组合数、二项式系数等问题。GESP 八级明确将"杨辉三角的定义与实现"列为考核点。

杨辉三角前 7 行

62.1 杨辉三角的定义与性质

62.1.1 定义（递推构造）

杨辉三角从上到下、从左到右排列，满足：

第 $0$ 行只有一个数字 $1$ ；
三角形左右两边（每行的第一个和最后一个）都是 $1$ ；
除边界外，任意一个内部数字 = 它上方两个数字之和：

T(n, k) = T(n-1, k-1) + T(n-1, k)

其中 $n$ 为行号（从 $0$ 开始）， $k$ 为该行从左往右的位置（从 $0$ 开始）。

下标约定

本书一律使用「从 0 开始」的下标：第 $n$ 行有 $n+1$ 个数，最左边是 $T(n,0)$ ，最右边是 $T(n,n)$ 。请和题目里"第 1 行"的说法区分开。

62.1.2 与组合数的关系（核心）

杨辉三角第 $n$ 行第 $k$ 个数，恰好等于组合数：

T(n, k) = C(n, k) = \frac{n!}{k!(n-k)!}

也就是说，杨辉三角就是组合数表。这是它最重要的性质，也是八级考试里反复考查的"隐藏考点"。

一眼认出组合数

凡是题目出现"从 $n$ 个里选 $k$ 个""求系数""方案数"，先想能不能转成 $C(n,k)$ ，而 $C(n,k)$ 就能从杨辉三角里取——不用每次都写阶乘。

62.1.3 重要性质

性质	表达式 / 说明
对称性	$C(n,k) = C(n, n-k)$
每行之和	$\sum_{k=0}^{n} C(n,k) = 2^n$
边界	$C(n,0)=C(n,n)=1$ ， $C(n,1)=n$
斜列求和	沿"平行边"的斜列相加会得到斐波那契数列
二项式定理	$(a+b)^n = \sum_{k=0}^{n} C(n,k)a^{n-k}b^k$

下标差 1 是常见坑

题目描述常说"第 5 行第 3 个数"，如果你按从 1 开始计就会错。统一先减 1 变成 $(n,k)$ 从 0 开始再计算，能避免绝大多数越界与错位。

62.2 杨辉三角的实现

62.2.1 二维数组递推（最直观）

按定义逐行递推，适合"打印前 $n$ 行"这类题目：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;                 // 读入要打印的行数
    // tri[i][j] 表示第 i 行第 j 个数（均从 0 开始）
    vector<vector<long long>> tri(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; ++i) {
        tri[i][0] = tri[i][i] = 1;             // 两边都是 1
        for (int j = 1; j < i; ++j) {
            tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];  // 上方两数之和
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cout << tri[i][j] << (j == i ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。

62.2.2 滚动数组优化（空间 $O(n)$ ）

计算第 $i$ 行只需要第 $i-1$ 行，因此只需保留"上一行"，从后往前更新即可：

#include <iostream>
#include <vector>
using namespace std;

// 只保留一行，cur[j] 表示当前正在算的第 i 行第 j 个
void pascalRow(int n) {
    vector<long long> cur(n + 1, 0);
    cur[0] = 1;
    for (int i = 1; i <= n; ++i) {
        // 必须从后往前更新，否则会覆盖还没用到的上一行值
        for (int j = i; j >= 1; --j) {
            cur[j] = cur[j] + cur[j - 1];
        }
        // 此时 cur[0..i] 就是第 i 行
    }
    for (int j = 0; j <= n; ++j) cout << cur[j] << (j == n ? "" : " ");
    cout << "\n";
}

为什么从后往前？

cur[j] = cur[j] + cur[j-1] 需要"上一轮"的 cur[j] 和 cur[j-1]。若从左往右更新，cur[j-1] 已经被本轮改过，结果就错了。倒序更新可保证用到的是上一行的值。

62.2.3 直接求单点 $C(n,k)$ （最省空间）

如果只需要某一个组合数，不必生成整张表，用单行 DP 即可，空间仅 $O(k)$ ：

#include <algorithm>
#include <vector>
using namespace std;

// 返回 C(n, k)，n, k 在 long long 范围内不溢出时正确
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;          // 利用对称性，只算较小的一半
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;                         // C(0,0)=1
    for (int i = 1; i <= n; ++i) {
        for (int j = min(i, k); j >= 1; --j) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[k];
}

62.2.4 真题示例（组合数求值）

【GESP 八级风格·编程题】 题目描述：输入两个非负整数 $n$ 和 $k$ （ $0 \le k \le n \le 30$ ），输出组合数 $C(n,k)$ 的值。 输入格式：一行两个整数 $n,\ k$ 。 输出格式：一个整数，表示 $C(n,k)$ 。 样例输入：5 2 样例输出：10

参考解答：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = min(i, k); j >= 1; --j)
            dp[j] = dp[j] + dp[j - 1];
    return dp[k];
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << comb(n, k) << endl;
    return 0;
}

数据范围决定写法

$n \le 30$ 时， $C(30,15)=155117520$ 在 long long 内，直接算即可；
若 $n$ 很大或要求取模，就边算边 % MOD（如 1e9+7）；
若 $n \le 10^6$ 且只需单点，可用"连乘连除"公式 $C(n,k)=\prod_{i=1}^{k}\frac{n-k+i}{i}$ 。

62.3 应用：二项式定理

杨辉三角的每一行，正是二项式展开 $(a+b)^n$ 的系数：

(a+b)^3 = C(3,0)a^3 + C(3,1)a^2b + C(3,2)ab^2 + C(3,3)b^3 = a^3 + 3a^2b + 3ab^2 + b^3

编程应用：给定 $n$ ，输出 $(a+b)^n$ 的系数表——本质上就是把第 $n$ 行打印出来。在八级里，这类题常与"多项式系数""概率"综合考查。

62.4 注意事项

溢出：组合数增长极快， $n$ 稍大就会超过 int/long long，必须按题目是否取模处理；
下标从 0 还是 1：先统一减 1 再计算，避免差 1 错误；
对称性优化：k > n-k 时改成算 n-k，循环次数减半；
滚动数组更新方向：务必从后往前，否则会串用本轮已改的值。

练习题

说明

下列选择题考查杨辉三角与组合数的核心概念，参考答案默认折叠，点击"参考答案"展开。

1.（基础） 杨辉三角第 $6$ 行（从 $0$ 开始计数）第 $2$ 个数等于多少？

A. 6
B. 15
C. 20
D. 10

参考答案

B。第 $n$ 行第 $k$ 个数 = $C(n,k)$ ，所以第 6 行第 2 个数 = $C(6,2) = \frac{6\times5}{2} = 15$ 。注意行号、列号均从 0 开始。

2.（性质） 关于杨辉三角，下列说法正确的是？

A. 第 $n$ 行所有数之和等于 $n$
B. 杨辉三角与组合数无关
C. 第 $n$ 行第 $k$ 个数等于 $C(n,k)$
D. 内部每个数等于它下方两个数之和

参考答案

C。第 $n$ 行第 $k$ 个数等于组合数 $C(n,k)$ ；每行之和等于 $2^n$ （非 $n$ ）；内部数等于"上方"两数之和（非下方）；杨辉三角正是组合数表。

3.（应用） 展开 $(a+b)^4$ 中 $a^2b^2$ 项的系数是？

A. 4
B. 6
C. 8
D. 12

参考答案

B。 $(a+b)^n$ 展开中 $a^{n-k}b^k$ 的系数为 $C(n,k)$ ，此处 $n=4,k=2$ ， $C(4,2)=6$ 。

4.（编程） 用滚动数组求杨辉三角某一行时，内层循环应该如何遍历？

A. 从前往后（j = 1 → i）
B. 从后往前（j = i → 1）
C. 任意顺序均可
D. 必须递归实现

参考答案

B。递推式 cur[j] = cur[j] + cur[j-1] 需要"上一轮"的 cur[j] 与 cur[j-1]，从后往前更新才能保证用到的是上一行的值，从前向后会提前覆盖导致错误。

5.（综合） 计算 $C(100, 50) \bmod (10^9+7)$ 时，下列哪种做法最可能出错？

A. 用二维数组递推后取模
B. 用单行 DP 边算边取模
C. 直接算 $100!$ 再取模
D. 用公式连乘连除并在乘法后取模

参考答案

C。 $100!$ 远超 long long 范围，直接算出再取模会因溢出得到错误结果；正确做法是在递推或连乘过程中每一步都取模（注意连除时要配合逆元，不能直接除）。

62.1 杨辉三角的定义与性质

62.1.1 定义（递推构造）

62.1.2 与组合数的关系（核心）

62.1.3 重要性质

62.2 杨辉三角的实现

62.2.1 二维数组递推（最直观）

62.2.2 滚动数组优化（空间 O(n)O(n)O(n)）

62.2.3 直接求单点 C(n,k)C(n,k)C(n,k)（最省空间）

62.2.4 真题示例（组合数求值）

62.3 应用：二项式定理

62.4 注意事项

练习题

62.2.2 滚动数组优化（空间 $O(n)$ ）

62.2.3 直接求单点 $C(n,k)$ （最省空间）