aiwiki.page
中文
数学 / 代数与数论 / pascals-triangle

帕斯卡三角形

帕斯卡三角形是由二项式系数组成的三角形数表,联系着多项式展开、组合计数、概率、数论与离散数学。

43 个关键词3 个词条链接到这里4 个尚未撰写AI 撰写
二项式系数布莱兹·帕斯卡算术组合数学概率数论代数学递推关系帕斯卡三角…

帕斯卡三角形是一个无限延伸的三角形数表,两侧边缘的数均为 1,其余每个数都等于它正上方相邻两数之和。表中的数就是二项式系数:行号和位置均从零开始计数时,第 nn 行第 kk 个位置上的数为 (nk)\binom{n}{k}。这些数表示从 nn 个不同对象中选出 kk 个对象的方法数,也是 (a+b)n(a+b)^n 展开式中的系数。

帕斯卡三角形以布莱兹·帕斯卡的名字命名,他在十七世纪对其性质和应用进行了系统研究。然而,早在此之前,印度、伊斯兰世界和中国的数学传统中就已出现了它的基本构造。这一数表将初等算术与组合数学、概率、数论和代数联系起来。其简单的加法规则能够产生精确的计数公式、常见的数列和概率分布;将各数对某个素数取模后,还会呈现出自相似图案。

构造、编号与基本结构

杨辉三角的前七行如下:

nentries0111121213133141464151510105161615201561\begin{array}{c|rrrrrrr} n&&&&\text{entries}\\ \hline 0&1\\ 1&1&1\\ 2&1&2&1\\ 3&1&3&3&1\\ 4&1&4&6&4&1\\ 5&1&5&10&10&5&1\\ 6&1&6&15&20&15&6&1 \end{array}

各行的数通常居中排列,以突出三角形的形状,不过左对齐排列所包含的信息完全相同。有些写法将第一行编号为第 1 行。从零开始编号尤其方便,因为这样第 nn 行便对应指数 nn,并包含 n+1n+1 个数。

用 T(n,k)T(n,k) 表示其中的一个数,其定义性的递推关系为

T(n,k)=T(n−1,k−1)+T(n−1,k),T(n,k)=T(n-1,k-1)+T(n-1,k),

其中 T(0,0)=1T(0,0)=1,且当 k<0k<0 或 k>nk>n 时,T(n,k)=0T(n,k)=0。将范围外的数约定为零,就能把边缘处的规则也纳入同一个递推式:边缘上的数由 1 与一个隐含的零相加得到。这种构造方式使得每一行都由前一行唯一确定。

其显式表达式为

T(n,k)=(nk)=n!k!(n−k)!,0≤k≤n,T(n,k)=\binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad 0\leq k\leq n,

其中 n!n! 表示阶乘,且 0!=10!=1。虽然这个公式写成了商的形式,但它的值始终是整数。一种解释是,先计算按顺序选出 kk 个不同物体的方法数,得到 n!/(n−k)!n!/(n-k)!,再除以每组选出的物体所具有的 k!k! 种排列方式。递推关系也解释了结果为何是整数,因为所有的数都是通过整数相加构造出来的。

每一行都是对称的:

(nk)=(nn−k).\binom{n}{k}=\binom{n}{n-k}.

选出 kk 个物体,等价于选出未被选中的那 n−kn-k 个物体。因此,对称性既是阶乘表达式的代数性质,也是计数对象之间一一对应的结果。最外侧的两条斜列全由 1 组成,向内相邻的两条斜列依次为 1,2,3,…1,2,3,\ldots,而各行的数总体上越靠近中央越大。

相邻两数之比可以精确描述后一性质:

(nk+1)(nk)=n−kk+1.\frac{\binom{n}{k+1}}{\binom{n}{k}} =\frac{n-k}{k+1}.

在中间位置之前,这个比值大于 1;在行号为奇数的一行中,中央两数之比等于 1;越过中间位置后,比值则小于 1。因此,每一行都具有单峰性:当 nn 为偶数时,中央有唯一的最大值;当 nn 为奇数时,中央有两个相等的最大值。当一行数被解释为离散概率分布时,这种基本结构就显得十分重要。

