

卡特兰数

Catalan 数列¶

以下问题属于 Catalan 数列：

有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
一个栈（无穷大）的进栈序列为 $1,2,3, \cdots ,n$ 有多少个不同的出栈序列？
$n$ 个结点可够造多少个不同的二叉树？
$n$ 个不同的数依次进栈，求不同的出栈结果的种数？
$n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2, \cdots ,a_{2n}$ ，其部分和满足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 对与 $n$ 该数列为？

其对应的序列为：

$H_0$	$H_1$	$H_2$	$H_3$	$H_4$	$H_5$	$H_6$	...
1	1	2	5	14	42	132	...

(Catalan 数列）

递推式¶

该递推关系的解为：

$H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})$

关于 Catalan 数的常见公式：

$H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}$

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

$H_n = \binom{2n}{n} - \binom{2n}{n-1}$

例题洛谷 P1044 栈

题目大意：入栈顺序为 $1,2,\ldots ,n$ ，求所有可能的出栈顺序的总数。

#include <iostream>
using namespace std;
int n;
long long f[25];
int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见公式2
  cout << f[n] << endl;
  return 0;
}

路径计数问题¶

非降路径是指只能向上或向右走的路径。

从 $(0,0)$ 到 $(m,n)$ 的非降路径数等于 $m$ 个 $x$ 和 $n$ 个 $y$ 的排列数，即 ${n + m \choose 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$ 的非降路径数。

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

用类似的方法可以得到： $\frac{2}{n+1} {2n \choose n}$

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

卡特兰数

Catalan 数列¶

递推式¶

路径计数问题¶

评论