组合数的秘密：杨辉三角与递推公式-野牛程序员教少儿编程

? 什么是组合数？

组合数表示从 n个物品中选出 r 个的方法数，不考虑顺序。

我们记作：

C(n,r)=(n \ r)

? 例子：从 A、B、C 中选 2 人值日，可能有：

• AB、AC、BC，共 3 种方法
  所以：

C(3,2)=3

---

?‍♂️ 组合数的“魔法公式”：递推公式

组合数满足这样的递推关系：

C(n,r)=C(n−1,r)+C(n−1,r−1)

? 理解：

要从 n 本书中选 r本，第 n本《哈利波特》可以选也可以不选：

• 不选：《哈利波特》被跳过 → 从前 n−1 本中选 r本 → C(n−1,r)

• 选了它 → 从前 n−1 本中选 r−1本 → C(n−1,r−1)

? 所以：

C(n,r)=C(n−1,r)+C(n−1,r−1)

---

? 杨辉三角：组合数变身“魔法塔”

递推公式可以生成神奇的三角形结构：

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

? 规律：

• 每一行是对应的 C(n,r)（第 n 行的第 r 个）

• 每个数等于它左上角 + 右上角两个数之和

---

? C++代码讲解：构建组合数表

#include <iostream>
using namespace std;

const int MAX = 101; // 最大支持 C(100, r)
long long C[MAX][MAX]; // 组合数数组

// 构建组合数的二维表
void build_combinations() {
    for (int n = 0; n < MAX; ++n) {
        C[n][0] = 1; // 选0个：永远只有1种方法
        for (int r = 1; r <= n; ++r) {
            C[n][r] = C[n - 1][r] + C[n - 1][r - 1]; // 使用递推公式
        }
    }
}

int main() {
    build_combinations(); // 初始化组合数表

    int n, r;
    cout << "请输入 n 和 r（如 5 2 表示 C(5,2)）: ";
    cin >> n >> r;

    cout << "C(" << n << ", " << r << ") = " << C[n][r] << endl;

    return 0;
}

✅ 示例输出：

请输入 n 和 r（如 5 2 表示 C(5,2)）: 5 2
C(5, 2) = 10

---

? 课堂练习

编号	题目
①	写出杨辉三角前 6 行
②	手算 C(6,3) 并验证
③	输出所有 C(10, r)，r 从 0 到 10
④	思考：为什么 C(n, r) = C(n, n-r) 是对称的？