Catalan数列及其应用

版权声明：本文为博主原创文章，转载请注明博客地址： https://cloud.tencent.com/developer/article/1433374

问题引入：现在有1,2,3,...,n个数字，按照顺序入栈，不同的堆栈操作（Push ，Pop）顺序可能会得到不同的堆栈输出序列。请问n个数字共有多少种不同的输出序列。

解决过程：由于必须先入栈，才能出栈。对一个空栈的Pop是非法的操作。因此K次连续的出栈，在它之前必有K次入栈。一个简单的想法是看看能否找到它的递推公式。很遗憾，愚钝的我通过前几项（1,2,5,14）根本无法找出递推公式。上网找了很久，也没看到如何解决它，突然之间瞎翻了几页搜索结果，突然看到了问题的答案。一个十分精彩的解答来自于高德纳的《计算机程序设计艺术》（这是本神作，它在计算机科学界的地位相当于牛顿当年写的《自然哲学的数学原理》）。《计算机程序设计艺术（卷一）》2.2.1节习题4的解答提到的精彩解法“反射原理”。附上地址：http://www.nowamagic.net/academy/detail/40140311。

卡特兰数：卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 的名字来命名。详见百度百科。

这个数列的前几项（这个数列从第0个开始）是这样的： 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640,...。可以看到数列的增长在n>10以后，变得非常的快。所以想求其递推公式的我果真太年轻了。因此，我们必须站在巨人的肩膀之上，才能看的更远。

这是卡特兰数列的通项公式：

关于卡特兰数列的具体应用的解释，可以参考这篇Catalan 数列及其应用。