卡特兰数(Catalan number)

catalan介绍

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

catalan原理

令h(0)=1,h(1)=1，catalan数满足递推式 ^[2] ：

h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)*h(0) (n>=2)

例如：h(2)=h(0)h(1)+h(1)h(0)=11+11=2

h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5

另类递推式 ^[3] ：

h(n)=h(n-1)(4n-2)/(n+1);

递推关系的解为：

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为：

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

出栈次序

   一个栈(无穷大)的进栈序列为1,2,3,...,n,有多少个不同的出栈序列?

  常规分析

  首先,我们设f(n) = 序列个数为n的出栈序列种数。(我们假定,最后出栈的元素为k,显然,k取不同值时的情况是相互独立的,也就是求出每种k最后出栈的情况数后可用加法原则,由于k最后出栈,因此,在k入栈之前,比k小的值均出栈,此处情况有f(k-1)种,而之后比k大的值入栈,且都在k之前出栈,因此有f(n-k),由于比k小和比k大的值入栈出栈情况是相互独立的,此处可用乘法原则,f(n-k)*f(k-1)种

  此时,我们若把k视为确定一个序数,那么根据乘法原理,f(n)的问题就等价于--序列个数为k-1的出栈序列种数乘以序列个数为n-k的出栈序列种数,即选择k这个序数的f(n)= f(k-1) × f(n-k)。而k可以选1到n,所以再根据加法原理,将k取不同值的序列种数相加,得到的总序列种数为:f(n) =f(0) f(n-1) + f(1) f(n-1) +......+f(n-1) f(0)

  看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n-1）（n=0，1，2，……）。
  最后，令f（0）=1，f（1）=1。

类似问题

买票找零
  有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

  在图书馆一共6个人在排队，3个还《面试宝典》一书，3个在借《面试宝典》一书，图书馆此时没有了面试宝典了，确保三个人都能借到书，求他们排队的总数？

给定节点组成二叉搜索树

  给定N个[节点]，能构成多少种不同的二叉搜索树？

  （能构成h（N）个）

  （这个公式的下标是从h(0)=1开始的）