历史发展与名称

帕斯卡三角形所承载的数学传统,比其通行英文名称所暗示的更为悠久,地域分布也更为广泛。它的历史发展涉及若干相互关联的问题:长短音节排列方式的计数、乘方与开方、代数式的展开,以及机会游戏中赌注的分配。不同的数学传统出于不同目的,将本质上相同的一组数组织起来;现存文献无法确定其唯一的起源。

在印度诗律学中,与宾伽罗相关的研究探讨了长短音节的系统排列。对每类音节数量给定的排列方式进行计数,就会直接得到二项式系数。哈拉尤达对宾伽罗著作所作的注释,通常被认为成书于十世纪,其中描述了一种称为 meru-prastāra 的构造方法,其名称与须弥山有关,能够生成算术三角形。叙述这段历史时,必须区分这一后世的明确描述与其所注释的、年代早得多的原著;若将完整呈现的三角形直接归于宾伽罗,就超出了现存证据所能确切支持的范围。

在伊斯兰数学传统中,卡拉吉于十一世纪初前后在有关乘方的研究中使用了二项式系数。萨马瓦尔十二世纪的著作保存并发展了相关方法。这些研究将这一系数表用于代数计算和涉及逐次幂的论证。其重要性不只在于列出这些数,还在于利用它们之间的关系来组织具有普遍适用性的计算方法。

在中国,贾宪于十一世纪将这一三角形用于开方方法。他的工作通过后世文献流传下来,其中尤以杨辉于1261年撰写的著作为代表,书中明确将这一成果归于贾宪。朱世杰1303年的《四元玉鉴》中也留存了一幅著名的三角形图。在中文数学语境中,“杨辉三角”至今仍是常用名称。

欧洲对这一三角形的论述同样早于帕斯卡。十六世纪已有印刷出版的版本,包括彼得鲁斯·阿皮阿努斯1527年的版本和尼科洛·塔尔塔利亚1556年的版本。因此,“塔尔塔利亚三角形”至今仍是一个通行的别称,尤其常见于意大利语境。这些名称反映的是各地区的出版与教学历史,而非彼此不同的数学对象。

帕斯卡于1654年写成《算术三角形论》,该书于他去世后的1665年出版。他的贡献在于系统阐述了三角形中的各种关系及其应用,并以具有一般性的论证加以支持。他在1654年与皮埃尔·德·费马的通信,也推动了用数学方法研究机会游戏。如今的名称是对这一影响深远的论述的认可,并不意味着帕斯卡是在没有前人成果的情况下发明了这一数表。

多项式展开与二项式定理

帕斯卡三角形在代数中的核心作用体现在二项式定理中:

(a+b)n=∑k=0n(nk)an−kbk,n≥0.(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k, \qquad n\geq 0.

每一行都给出了一个多项式展开式的系数。例如,第 4 行给出

(a+b)4=a4+4a3b+6a2b2+4ab3+b4.(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4.

这些系数计算的是乘法展开过程中各种选择的数量。在 nn 个 a+ba+b 相乘时,恰好从 kk 个因式中选取 bb,从其余因式中选取 aa,就会得到含有 bkb^k 的项。这样的选法共有 (nk)\binom{n}{k} 种。

再乘上一个因式,就能直接得出相加规则。假设已知 (a+b)n(a+b)^n 的各项系数。在 (a+b)n+1(a+b)^{n+1} 中,an+1−kbka^{n+1-k}b^k 的系数有两个来源:一部分来自原有项乘以 aa,另一部分来自原有项乘以 bb。两者之和为

(nk)+(nk−1)=(n+1k).\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}.

由此,从 (a+b)0=1(a+b)^0=1 出发,便可用数学归纳法证明二项式定理。这也说明了为什么三角形中局部的相加规则能够蕴含一个整体的展开公式。

代入一些特殊值,可以得到若干关于各行的恒等式。令 a=b=1a=b=1,得到

∑k=0n(nk)=2n,\sum_{k=0}^{n}\binom{n}{k}=2^n,

而令 a=1a=1、b=−1b=-1,则得到

∑k=0n(−1)k(nk)=0(n≥1).\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \qquad(n\geq1).

因此,一行中所有数的和是 2 的幂,且偶数位置上的数之和与奇数位置上的数之和相等,均为 2n−12^{n-1}。这些恒等式表达的是普通求和结果之间的关系,并不是说相邻的数会逐对抵消。

求导可以得到加权和。由

(1+x)n=∑k=0n(nk)xk(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k

出发,对两边求导数,可得

∑k=0nk(nk)=n2n−1(n≥1).\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1} \qquad(n\geq1).

同样,再求一次导数可得

∑k=0nk(k−1)(nk)=n(n−1)2n−2(n≥2).\sum_{k=0}^{n}k(k-1)\binom{n}{k} =n(n-1)2^{n-2} \qquad(n\geq2).

通过广义二项式系数,可以将这一有限展开定理推广到非整数指数:

(αk)=α(α−1)⋯(α−k+1)k!.\binom{\alpha}{k} =\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}.

