Knight's Tale
联系
Weixin
Knight's Tale » 技术

有意思的数列: Catalan数*

2010-08-30 23:54

今天晚上小妹问我一个问题，

“有一个随意的数组，一个栈，一个队列。现将数组内的元素随机进栈或进队列，等数组中所有元素均在栈中与队列中时，开始出栈和出队列。问题是：这样形成的序列总数有多少种？”

对于这个问题，我现在还没有很确切的解答。要解决这个问题，需先了解如果单独只有栈时，序列有多少种的解决方法。因此，我也花了些时间在“出栈序列”种类问题上，从而发现了非常有趣了“Catalan数”。

【对于小妹的问题，我已经在8月31号做出了解答，用程序模拟出来了。可以发现得出来的序列并不是全排列，是介于栈与全排列之间的序列】

在中文维基上[1]，它是这么来定义的：

卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡塔兰数的一般项公式为 C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}

前几项为 （OEIS中的数列A000108）: 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, ...

卡塔兰数是一个非常有意思的数列。它的应用在维基和百科[2]上都有详细的介绍。在维基上还详细介绍了如何将“栈序列”问题与“卡塔兰数”结合起来的证明。写得非常棒。

卡塔兰数的应用可以在[1]：

  • Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。
  • Cn表示有n+1个叶子的二叉树的个数
  • Cn表示所有不同构的含n个分枝结点的满二叉树的个数。
  • Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数
  • Cn表示对{1, ..., n}依序进出栈的置换个数
  • Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。
  • 一个有n个结点的二叉树总共有多少种形态的问题[2][4].
还有些有用的实例问题可以参考[2].  更多有意思的证明，更详细的论证请参阅英文维基[3]. 我是从[5]中发觉到Catalan数的重要性的。

回归到本文开头，出栈序列种数问题。知道了Catalan数，该问题也迎难而解了。种数就是Cn 例如，

顺序进栈1，2，3。则出栈顺序可能是（这是我用CODE算法实现的）

3 2 1 2 3 1 2 1 3 1 3 2 1 2 3

用Catalan数计算出来是(6,3)/4=5。

简单判断栈的出栈序列是否正确的方法：如果一个数已经输出，则比它小的数不可能按照从小到大顺序输出，否则是不可能序列

Reference:

[1]. 维基， http://zh.wikipedia.org/zh-cn/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0 [2]. 百度百科， http://baike.baidu.com/view/1163998.htm?fr=ala0_1_1 [3]. 英文维基，http://en.wikipedia.org/wiki/Catalan_number [4]. 逸空博客， http://hi.baidu.com/lonelinsky/blog/item/049b342b0e95a4325243c1c5.html [5]. dlyme的专栏 http://blog.csdn.net/dlyme/archive/2008/06/10/2532831.aspx

本文创建于2010年8月30号  23：54 修改1：2010年8月31号 14：32

本文链接地址：有意思的数列: Catalan数*