卡塔兰数

定义

卡特兰数是一个数列

通项公式为

$$\begin{array}{c}{C}_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)n\in N\end{array}$$

卡塔兰数有三种计算方式

$$\begin{array}{rl}通项公式：C_n& =\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{2n}{n-1}\right)\\ & \\ 递推公式：C_n& =C_0{C}_{n-1}+C_1{C}_{n-2}+\cdot \cdot \cdot +C_{n-2}{C}_1+C_{n-1}{C}_0=\sum _{k=0}^{n-1}{C}_k{C}_{n-1-k},C_0=1\\ & \\ 快速公式：C_n& =\frac{4n-2}{n+1}{C}_{n-1},C_0=1\end{array}$$

应用场景： 栈混洗 n 个括号能构成的合法表达式 $n$ 个节点的二叉树形态 $n$ 个互异节点的 $BST$ 种类 $n$ 个叶节点的真二叉树种类（度要么为0，要么为2）

场景	答案
n 对括号合法表达式	$C_n$
n 个节点的二叉树形态	$C_n$​
n 个互异节点的 BST	$C_n$
n 个叶节点的真二叉树	$C_{n-1}$​
栈混洗（n 个元素）	$C_n$​

---

栈混洗

对于给定数值为 $n$ 的一个数列，求其出栈顺序？

求解步骤：

1. 确定 操作步骤数
2. 根据 不同步骤 进行排列组合
3. 得出答案

具体求解

分析

给定的 $n$ 个数，从入栈到出栈，一定有且仅有 $2n$ 次操作，故共有 $C_{2n}^n$ 种可能，但是
其中含有不合法的可能。

计算不合法的可能个数 需要利用 折线原理 进行几何分析

在折线图中只有 右上 和 右下 两个操作，对应的就是 入栈和出栈。

如图所示，当折线达到 $y=-1$ ，则该折线一定代表违法操作。

1. 随意假设第 $x_0$ 个操作时折线刚好到达 $y=-1$ ，设该点为 $A$ , 终点为 $B$;

2. 又因为 从 $A$ 到 $B$ 的折线数，由于对称，在图中可以改为由 $A$ 到 $C$ 的折线数。

3. 再回到全局中去看，因为从原点 $O$ 到点 $C$ 是一定经过 $y=-1$ 这条线的，故不用管 $A$ 的位置

4. 因此，求解 违法操作数 等价于 求从原点 $O$ 到 点 $C$ 的 所有折线数： $C_{2n}^{n-1}$

5. 最后可以计算出：一个 $n$ 位序列，从入栈到出栈，具有 $C_{2n}^n-C_{2n}^{n-1}$ 中可能

$Catalan(n)=\frac{C_{2n}^n}{n+1}$

视频解析

折线原理

Catalan数的应用和证明

好题，非常适合用 折线定理