(3) 杨辉三角与组合数

GESP C++ 八级考试大纲知识点梳理系列文章：
计数原理：加法与乘法
排列与组合
杨辉三角与组合数
倍增法
代数与平面几何 {: .prompt-tip}

继上一篇我们探讨了排列和组合之后，GESP C++八级大纲的第三条考点非常经典，它是计算机算法（尤其是动态规划）的重要入门案例。

（3）掌握杨辉三角形（又称帕斯卡三角形）的概念。 {: .prompt-info}

杨辉三角形（Yang Hui’s Triangle），在西方称为帕斯卡三角形（Pascal’s Triangle），是一个无限对称的数字三角形。它不仅在形式上优美，更蕴含了深厚的组合数学原理。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。 {: .prompt-warning}

一、杨辉三角的概念与构造

杨辉三角的构造规则非常简单，概括为一句话：每个数等于它上方两数之和。

1.1 形状演示

如果我们把三角形写出来，前几行是这样的：

Row 0:      1
Row 1:     1 1
Row 2:    1 2 1
Row 3:   1 3 3 1
Row 4:  1 4 6 4 1
...

或者用左对齐的方式（在计算机二维数组中更常见）：

1.2 递推公式

如果用 $tri[i][j]$ 表示第 $i$ 行第 $j$ 列的数字（行列索引从 0 开始），那么有：

边界条件：每一行的第一个数和最后一个数都是 1。 $tri[i][0] = 1, \quad tri[i][i] = 1$
递推关系：中间的数等于它正上方 ( $i-1, j$ ) 和左上方 ( $i-1, j-1$ ) 的数之和。 $tri[i][j] = tri[i-1][j-1] + tri[i-1][j]$

这其实就是我们上一章提到的组合数公式 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 的完美图形化体现。

二、杨辉三角与组合数的关系

杨辉三角最核心的数学意义在于：第 $n$ 行的第 $m$ 个数，恰好就等于组合数 $C_n^m$ （即 $\binom{n}{m}$ ）。

注意：这里的行号 $n$ 和列号 $m$ 都是从 0 开始计数的。

2.1 验证

第 2 行：1, 2, 1
- $C_2^0 = 1$
- $C_2^1 = 2$
- $C_2^2 = 1$
第 3 行：1, 3, 3, 1
- $C_3^0 = 1$
- $C_3^1 = 3$
- $C_3^2 = 3$
- $C_3^3 = 1$
第 4 行：1, 4, 6, 4, 1
- $C_4^2 = \frac{4 \times 3}{2 \times 1} = 6$ ，确实对应第 4 行第 2 列的 6。

2.2 为什么会有这个关系？

这就回到了组合数的定义。假设我们要在 $n$ 个物品中选 $m$ 个（ $C_n^m$ ）：我们可以把这 $n$ 个物品中的某一个特定物品（比如“特殊的红球”）单独拿出来看。选出的 $m$ 个物品中，只有两种情况：

包含这个红球：那么还需要从剩下的 $n-1$ 个中选 $m-1$ 个。即 $C_{n-1}^{m-1}$ 。
不包含这个红球：那么需要从剩下的 $n-1$ 个中选完整 $m$ 个。即 $C_{n-1}^m$ 。

所以， $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。这正是杨辉三角的递推公式。

三、杨辉三角的应用

3.1 二项式定理系数

杨辉三角的第 $n$ 行，正是二项式 $(a+b)^n$ 展开后的各项系数。

$(a+b)^1 = 1a + 1b$ $\rightarrow$ 1, 1
$(a+b)^2 = 1a^2 + 2ab + 1b^2$ $\rightarrow$ 1, 2, 1
$(a+b)^3 = 1a^3 + 3a^2b + 3ab^2 + 1b^3$ $\rightarrow$ 1, 3, 3, 1

在解题时，如果让你求 $(x+1)^n$ 的展开式系数，可以直接打印杨辉三角。

3.1.1 扩展：关于“第 $n$ 行的所有数之和为 $2^n$ ”

这一条的原理主要有两种解释方式：代数推导和组合意义。

(1) 代数推导（利用二项式定理）我们在文章前面提到过，杨辉三角的第 $n$ 行实际上就是 $(a+b)^n$ 展开后的系数。

(a+b)^n = C_n^0 a^n b^0 + C_n^1 a^{n-1} b^1 + \dots + C_n^n a^0 b^n

如果我们令 $a=1$ 且 $b=1$ ，代入上面的公式，就会神奇地发现：

(1+1)^n = C_n^0 \cdot 1^n \cdot 1^0 + C_n^1 \cdot 1^{n-1} \cdot 1^1 + \dots

即：

2^n = C_n^0 + C_n^1 + C_n^2 + \dots + C_n^n

而 $C_n^0, C_n^1, \dots$ 正是杨辉三角第 $n$ 行的所有数字。所以，它们的和一定等于 $2^n$ 。

(2) 组合意义（子集总数）

想象你有一个包含 $n$ 个不同元素的集合（比如 ${1, 2, \dots, n}$ ）。

