卡特兰数

定义

好像没什么明确的定义，口胡一个吧

(cat_n)为由(n)个(0)和(n)个(1)组成的序列中，满足前缀(0)的个数永远大于等于前缀(1)个数的序列的方案数

公式

定义式：

定义(cat_0=0,cat_1=1)

(cat_n=sumlimits_{i=0}^{n}cat_i*cat_{n-i}(nge 2))

相当与枚举数列断点然后加法原理，比较显然是对的

通项一：

(cat_n=C_{2n}^{n}-C_{2n}^{n+1})

(C_{2n}^{n})为没有限制时的总方案数，即在(2n)个位置中随便放(0)的方案数

考虑不合法方案：对于每个不合法，一定存在一个最位置使得该序列首次前缀(1)个数大于前缀(0)的个数

我们把这个位置和之前的(01)全部取反，将得到一个(n+1)个(0)和(n-1)个(1)组成的序列

每个非法情况都对应着一个这样的序列，所以总方案数(C_{2n}^{n}-C_{2n}^{n+1})

通项二：

(cat_n=frac{1}{n+1}C_{2n}^{n})

证明：

(cat_n=C_{2n}^{n}-C_{2n}^{n+1})

(=frac{(2n)!}{n!*n!}-frac{(2n)!}{(n+1)!(n-1)!})

(=frac{1}{n+1}(frac{(2n)!(n+1)}{n!*n!}-frac{(2n)!}{n!(n-1)!}))

(=frac{1}{n+1}(frac{(2n)!(n+1)}{n!*n!}-frac{(2n)!(n)}{n!*n!}))

(=frac{1}{n+1}(frac{(2n)!(n+1-n)}{n!*n!}))

(=frac{1}{n+1}(frac{(2n!){n!*n!}}))

(=frac{1}{n+1}C_{2n}^{n})

递推：

(cat_{n+1}=frac{4n+2}{n+2}cat_n)

证明：

(cat_{n+1}=frac{1}{n+2}C_{2n+2}^{n+1})

(cat_{n+1}=frac{1}{n+2}*frac{(2n+2)!}{(n+1)!(n+1)!})

(cat_{n+1}=frac{1}{n+1}*frac{(2n+2)!}{n!(n+2)!})

(cat_{n=1}=frac{1}{n+1}*frac{(2n)!}{n!*n!}*frac{(n+1)(n+2)}{(2n+1)(2n+2)})

(cat_{n=1}=frac{n+2}{4n+2}*frac{1}{n+1}C_{2n}^{n})

(cat_{n+1}=frac{4n+2}{n+2}cat_n)

应用：

输入(3)输出(5)就是了

括号匹配

给定(n)个左括号和(n)个右括号，求合法的括号组合方案数

裸体

网格

给定(n*n)的网格，只能向上或向右走，求不越过对角线到达右上角的方案数

裸体

栈模型

裸体

二叉树形态数

求(n)个节点构成的二叉树的形态数

考虑根节点确定后，我们可以枚举左右子树各有多少个节点

得到式子：(f(n)=sumlimits_{i=0}^{n}f_if_{n-i})

发现是卡特兰数列

(n+2)边形进行三角分割的方案数

每一刀可以把(n+2)边形分割为两个小凸多边形

定义(f(0)=0,f(1)=1)，得到

(f(n)=sumlimits_{i=1}^{n-1}f_if_{n-i})

发现答案就是(cat_{n})

楼梯分割

(n)阶楼梯分割为(n)个矩形

和上面两个例子一样分析

问题变形：

用(n)个(0)和(m)个(1)组成前缀(0)个数永远大于等于前缀(1)个数的方案数

总方案数为(C_{n+m}^{n})

假设位置(k)的时候前缀(1)超过了前缀(0)的数量，那么把前面的(01)翻转

不合法方案数：(C_{n+m}^{n+1})

答案(C_{n+m}^{n}-C_{n+m}^{n+1})