$$$$

INFO

若无特殊说明，本章涉及的变量皆为正整数。

简介

卡特兰数列同时是许多看似毫不相关的问题的解。

• $n$ 个节点能构成 ${\mathrm{Cat}}_n$ 种不同的二叉树；
• $n$ 个左括号和 $n$ 个右括号组成的合法序列有 ${\mathrm{Cat}}_n$ 种；
• $n$ 个元素的进栈顺序为 $1,2,\cdots ,n$，合法的出栈顺序有 ${\mathrm{Cat}}_n$ 种；
• 在圆上选择 $2n$ 个点成对连接，使得 $n$ 条线段不相交的方法数为 ${\mathrm{Cat}}_n$；
• 通过若干条互不相交的对角线,把凸 $n$ 边形拆分成若干个三角形的方案数为 ${\mathrm{Cat}}_{n-2}$；
• 在平面直角坐标系上，每一步只能向上或向右走 $1$ 个单位，从 $(0,0)$ 走到 $(n,n)$ 且不接触直线 $y=x$ 的路径数量为 $2{\mathrm{Cat}}_n-1$。

通项公式

$${\mathrm{Cat}}_n=(\genfrac{}{}{0ex}{}{2n}{n})÷(n+1)=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n-1})$$

递推公式

$${\mathrm{Cat}}_n=\sum _{i=0}^{n-1}{\mathrm{Cat}}_i\cdot {\mathrm{Cat}}_{n-i+1}$$

附表

${\mathrm{Cat}}_0$	${\mathrm{Cat}}_1$	${\mathrm{Cat}}_2$	${\mathrm{Cat}}_3$	${\mathrm{Cat}}_4$	${\mathrm{Cat}}_5$	${\mathrm{Cat}}_6$	${\mathrm{Cat}}_7$	${\mathrm{Cat}}_8$	$\cdots$
$1$	$1$	$2$	$5$	$14$	$42$	$132$	$429$	$1430$	$\cdots$