本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551802.html

卡特兰数

博客园的 LaTeX\LaTeX 好容易炸啊

设 f(1)=1f(1)=1，则 ：

f(n)=∑i=0n−1(f(i)×f(n−i−1))f(n)=\sum_{i=0}^{n-1}(f(i)\times f(n-i-1))

当然，也有两个通用公式：

f(n)=C2nnn+1f(n)=\frac{C_{2n}^n}{n+1}\\

f(n)=C2nn−C2nn−1f(n)=C_{2n}^n-C_{2n}^{n-1}

更奇怪的递推公式：

f(n)=f(n−1)×4×n−2n+1f(n)=f(n-1)\times \frac{4\times n-2}{n+1}

其中，CnmC_n^m 表示：

Cnm=Anmm!=n!m!(n−m)!=Cnn−mC_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}=C_n^{n-m}

此处给出卡特兰数的前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

常见应用：

  1. 二叉树形态问题
  2. 三角形划分问题

只要看到有题目分析之后满足卡特兰数前几项或者满足卡特兰数的任意一项公式，就可以用卡特兰数解决。