$C_n^0$ 表示选 0 个元素的方案数（空集）； $C_n^1$ 表示选 1 个元素的方案数； … $C_n^n$ 表示选 $n$ 个元素的方案数（全集）。把这一行所有数字加起来，意思就是**“从中选出任意个元素的方案总数”，也就是这个集合的所有子集的数量。对于集合中的每一个元素，它只有两种状态：“被选中”** 或 “不被选中”。 $n$ 个元素，每个都有 2 种选择，根据乘法原理，总方案数就是 $\underbrace{2 \times 2 \times \dots \times 2}_{n \text{个} } = 2^n$ 。

3.2 动态规划求组合数

这是编程中最实用的功能。直接利用阶乘公式 $C_n^m = \frac{n!}{m!(n-m)!}$ 计算组合数有两个大问题：

溢出风险： $20!$ 就已经超过 long long 范围了，但 $C_{20}^{10}$ 其实并不大。
计算量：频繁计算阶乘效率低，且涉及除法（取模时需要逆元）。

利用杨辉三角递推（其实就是动态规划），我们可以只用加法，安全、快速地计算出小范围内的所有组合数。

适用于 $N \le 2000$ 左右的情况。如果是 $N$ 很大但 $M$ 很小，或者 $N, M$ 都很大且需要取模，则需要用其他方法（如卢卡斯定理）。

四、代码实现 (C++)

下面展示如何利用二维数组生成杨辉三角，并查询组合数。

#include <iostream>
#include <vector>

using namespace std;

// 定义最大行数
const int MAXN = 20;

long long triangle[MAXN + 1][MAXN + 1];

