卡特兰数
考虑以下问题：
现在我们有\(n+1\)个数，\(x_0,x_1,x_2,\cdots,x_n\)，考虑它们的乘积\(x_1\cdot x_2\cdots x_n\)，现在我们可以在其中插入括号来改变计算顺序。那么一共有多少种排列的顺序呢？比如说，现在有三个数\(x_0, x_1, x_2\)，它们的计算顺序有\((x_0x_1)x_2\)以及\(x_0(x_1x_2)\)两种排列方式
问题分析
我们可以使用递归的思想来考虑这个问题。我们把这\(n+1\)个数分为两组，在第\(k\)个数处分开，就形成了下面\(A, B\)两组数。
\[ \underbrace{(x_0\space x_1\space x_2 \cdots x_k)}_{A} ,\underbrace{(\space x_{k+1}\cdots x_{n-1}\space x_{n})}_{B} \]
我们记\(n+1\)个数的插入括号后的计算顺序个数为\(C_n\)，那么\(A\)的计算顺序个数就是\(C_k\)，\(B\)的就是\(C_{n-k-1}\)。所以说，如果说我们把最后一个括号放在第\(k\)个数的地方，那么我们总的个数就是\(C_kC_{n-k-1}\)。这里\(k\)可以从0到\(n-1\)，根据加法原则，
\[ C_n=\sum^{n-1}_{k=0}C_kC_{n-k-1}, \space\space\space\space n\geqslant 1 \]
剩下的事情就是用数学方法计算出这个数列的通项公式。
数学解法
通过生成函数法(generating function)可以解出符合方法一中递推公式的数列的通项公式。
首先我们定义函数
\[ f(x)=\sum_{k\geqslant0}C_kx^k \]
然后我们可以将上面的递推公式推广到\(n\geqslant0\)，也就是
\[ C_n=\sum_{k\geqslant0}C_kC_{n-k-1}+\mathbb{I}_{\{n=0\}}, \space\space\space\space \forall n\geqslant0 \]
其中\(\mathbb{I}_{\{n=0\}}\)是示意函数(indicator function)，当\(n=0\)时此函数值为1，否则值为0。并且我们定义当\(k<0\)时，\(C_k=0\)。等式两边同乘我们可以得到
\[ \begin{aligned} f(x)& = \sum_{n\geqslant0}C_nx^n =\sum_{n\geqslant0}C_kC_{n-k-1}x^n+\mathbb{I}_{\{n=0\}}x^n \\ & = \sum_{n\geqslant0}\sum_{k\geqslant0}C_kC_{n-k-1}x^kx^{n-k}+1 \\ & = \sum_{k\geqslant0}\Big[C_kx^k\sum_{n\geqslant0}C_{n-k-1}x^{n-k-1}\cdot x\Big]+1 \\ \end{aligned} \]
我们对\(n-k+1\)进行一个换元之后，式子中的\(\sum_{n\geqslant0}C_{n-k-1}x^{n-k-1}\)可以写成\(\sum_{j\geqslant0}Cjx^j\)，也就是\(f(x)\)，所以我们得到
\[ \begin{aligned} f(x)& =\sum_{k\geqslant0}C_kx^kf(x)x+1 \\ & =x\big(f(x)\big)^2+1 \\ \Longrightarrow f(x)& =\frac{1\pm\sqrt{1-4x}}{2x} \end{aligned} \]
通过观察，由于\(f(x)=C_0+C_1x+C_2x^2+\cdots\)并且\(f(0)=C_0=1\)，可以推断出这里我们需要取减号。接下来计算\((1-4x)^{\frac{1}{2}}\)
\[ \begin{aligned} (1-4x)^{\frac{1}{2}} & =\sum_{k\geqslant0}\tbinom{\frac{1}{2}}{k}(-4x)^k \space\space\space\space |x|<\frac{1}{4}\\ & = 1+\sum_{k\geqslant1}(-1)^k\tbinom{\frac{1}{2}}{k}4^kx^k \end{aligned} \]
通过广义二项式定理，我们可以进一步化简
\[ \begin{aligned} \tbinom{\frac{1}{2}}{k}& =\frac{\frac{1}{2}(\frac{1}{2}-1)\cdots(\frac{1}{2}-k+1)}{k!} \\ & = \frac{1}{2k}\cdot\frac{(-\frac{1}{2})(-\frac{3}{2})\cdots(-\frac{1}{2}-(k-1)+1)}{(k-1)!} \\ & = \frac{1}{2k}\cdot(-\frac{1}{2})^{k-1}\cdot\frac{1\cdot3\cdots(2k-3)}{(k-1)!} \\ & = \frac{1}{2k}\cdot(-\frac{1}{2})^{k-1}\cdot\frac{1\cdot2\cdot3\cdot4\cdots(2k-3)\cdot(2k-2)}{2^{k-1}(k-1)!(k-1)!} \\ & =\frac{1}{2k}\cdot(-\frac{1}{4})^{k-1}\cdot\tbinom{2k-2}{k-1} \end{aligned} \]
代入上述式子可得
\[ \begin{aligned} (1-4x)^{\frac{1}{2}}& =1-\sum_{k\geqslant1}\frac{1}{2k}\tbinom{2k-2}{k-1}\cdot4\cdot x^k \\ & =1-2x\sum_{k\geqslant0}\frac{1}{k+1}\tbinom{2k}{k}x^k \end{aligned} \]
最后把这个式子代回到\(f(x)\)的表达式中去，我们可以得到
\[ f(x)=\sum_{k\geqslant0}\frac{1}{k+1}\tbinom{2k}{k}x^k \]
与\(f(x)=\sum_{k\geqslant0}C_kx^k\)进行对比我们可以得出结论
\[ C_n=\frac{1}{n+1}\tbinom{2n}{n} \]
这就是卡特兰数(Catalan Number)
卡特兰数的其他等价问题
Dyck word的个数. Dyck word表示一个有由\(n\)个X和\(n\)个Y组成的字符串，并且需要满足：在任意一个位置，之前的X个数都必须大于等于Y的个数。
这里可以给出一个卡特兰数简单的计算方法
首先不考虑限制条件，那么总共的排列方式有\(\tbinom{2n}{n}\)种，然后考虑不满足题目限制的个数。假设在第\(2m+1\)处有\(m+1\)个Y和\(m\)个X(不满足题目要求)，那么后面就有\(n-m\)个X和\(n-m-1\)个Y，将这里的X全部替换为Y，Y全部替换为X，那么这样的字符串就变成了由\(n-1\)个X和\(n+1\)个Y组成的字符串。这样的字符串总数是\(\tbinom{2n}{n+1}\)，所以总数是
\[ \tbinom{2n}{n}-\tbinom{2n}{n+1}=\frac{1}{n+1}\tbinom{2n}{n} \]
包含n组括号的合法运算式的个数。
不相交的弦问题：在一个圆周上分布着\(2n\)个点，要求在每两个点之间连接一条弦，并 且弦与弦不能相交，求这样的连接方式个数。
格路问题：所有在\(n\times n\)格点中不越过对角线的单调路径的个数。可以等价于计算Dyck word的个数(X代表“向右”，Y表示向右)
参考资料
维基百科, https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
卡特兰数（Catalan number）（一）,https://zhuanlan.zhihu.com/p/31317307