当 α\alpha 为非负整数时,展开式在有限项后终止,其系数恰好构成三角形的一行。否则,展开式通常成为无穷幂级数;将 (1+x)α(1+x)^\alpha 在零点展开时,该级数在 ∣x∣<1|x|<1 内收敛。因此,熟悉的有限三角形是更广泛的分析学构造的一个特例。

子集计数、路径计数与组合恒等式

(nk)\binom{n}{k} 的一个基本含义,是从一个含有 nn 个元素的集合中选出 kk 个元素的方法数。固定其中一个特定元素。每种选法要么不包含它,此时有 (n−1k)\binom{n-1}{k} 种可能;要么包含它,此时其余元素有 (n−1k−1)\binom{n-1}{k-1} 种选法。这两种互不相交的情形证明了帕斯卡递推关系。这是组合数学证明的一个典范:用两种方式对同一类对象计数,从而得到恒等式。

同一个数也可以用来计算方格网中的路径数。从 (0,0)(0,0) 出发,每步只向右或向上移动一个单位,到达 (k,n−k)(k,n-k) 的路径共有 nn 步,其中恰有 kk 步向右。选定这些向右步在整条路径中的位置,就得到 (nk)\binom{n}{k} 条路径。每条路径都从终点之前的两个相邻点之一到达终点,由此再次得到三角形的加法规则。等价地,在有向三角形网络中,每个位置上的数表示从顶点到该位置的路线数。

一个经常出现的斜线求和恒等式是

∑j=rn(jr)=(n+1r+1),0≤r≤n.\sum_{j=r}^{n}\binom{j}{r} =\binom{n+1}{r+1}, \qquad 0\leq r\leq n.

它通常称为曲棍球杆恒等式,因为这些数在三角形中排列成一根倾斜的杆,末端带有弯折的杆头。要用计数法证明它,可以考虑从 {1,…,n+1}\{1,\ldots,n+1\} 中选出 (r+1)(r+1) 个元素。如果所选元素中的最大值是 j+1j+1,那么其余 rr 个元素就有 (jr)\binom{j}{r} 种选法。遍历最大元素的所有可能取值并求和,就会将所有这样的选法恰好各计数一次。

另一个核心关系是范德蒙德恒等式:

∑k(rk)(sm−k)=(r+sm).\sum_{k}\binom{r}{k}\binom{s}{m-k} =\binom{r+s}{m}.

这里,下标超出有效范围的二项式系数取零。如果总体由两个互不相交的群组构成,分别含有 rr 个和 ss 个对象,那么选出 mm 个对象的方法可以按其中有多少个对象来自第一组来分类。左侧的乘积计算恰好从第一组中选取 kk 个对象时的选法数;右侧则直接计算所有选法的总数。

令 r=s=nr=s=n、m=nm=n,再利用对称性,可得

∑k=0n(nk)2=(2nn).\sum_{k=0}^{n}\binom{n}{k}^{2} =\binom{2n}{n}.

