卡特兰数：
其对应序列为：
| \(H_0\) | \(H_1\) | \(H_2\) | \(H_3\) | \(H_4\) | \(H_5\) | \(H_6\) | \(H_7\) | \(\cdots\) | \(H_n\) |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | \(\cdots\) | \(\frac{C_{2n}^n}{n+1}\) |
- \( H_n\begin{cases} \sum_{i=1}^nH_{i-1}\times H_{n-i}\ n\geq2,n\in\mathbb{N_{+}}\\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n=0,1 \end{cases} \)
- \(H_n=\frac{H_{n-1}\ \times(4n-2)}{n+1}\)
- \(H_n=C_{2n}^n-C_{2n}^{n-1}\)
对于一下问题属于 Catalan 数列：
\(1\).给定 \(n\) 个 \(0\) 和 \(n\) 个 \(1\)，排成的长度为 \(2n\) 的序列，满足任意前缀序列中 \(0\) 的个数都不少于 \(1\) 的个数的序列有多少个。(将 \(01\) 序列置于坐标系中，起点定于原点。若 \(0\) 表示向右走，\(1\) 表示向上走，路径上的任意一点，横坐标大于等于纵坐标的合法路径数量。)
\(2\).一个栈的进栈序列为 \(1,2,3, \cdots ,n\) 有多少个不同的出栈序列？
将进栈视为 \(0\) ，将出栈视为 \(1\) ，则与第一个问题相同，故答案为 \(Cat_n\)
\(3\).\(n\) 个节点，可以构造多少不同二叉树？
标签：Cat,cdots,序列,2n,times,卡特兰 From： https://www.cnblogs.com/programmingysx/p/18280425设 \(f(n)\) 为 \(n\) 个节点构成的不同二叉树的数量。
该问题答案为 不同情况下左子树的方案数 \(\times\) 对应右子树的方案数 的和。
即 \(f(n)=f(0)\times f(n-1)+f(1)\times f(n-2)+\cdots+f(n-1)\times f(0)\)
会发现 \(f(n)=\sum_{i=1}^nf(i-1)\times f(n-i)\) ，与 \(Cat_n\) 的递推式相同，故答案为 \(Cat_n\) 。