Catalan数

Catalan数一瞥

关于Catalan，这是一个特殊的数列，可以方便求解许多问题。

这里，先给出Catalan数的通项公式，再举例进行进一步的分析：Cat_n = \frac{1}{n+1}C_{2n}^n。 先分析它的递推关系：

题目：在一个有n+2条边的多边形中，我们可以画出n-1条不相交的对角线将多边形分为n个三角形，设所有满足条件的方案数是h_n，定义h_0=1，求h_2、h_4、h_4。

分析：由题意，我们知道，有n+2条边的多边形，就相当于有n+2个点。我们又知道，因为每个点都通向两外两个相邻的点，那么，与它不相交的点就有n个点。给你们画张图就知道了。此时，n=4。（如下图）。

现在，我们知道，与它不相交的点有n个。那我们来帮助理解一下，什么叫做n-1条不相交对角线。

这是一种方案。

这也是一种方案。

那么，我们可以得到，每次在我们连接完一条不相交的对角线后，我们会发现，这条对角线把当前图行分割成了2部分。那我们设其中一块有k+2条边(这样我们就可以得到k个三角形）。同理，另一块图形我们会得到n-1-k个三角形。因为乘法原理，这样剖分的方案数就为

h_{k} * h_{n-1-k}

（其中n为三角形的总数量，看前面n的介绍）。

显然，k可以从0一直变化到n-1（注意，考虑边界情况，并注意到这里的对角线不相交，所以这里不会出现重复计数）。

所以，递推式为h_{n}=\sum_{k=0}^{n-1} h_{k} * h_{n-1-k} 。

这个数列就是著名的Catalan数列。

现在，我们将这玩意整成我们熟悉的带有组合数的通项公式：h_n = \frac{1}{n+1}C_{2n}^n 需要用到一点点生成函数：

我们很容易写出上文h_n 的生成函数

g(x)=h_{1} x+h_{2} x^{2}+\ldots+h_{n} x^{n}+\ldots

我们进一步计算

[g(x)]^{2}=h_{1}^{2} x^{2}+\left(h_{1} h_{2}+h_{2} h_{1}\right) x^{3}+\left(h_{1} h_{3}+h_{2} h_{2}+h_{3} h_{1}\right) x^{4}+\ldots+\left(h_{1} h_{n-1}+h_{2} h_{n-2}+\ldots+h_{n-1} h_{1}\right) x^{n}+\ldots

因为有：h_{n}=h_{1} h_{n-1}+h_{2} h_{n-2}+\ldots+h_{n-1} h_{1} ，所以进一步得到： [g(x)]^{2}=h_{1}^{2} x^{2}+h_{3} x^{3}+h_{4} x^{4}+\ldots+h_{n} x^{n}+\ldots ，由于h_{1}=h_{2}=1

所以有：[g(x)]^{2}=g(x)-h_{1} x=g(x)-x ，解之得到：g(x)=\frac{1-\sqrt{1-4 x}}{2}=\frac{1}{2}-\frac{1}{2}(1-4 x)^{1 / 2} ，另一个解不符合，舍去。

那么根据牛顿二项式有：

(1+z)^{1 / 2}=1+\sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n \times 2^{2 n-1}}\left(\begin{array}{c} 2 n-2 \\ n-1 \end{array}\right) z^{n}

那么带入化简得到：

(1-4 x)^{1 / 2}=1-2 \sum_{n=1}^{\infty} \frac{1}{n}\left(\begin{array}{c} 2 n-2 \\ n-1 \end{array}\right) x^{n}

那么我们最终得到：

g(x)=\sum_{n=1}^{\infty} \frac{1}{n}\left(\begin{array}{c} 2 n-2 \\ n-1 \end{array}\right) x^{n}

所以：，

h_{n}=\frac{1}{n+1} C_{2 n}^{n}

这就是Catalan的推导过程。 另一种方式看一看Catalan数：

题目：我们有n个+1和n个-1，将它们排列起来，其中任何长度的前缀和都大于等于0。问，有几种排列方案？、

这时，答案h_{n}=\frac{1}{n+1} C_{2 n}^{n} 。

解释：我们设A_n表示满足条件的排列数的个数。再设U_n表示不满足条件即任何长度的前缀和有一个或多个前缀和答案小于0。那么由组合数定义我们可以知道：A_{n}+U_{n}=C_{2 n}^{n} 。

接下来，我们试图求出U_n 。

根据题目定义，我们先设k满足某些前缀和小于0，且这个k必须要保证最小。

那么我们可以知道，前k个数中-1的数量肯定比+1的数量多1，换句话说，前k-1个数中+1和-1的数量是相等的且是符合要求的。

那么，我们根据k的定义可以知道，k是一个正奇整数（-1的数量比+1多1），且第k个数必须是-1，这样才能保证k最小。

那么，我们将前k个数取反（每一个数1变0或者0变1），就可以得到有n+1个+1和n-1个-1（因为前k个数中-1的数量比+1的数量多1）。那么不可接受的数列 就和 有n+1个+1和n-1个-1的数列是一一对应的。因为如果有n+1个+1和n-1个-1的序列出现，那么从头到尾遍历序列，一定在某一个点上（包括这个点）的前缀和大于0。因为这是取反的数列，那么我们把这个点之前（包括这个点）的所有数字都去反，就会得到一个前缀和小于0的序列，那么这就是一个不符合的序列。

我们很容易求出不可接受的数列为U_{n}=C_{2 n}^{n+1}=\frac{n}{n+1} C_{2 n}^{n} 。

所以，A_{n}+U_{n}=C_{2 n}^{n} 。

所以，解就是A_{n}=\frac{1}{n+1} C_{2 n}^{m}=h_{n} 。