<总结>卡特兰数

本文来自原博客,最后更新时间为2019年7月,请知悉

基本数论算法

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

这就是优美毒瘤的卡特兰数的前10
不要把它和斐波拉契数列搞混了(我就经常搞混)

公式

  • 通项(不会算组合数可以去基本数论算法哦)
    1. C_n=\frac{1}{n+1}{\rm C}_{2n}^n={\rm C}_{2n}^n-{\rm C}_{2n}^{n-1}
    2. C_n=\frac{1}{n+1}\sum\limits_{i=0}^n\left({\rm C}_n^i\right)^2
  • 递推
    1. C_{n+1}=\frac{2(2n+1)}{n+2}C_n\quad C_0=1
    2. C_{n+1}=\sum\limits_{i=0}^nC_iC_{n-i}\quad C_0=1

应用

括号配对

n对括号的配对方法总数
这道题用DP是很好推的。
我们用f(n)表示n对括号的配对方法,f(0)=f(1)=1
我们想如何用少一点的括号数量推出多一点的括号数量
考虑n对括号时的任意一种配对方案,最后一个右括号有唯一的与之匹配的左括号,于是有唯一的表示A(B),其中AB也是合法的括号匹配序列(AB可为空)
我们可以十分快地推出DP方程:f(n)=\sum\limits_{i=0}^{n-1}f(i)f(n-i-1)\quad f(0)=1
所以由n对括号形成的合法括号表达式的个数为C_n

凸多边形的剖分(卡特兰问题)

求凸n+3边形用其n条对角线分割为互不重叠的三角形的分法总数.
了解了括号配对的问题后,我们就可以很轻松地看这个问题了。

我们先任意选择一条对角线,把这个图形分成两部分。

那么一个n+3边形就可以划分成两个多边形,边数相加等于n+5
f(n)表示n+3边形分法总数,那么f(n)=\sum\limits_{i=0}^{n-1}f(i)f(n-i-1)\quad f(0)=1

折线法求卡特兰数公式

xy
我们把左括号看做是向右上方45度走\sqrt 2个单位,右括号看做向右下方45度走\sqrt 2个单位。显然如果有n对括号这条线最后要过(2n,0),方法数为\mathrm C_{2n}^n。但是如果要合法,那么这条折线就不能过x轴。
对于不合法的情况,折现一定会碰到y=-1。我们从第一次碰到y=-1的点开始把后面的折线翻转,那么这条折线的终点就一定在(2n,-2)处:
xy
那么不合法的步骤就可以等价地看做n-1个左括号,n+1个右括号,方法数为\mathrm C_{2n}^{n-1}(=\mathrm C_{2n}^{n+1}),合法步骤就是\mathrm C_{2n}^n-\mathrm C_{2n}^{n-1}=\frac{1}{n+1}{\rm C}_{2n}^n

其他应用

  1. 一个栈(无穷大)的进栈序列为1,2,3,n,有多少个不同的出栈序列?
  2. 2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少种方法使得只要有10元的人买票,售票处就有5元的钞票找零?
  3. 给定N个节点,能构成多少种不同的二叉搜索树?

切题

洛谷P3200 [HNOI2009]有趣的数列
有趣的题解(/archives/192 "有趣的题解")

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注