问长度为 2n 的括号序列有多少个.

　　以 ( 的数量为 x 轴, ) 的数量为 y 轴, 建立坐标系.

　　初始状态对应 (0, 0) .

　　假设当前在 (x, y) , 如果下一位为 ( , 那么转移到 (x, y) + (1, 0) , 否则转移到 (x, y) + (0, 1) .

　　现在要求不超过 y = x 的从 (0, 0) 到 (n, n) 的路径数.

　　我们考虑用从 (0, 0) 到 (n, n) 的总的路径数, 减去非法的路径数.

　　总的路径数为 $\binom{2n}{n}$ .

　　对于非法的路径数, 我们要经过 y = x+1 , 考虑作轴对称, (0, 0) 对应 (-1, 1) , 即求 (-1, 1) 到 (n, n) 的总的路径数, 即为 $\binom{2n}{n-1}$ .

　　答案为 $$\binom{2n}{n} - \binom{2n}{n-1} = \frac{(2n)!}{n!n!} - \frac{(2n)!n}{n!n!(n+1)} = \frac{\binom{2n}{n}}{n+1}$$ .

　　所以它是卡特兰数的第 n 项 $C_n = \frac{\binom{2n}{n}}{n+1}$ .

括号序列计数 数形结合 卡特兰数