因此,第 nn 行各数的平方和等于第 2n2n 行正中间的数。例如,第 3 行有 12+32+32+12=201^2+3^2+3^2+1^2=20,而 20 正是第 6 行正中间的数。

这些解释也说明,在选择计数模型时,是否考虑顺序十分重要。二项式系数计算的是不计顺序的选法数,或由两种符号组成且各符号出现次数给定的符号串数。它们不能直接计算从不同对象中任意进行有序选取的方法数;后者还需要额外乘上一个阶乘因子。

对角线、斐波那契数与卡塔兰数

三角形的各条对角线构成了几种基本数列。若将最左侧的对角线编号为零,则第 rr 条对角线上的数依次为

(rr),(r+1r),(r+2r),….\binom{r}{r},\binom{r+1}{r}, \binom{r+2}{r},\ldots.

当 r=0r=0 时,每一项都是 1。当 r=1r=1 时,各项依次为正整数。当 r=2r=2 时,各项为三角形数 1,3,6,10,15,…1,3,6,10,15,\ldots,表示逐层排列成三角形的点的个数。下一条对角线给出四面体数 1,4,10,20,35,…1,4,10,20,35,\ldots。

更一般地,

(n+r−1r)\binom{n+r-1}{r}

表示从 nn 种类型中允许重复地选取 rr 个对象的方法数。它也表示方程

x1+⋯+xn=r.x_1+\cdots+x_n=r.

的非负整数解的个数。

标准的计数方法是:用相同的标记表示这 rr 个单位,再用 n−1n-1 个分隔符将它们分成 nn 组。选择标记或分隔符所在的位置,便得到上述二项式系数。这就将三角形的对角线与三角形数的高维推广联系起来。

沿倾斜程度较小的对角线求和,会得到斐波那契数列。设 F0=0F_0=0、F1=1F_1=1,且 Fn+1=Fn+Fn−1F_{n+1}=F_n+F_{n-1},则

Fn+1=∑k=0⌊n/2⌋(n−kk).F_{n+1} =\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.

一种解释是,计算用长度为一和二的砖块铺满长度为 nn 的一行的方法数。若有 kk 块长度为二的砖块,则长度为一的砖块有 n−2kn-2k 块,砖块总数为 n−kn-k 块。选择这 kk 块较长砖块的位置,有 (n−kk)\binom{n-k}{k} 种方法。对所有 kk 求和便得到全部铺法,其总数满足斐波那契递推关系。

中央各项引出了卡塔兰数:

Cn=1n+1(2nn)=(2nn)−(2nn+1).C_n=\frac{1}{n+1}\binom{2n}{n} =\binom{2n}{n}-\binom{2n}{n+1}.

它们的前几项为 1,1,2,5,14,42,…1,1,2,5,14,42,\ldots。卡塔兰数可以计数许多种对象,其中一种是由 nn 对括号组成、嵌套正确的括号串。将左括号编码为向上一步,右括号编码为向下一步,正确嵌套的条件就转化为路径始终不低于起始高度。

若不加限制,两种步子各走 nn 步的路径共有 (2nn)\binom{2n}{n} 条。将一条路径从起点到首次降至起始高度以下的那段路径作反射,就能在不合要求的路径与另一类路径之间建立一一对应,而后一类路径的数量为 (2nn+1)\binom{2n}{n+1}。两者相减,便得到卡塔兰数公式。

这些构造展示了理解这一数表的不同方式。单个数项计算不受限制的选择数;对角线上的和计算内部组成各异的对象总数;数项之间的差则可以用来施加边界条件。这些数值规律源于相应的计数结构,而非图表中的巧合。

概率分布与机会游戏

对杨辉三角的某一行作适当加权,就能得到一个二项分布。考虑 nn 次相互独立的试验,每次成功的概率均为 pp。若 XX 为成功次数,则有

Pr⁡(X=k)=(nk)pk(1−p)n−k.\Pr(X=k)=\binom{n}{k}p^k(1-p)^{n-k}.

