论杨辉三角

Dijkstra_zyl · 2025-11-26 13:55:39 · 算法·理论

1.杨辉三角的定义与构造

杨辉三角，又称帕斯卡三角，是一个无限对称的三角形数阵，其构造遵循以下规则：

1.边界条件： 第\ n\ 行（n \geq 0，从0开始计数）有\ n+1\ 个数，首位均为\ 1，即\ C(n,0) = C(n,n) = 1；

2.递推关系： 中间第\ k\ 个数（1 \leq k \leq n-1）等于上一行第\ k-1\ 个数与第\ k\ 个数只和，即

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

其中\ C(n,k)\ 表示从\ n\ 个元素中取\ k\ 个数的组合数。

以下是杨辉三角的一部分

杨辉三角的第\ n\ 行恰好是二项式\ (a+b)^n\ 展开式的系数。根据二项式定理：

(a+b)^n=\sum_{k=0}^{n}C(n,k)a^{n-k}b^k

证明: 数学归纳法

基例：\ n=0\ 时，(a+b)^0=1=C(0,0)，成立。
归纳假设：设\ (a+b)^{n-1}=\sum_{k=0}^{n-1}C(n-1,k)a^{n-1-k}b^k。
归纳步骤：
\begin{aligned} (a+b)^n &= (a+b)(a+b)^{n-1}\\ &= a\sum_{k=0}^{n-1}C(n-1,k)a^{n-1-k}b^k+b\sum_{k=0}^{n-1}C(n-1,k)a^{n-1-k}b^k\\ &= \sum_{k=0}^{n-1}C(n-1,k)a^{n-k}b^k+\sum_{k=0}^{n-1}C(n-1,k)a^{n-1-k}b^{k+1}\\ &= C(n-1,0)a^n+\sum_{k=1}^{n-1}[C(n-1,k-1)+C(n-1,k)]a^{n-k}b^k+C(n-1,n-1)b^n\\ &= \sum_{k=0}^{n}C(n,k)a^{n-k}b^k \end{aligned}
故等式成立。

性质：C(n,k)=C(n,n-k)。

证明：由组合数公式

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

显然两者相等

性质：第\ n\ 行所有数之和为\ 2^n，即\ \sum_{k=0}^{n}C(n,k)=2^n。

证明：在二项式定理中令\ a=1,b=1，得

(1+1)^n=\sum_{k=0}^{n}C(n,k)1^{n-k}1^k \implies 2^n = \sum_{k=0}^nC(n,k)

性质1（自然数序列）：第2条斜线（从左起，不含首尾1）为\ C(n,1)=n(n \geq 1)。

证明：由组合公式\ C(n,1)=\frac{n!}{1!(n-1)!}=n。

性质2（三角形序列）：第3条斜线为\ C(n,2)=\frac{n(n-1)}2 （n \geq 2），即\ 1,3,6,10,...（三角数）。

证明：C(n,2)=\frac{n(n-1)}2

The\ End