前言

卡特兰数是初赛中比较重要的数学知识，所以写篇博客总结一下。

定义

用 \(C_n\) 表示从 \((0,0)\) 出发，每次只能向右或向上走 1 步，且 \(x\) 轴的值始终不小于 \(y\) 轴的值，到 \((n,n)\)的方案种数。

通项+证明

\[C_n=\dfrac{1}{n+1}\left(\begin{matrix}2n \\ n\end{matrix}\right) \]

证明：

不考虑越过线的情况的话显然有 \(\left(\begin{matrix}2n \\ n\end{matrix}\right)\) 种情况。

考虑非法的情况，令直线 \(l:y=x+1\)，那么每一个非法的方案都与 \(l\) 有至少 1 个交点。

对于每一个方案，我们取 \(x\) 值最小且在 \(l\) 上的点记为 \(p(x_1,y_1)\)，将 \(x>x_1,y\leq x\) 的点沿 \(l\) 对称，那么就变为从 \((0,0)\) 到 \((n-1,n+1)\) 的路径了，显然是一个映射，所以有 \(\left(\begin{matrix}2n \\ {n-1}\end{matrix}\right)\) 种非法方案。

所以 \(C_n=\left(\begin{matrix}2n \\ n\end{matrix}\right) - \left(\begin{matrix}2n \\ {n-1}\end{matrix}\right)\)。

化简

\[\begin{aligned} C_n=&\left(\begin{matrix}2n \\ n\end{matrix}\right) - \left(\begin{matrix}2n \\ {n-1}\end{matrix}\right) \\ =&\dfrac{(2n)!}{n!\cdot n!}-\dfrac{(2n)!}{(n-1)!\cdot (n+1)!}\\ =&(2n)!\cdot\bigg[\dfrac{(n+1)-n}{n!\cdot (n+1)!}\bigg]\\ =&\dfrac{1}{n+1}\left(\begin{matrix}2n \\ n\end{matrix}\right) \end{aligned} \]

应用

1. \(n\) 对括号的合法配对方案书
2. \(n\) 个节点的二叉树的形态数
3. \(n+1\) 个叶子（\(n\) 个非叶节点）的满二叉树的形态数, 走到左儿子 \(+1\),走到 右儿子 \(-1\),类似于括号匹配(大致同2)
4. \(n\) 个数入栈后出栈的排列总数
5. 对凸 \(n+2\) 边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交)
6. \(n\) 层的阶梯切割为 \(n\) 个矩形的切法数

转自 https://www.cnblogs.com/linzhengmin/p/11298140.html。