# 卡特兰数可以解决的问题

• $2n$ 个人排队进入剧场，入场费 $5$ 元。其中只有 $n$ 个人有 $5$ 元的钞票，另外 $n$ 个人只有 $10$ 元的钞票，问有多少种合法的，能够完成买票 - 找钱的合法排队序列？
• 有一个 $n \times n$ 的方格图，从 $(0,0)$ 走到 $(n,n)$. 每次只能向右或者向上走一单位，不能走过对角线 y = x ，问有多少种方法？
• 在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
• $n$ 个结点可以构造多少个不同的二叉树？
• $......$

# 卡特兰数的前几项序列

# 卡特兰数的计算公式

以 $n$ 个结点构成的不同的二叉树为例。
$H_0 = 1$，显然，$0$ 个结点只有一种情况。
$H_1 = 1$，显然，$1$ 个结点只有一种情况。
$H_2 = H_0 \times H_1 + H_1 \times H_0 = 2$，确定根结点之后，左 $0$ 右 $1$ / 左 $1$ 右 $0$
$H_3 = H_0 \times H_2 + H_1 \times H_1 + H_2 \times H_0 = 5$
$....$ 以此类推，得到通项公式

$${H_0} = {H_1} = {1},~{H_n} = {\sum\limits_{i=1}^{n}H_{i-1}H_{n-i},~({n} \ge {2})}$$

这里再给出一些关于卡特兰数的常见公式：

$${H_n} = \frac{H_{n-1}(4n-2)}{n+1}$$

$${H_n} = {C_{2n}^{n}} - {C_{2n}^{n-1}}$$

$${H_n}={\frac{C_{2n}^{n}}{n+1}},~(n \ge {2})$$