卡特兰数/Catalan

问题

$n$ 对括号 () 构成的序列，求满足括号合法匹配的排列数量。

设 $a_i$ 表示由 $i$ 对括号组成的匹配排列的数量，显然 $a_1 = 1$ ，从下面的递推式分析中可以看出 $a_0$ 起到了乘法幺元的作用，故令 $a_0 = 1$ 。

对于由 $n$ 对括号组成的排列，考虑与首位 ( 匹配的 ) 的位置，其左右各有一个长度更短的匹配序列，递推式为

$a_n = \sum_{i=0}^{n-1} a_i a_{n - 1 - i}$

如此可以在 $O(n^2)$ 的时间内得到结果。

在这个问题中，数列 ${a_1, a_2, ...}$ 称为 Catalan数列 。

通项 $a_n$ 称为 Catalan数

上述递推关系的解为：

$a_0 = a_1 = 1$

$a_n = \frac{C_{2n}^n}{n+1} (n \geq 2, n \in \mathbb{N}_+)$

$a_n = \begin{cases} \sum_{i=1}^{n} a_{i-1} a_{n-i} & n \geq 2, n \in \mathbb{N_{+}}\ 1 & n = 0, 1 \end{cases}$

$a_n = \frac{a_{n-1} (4n-2)}{n+1}$

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

买票找零： $2n$ 个人买票，票价 $50$ ，其中 $n$ 个人手中握有 $100$ 元钞票， $n$ 个人手中握有 $50$ 元钞票。假设开始时售票处没有零钱，请问有多少种排队方式可以避免出现找不开钱的问题？
$n$ 个节点可构造多少个不同的二叉树
多边形划分成三角形的问题：求一个凸多边形区域划分成三角形区域的方法数
- 类似题目：圆上的 $2n$ 个点，成对连接得到 $n$ 条线段不想交，求可行的方法数
路径计数问题：

考虑非降路径

从 $(0, 0)$ 到 $(m, n)$ 的非降路径数等于 $m$ 个 $x$ 和 $n$ 个 $y$ 的排列数，即 $C_{n + m}^m$
从 $0, 0$ 到 $n, n$ 的除端点外不接触直线 $y = x$ 的非降路径数：

先考虑 $y=x$ 下方的路径，都是从 $(0, 0)$ 出发，经过 $(1, 0)$ 及 $(n, n-1)$ 到 $(n,n)$ ，可以看做是 $(1,0)$ 到 $(n,n-1)$ 不接触 $y=x$ 的非降路径数。

所有的的非降路径有 $C_{2n-2}^{n-1}$ 条。对于这里面任意一条接触了 $y=x$ 的路径，可以把它最后离开这条线的点到 $(1,0)$ 之间的部分关于 $y=x$ 对称变换，就得到从 $(0,1)$ 到 $(n,n-1)$ 的一条非降路径。反之也成立。从而 $y=x$ 下方的非降路径数是 $C_{2n-2}^{n-1} - C_{2n-2}^n$ 。根据对称性可知所求答案为 $2(C_{2n-2}^{n-1} - C_{2n-2}^n)$ 。