[toc]

卡特兰数

公式一 递归公式



推导：

视频链接：https://www.bilibili.com/video/BV1nE411A7ST?from=search&seid=7193588783915104419

公式二、三 组合数通项公式


推导：
下图中，表示从 (0,0)(0,0) 走到 (n,n)(n,n) 的路径，在绿线及以下表示合法，若触碰红线即不合法。
avatar
图片来源：https://www.acwing.com/solution/acwing/content/8907/
详细推导过程可参考：https://www.cnblogs.com/zyt1253679098/p/9190217.html

公式四 递推公式

推导：
可参考 https://www.cnblogs.com/zyt1253679098/p/9190217.html