帕斯卡三角形公式及其示例
陈莎拉
什么是帕斯卡三角形？
帕斯卡三角形是一个三角形排列的数字阵列，其排列遵循基于上一行数字的简单模式。它由法国数学家布莱兹·帕斯卡在17世纪推广开来。三角形以顶部的单个数字“1”开始，并且后续每一行也都以“1”开始和结束。
除了其优美的形状，帕斯卡三角形还蕴含着深刻的数学关系。它与二项式定理、组合计数和概率论密切相关，因此出现在世界各地的代数、统计学和计算机科学课堂上。
帕斯卡三角形的历史
虽然三角形以布莱兹·帕斯卡的名字命名，但它的出现比帕斯卡早了几个世纪。中国数学著作《九章算术》中包含已知最早的例子之一，其中展示了许多与我们今天使用的相同的模式。
波斯数学家卡拉吉和印度学者 Ping阿拉也探索过类似的阵列。帕斯卡在1654年发表的论文《算术三角形论》中正式阐述了三角形的性质，该论文赋予了三角形在西方数学中现代的名称。
帕斯卡三角形的构造
绘制帕斯卡三角形很简单。只需记住一条规则：每一行都以 1 开头和结尾，其余数字均由上一行递增。
对于任意行 r 和列 c，其值等于行 r-1 的列 c-1 和列 c 中的数字之和。
在这里，
- r = 3, 4, 5, …
- n 和 c = 2, 3, 4, …, r-1。
以下是构建帕斯卡三角形的步骤：
步骤1） 先填写前两行。
步骤2） 第三行的第二个元素是第二行第一个数字和第二个数字之和。
步骤3） 第四行以“1”开头。第二个数字是3，它是1和2的和（蓝色高亮显示）。
下图展示了如何填写第四行：
步骤4） 第五行由五个数字组成。我们已经从前面的步骤中知道了填充行的规律。
帕斯卡三角公式 – 二项式系数
二项式系数计算从 n 个元素的集合中选择 k 个元素的子集的方法数。它通常记为“C(n, k)”或“n 选 k”。
二项式系数定义为：
“！”符号表示一个数的阶乘。
n! = n.(n-1).(n-2)…3.2.1
例如，
5！ = 5.4.3.2.1
= 120
所以，C(5, 3) 或“5 选 3” = 5! / 3!(5-3)!
= 120 / 12
= 10
方法一：通过前一行构建帕斯卡三角形
这里的步骤与我们手动绘制三角形的方法类似。假设我们要生成最多七行的帕斯卡三角形。
具体步骤如下：
步骤1） 最上面一行从“1”开始。
步骤2） 对于第“r”行，元素“c”将是第“c-1”列和第“r-1”行第“c”列的总和。
步骤3） 每一行的第一个和最后一个数字始终为“1”。
遵循这三个简单的步骤，我们就可以系统地构建整个三角形。
C++ Code 上一行帕斯卡三角形
#include <bits/stdc++.h> using namespace std; void printRow(int n) { int numbers[n][n]; for (int row = 0; row < n; row++) { for (int col = 0; col <= row; col++) { if (col == 0 || col == row) { numbers[row][col] = 1; } else { numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col]; } cout << numbers[row][col] << "\t"; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printRow(n); }
输出：
How many rows: 7 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
Python Code 上一行帕斯卡三角形公式
def printRow(n): numbers = [[0 for row in range(n)] for col in range(n) ] for row in range(len(numbers)): for col in range(0, row+1): if row == col or col == 0: numbers[row][col] = 1 else: numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col] print(numbers[row][col],end="\t") print("\n") n = int(input("How many rows: ")) printRow(n)
帕斯卡三角形示例输出：
How many rows: 7 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
复杂度分析
A 二维数组 本实现中使用了。鉴于 N 是帕斯卡三角形的行数，这需要 N2 单位空间。因此，空间复杂度为 O(N)。2).
该函数使用了两个嵌套循环，每个循环最多运行“N”次。因此，其时间复杂度也为 在2)或时间复杂度的平方。
方法二：通过计算二项式系数构建帕斯卡三角形
我们可以直接利用二项式系数推导出帕斯卡三角形的元素个数。下图展示了这种关系：
以下是通过计算二项式系数来构建帕斯卡三角形的步骤：
步骤1） 最上面一行是 C(0, 0)。根据上面的公式，C(0, 0) = 1，因为 0! = 1。
步骤2） 对于第“i”行，总共有“i”个元素。每个元素的计算公式为C(n, r)，其中n为i-1。
步骤3） 重复步骤 2，生成你想要的帕斯卡三角形的行数。
C++ Code 帕斯卡三角形的二项式系数
#include <iostream> using namespace std; int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; } int binomialCoefficient(int n, int r) { int result = 1; if (r > n) { return -1; } result = factorial(n) / (factorial(r) * factorial(n - r)); return result; } void printPascalTriangle(int row) { for (int i = 0; i <= row; i++) { for (int j = 0; j <= i; j++) { cout << binomialCoefficient(i, j) << "\t"; } cout << endl; } } int main() { int n; cout << "Enter row number: "; cin >> n; printPascalTriangle(n); }
输出：
Enter row number: 9 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
Python Code 帕斯卡三角形的二项式系数
def factorial(n): result = 1 for i in range(1,n+1): result*=i return result def binomialCoefficient(n,r): result =1 if r>n: return None result = factorial(n) / (factorial(r) * factorial(n - r)) return int(result) def printPascalTriangle(row): for i in range(row+1): for j in range(i+1): print(binomialCoefficient(i, j), end="\t") print() # print(binomialCoefficient(3, 2)) n = int(input("Enter row number: ")) printPascalTriangle(n)
帕斯卡三角形示例输出：
Enter row number: 8 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
复杂度分析
此实现中使用了三个循环：一个用于计算二项式系数，另外两个用于遍历每一行和每一列。就行数而言，这三个循环最多运行“n”次。因此，整体时间复杂度为 O(n)。3).
由于我们不存储任何中间结果，因此空间复杂度为常数。程序实时计算每个元素并将其打印在一行中，因此空间复杂度降低为 O（1）.
方法 3：利用修正二项式系数构建帕斯卡三角形
在之前的方法中，我们使用二项式系数公式来计算每个元素。改进后的方法直接从 C(n, r-1) 推导出 C(n, r)，从而减少了一个数量级的计算量。
以下是利用修正二项式系数构建帕斯卡三角形的步骤：
步骤1） 第一行以“1”开头。
步骤2） 计算 C(n, r)，其中“n”是行号，“r”是列索引。将该值赋给变量 C。
步骤3） 要计算下一个系数，请使用 C * (n – k) / k。将此新值赋回 C。
步骤4） 重复步骤 3，直到“k”到达行尾。每次迭代后，将 k 加 1。
C++ Code 利用修正二项式系数求解帕斯卡三角形
#include <bits/stdc++.h> using namespace std; void printpascalTriangle(int n) { for (int row = 1; row <= n; row++) { int previous_coef = 1; for (int col = 1; col <= row; col++) { cout << previous_coef << "\t"; previous_coef = previous_coef * (row - col) / col; } cout << endl; } } int main() { int n; cout << "How many rows: "; cin >> n; printpascalTriangle(n); }
输出：
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python Code 利用修正二项式系数求解帕斯卡三角形
def printpascalTriangle(n): for row in range(1, n+1): previous_coef = 1 for col in range(1, row+1): print(previous_coef, end="\t") previous_coef = int(previous_coef*(row-col)/col) print() n = int(input("How many rows: ")) printpascalTriangle(n)
帕斯卡三角模式输出：
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
复杂度分析
该实现使用了两个循环，每个循环最多运行“n”次，其中“n”是三角形的行数。因此，时间复杂度为 上2)，平方时间。
就空间复杂度而言，我们不需要任何数组来存储。我们只使用一个变量来保存之前的二项式系数，因此只需要一个额外的空间。因此，空间复杂度为 O（1）.
帕斯卡三角形的应用
以下是帕斯卡三角形的一些实际应用：
二项式展开式： 任何二项式展开式的系数都可以直接从帕斯卡三角形中读出。例如：
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2坐标 + 1y2 |
| (x + y)3 | 1x3 + 3x2和+ 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3和+ 6x2y2 + 4xy3 + 1y4 |
计算组合： 帕斯卡三角形的元素与二项式系数直接对应。例如，如果你有 6 个球，想从中选出 3 个，答案是： 6C3你可以在帕斯卡三角形第六行的第三个元素中找到这个值。
可能性： 帕斯卡三角形广泛用于计算抛硬币、掷骰子问题和其他组合事件中的概率，其中每个结果都对应于二项分布。
关于帕斯卡三角形的有趣事实
以下是有关帕斯卡三角形的一些有趣的事实：
- 任意一行中所有元素的总和始终是 2 的幂。
- 各行的对角线和构成斐波那契数列。
- 每一行对应于 (a+b) 展开式中的系数n.
- 如果只给奇数部分涂上阴影，得到的图形就是谢尔宾斯基三角形分形。
