卡特兰数
以下四种公式都表示卡特兰数。
其中，公式二可以从第 \(0\) 项开始推导。公式四计算时间复杂度为 \(O(n^2)\)，其余为 \(O(n)\)。
根据题目数据范围、是否取模选择合适的计算方法，其中公式一二四最为常用。
进出栈问题
给定一个序列 \(1,2,\dots n\)，数字依次进栈，可自由选择时机出栈。问出栈序列有多少种可能的情况。
不妨把进栈操作视为左括号，出栈操作视为右括号，这样就得到了一个长度为 \(2n\) 的括号序列。现在要求，对于此序列任意前缀，都有左括号数量 \(\ge\) 右括号数量。
首先你需要选择 \(n\) 个括号作为左括号，总方案数 \(\dbinom{2n}{n}\)。
接着考虑减去不合法情况。对于任意一个不合法的括号序列，我们找到他第一个右括号数量 \(>\) 左括号数量的前缀。如此序列：
())()(())(
第一个不合法位置是 \(3\)。我们在此位置分割序列，观察前后括号数量。
()) | ()(())(
我们设左侧有 \(k\) 个右括号，那么右侧就有 \(n-k\) 个右括号。
此时左侧有 \(k-1\) 个左括号，右侧有 \(n-(k-1)\) 个左括号。
注意到左侧的左括号数量 \(+\) 右侧的右括号数量恒为 \(n-1\)，左侧的右括号数量 \(+\) 右侧的左括号数量恒为 \(n+1\)。
那么我们考虑把右侧的左右括号反转，这样就形成了一个有 \(n-1\) 个左括号，\(n+1\) 个右括号的序列。
()) | )())(()
容易证明，以这种方法转换形成的序列与所有原不合法操作序列一一对应。
因此不合法的方案数为从 \(2n\) 个位置里选 \(n-1\) 个放左括号，\(\dbinom{2n}{n-1}\)。
答案就是 \(\dbinom{2n}{n}-\dbinom{2n}{n-1}\)，与卡特兰数公式一一致。
这个问题还可以换一些问法。
比如买票问题：票价 \(5\) 元，有 \(n\) 个游客带了 \(5\) 元，\(n\) 个旅客带了 \(10\) 元，售票员起始 \(0\) 元，问有多少种合法的购票序列。
注意到如果要给 \(10\) 元旅客找零，就必须要剩下至少 \(5\) 元，也就是有一个 \(5\) 元旅客买过票。于是问题等价。
以及：给定 \(n\) 个 \(1\) 和 \(n\) 个 \(-1\)，问有多少种排列方式使得任意前缀和不小于零。显然等价。
还有下面这个。
Luogu P1375 小猫
圆上有 \(2n\) 个点，点之间两两连线，问有多少种连法使得线不交叉。
首先给点顺时针编上号，按编号从小到大处理，发现不能回连，也就是必须得连当前最后一个没连的，否则会连到两个已连过点之间的点上造成交叉。
然后是被两个连接点包含的必须得有偶数个点，让他们内部配对。也即奇连偶，偶连奇。
那我们把奇数从小到大依次进栈，偶数从小到大依次视作出栈，当前出栈的奇数就与当前偶数配对连线。与连线方案一一对应。所以答案即为卡特兰数。