卡特兰数

转载 原址

公式

$Cat_{n}=\frac{1}{n+1}C_{2n}^{n}=\frac{(2n)!}{(n+1)!n!}$

$Cat_{n}=\frac{4n+2}{n+1}Cat_{n-1}$

$Cat_{n}=C_{2n}^{n}-C_{2n}^{n-1}$

性质

所有的奇卡塔兰数$C_{n}$都满足$n=2^k-1$。

所有其他的卡塔兰数都是偶数

实际问题的解决

说了这么多,那么卡特兰数在实际问题中的应用还是很广泛的:

经典问题:

Dyck word

给出一个$n$,要求一个长度为$2n$的$01$序列,使得序列的任意前缀中$1$的个数不少于$0$的个数, 以下为长度为$6$的序列:

111000 101100 101010 110010 110100

证明:

令$1$表示进栈,$0$表示出栈,则可转化为求一个$2n$位,含$n$个$1$,$n$个$0$的二进制数,

满足从左往右扫描到任意一位时,经过的0数不多于1数

显然含$n$个$1$,$n$个$0$的$2n$位二进制数共有$C_{2n}^{n}$个,下面考虑不满足要求的数目.

考虑一个含$n$个$1$,$n$个$0$的$2n$位二进制数,扫描到第$2m+1$位上时有$m+1$个$0$和$m$个$1$(容易证明一定存在这样的情况), 则后面的$01$排列中必有$n-m$个$1$和$n-m-1$个$0$ 将$2m+2$及其以后的部分$0$变成$1$,$1$变成$0$,则对应一个$n+1$个$0$和$n-1$个$1$的二进制数 反之亦然(相似的思路证明两者一一对应)

可得:

$Cat_n=C_{2n}^{n}-C_{2n}^{n+1}=\frac{1}{n+1}C_{2n}^{n}$

将上例的$X$换成左括号,$Y$换成右括号,$Cat_n$表示所有包含$n$组括号的合法运算式的个数: ((())) ()(()) ()()() (())() (()())

$Cat_n$表示有$n+1$个叶子的二叉树的个数

$Cat_n$表示所有不同构的含$n$个分枝结点的满二叉树的个数

(一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树)

$Cat_n$表示所有在$n × n$格点中不越过对角线的单调路径的个数 一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右

计算这种路径的个数等价于计算Dyck word的个数(同问题1):$X$代表“向右”,$Y$代表“向上”

$Cat_n$表示通过连结顶点而将$n + 2$边的凸多边形分成三角形的方法个数 下图中为$n = 4$的情况:

$Cat_n$表示对{$1, …, n$}依序进出栈的置换个数 一个置换w是依序进出栈的当$S(w) = (1, …, n)$, 其中$S(w)$递归定义如下:令$w = unv$,其中$n$为$w$的最大元素,$u$和$v$为更短的数列 再令$S(w)$ =$S(u)S(v)n$,其中S为所有含一个元素的数列的单位元。

$Cat_n$表示集合{$1, …, n$}的不交叉划分的个数. 其中每个段落的长度为$2$

$Cat_n$表示用$n$个长方形填充一个高度为$n$的阶梯状图形的方法个数 下图为 $n = 4$的情况:

应用总结

(实质上却都一样,无非是递归等式的应用,就看你能不能分解问题写出递归式了)

1.括号化问题

  矩阵链乘: $P=a1×a2×a3×……×an$,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?($h(n)$种)

2.出栈次序问题。

  一个栈(无穷大)的进栈序列为$1,2,3,..n$,有多少个不同的出栈序列?   

  类似:

  (1)有$2n$个人排成一行进入剧场。入场费$5$元。其中只有$n$个人有一张$5$元钞票,另外$n$人只有$10$元钞票,剧院无其它钞票,问有多少中方法使得只要有$10$元的人买票,售票处就有$5$元的钞票找零?(将持$5$元者到达视作将5元入栈,持$10$元者到达视作使栈中某$5$元出栈)   

  (2)在圆上选择$2n$个点,将这些点成对连接起来,使得所得到的$n$条线段不相交的方法数。   

3.将多边行划分为三角形问题

  将一个凸多边形区域分成三角形区域的方法数?   

  类似:一位大城市的律师在她住所以北$n$个街区和以东$n$个街区处工作。每天她走$2n$个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?

   类似:在圆上选择$2n$个点,将这些点成对连接起来使得所得到的$n$条线段不相交的方法数?   

4.给顶节点组成二叉树的问题。

  给定$N$个节点,能构成多少种形状不同的二叉树?

  先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是$h(0)*h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)$(能构成$h(N)$个)


发表于 2018-10-15 20:27:43 in 数论