卡特兰数列

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

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

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

$$Cat_n={2n\choose n}÷(n+1)={2n\choose n}-{2n\choose n-1}$$

$$Cat_n=\sum_{i=0}^{n-1}Cat_i\cdot Cat_{n-i+1}$$