卡特兰数相关及通项公式简单证明
卡特兰数有两个递推公式，两个通项公式（或者说是⼀个）：
规定,
⽤折线法证明通项公式：
点即为第⼀次⾛过的点，绿线和黄线组成了⼀条⾮法的路径
现在按照对称，则绿线和蓝线构成了另⼀条路径
蓝线和黄线总是⼀⼀对应的，⽽蓝线⾛到的点总是从原点到的⽅案数就是，得出通项公式
其他
h (0)=1h (1)=1
h =n h h i =0∑n −1i n −i
h =n h n −1n +14n −2h =n C −2n n C 2n n −1h =n n +1
二叉树公式C 2n
n
L y =x y =x +1(n −1,n +1)A ′C 2n n −1
卡特兰数还代表着什么出栈⼊栈⽅案数，⼆叉树构成⽅案数，在这就不写了，有兴趣可以去别的博客看卡特兰数的渐进增长：奇数卡特兰数满⾜（注意是第⼏项的项数）
前⼏项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796，注意从第零项开始
图⽚来源：n 23π
4n h n n =2−k 1(k =0,)n

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。