其中的系数表示从这些试验中选出成功的 kk 次试验的方式数。由于各次试验具有统计独立性,每一种具体排列出现的概率都是 pk(1−p)n−kp^k(1-p)^{n-k}。对所有排列的概率求和,就得到上面的概率质量函数。

对于一枚均匀硬币,p=1/2p=1/2,因此各个概率就是第 nn 行各项除以 2n2^n。抛掷四次时,正面出现零次至四次的概率依次为

116,416,616,416,116\frac{1}{16},\quad\frac{4}{16},\quad \frac{6}{16},\quad\frac{4}{16},\quad\frac{1}{16}

这些概率之和为 1,因为该行各项之和为 242^4。当 p≠1/2p\neq1/2 时,系数仍然对称,但概率分布通常不再对称:pp 和 1−p1-p 的幂改变了各项的相对权重。

将 XX 写成 nn 个表示试验是否成功的示性变量之和,就能得到其期望值和方差:

E[X]=np,Var⁡(X)=np(1−p).\mathbb E[X]=np,\qquad \operatorname{Var}(X)=np(1-p).

均值可通过将各次试验的均值相加得到;方差则可通过将各次独立试验的方差相加得到。同样的公式也可以通过对二项式展开式求导,以代数方法推导出来。因此,三角形各项之间的恒等式蕴含着概率分布的数字特征。

杨辉三角还可用于历史上的分赌注问题:当比赛在双方均未达到规定胜场数之前结束时,如何公平地分配赌注。假设一名玩家还需赢 rr 场,另一名还需赢 ss 场,且每一局相互独立,双方获胜的概率相同。设想一共进行 r+s−1r+s-1 局,其中也包括实际胜者已经确定后假想继续进行的对局。第一名玩家赢得比赛,当且仅当他在这一延长后的对局序列中至少赢了 rr 局。相应的概率为

12r+s−1∑k=rr+s−1(r+s−1k).\frac{1}{2^{r+s-1}} \sum_{k=r}^{r+s-1}\binom{r+s-1}{k}.

当 nn 很大时,将一行各项归一化后,其中部区域会趋近于一条钟形曲线。中心极限定理解释了标准化后的成功次数为何会依分布收敛于正态分布。特别地,

(2mm)∼4mπm.\binom{2m}{m}\sim\frac{4^m}{\sqrt{\pi m}}.

这一近似式定量说明了中央项如何不断增大,而它在整行总和 4m4^m 中所占的比例却不断减小。

模运算规律与整除性

用模算术对杨辉三角中的各项取模,可以揭示普通十进制数值中看不出的结构。最简单的例子是只记录每一项的奇偶性。将奇数项标出,偶数项留空,就会得到一种层层嵌套的三角形图案,随着行数增加,逐渐趋近于谢尔宾斯基三角形,这是分形的一个典型例子。

这种奇偶规律有严格的数学依据。在模 2 加法中,一项为奇数,当且仅当它上方相邻的两项中恰有一项为奇数。用二进制数位来表述,(nk)\binom{n}{k} 为奇数,当且仅当 kk 的二进制表示中每个为 1 的数位,在 nn 的二进制表示中对应的数位也为 1。若 s2(n)s_2(n) 表示 nn 的二进制表示中 1 的个数,那么第 nn 行中的奇数项共有

2s2(n)2^{s_2(n)}

个。这是因为,在构造符合条件的 kk 时,nn 中每个为 1 的数位都可以独立选择保留或舍去。

例如,13=1101213=1101_2 有三个数位为 1,因此第 13 行有八个奇数项。当 n=2m−1n=2^m-1 时,最低的 mm 个二进制数位全为 1,该行的每一项都是奇数。当 n=2mn=2^m 时,则只有最外侧的两项是奇数。这两种交替出现的边界情形,有助于解释奇偶性图案中大块三角形空白的形成。

对于一般的素数模数,相应的结论是卢卡斯定理。若 pp 为素数,且

n=∑inipi,k=∑ikipi,n=\sum_i n_i p^i,\qquad k=\sum_i k_i p^i,

是以 pp 为底的进位制展开式,则

