卡特兰数——括号匹配问题

卡特兰数的递推公式是F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}
一般性公式为F(n)=C(2n,n)/(n+1)

可以描述的问题有
1、n个元素的二叉查找树有多少种。
2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。
3、2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。
4、n个元素全部入栈并且全部出栈的所有可能顺序。

这些问题的答案都是卡特兰数F(n)。但是很明显可以看出后三个问题是同质的。
都可以抽象成2n个操作组成的操作链，其中A操作和B操作各n个，且要求截断到操作链的任何位置都有：A操作（向右走一步、收到50元、元素入栈）的个数不少于B操作（向上走一步、收到100元找出50元、元素出栈）的个数。故问题2、3、4其实是同一个问题。

下面先证明问题2、3、4和问题1同解，再证明问题2、3、4的解是F(n)=C(2n,n)/(n+1)，从而证明问题1的解也是F(n)=C(2n,n)/(n+1)。

1、问题2、3、4和问题1同解
问题1的解是F(n)=∑(k=0…n-1){F(k)*F(n-1-k)}，因为一棵n个结点的二叉排序树的根可以是1到n的任意结点，设为k，则其左子树结点个数为k，左子树的种类一共有F(k-1)种，右子树结点个数为n-k，右子树的种类一共有F(n-k)。而究竟哪一点为根可以有1到n共n个选择，故k取遍1到n——F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}。

如果我们能证明问题2的解也可表示为F(n)=∑(k=0…n-1){F(k)*F(n-1-k)}，就完成了证明。

考虑n*n棋盘，记主对角线为L。从左下角走到右上角不穿过对角线L的所有路径，不算起点，一定有第一次接触到L的位置（可能是终点），设此位置为M，坐标为(x,x)——设第一个数为横轴坐标。该路径一定从下方的(x,x-1)而来，而起点处第一步也一定是走向(1,0)，两者理由相同——否则就穿过了主对角线。考虑从(1,0)到(x,x-1)的(x-1)*(x-1)的小棋盘中，因为在此中路径一直没有接触过主对角线（M的选取），所以在此小棋盘中路径也一定没有穿过从(1,0)到(x,x-1)的小棋盘的对角线L1。这样在这个区域中的满足条件的路径数量就是一个同构的子问题，解应该是F(x-1)，而从M到右上角终点的路径数量也是一个同构的子问题，解应该是F(n-x)，而第一次接触到主对角线的点可以从(1,1)取到(n,n)，这样就有F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k-1)*F(n-k)}。证毕。

2、问题2的解为F(n)=C(2n,n)/(n+1)
思路是先求所有从(0,0)到(n,n)的路径数X，再求所有穿过主对角线L的从(0,0)到(n,n)的路径数Y，用前者减去后者得到所求。
从(0,0)到(n,n)的路径数显然是C(2n,n)，一共要走2n步到达右上角，其中向右和向上各n步，总走法是C(2n,n)。
考虑一个新增的位置(n-1,n+1)，它位于终点的左上角一个格处，设所有从(0,0)到(n-1,n+1)的路径数为Z，下面要证明Y和Z相等，从而通过求Z来求Y。
考虑从(0,1)到(n-1,n)的对角线L2，对于所有穿过L而到达终点的路径，一定会接触到L2，找出某路径第一次接触到L2的位置M1，将从M1到终点的路径沿L2做对折一定会得到一条从M1到(n-1,n+1)的路径，故每条穿过L到达终点的路径都对应一条到达(n-1,n+1)的路径，即有Y<=Z。

所有从起点到达(n-1,n+1)的路径都一定会穿过L2，找出某路径第一次穿过L2的位置M2，将M2到(n-1,n+1)的路径沿L2对折，就得到一条M2到(n,n)的路径，且该条路径一定穿过L，故每条到达(n-1,n+1)的路径都对应一条穿过L到达终点的路径，即有Z<=Y。
故Z==Y。
接下来通过求Z来求Y。Z是显然的从(0,0)到(n-1,n+1)共需走2n步，其中向右n-1步、向上n+1步，故Z=C(2n,n-1)。
由以上可知F(n)=X-Y=X-Z=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。证毕。

由以上可知问题1的解也是F(n)=C(2n,n)/(n+1)，故求和(k){F(k)*F(n-1-k)}=C(2n,n)/(n+1)。这个数称为卡特兰数，前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796。

除了上面描述的四个问题外，它对应的问题还有：
矩阵链所有乘法顺序问题（同问题1）。
凸多边形剖分成三角形的方法数（同问题1）。

3 Responses to “卡特兰数”
carter Says:
一月 6th, 2011 at 5:50 下午
请问楼主对括号配对和入栈出栈这2个问题，如何分析成F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}？ 并且如何进一步分析成C(2n,n)-C(2n,n-1)？

chris Says:
一月 10th, 2011 at 9:26 上午
这两个问题与棋盘问题都是同质的，这个很明显。而棋盘问题实际是可以写成F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}的，我上面好像忘了写了，等我下午考完试来补上吧。

chris Says:
一月 10th, 2011 at 4:24 下午
原来我上面已经证明过了。因为入栈出栈问题和括号配对问题与棋盘街问题同质（考虑入栈和一个左括号等于向右走一格，出栈和一个右括号等于向左走一格）；而棋盘街问题可以分析成F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}（文中有证明）。