卡特兰数

Summary

卡特兰数 C_n 计数一大类看似不同、实则同构的组合结构：合法的括号序列、栈的出栈序列、不越过对角线的格点路径、n 个节点的不同二叉树形态、凸多边形的三角剖分等，它们的方案数都由同一列数给出。文中列出其通项与递推——通项可写成 1/(n+1) 乘以组合数 C(2n,n)，也等于 C(2n,n) 减去 C(2n,n-1)，并有卷积形式的递推式把 C_{n+1} 用前面各项表出。前几项依次为 1、1、2、5、14、42、132，据此可在遇到一个计数结果时快速判断它是否落在卡特兰数列上。

参考资料

• 卡特兰数 - OI Wiki

简介

卡特兰数 $C_n$ 计数一大类结构：合法括号序列、出栈序列、不越过对角线的格路、$n$ 个节点的二叉树形态、凸多边形三角剖分等。

通项与递推：

$$C_n=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1},\quad C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}$$

前几项为 $1,1,2,5,14,42,132,\dots$。

例题

洛谷 P1044 [NOIP 2003 普及组] 栈

将 $1\sim n$ 依次入栈，可在任意时刻出栈，求能得到的出栈序列总数，即卡特兰数 $C_n$。