卡特兰数的求法及其常见应用。
以 Catalan 数列为结果的等价问题
给定 n 个 0 和 n 个 1,它们将按照某种顺序排成长度为 2n 的序列,求它们能排列成的所有序列中,能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票,剧院无其它钞票,问有多少种方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零。
有一个大小为 n * n 的方格图左下角为 (0, 0) 右上角为 (n, n),从左下角开始每次都只能向右或者向上走一单位,不走到对角线 y = x 上方(但可以触碰) 的情况下到达右上角有多少可能的路径。
在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数。
对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数。
一个栈(无穷大)的进栈序列为 1, 2, 3, … , n 有多少个不同的出栈序列?
求法
Catalan 数列 通项为 Cn2nn+1.
组合数求法:
1 |
|