基本介绍

定义

引入-括号模型

举个例子，有什么 n 个左括号和 n 个右括号，求能够配对出多少个合法的完整括号范式。
怎么样算合法呢？对于每个前缀，右括号的数量不超过左括号。

我们的思路是“正难则反”。我们用总的方法数减去不合法的方法数就是合法的方法数。
总的方法数：$C_{2n}^n$。总共有 2 n 个位置，我们从中选 n 个位置给左括号，剩下的放右括号。

什么情况不合法？一定存在一个前缀使得右括号的数量比左括号多一个。
再考虑一个问题：
怎么定义两个可数集合元素数量相等？找到两个单射函数，使得 A 对应 B （一对一），B 一对一 A。
定义集合 B，为 $n+1$ 个右括号和 $n-1$ 个左括号能够组合成的任何一个样子。
定义集合 A，为不合法的括号组合集合。

我们找到右括号比左括号对一个位置的，反转后面所有的括号，我们会发现 A 正好可以一一对应 B 集合。而 B 集合也一定通过一定的变换一一转化为 A 集合。所以 $\left|A\right|=\left|B\right|$。
不合法的数量：$C_{2n}^{n+1}=C_{2n}^{n-1}$。
合法的数量为：$C_{2n}^n-C_{2n}^{n-1}$。这就是卡特兰数的通项公式。