卡特兰数和超级卡特兰数

卡特兰数和超级卡特兰数

---

这篇博客主要是想讲一下超级卡特兰数(大施罗德数),顺带就想讲一下卡特兰数.

卡特兰数

定义

卡特兰数记为(C_n)
(C_1=1)
(forall n geq 2, C_n=sum_{i=1}^{n-1}C_i C_{n-i})

前几项大概是: 1, 1, 2, 5, 14, 42, 132......

直接递推未免效率太低,我们考虑用生成函数优化.
显然有(C(x)=C(x)^2+x)
解得(C(x)={1-(1-4x)^{frac 1 2}over 2})
将((1-4x)^{frac 1 2})用广义二项式定理展开
得到(C(x))中(x^n)项系数为(frac 1 n inom {2n-2}{n-1})

组合意义

1.(n+1)边形的三角剖分方案数.
注意到任意三角形一定是某一条边在多边形上,然后再选一个不是这条边的端点的点,而且注意到这样一个三角形不会被计算两次,所以会得到一个类似于卡特兰数的递推式.
如果直接枚举一条边然后分成两边的话,是算不对的,因为可能一个点不与多边形上任意非相邻点连边.如果要强行这么算的话,那就得枚举所有的边然后除以算重的次数.

2.(n)个数的连乘积,只用结合律(加括号)来改变乘法顺序,问有多少中乘法的顺序.
考虑枚举最后是哪两个数相乘,不难发现是卡特兰数的形式.

3.(n-1)对括号的括号序列的合法方案数.
枚举第一个左括号所对应的右括号的位置即可.

4.从(0,0)到(n-1,n-1),每次只能往右或往上走,求不超过(y=x)这条直线的方案数.
考虑第一步肯定是往右边走,然后枚举第一个经过(y=x)这条直线的位置.
另外一种思路,将条件变成不经过(y=x+1)这条直线,那么寻找(0,0)关于(y=x+1)的对称点
(-1,1),显然每一条从(0,0)到(n-1,n-1)的不合法路径对应一条从(-1,1)到(n-1,n-1)的不合法路径.

超级卡特兰数

记超级卡特兰数为(S_i)
有(S_1=1)
(forall i geq 2,S_i=S_{i-1}+sum_{i=1}^{n-1}S_iS_{n-i})

写成生成函数的形式是(S(x)=xS(x)+S(x)^2+x)
解得(S(x)={1-x - sqrt{x^2-6x+1} over 2})

如果还是用广义二项式定理展开的话,经过复杂化简,可以得到(S_n=sum_{i=1}^n inom {n+i-1} {2i}C_i),后面我们可以看见,这个式子有着清晰的组合意义.

不过网上还有一种(O(n))递推的方法,简而言之就是快速求出(sqrt{x^2-6x+1})

接下来给出的一种方法,可以在(O(nk))的复杂度快速求出k次多项式开方后前n项的值
设要开方的多项式为(P(x)),开方后的多项式为(F(x)).
有(F(x)=P(x)^{frac 1 2}=sum_{i=0}^{infty} f_i x^i)
两边求导,可得(F'(x)=frac 12 P(x)^{-frac 12} P'(x))
有(F(x)P'(x)=F'(x)P(x))
对比每一项系数,不难得到k+1项的递推式.

最后给出递推公式:((n+1)f_{n+1}=(6n-3)f_n-(n-2)f_{n-1}),不过要注意这个递推公式除了第一项其他的项都是超级卡特兰数的(frac12)

组合意义

相比卡特兰数,超级卡特兰数的唯一区别就是在递推的时候加了一个(S_{n-1}),那么其组合意义也可以看做是卡特兰数的扩展.

1.(n+1)边形的任意剖分方案数.
还是考虑枚举一条多边形上的边,那么有可能这条边仍然与另一个点拉成一个三角形,也有可能这条边上没有,那么把这两种加起来就是定义的递推式

2.括号序列,每个位置可能左括号,右括号和0.括号对数与0的个数之和为n-1, 问合法的括号序列数.
同样枚举第一个是左括号还是0.
值得一提的是,可以看成先插括号再插0,那么枚举括号对数i,0有n-i-1个,需要放入2i+1个位置中,那么不难得到上面通过广义二项式推出来的式子.

3.从(0,0)到(n-1,n-1),每次能往右,往上,往右上走,求不超过(y=x)这条直线的方案数.
枚举第一次是走右上还是走右.
同样使用容斥思想,把答案转化为从(0,0)到(n-1,n-1)减去(-1,1)到(n-1,n-1).
那么从(0,0)到(n,m)的路径条数怎么求呢.可以考虑枚举往右上的次数,然后还是考虑先走右和上,然后再把走右上的插入即可.