Catalan卡塔兰数

2023-11-16

今天在二叉搜索树（随机组成情况）分析复杂度遇到 catalan数，学习并记录一下。

背景：

分析二叉搜索树（BST）的平均性能时，我们可以分为随机生成和随机组成分析。

随机生成：将各节点按照数的顺序随机排列。若含有n个节点（n个互异关键码），则有n!种全排列。若各排列作为输入序列的概率均等，则只要它们各自所生成二叉收缩树的平均查找长度进行平均，则可在一定程序上反映二叉搜索树的平均查找性能。

根据Devroye, Luc. A note on the height of binary search trees[J]. Journal of the ACM, 1986, 33(3):489-498.和 Flajolet P , Odlyzko A . The average height of binary trees and other simple trees[J]. Journal of Computer and System Sciences, 1982, 25(2):171-213.文档的描述。我们可以得到，在这一随机意义下，二叉搜索树的平均高度为O(logn)。

随机组成：假定n个互异的节点同时给定，然后再遵循顺序性的前提下，随机确定它们之间的拓扑联接。可以证明，如此所得到的BST的总数恰好等于Catalan（n）。同时，因为这种分析得到的结果没有图7.9第五种情况一种BST结构对应两种不同的关键码序列，即结果更为准确。若这些树出现的概率相等，则通过对其高度做平均可知，平均查找长度为O( $\sqrt{n}$ )。

Catalan数

卡塔兰数是排列组合经常遇见的问题。以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。

背景：

非负整数上的加泰罗尼亚数字是一组数字，这些数字出现在类型的树枚举问题中，“ 如果不同的方向分别计算，有多少种方法可以将正 n 边形分为 n-2 个三角形？” （欧拉多边形除法问题）。解决方案是加泰罗尼亚数字 $C_{n-2}$ （Pólya1956;Dörrie1965; Honsberger 1973; Borwein和Bailey 2003，第21-22页）。

卡塔兰数前20項為（OEIS中的数列A000108）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 17672631

特点：

1.卡特兰数的一个特点是问题有n点，选择某一点后分成两个子问题，两个子问题互相独立

2.或者可以直接往原始定义方向建模：每一步有两种决策，规定任意时刻一种决策数量不能超过另一种

推导过程：

我们首先连接 n 边形的一条对角线，此时，我们会发现，这条对角线把当前图形分割成了2部分。那我们设其中一块有k+1条边(这样我们就可以得到k个三角形）。另一块图形我们剩余n-k-1条边，可以得到n-k-1个三角形。因为乘法原理，这样剖分的方案数就为 $C_{k}$ * $C_{n-k-1}$ 。

显然，k可以从0一直变化到n-1（注意，考虑边界情况，并注意到这里的对角线不相交，所以这里不会出现重复计数）。

所以，递推式为 $C_n = \sum_{k=0}^{n-1}C_k*C_{n-1-k}$

这个数列就是著名的Catalan数列。

现在，我们将这玩意整成我们熟悉的带有组合数的通项公式： $Cat_n = \frac{1}{n+1}C_{2n}^n$

基本公式

卡塔兰数的一般公式为: $Cat_n = \frac{1}{n+1}C_{2n}^n$

我们常使用以下形式：

$C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}$

其中组合公式（二项式系数） $C_{n}^{k}$ ：

$C_{n}^{k}$ = ${\ binom {n} {k}} = {\ frac {n（n-1）\ dotsb（n-k + 1）} {k（k-1）\ dotsb 1}}，$ 可以用阶乘法写成 $\ textstyle {\ frac {n！} {k！（nk）！}}$

拓展：

$C_{n}$ 的另一个表达形式为

$C_n = {2n\choose n} - {2n\choose n+1} \quad\mbox{ for }n\ge 1$

它也满足

$C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,$

这提供了一个更快速的方法来计算卡塔兰数。

卡塔兰数的渐近增长为

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

它的含义是当n → ∞时，左式除以右式的商趋向于1。（这可以用n!的斯特灵公式来证明。）

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

参考文献:

https://en.wikipedia.org/wiki/Combination

https://baike.baidu.com/item/%E6%8E%92%E5%88%97%E7%BB%84%E5%90%88/706498?fr=aladdin

https://www.cnblogs.com/candy99/p/6400735.html

http://mathworld.wolfram.com/CatalanNumber.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

高数线代