卡特兰数
2026-05-13
简介
卡特兰数 Cn 的递推定义如下:
Cn={1,∑i=0n−1CiCn−1−i,n=0,n>0.
封闭形式与展开
注意到若 n>0,则 Cn=∑i=0n−1CiCn−1−i 这个式子满足离散卷积定义,也就是说,这个函数生成函数内部发生了自身相乘,将自身卷积序列写出:
C(x)2=n=0∑∞(i=0∑nCiCn−i)xn=n=0∑∞Cn+1xn
将其两边同时乘以 x 并构造一元二次方程,得到 xC(x)2−C(x)+1=0,利用求根公式后发现需要取负号(正号会导致分子趋近于 2,分母趋近于 0 从而无穷大),进而有:
C(x)=2x1−1−4x
这就是卡特兰数的封闭形式,将其利用广义二项式定理展开后,可以得到:
Cn=n+11(n2n)
这就是其通项公式。
其他形式
- 利用递推式和通项公式,将 Cn 与 Cn−1 对比,可以得到:
Cn=Cn−1⋅n+14n−2
- 从路径计数问题,可以得到:
Cn=(n2n)−(n+12n)
