定义：

  1. 长度为 $2n$ 的合法括号序列数量
  2. 二维平面上只能向右或向上走，不经过直线 $y=x+1$ 的方案数

有递推式

$$C_n=\begin{cases}1& (n=0) \
\sum\limits_{i=0}^{n-1}C_iC_{n-i-1} &otherwise\
\end{cases}$$
这个式子可以理解为在后方新增一个括号，形成类似 ...(...) 的结构

有通项公式

$$C_n=C_{2n}^{n}-C_{2n}^{n-1}$$
可以用 [[反射容斥]] 来搞

进阶：卡特兰数的自卷积

设 $F$ 表示卡特兰数生成函数

那么根据上边的递推式有

$$\begin{eqnarray}F&=&1+xF^2\
F&=&\frac{1-\sqrt{1-4x}}{2x}\
\end{eqnarray}$$

对于 $[x^n]F^m$ ，我们可以考虑他的组合意义：在 $m$ 个有序箱子中，存储 $m$ 个合法括号串，使得括号串的总左括号数为 $n$

我们可以考虑他的组合意义，先构造一个大括号串 ((())) ，满足共有 $n$ 个左括号，考虑在其中插入括号序列，形成 (((...)...)...) 的结构，发现其与每种合法填空方式形成双射，故在其中插入括号串即可

而这个前缀的 $m$ 个左括号，则可以理解为在坐标轴上先向右移动了 $m$ 步，照常反射容斥即可

然后就做完了

详见：[[2025.2.5#T3]]