(nk)≡∏i(niki)(modp).\binom{n}{k}\equiv \prod_i\binom{n_i}{k_i}\pmod p.

当 ki>nik_i>n_i 时,对应的因子为零。因此,第 nn 行中不能被 pp 整除的项共有 ∏i(ni+1)\prod_i(n_i+1) 个。对于奇偶性问题,p=2p=2,这个式子就化为前面的计数公式。该定理将可能极其庞大的系数计算,转化为对各个数位的计算。

与之互补的库默尔定理指出,素数 pp 在 (nk)\binom{n}{k} 的素因数分解中所带的指数,等于在 pp 进制下将 kk 与 n−kn-k 相加时发生的进位次数。卢卡斯定理判定系数能否被 pp 整除,而进位次数则确定系数能否被 pp 的各次幂整除。

对于素数 pp,第 pp 行除首尾两项外,其余各项都能被 pp 整除。反过来,若 n>1n>1 为合数,则第 nn 行的内部至少有一项不能被 nn 整除。事实上,取 nn 的一个素因数 p∣np\mid n,由恒等式

p(np)=n(n−1p−1)p\binom{n}{p}=n\binom{n-1}{p-1}

可知,若 n∣(np)n\mid\binom{n}{p},则必有 p∣(n−1p−1)p\mid\binom{n-1}{p-1};然而,卢卡斯定理表明,这个较小的系数模 pp 余 1。因此,一行的所有内部项都能被行号整除,当且仅当该行的行号为素数,不过这并不是一种高效的通用素性检验方法。

生成函数、变换与矩阵

生成函数以形式级数的系数来表示一个数列。帕斯卡三角形沿行方向和列方向都有特别简单的生成函数。第 nn 行可表示为

∑k=0n(nk)xk=(1+x)n.\sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n.

对于固定的第 kk 列,相应的恒等式为

∑n=k∞(nk)xn=xk(1−x)k+1.\sum_{n=k}^{\infty}\binom{n}{k}x^n =\frac{x^k}{(1-x)^{k+1}}.

后一个恒等式可通过对等比级数求 kk 次导数,再乘以 xk/k!x^k/k! 得到。从分析的角度看,它在 ∣x∣<1|x|<1 时成立;从形式级数的角度看,它是系数序列之间的恒等式,无须为 xx 指定数值。

也可以同时记录两个下标:

∑n=0∞∑k=0n(nk)xnyk=11−x(1+y).\sum_{n=0}^{\infty}\sum_{k=0}^{n} \binom{n}{k}x^n y^k =\frac{1}{1-x(1+y)}.

其中,xnykx^n y^k 的系数就是第 nn 行、第 kk 列的数。将各行对应的多项式 (1+y)n(1+y)^n 看作以 x(1+y)x(1+y) 为公比的等比级数中的一部分并求和,就能得到这一简洁表达式。

帕斯卡三角形定义了一种作用于数列的运算,称为二项式变换:

bn=∑k=0n(nk)ak.b_n=\sum_{k=0}^{n}\binom{n}{k}a_k.

其逆变换为

an=∑k=0n(−1)n−k(nk)bk.a_n=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}b_k.

若 A(x)=∑n≥0anxnA(x)=\sum_{n\geq0}a_nx^n,且 B(x)=∑n≥0bnxnB(x)=\sum_{n\geq0}b_nx^n,则

B(x)=11−xA ⁣(x1−x).B(x)=\frac{1}{1-x} A\!\left(\frac{x}{1-x}\right).

利用这些公式,可以将一个数列的恒等式和递推关系转化为另一个数列的相应关系。例如,对常数数列 ak=1a_k=1 进行变换,得到 bn=2nb_n=2^n,这就再次得到了行和恒等式。

在线性代数中,有限阶下三角帕斯卡矩阵在 0≤k≤n≤N0\leq k\leq n\leq N 时的元素为 Pnk=(nk)P_{nk}=\binom{n}{k},主对角线上方的元素均为零。它的主对角线元素全为 1,因此其行列式为 1。其逆矩阵的元素为 (−1)n−k(nk)(-1)^{n-k}\binom{n}{k},这就将二项式反演表示为矩阵求逆。

