从数学家布莱斯·帕斯卡著名的三角形中提取的二项式系数有几个优雅的性质。当然,它们在组合分析中是有用的,通常是必要的,但它们的作用远不止于此。有些性质利用对称性,有些涉及膨胀,但它们都可以相当直观地证明。我们先来看二项式系数最原始的形式帕斯卡三角。
1
11
121
13.3.1
14641
15101051
。。。
从上图中我们可以看出,构造的基本规则是
(kn)+(k+1n)=(k+1n+1)。
我们有
(kn)+(k+1n)====k!((n−k)!)n!+(k+1)!(n−(k+1))!n!(k+1)!(n−k)!(k+1)n!+(n−k)n!(k+1)!(n−k)!(n+1)!(k+1n+1)。□
或者,换句话说,两个相邻的二项式系数的和等于它下面的一个,假设帕斯卡三角形是上面所示的等边三角形形状。另一个重要的身份是
(kn)=(n−kn)。
我们有
(kn)=k!(n−k)!n!=(n−(n−k))!(n−k)!n!=(n−kn)。□
这说明帕斯卡三角形的每一行在两种情况下都是对称的。它要么是回文的,要么是面向中心的(甚至
n),或者回文和“镜像”,即三角形一边的所有数字都复制到另一边(对于奇数)
n).
固定行二项式系数的和
n等于2的幂。的确,
k=0∑n(kn)=2n,
可以很容易地显示出来
2n=(1+1)n=(0n)(1)n(1)0+(1n)(1)n−1(1)1+⋯+(nn)(1)0(1)n=k=0∑n(kn)。
沿着类似的思路,我将演示一个更一般、更迷人的性质,关于二项式系数相对于它们的指标的加权和:
k=0∑nk(kn)=n2n−1。
首先,我们注意到这个和的样子:
0(0n)+1(1n)+2(2n)+3.(3.n)+⋯+n(nn)。
第一项是零,我们把求和写成
k=1∑nk(kn)=n2n−1。
利用这个公式来计算二项式系数,我们得到
k(kn)=k(k!(n−k)!n!)=k((k)(k−1)(k−2)⋯(2)(1)(n)(n−1)(n−2)⋯(n−k+1))=n((k−1)(k−2)⋯(2)(1)(n−1)(n−2)⋯(n−k+1))=n((k−1)(k−2)⋯(2)(1)(n−1)(n−2)⋯((n−1)−(k−1)+1)),
这对我们很有利,因为我们有一个固定的
n。我们终于可以这么说了
k=1∑nk(kn)=k=1∑nn(k−1n−1)=nk=1∑n(k−1n−1)。
根据我们之前对二项式系数和的定义
nk=1∑n(k−1n−1)=nk=0∑n−1(kn−1)=n2n−1。
现在有趣的事情来了。二项系数在固定行上的交替和
n=
0。更正式,
(0n)−(1n)+(2n)−(3.n)+⋯+(−1)n(nn)=k=0∑n(−1)k(kn)=0。
由此可见,
0=(1−1)n=(0n)(1)n(−1)0+(1n)(1)n−1(−1)1+⋯+(nn)(1)0(−1)n。
让
αe等于行中所有偶数项的和
n,让
αo等于一行中所有奇数项的和
n。我们之前的方程可以表示为
αe−αo=0⟹αe=αo。
因为行中所有偶数项的和
n然后是行中所有奇指标项的和
n相等,它们对这一行的总和贡献相同的量,
2n。因此,如果我们省略偶数项或奇数项,我们将恰好得到原来总数的一半。因此,我们可以说
k=0∑n(2kn)=k=0∑n(2k+1n)=22n=2n−1。
人们可能还会注意到帕斯卡三角中隐藏着一个熟悉的序列。
(2n)代表了
(n−1)th三角形数
Tn=2(n+1)(n)。如果你对这个序列不熟悉,在这里是一个让你开始的链接!这个证明利用了一些事实
(1n)=n,(22)=1=T1,
假设所有人
n≥2,
(2n)=Tn−1(2n+1)=Tn=2(n)(n−1)=2(n+1)(n),
它在归纳法下成立。我们可以通过查看帕斯卡三角形并使用我们的构建指南来直观地验证这一点:
(kn)+(k+1n)=(k+1n+1)。
现在,如果你知道三角数的知识,你可以这么说
(2n)2=j=1∑n−1(1j)3.。
这就留给读者自己去证明了,但如果你卡住了,这是证据的链接。
一个更直观的特性是Sierpiński筛,它是通过对每个二项式系数取模2得到的。这个过程将每个二项式系数按宇称分离。如果每个奇数都被替换成一个黑色的三角形,一个谢尔宾斯基三角形就开始形成。自己试试吧!这也适用于卢卡斯对应定理,它留给读者进一步学习去发现。