Catalan Number滿足下列遞推公式：

N個元素元素進(jìn)棧，多少種出棧方式

考慮A、B、C、D依次進(jìn)棧，那么所有的出棧順序是下列4種情況的并集：

1）A第一個出棧。肯定是A進(jìn)棧后馬上出棧，剩下B、C、D的出棧順序有h(3)種。h(0)*h(3)。

2）A第二個出棧。在A之前出棧的肯定是B，B的出棧順序有h(1)種，剩下C、D的出棧順序有h(2)種。h(1)*h(2)。

3）A第三個出棧。在A之前出棧的肯定是B、C，B、C的出棧順序有h(2)種，剩下D的出棧順序有h(1)種。h(2)*h(1)。

4）A第四個出棧。在A之前出棧的肯定是B、C、D，B、C、D的出棧順序有h(3)種。h(3)*h(0)。

h(4)=h(0)*h(3)+h(1)*h(2)+h(2)*h(1)+h(3)*h(0)

買票找零問題

有2n個人排成一行進(jìn)入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？

來一位持5元的顧客記為+1（使劇院多了一張5元的零錢），來一位持10元的顧客記為-1（使劇院少了一張5元的零錢）。那么購票順序可表示一個包含n個1和n個-1的序列，要求符合條件：

對于任意的K（），都有序列的前K項和不小于0。

下面我們要證明所有不符合條件的序列跟一個包含n-1個1和n+1個-1的序列是一一對應(yīng)的。

1）一個不符合條件的序列對應(yīng)唯一一個包含n-1個1和n+1個-1的序列。如果一個序列不符合條件，則必然在某個奇數(shù)位K上使得前K個數(shù)中-1的個數(shù)比+1的個數(shù)多1，也就是說第K位以后（不包含K）1的個數(shù)比-1的個數(shù)多1。現(xiàn)在我們把第K位以后（不包含K）的1改為-1，-1改為1，則整個序列中包含n-1個1和n+1個-1。

2）一個包含n-1個1和n+1個-1的序列對應(yīng)唯一一個不符合條件的序列。一個包含n-1個1和n+1個-1的序列必然在某個奇數(shù)位K上使得前K個數(shù)中-1的個數(shù)比+1的個數(shù)多1，也就是說第K位以后（不包含K）1的個數(shù)比-1的個數(shù)多1。現(xiàn)在我們把第K位以后（不包含K）的1改為-1，-1改為1，剛好就對應(yīng)一個個不符合條件的序列。

長度為2n的序列中出現(xiàn)n個1和n個-1的可能情況有種，長度為2n的序列中出現(xiàn)n-1個1和個n+1-1的可能情況有種，所以滿足條件的情況的種。

實際上可以把“找零問題”轉(zhuǎn)換為“N個元素入棧，有多少種出棧順序”的問題：來一個持5元的顧客對應(yīng)入棧，來一個持10元的顧客對應(yīng)出棧。

如何編程計算

使用公式（2）來計算卡待蘭數(shù)列需要用遞歸的方法，而遞歸是一種計算量很大的方法，很多時候會出現(xiàn)重復(fù)的計算。公式（1）也可以很直接地翻譯為一種遞歸的算法，不過也可以很容易地使用動態(tài)規(guī)劃把它轉(zhuǎn)換為非遞歸的方法----先算h(0)，再算h(1)，再算h(2)……復(fù)雜度為O(N)。

如果使用公式（3）就需要掌握排列組合的計算方法。

復(fù)雜度也是O(N)。

總結(jié)

以上是生活随笔為你收集整理的卡特兰数Catalan Number的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。