数学 | 卡特兰数

2020-03-22 本文已影响0人水土七口刀

卡特兰数

定义

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为: $1 ，1，2， 5，14， 42，132， 429， 1430，4862， 16796，58786，208012$

递推关系

$C_{n+1}=C_0C_n+C_1C_{n-1}+……+C_nC_0$
$(n-3)C_n=n/2(C_3C_{n-1}+C_4C_{n-2}+……+C_{n-2}C_4+C_{n-1}C_3)$

递推公式

$C_{n}=\frac{1}{n+1}\left(\begin{array}{c}{2 n} \\{n}\end{array}\right)=\frac{(2 n) !}{(n+1) ! n !}$
$\displaystyle C_n=\binom{2n}{n}-\binom{2n}{n+1}\quad \operatorname{for} n\ge1$

数据结构相关问题

进出栈问题：栈是一种先进后出（FILO，First In Last Out）的数据结构．1,2,3,4顺序进栈，那么一种可能的进出栈顺序是：1In→2In→2Out→3In→4In→4Out→3Out→1Out, 于是出栈序列为1,3,4,2。
那么一个足够大的栈的进栈序列为1,2,3,⋯,n时有多少个不同的出栈序列？

我们可以这样想，假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数，一共有h(k-1)种方案。比k晚进栈且早出栈的有n-k个数，一共有h(n-k)种方案。所以一共有h(k-1)h(n-k)种方案。显而易见，k取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。k的取值范围为1至n，所以结果就为h(n)= h(0)h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0)。

二叉树构成问题。有n个结点，问总共能构成几种不同的二叉树。

我们可以假设，如果采用中序遍历的话，根结点第k个被访问到，则根结点的左子树有k-1个点、根结点的右指数有n-k个点。k的取值范围为1到n。讲到这里就很明显看得出是卡特兰数了。

待分析问题

括号化问题。左括号和右括号各有n个时，合法的括号表达式的个数有Catalan(N)种。
有n+1个数连乘，乘法顺序有Catalan(N)种,相当于在式子上加括号。
n个非叶节点的满二叉树的形态数为Catalan(N)。
对于一个n*n的正方形网格，每次只能向右或者向上移动一格，那么从左下角到右上角的不同种类有Catalan(N)种。
对凸n+2边形进行不同的三角形分割（只连接顶点对形成n个三角形）数为Catalan(N)。
将有2n个元素的集合中的元素两两分为n个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分。此时不交叉的划分数是Catalan(N)。
n层的阶梯切割为n个矩形的切法数也是Catalan(N)。
在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是Catalan(N)。