void buildPascalTriangle() {
    // 初始化边界和递推
    for (int i = 0; i <= MAXN; i++) {
        triangle[i][0] = 1;       // 每行第一个是 1
        triangle[i][i] = 1;       // 每行最后一个是 1
        for (int j = 1; j < i; j++) {
            // 递推公式：头顶两数之和
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
}

void printTriangle() {
    for (int i = 0; i <= 10; i++) { // 打印前10行看看
        // 打印一些空格做格式化（仅仅为了美观，非必须）
        for(int k=0; k<10-i; k++) cout << "  ";
        
        for (int j = 0; j <= i; j++) {
            printf("%4lld", triangle[i][j]);
        }
        cout << endl;
    }
}

int main() {
    buildPascalTriangle();
    
    // 1. 打印图形
    cout << "=== 杨辉三角前10行 ===" << endl;
    printTriangle();
    
    // 2. 利用杨辉三角查询组合数
    // C(5, 2)
    int n = 5, m = 2;
    cout << "\n=== 组合数查询 ===" << endl;
    cout << "C(" << n << ", " << m << ") = " << triangle[n][m] << endl;
    
    // C(10, 4)
    n = 10; m = 4;
    cout << "C(" << n << ", " << m << ") = " << triangle[n][m] << endl;
    
    return 0;
}

代码运行结果演示

=== 杨辉三角前10行 ===
                      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
        1   7  21  35  35  21   7   1
      1   8  28  56  70  56  28   8   1
    1   9  36  84 126 126  84  36   9   1
    
=== 组合数查询 ===
C(5, 2) = 10
C(9, 4) = 126

五、实战演练：计算系数（洛谷 P1313）

题目描述：给定一个多项式 $(ax + by)^k$ ，请求出多项式展开后 $x^n y^m$ 项的系数。结果对 $10007$ 取模。

核心考点：二项式定理 + 组合数计算

解题思路：根据二项式定理， $(ax+by)^k$ 的通项公式为：

T_{r+1} = C_k^r (ax)^{k-r} (by)^r = C_k^r a^{k-r} b^r x^{k-r} y^r

题目要求 $x^n y^m$ 项的系数，意味着对应的是 $x^n y^m$ 这一项。即 $k-r = n$ 且 $r = m$ （题目保证 $n+m=k$ ）。所以，该项的系数为：

\text{系数} = C_k^m \times a^n \times b^m

为何使用杨辉三角？ 题目中 $k \le 1000$ 。虽然 10007 是质数，可以用卢卡斯定理或逆元，但直接用杨辉三角预处理 $C(k, m)$ 是最稳健、最不容易出错的方法（此范围 $O(k^2)$ 约为 $10^6$ ，非常快）。

代码核心片段：

// 1. 预处理杨辉三角 (只算到 k 行即可)
for (int i = 0; i <= k; i++) {
    c[i][0] = 1;
    c[i][i] = 1;
    for (int j = 1; j < i; j++)
        c[i][j] = (c[i-1][j-1] + c[i-1][j]) % 10007; // 边算边取模，完美
}

// 2. 计算答案
// ans = C(k, m) * a^n * b^m % 10007
long long ans = c[k][m]; 
ans = (ans * quick_pow(a, n)) % 10007; // 配合快速幂计算 a^n
ans = (ans * quick_pow(b, m)) % 10007; // 配合快速幂计算 b^m

cout << ans << endl;

代码核心片段分析（以连乘取模为例）

这段代码的核心逻辑是利用模运算的乘法性质来防止数据溢出。

我们以 3 个数连乘取模为例，公式如下：

(A \times B \times C) \pmod P = [((A \times B) \pmod P) \times C] \pmod P

即：步步取模。每乘一个数，就取一次模，最终结果不变。

1. 变量对应关系

在代码中，我们需要计算的是：

\text{ans} = (C_k^m \times a^n \times b^m) \pmod{10007}

我们可以将其视为三个数 $A, B, C$ 的连乘：

$A = C_k^m$ (即 c[k][m])
$B = a^n$ (即 quick_pow(a, n))
$C = b^m$ (即 quick_pow(b, m))
$P = 10007$

2. 数学推导与代码执行对照

假设我们用小一点的数字来模拟：计算 $(2 \times 3 \times 4) \pmod 5$ 。直接计算： $2 \times 3 \times 4 = 24$ ， $24 \div 5 = 4 \dots 4$ 。结果为 4。

代码的分步执行过程（步步取模）：

初始状态：
```
long long ans = c[k][m]; // 对应 A
```
假设 $A=2$ ，则 ans = 2。
第一步乘法：
```
ans = (ans * quick_pow(a, n)) % 10007; // 对应 (A * B) % P
```
假设 $B=3, P=5$ 。
- 计算乘积： $ans \times B = 2 \times 3 = 6$
- 取模： $6 \pmod 5 = 1$
- 此时 ans = 1。
第二步乘法：
```
ans = (ans * quick_pow(b, m)) % 10007; // 对应 (ans * C) % P
```
这里用的是上一步计算出的 ans（即 1）。假设 $C=4$ 。
- 计算乘积： $ans \times C = 1 \times 4 = 4$
- 取模： $4 \pmod 5 = 4$
- 此时 ans = 4。

结论：最终结果 4 与直接计算的结果一致。

3. 为什么要这样做？

虽然本题模数 $10007$ 很小，直接算也不会溢出 long long，但在算法竞赛中，通常模数 $P$ 很大（如 $10^9+7$ ）。如果不“步步取模”，直接算 $A \times B \times C$ ，结果可能会是一个巨大的天文数字，远超计算机整数类型的存储上限（即溢出）。通过步步取模，我们保证了中间结果永远不会超过 $P \times P$ （约 $10^{18}$ 范围内），从而可以安全地使用 long long 存储。

六、总结

杨辉三角形是连接几何（三角形结构）与代数（组合数、二项式定理）的桥梁。在 GESP 八级考试中，主要考察以下几点：

基本性质：要知道第 $n$ 行第 $m$ 列对应 $C_n^m$ 。
递推构造：能够手写代码构建杨辉三角数组（DP思想）。
行和性质：第 $n$ 行的所有数之和为 $2^n$ （对应集合所有子集的总数）。
组合数计算：利用杨辉三角解决不需要取模或模数不是质数的组合数计算问题。

注：关于“不需要取模或模数不是质数时的组合数计算”

这一条是针对编程竞赛（算法竞赛）中常见的坑点。

为什么要用杨辉三角（递推法）？通常计算组合数 $C_n^m$ 有两种方法：

公式法： $C_n^m = \frac{n!}{m!(n-m)!}$ 递推法（杨辉三角）： $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 公式法的问题在于那个除法。

在计算机中，整数运算 $a / b \pmod p$ 不等于 $(a \pmod p) / (b \pmod p)$ 。要计算模运算下的除法，必须转换成乘以 $b$ 的逆元，即 $a \cdot b^{-1} \pmod p$ 。关键限制：只有当模数 $p$ 是质数（且 $b$ 不是 $p$ 的倍数）时，我们可以简单地用费马小定理求逆元。如果题目要求的模数 $p$ 不是质数（比如 $p=1000$ ），或者根本不取模（但在 long long 范围内），公式法就非常麻烦：

不取模时：中间的阶乘 $n!$ 极易溢出（21! 就爆了 unsigned long long），通过公式算出结果很难。模数组合数非质数时：无法使用费马小定理求逆元，需要用扩展欧几里得算法求逆元，或者分解质因数，代码极其复杂且容易写错。杨辉三角的优势：它全程只使用加法（ $dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$ ）。

没有除法：不需要担心除不尽，也不需要求逆元。适用性广：无论模数 $p$ 是质数还是合数，加法取模恒成立

(a+b) \pmod p = (a\%p + b\%p) \% p

。防溢出：可以直接在计算过程中取模，或者直接利用 long long 存储最终结果（只要最终结果不超）。总结：只要 $n$ 的范围较小（比如 $n \le 2000$ ），无论模数是什么妖魔鬼怪，这套杨辉三角递推代码都是通杀的“万金油”解法。

掌握了杨辉三角，我们就有了处理简单组合计数问题的有力武器。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月4日

(2) 排列与组合 (4) 倍增法