外观
一条格路走出来的恒等式
这题的式子长成那样,第一反应肯定是“拆成奇偶两段然后递推”。
确实能递推出来。但递推完总觉得哪里不对劲:这个 2 是从哪冒出来的?
后来想明白了——它就藏在一条格路里。
问题
设 n 为非负整数,求
k=0∑n2⌊(n−k)/2⌋C⌊(n+k)/2⌋⌊(n−k)/2⌋
的值。
注
Cmr 表示从 m 个东西里选 r 个的方案数。原题里 C 的上标被吞了,这里补上;漏掉上标会得到另外一个和,而且没什么意思。
人类注
原题里 C 的上标没被吞,是 k。这和 AI 推断出的 ⌊(n−k)/2⌋ 是等价的。
答案是 2n。下面给两种证法,一种老老实实递推,一种让一条随机格路替我们数。
递推法
记
Sn=k=0∑n2⌊(n−k)/2⌋C⌊(n+k)/2⌋⌊(n−k)/2⌋.
关键是把求和项按 k 与 n 的奇偶关系劈成两半。
拆分
令
A(n)=j≥0∑2jCn−jj,
(约定 r>m 或 r<0 时 Cmr=0),则对一切 n≥1 有
Sn=A(n)+A(n−1).
证明
当 k≡n(mod2) 时,写 k=n−2j。此时 ⌊2n−k⌋=j 且 ⌊2n+k⌋=n−j,对应 A(n) 的一项 2jCn−jj。
当 k≡n(mod2) 时,写 k=n−2j−1。此时两处取整分别是 j 与 n−j−1,对应 A(n−1) 的一项 2jCn−j−1j。
两段合起来即得。□
接下来用 Pascal 递推式把 A 的系数拆开:
A(n)=j≥0∑2j(Cn−j−1j+Cn−j−1j−1)=A(n−1)+2A(n−2).
于是对 n≥2,
Sn=A(n)+A(n−1)=2A(n−1)+2A(n−2)=2(A(n−1)+A(n−2))=2Sn−1.
初值 S0=1、S1=2,归纳即得
Sn=2n.
(顺便一提,A(n)=A(n−1)+2A(n−2) 的特征根是 2 与 −1,解出 A(n)=32n+1+(−1)n,代回 Sn=A(n)+A(n−1) 也直接得到 2n。这个式子待会儿还要用。)
概率法
递推法好看,但它没解释那个 2 的来历。换个角度:让一条格路替我们数。
铺路
在第一象限从原点出发,每一步以 21 的概率向右走 (x,y)→(x+1,y),以 21 的概率向上走 (x,y)→(x,y+1)。走满 n 步,一共 2n 条等概率的路径。
盯住 s=x+2y:每向右一步 s 加 1,每向上一步 s 加 2。起点 s=0,走完 n 步之后 s∈[n,2n],而且 s 严格单调递增。于是每条路径都恰好穿过一次直线
ℓ: x+2y=n.
穿过的方式只有两种:
- 踩线:路径落在 ℓ 上的某个格点 (x,y);
- 跨线:路径走“上”这一步时从 s=n−1 跳到 s=n+1,从直线中间穿过去。
把这 2n 条路径按穿过的横坐标 k 分类,k 从 0 到 n。
数路径
主引理
穿过横坐标为 k 的路径恰有
2⌊(n−k)/2⌋C⌊(n+k)/2⌋⌊(n−k)/2⌋
条。
证明
分 n−k 的奇偶讨论。
n−k 为偶数,记 j=2n−k,于是 k+2j=n。此时路径只能踩线,且踩在格点 (k,j) 上。到达 (k,j) 有两种走法:
- 越过直线的那一步是“右”:前缀是一条走到 (k−1,j) 的路径,共 Ck+j−1j 条;
- 越过直线的那一步是“上”:前缀是一条走到 (k,j−1) 的路径,共 Ck+j−1j−1 条。
两种情况下越过之后都还剩 n−k−j=j 步自由走,每步两种走法。于是共
2j(Ck+j−1j+Ck+j−1j−1)=2jCk+jj
条。
n−k 为奇数,记 j=2n−k−1,于是 k+2j=n−1。此时踩线是不可能的(踩线要求 k+2j′=n,而 n−k 是奇数),路径只能跨线:先走到 (k,j),再走一步“上”跳过直线。走到 (k,j) 的路径有 Ck+jj 条,跳过之后还剩 n−k−j−1=j 步自由走。于是共
2jCk+jj
条。
两种情形里 j=⌊2n−k⌋ 且 k+j=⌊2n+k⌋,引理得证。□
结论
每条路径恰好穿过 ℓ 一次,按穿过的横坐标把 2n 条路径分成 n+1 类,第 k 类的大小由主引理给出,于是
k=0∑n2⌊(n−k)/2⌋C⌊(n+k)/2⌋⌊(n−k)/2⌋=2n.
注意两种证法其实是同一回事:递推法里按 k≡n(mod2) 劈开的那两段,恰好就是概率法里“踩线”与“跨线”两类路径。奇偶性只是 x+2y 的取值被 2 整除与否的另一种说法。
验证
主引理说“穿过横坐标为 k”是一个可以穷举检验的命题。枚举所有 2n 条路径、数出每条路径穿过直线的横坐标,再和公式对照:
Code
from itertools import product
from math import comb
def C(m, r):
return comb(m, r) if m >= 0 and 0 <= r <= m else 0
def summand(n, k):
return 2 ** ((n - k) // 2) * C((n + k) // 2, (n - k) // 2)
def cross_x(n, steps):
"""返回路径穿过 x + 2y = n 时的横坐标"""
x = y = 0
for s in steps:
if s == "R":
x += 1
else:
y += 1
if x + 2 * y >= n:
return x
return None
for n in range(1, 11):
cnt = {}
for steps in product("RU", repeat=n):
k = cross_x(n, steps)
cnt[k] = cnt.get(k, 0) + 1
assert all(cnt.get(k, 0) == summand(n, k) for k in range(n + 1)), n
assert sum(cnt.values()) == 2 ** n
print(n, [cnt.get(k, 0) for k in range(n + 1)])输出(n=4 时各类的路径数)是 [4,4,6,1,1],和 (4,4,6,1,1) 逐项吻合。
推广
概率法的视角比递推法好用得多,因为它把“和”翻译成了“事件”。顺着这个思路可以推广出两件事。
踩线与跨线的比例
上面的计数其实把 2n 条路径又切了一刀:踩线的有 A(n) 条,跨线的有 A(n−1) 条。由递推法算出的闭式,
A(n)=32n+1+(−1)n,A(n−1)=32n−(−1)n.
所以随机取一条 n 步格路,它恰好落在直线 x+2y=n 上的概率是
3⋅2n2n+1+(−1)n⟶32,
而跨过直线的概率趋于 31。
n 越大,这个比例越接近 2:1。
把斜率换成 c
把直线换成
ℓc: x+cy=n(c 为正整数),
路径与分类方式都不变。落在直线上的格点 (x,y) 满足 x+cy=n。停在 (x,y) 的路径数为
(Cx+y−1y+Cx+y−1y−1)2n−x−y=Cx+yy2n−x−y,
其中两项分别是最后一步走“右”与走“上”的贡献,剩下的 n−x−y 步自由走。于是踩线的路径总数是
Tc(n)=y=0∑⌊n/c⌋2(c−1)yCn−(c−1)yy,
其余 2n−Tc(n) 条路径跨过直线。
这个数有个漂亮的递推:
Tc(n)=Tc(n−1)+2c−1Tc(n−c).
因为它正是长度为 n 的一维长条用“1 格方块”与“c 格长条(带 2c−1 种颜色)”的铺法数——长条占 c 格、方块占 1 格,若用了 y 根长条则占 cy 格,剩下的格子填方块,总块数 n−(c−1)y,从中挑出 y 个位置放长条,再给每根长条挑颜色。
几个特例:
- c=1:T1(n)=2n,所有路径都踩线,恒等式退化成二项式定理 ∑kCnk=2n;
- c=2:回到本文,T2(n)=32n+1+(−1)n;
- c 越大,能踩线的格点越稀疏,跨线的路径占比越高。
最后一条其实是废话,但补一句:c=2 之所以特殊,是因为上一步的增量 2 恰好等于组合数里的那个 2——巧合得让人怀疑是刻意设计的。
结语
回头看,这个恒等式的两种证法其实是同一个计数的两种语言:递推法把和拆成两段,概率法把路径分成两类,两边都是“踩线”与“跨线”。
而 2 从哪来?它就是“每一步都有两种走法”。整件事的起点不过是:一条 n 步的格路有 2n 条,而每条都会穿过 x+2y=n 一次。
这就完了。