卡特兰数——学习笔记

什么是卡特兰数？ 先看几个经典问题： n个元素依次入栈，其出栈序列的方案总数。 由n个1与n个-1组成的满足任意前缀和非负的序列总数。 多边形三角剖分方案数。 n个节点组成的不同二叉树方案数。 … 可以看出上述问题都有共同的特点，我们可以把它们都转化为这样一个模型： 在平面直角坐标中，起始位置在（0，0），每次只能（+1，+1）或（+1，-1），求在路线不跨越x坐标的前提下走到（2*n, 0) 的方案数。 如何做呢？ 如果没有不跨越x坐标的限制，显然方案数为Cn2n$C_{2n}^{n}$。 考虑一条不合法的方案。显然这条折线一定在y=-1上有交点，把折线第一次与直线y=-1的交点之前的部分关于y=-1对称，现在得到的是一条从(0，-2)到（2n, 0）的折线。 不难得出，任意一条从从(0，-2)到（2n, 0）的路线都对应着一个不合法的方案。 得：Cn2n−Cn−12n$C_{2n}^{n}-C_{2n}^{n-1}$ 这个就是卡特兰数的通项式啦。 卡特兰数还满足一个递推式：f(n+1)=∑ni=0f(i)∗f(n−i)$f(n+1)=/sum_{i=0}^n f(i)*f(n-i)$ 怎么理解呢？其实就是枚举第一对+1与-1的位置，这个之内的序列，以及之后序列，这两个的问题都是原问题的子问题。 总之这种一一对应的东西很有可能用到卡特兰数。

上面这种证明方法还可以进行拓展： 看看这个稍微变一下的问题:由n个1与m个-1组成的满足任意前缀和大于等于-a的序列总数。 还是转化成图形：在平面直角坐标中，起始位置在（0，0），每次只能（+1，+1）或（+1，-1），求在路线不跨越y=-a的前提下走到（n+m, n-m) 的方案数。 同样的方法，把某不合法的折线第一次与直线y=-a的交点之前的部分关于y=-a对称，得到一条从（0，-2a）走到（n+m, n-m) 的折线。 剩下的不用多讲了吧，答案：Cmn+m−Cm−1−2an+m$C_{n+m}^{m}-C_{n+m}^{m-1-2a}$ 拓展之后还是很有用的。