求解\(Catalan(n)\)的四个公式：
- \[f(n) = C_{2n}^{n} - C_{2n}^{n-1} \]
- \[f(n) = C_{2n}^{n}/(n + 1) \]
- \[f(n) = f(n - 1) * (4n-2) / (n + 1) \]
- \[f(n) = \sum_{i=0}^{n-1}f(i)*f(n - 1 - i) \]
\(Catalan(n)\)的相关应用（简记为\(C_n\)）：
- 栈混洗\(->\) \(C_n\)
- \(n\)对括号组成的合法括号序列\(->\) \(C_n\)
- 含有\(n\)个节点的二叉树的形态数 -> \(C_n\)（利用公式4，划分为根节点和左右子树，递归计算）
- 含有\(n+1\)个叶节点的满二叉树（每个节点要么无子节点，要么有两个子节点）的形态数 \(->\) \(C_n\) （将\(n+1\)个叶节点去掉，就等价于3，所以3的每种方案补充上外结点就对应4的一种方案）
- 圆上\(2n\)个点，连\(n\)条线段，要求任意两条线段互不相交的方案数（编号为\(1,2,...,2n\)，奇编号看做左括号，偶编号看做右括号）\(->\) \(C_n\)
- 正方形中，从\((0,0)\)到\((n,n)\)，每次只能向上或向右走一步，只能在对角线的下半侧移动:
- 能碰对角线 \(->\) \(C_n\)
- 不能碰对角线 \(->\) \(C_{n-1}\)
- 将\(n+2\)条边的凸多边形通过顶点连线，划分成若干三角形，且连续不能相交\(->\) \(C_n\)（利用公式4）