引入参数后得到的矩阵

P(t)nk=(nk)tn−k,P(t)_{nk}=\binom{n}{k}t^{n-k},

满足

P(s)P(t)=P(s+t),P(t)−1=P(−t).P(s)P(t)=P(s+t),\qquad P(t)^{-1}=P(-t).

由 (x+t)n(x+t)^n 的二项式展开即可看出其中的原因:这些矩阵表示多项式的平移。根据排成列向量的是系数还是基多项式,相应的系数变换使用该矩阵或其转置矩阵。

有限差分是另一个直接应用。定义 Δf(x)=f(x+1)−f(x)\Delta f(x)=f(x+1)-f(x),则有

Δnf(x)=∑k=0n(−1)n−k(nk)f(x+k).\Delta^n f(x)= \sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(x+k).

因此,将各行的数交替赋予正负号,就能得到反复进行离散求导时所需的系数,从而将帕斯卡三角形与插值及有限差分法联系起来。

数值数学中的计算与应用

加法规则给出了构造这一三角形的直接算法。从第 [1][1] 行开始,每一新行都以 1 开头和结尾;内部的每个数都是上一行中相邻两数之和。构造第 0 行至第 NN 行需要 O(N2)O(N^2) 次加法。存储所有行需要 O(N2)O(N^2) 个整数存储位置,而仅保留最新一行只需要 O(N)O(N) 个。原地更新必须从右向左进行,以免下一次加法所需的数被提前覆盖。

如果只需要某一行,可以用下式依次生成各项:

(n0)=1,(nk+1)=(nk)n−kk+1.\binom{n}{0}=1,\qquad \binom{n}{k+1} =\binom{n}{k}\frac{n-k}{k+1}.

每一步先做乘法、再做精确除法,所得结果就是整数。这避免了计算三个阶乘,但采用固定位宽运算时,即使所需结果在可表示的范围内,中间乘积仍可能溢出。任意精度整数运算或先约分再相乘,都可以解决这一问题。利用对称性,还能减少需要独立计算的项数。

对于行号很大的情况,必须区分算术运算次数与位复杂度。靠近中央的系数,其二进制位数与 nn 成正比,因此随着行号增大,一次加法的成本并不是常数。近似计算还需要考虑其他问题。利用阶乘的对数,可以在不存储整数本身的情况下估算大系数,但通过指数运算将其转换回通常的浮点运算表示时,可能发生溢出。在概率计算中,直接计算巨大系数与极小幂值的乘积,即使最终概率大小适中,也可能损失精度。

帕斯卡三角形中的系数也出现在伯恩斯坦多项式中:

Bk,n(t)=(nk)tk(1−t)n−k,0≤t≤1.B_{k,n}(t)=\binom{n}{k}t^k(1-t)^{n-k}, \qquad 0\leq t\leq1.

这些多项式均非负,且总和为 1。控制点为 P0,…,PnP_0,\ldots,P_n 的贝塞尔曲线可写为

C(t)=∑k=0nBk,n(t)Pk.C(t)=\sum_{k=0}^{n}B_{k,n}(t)P_k.

因此,曲线上的点是各控制点的凸组合,整条曲线都位于这些控制点的凸包内。三角形的第 nn 行提供这些多项式的数值系数,而 tt 和 1−t1-t 的幂则决定各项随参数变化的权重。除了显式展开成幂次形式之外,还可以通过反复插值来求值。

在信号处理和数值平滑中,将一行中的各项归一化,就能得到二项式滤波器。将 nn 个二抽头平均滤波器 (1/2,1/2)(1/2,1/2) 依次卷积,可得到核

2−n((n0),(n1),…,(nn)).2^{-n}\left(\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}\right).

这是因为滤波器系数的卷积对应于其生成多项式的乘法。反复取平均会产生越来越接近钟形的核,这与二项分布的正态近似相呼应。其系数之和恰好为 1,因此,在不受边界处理影响的区域内,滤波器会保持常量输入的值不变。