新浪博客

神奇的卡特兰数

2011-09-16 08:18阅读：

http://blog.sina.cn/dpool/blog/u/1885661061

部分摘自http://yanpol.blog.163.com/blog/static/4817080620106184553824/
此外，在相关博文《折线法》中有一种卡特兰数的证明方法。

Catalan，Eugene，Charles，卡特兰（1814～1894）比利时数学家，生于布鲁日（Brugge）。
早年在巴黎综合工科学校就读。1856年任列日（Liege）大学数学教授，并被选为比利时布鲁塞尔科学院院士。

卡特兰一生共发表200多种数学各领域的论著。

在微分几何中，他证明了下述所谓的卡特兰定理：当一个直纹曲线是平面和一般的螺旋面时，他只能是实的极小曲面。他还和雅可比（Jacobi，C·G·J）同时解决了多重积分的变量替换问题，建立了有关的公式。

1842年，他提出了一种猜想：方程xz－yt＝1没有大于1的正整数解，除非平凡情形32－23＝1。这一问题至今尚未解决。（1962年我国数学家柯召以极其精湛的方法证明了不存在三个连续正整数，它们都是正整数的方幂，以及方程x2－yn＝1，n＞1，（xy≠0）无正整数解。并且还证明了如果卡特兰猜想不成立，其最小的反例也得大于1016。）

此外，卡特兰还在函数论、伯努利数和其他领域也做出了一定的贡献。

实际上，我们中学时代已经接触过卡特兰恒等式，不过当时我们对卡特兰知之甚少。我百度了一下卡
特兰，结果满街都是花的名字。卡特兰恒等式是这样的：

神奇的卡特兰数

今天我们来讨论一个以他名字命名的神奇数列（卡特兰数）的相关性质。

他的神奇之处在于，很多看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。我们不妨先看看下面这些问题：
1：给定n个数，有多少种出栈序列？
（问题的形象描述：
饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
一个有n个1和n个-1组成的字串，且前k个数的和均不小于0，那这种字串的总数为多少？
P=A1A2A3……An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？）
2：n个节点的二叉树有多少种构型？
3：有n+1个叶子的满二叉树的个数？

4：在n*n的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？
神奇的卡特兰数
5：将一个凸n+2边形区域分成三角形区域的方法数？
神奇的卡特兰数
6：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？

7：用n个长方形填充一个高度为n的阶梯状图形的方法个数？
神奇的卡特兰数

上面一些问题有些是同构的，但有些却实在看不出联系来，他们的答案却都为卡特兰数。在《Enumerative Combinatorics》一书中，竟然提到了多达 66种组合问题和卡特兰数有关。
我们先来看看何为卡特兰数：
卡塔兰数的一般项公式为 C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}
Cn的另一个表达形式为 C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1

递归式：令h(0)=1,h(1)＝1,catalan数满足递归式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + 神奇的卡特兰数 + h(n-1)h(0) (其中n>=2)
另类递归式： h(n)=((4*n-2)/(n+1))*h(n-1);

前几项为 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

卡塔兰数的渐近增长为
C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}

由于篇幅问题，上面一些问题的解答将会在相关博文中展示。
转载请注明出处,谢谢合作 http://blog.sina.com.cn/u/1885661061

我的更多文章

下载客户端阅读体验更佳

APP专享