杨辉三角 - CSP-J | C++ & Algorithm 编程研习社

杨辉三角：藏在数字里的组合秘密

杨辉三角（西方叫帕斯卡三角）是一个由数字排列成的三角形，看起来像一座数字金字塔。它的每一个数字都等于它上方两个数字之和，而且这个三角不仅结构优美，还藏着组合数、二项式系数、概率计算等好多数学秘密。学会它，就等于拿到了一把打开组合数学大门的钥匙。

1. 什么是杨辉三角？——从构造规则说起

我们先看一个5行的杨辉三角：

构造规则很简单：

第一行只有一个数 1。
每一行的首尾都是 1。
中间每个数等于它上方两个数相加的结果。比如第三行中间的 2 等于它上方 1 + 1，第四行中间的 3 等于 1 + 2，右边的 3 等于 2 + 1。

生活例子：想象你每天存零花钱。第一天存1元，第二天在左边放1元、右边放1元（首尾），第三天开始，每个位置的钱是它上面两个位置钱的和。这样存下去，就得到了杨辉三角的每一行！虽然钱不会真的这样算，但规则很简单。

2. 杨辉三角与组合数——扑克牌里的选人问题

组合数 C(n, m) 表示从 n 个不同物品中选出 m 个的方法数。比如从4个同学中选2个去扫地，有几种选法？答案是 C(4,2) = 6 种。

神奇的事情：杨辉三角的第 n 行的第 m 个数（行和列都从0开始计数）就是组合数 C(n, m)。

举个例子：

第4行（n=4）：1 4 6 4 1
- 第0个数 1 → C(4,0)=1
- 第1个数 4 → C(4,1)=4
- 第2个数 6 → C(4,2)=6
- 第3个数 4 → C(4,3)=4
- 第4个数 1 → C(4,4)=1

所以，如果你要快速计算小的组合数（比如n≤30），用杨辉三角比做阶乘除法快得多，而且不会遇到大数溢出的问题。

3. 杨辉三角与二项式定理——展开 (a+b)^n 的秘密

还记得初中数学里的 (a+b)^2 = a^2 + 2ab + b^2 吗？系数 1,2,1 正好是杨辉三角的第2行。更一般地，(a+b)^n 展开后的系数就是杨辉三角的第 n 行。

例如：

(a+b)^3 = 1·a^3 + 3·a^2b + 3·ab^2 + 1·b^3 → 系数 1,3,3,1（第3行）
(a+b)^4 = 1·a^4 + 4·a^3b + 6·a^2b^2 + 4·ab^3 + 1·b^4 → 系数 1,4,6,4,1（第4行）

生活例子：你在玩一个游戏，每次掷硬币有正面和反面两种结果。掷4次，恰好得到2次正面的概率是 C(4,2) / 2^4 = 6/16。这个系数6就来自杨辉三角第4行的第2个数。遇到选择、概率问题时，杨辉三角能帮你快速找出所有可能的情况数。

4. 用Python生成杨辉三角——一步一步来

下面是一个生成前 n 行杨辉三角的函数，每一行我们都用列表表示。

def yanghui_triangle(n):
    """
    生成杨辉三角的前 n 行，返回一个列表的列表
    """
    triangle = []                     # 存储所有行的列表
    for i in range(n):                # i 表示当前行号（从0开始）
        row = [1] * (i + 1)           # 当前行，先全部填1，长度 i+1
        # 计算中间的数（从索引1到i-1）
        for j in range(1, i):         # j 是列号，范围 1 到 i-1
            # 当前行的第j个数 = 上一行的第j-1个数 + 上一行的第j个数
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)          # 把这一行添加入整个三角形
    return triangle

# 生成前6行并美化打印
tri = yanghui_triangle(6)
for row in tri:
    # 将数字转成字符串，用空格连接，然后居中显示，总宽度20
    print(' '.join(map(str, row)).center(20))

输出：

         1          
        1 1         
       1 2 1        
      1 3 3 1       
     1 4 6 4 1      
    1 5 10 10 5 1

关键点解释：

第 i 行有 i+1 个数字（因为从0开始）。
row = [1] * (i+1) 先把整行都设为1，然后修改中间的部分。
中间的数字通过 triangle[i-1][j-1] + triangle[i-1][j] 计算，这正好对应“上方两个数之和”。

5. 新手常见错误

索引搞错：在 for j in range(1, i) 中，i 是当前行号（从0开始），所以 range(1, i) 只会在 i >= 2 时执行。如果写成 range(1, i+1)，就会多改最后一个1，导致结果错误。
把行和列搞混：第 n 行有 n+1 个数，但组合数中的 n 就是行号（从0起）。如果直接用题目中从1开始的行数，要记得减1。
忘记首尾都是1：有些人只初始化中间数字，结果首尾变成0。用 [1] * length 初始化就对了。
打印时对齐问题：简单用空格分隔可以，但如果数字位数不同（比如10和100），打印出来会歪。可以用 str(x).center(4) 或 format 来对齐。上面的 .center(20) 只是每一行整体居中，数字之间没有额外控制，适合小数字。

6. 完整可运行的示例——带用户输入

下面是一个完整程序，让用户输入要打印的行数，然后显示杨辉三角，并顺便输出第5行的组合数值作为验证。

def generate_yanghui(n):
    """生成杨辉三角的前n行，返回列表"""
    triangle = []                     # 存储所有行的列表
    for i in range(n):                # 当前行号 i（0起始）
        row = [1] * (i + 1)           # 当前行，首尾默认为1
        for j in range(1, i):         # 处理中间的数
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)          # 加入三角形
    return triangle

def print_triangle(tri):
    """美化打印杨辉三角，每行居中"""
    max_width = len(' '.join(map(str, tri[-1])))  # 最后一行的字符串宽度
    for row in tri:
        line = ' '.join(map(str, row))            # 数字用空格拼接
        print(line.center(max_width))             # 居中打印

# 主程序
num_rows = int(input("请输入要打印的行数："))
data = generate_yanghui(num_rows)
print_triangle(data)

# 验证：打印第5行（索引4），应该对应 C(4,0)到C(4,4)
print("\n第5行（索引4）的数字：", data[4])
print("组合数 C(4,2) =", data[4][2])  # 应该输出6

运行示例（输入6）：

请输入要打印的行数：6
    1    
   1 1   
  1 2 1  
 1 3 3 1 
1 4 6 4 1
1 5 10 10 5 1

第5行（索引4）的数字： [1, 4, 6, 4, 1]
组合数 C(4,2) = 6

7. 相关知识点拓展

二项式定理：杨辉三角就是二项式系数的直观展现，可以配合 (a+b)^n 展开一起学习。
斐波那契数列：把杨辉三角斜着看（左上到右下），把每斜行的数相加，得到的就是斐波那契数列！比如：
- 第0斜行：1
- 第1斜行：1
- 第2斜行：1+1=2
- 第3斜行：1+2=3
- 第4斜行：1+3+1=5
- 第5斜行：1+4+3=8 …… 神奇吧？
谢尔宾斯基三角形：把杨辉三角中的奇数涂黑，偶数留白，会得到一个分形图案，这就是有名的谢尔宾斯基三角形。
概率与组合恒等式：杨辉三角还藏着很多等式，比如每一行的和等于 2^n（因为 C(n,0)+C(n,1)+...+C(n,n)=2^n），可以用于二进制问题。

掌握杨辉三角，不仅让你在编程竞赛中快速计算组合数，更能帮你理解数学中那些美妙的关系。下次遇到“从N个物品中选M个”或者“二项式展开”的问题，不妨先画几行杨辉三角试试！

例题精讲