看到“合法嵌套、不能越界、左右递归划分、固定顺序进出”时，优先想到卡特兰数。
C_n =
(2n)!(n+1)! * n!
常用值：C_0=1，C_1=1，C_2=2，C_3=5，C_4=14，C_5=42，C_6=132。
卡特兰数不是简单排列数。它通常在“每一步都必须合法”的计数中出现。
例如括号序列中，任意前缀里的右括号不能多于左括号；路径问题中，任意时刻不能越过对角线；栈问题中，出栈前必须已经入栈。
有 n 个结点时，不同二叉树结构的数量是 C_n。
n=33 个结点的二叉树形态共有 C_3=5 种：
n 个不同元素按固定顺序入栈，问有多少种合法出栈序列，答案是 C_n。
1,2,3 依次入栈合法出栈序列共有 C_3=5 种：
312 不合法，因为 3 要先出栈时，1、2 已经被压在它下面，无法再按 1、2 的顺序出来。
n 对括号能组成多少种合法括号序列，答案是 C_n。
n=33 对括号的合法序列共有 C_3=5 种：
一个凸 n+2 边形，用不相交对角线划分成三角形的方法数是 C_n。
五边形是 n+2=5，所以 n=3。三角剖分数量为 C_3=5。
按顶点 A,B,C,D,E 顺时针编号，5 种三角剖分完整列出如下：
AC, AD三角形：ABC、ACD、ADE
AC, CE三角形：ABC、ACE、CDE
AD, BD三角形：ABD、BCD、ADE
BD, BE三角形：ABE、BCD、BDE
BE, CE三角形：ABE、BCE、CDE
从 (0,0) 到 (n,n)，每步向右或向上，且不越过主对角线的路径数是 C_n。
n=3用 R 表示向右，U 表示向上，合法路径共有 C_3=5 种：
RRRUUU
RRURUU
RRUURU
RURRUU
RURURU
用 1~n 这 n 个不同关键字，可以组成多少种不同形态的二叉搜索树，答案是 C_n。
1,2,3不同二叉搜索树共有 C_3=5 种，完整列出如下：