常規(guī)分析（如果對(duì)下面的分析感覺(jué)比較迷惑的，可以看看下面這個(gè)分析http://blog.csdn.net/wind__fantasy/article/details/5398358）

首先，我們?cè)O(shè)f（n）=序列個(gè)數(shù)為n的出棧序列種數(shù)。同時(shí)，我們假定，從開(kāi)始到棧第一次出到空為止，這段過(guò)程中第一個(gè)出棧的序數(shù)是k。特別地，如果棧直到整個(gè)過(guò)程結(jié)束時(shí)才空，則k=n

首次出空之前第一個(gè)出棧的序數(shù)k將1~n的序列分成兩個(gè)序列，其中一個(gè)是1~k-1，序列個(gè)數(shù)為k-1，另外一個(gè)是k+1~n，序列個(gè)數(shù)是n-k。

此時(shí)，我們?nèi)舭裬視為確定一個(gè)序數(shù)，那么根據(jù)乘法原理，f（n）的問(wèn)題就等價(jià)于——序列個(gè)數(shù)為k-1的出棧序列種數(shù)乘以序列個(gè)數(shù)為n - k的出棧序列種數(shù)，即選擇k這個(gè)序數(shù)的f（n）=f（k-1）×f（n-k）。而k可以選1到n，所以再根據(jù)加法原理，將k取不同值的序列種數(shù)相加，得到的總序列種數(shù)為：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。

看到此處，再看看卡特蘭數(shù)的遞推式，答案不言而喻，即為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。

非常規(guī)分析（比較容易理解）

對(duì)于每一個(gè)數(shù)來(lái)說(shuō)，必須進(jìn)棧一次、出棧一次。我們把進(jìn)棧設(shè)為狀態(tài)‘1’，出棧設(shè)為狀態(tài)‘0’。n個(gè)數(shù)的所有狀態(tài)對(duì)應(yīng)n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)。由于等待入棧的操作數(shù)按照1‥n的順序排列、入棧的操作數(shù)b大于等于出棧的操作數(shù)a(a≤b)，因此輸出序列的總數(shù)目=由左而右掃描由n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)的方案種數(shù)。

在2n位二進(jìn)制數(shù)中填入n個(gè)1的方案數(shù)為c(2n,n),不填1的其余n位自動(dòng)填0。從中減去不符合要求（由左而右掃描，0的累計(jì)數(shù)大于1的累計(jì)數(shù)）的方案數(shù)即為所求。

不符合要求的數(shù)的特征是由左而右掃描時(shí)，必然在某一奇數(shù)位2m+1位上首先出現(xiàn)m+1個(gè)0的累計(jì)數(shù)和m個(gè)1的累計(jì)數(shù)，此后的2(n-m)-1位上有n-m個(gè) 1和n-m-1個(gè)0。如若把后面這2(n-m)-1位上的0和1互換，使之成為n-m個(gè)0和n-m-1個(gè)1，結(jié)果得1個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)，即一個(gè)不合要求的數(shù)對(duì)應(yīng)于一個(gè)由n+1個(gè)0和n-1個(gè)1組成的排列。

反過(guò)來(lái)，任何一個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位二進(jìn)制數(shù)，由于0的個(gè)數(shù)多2個(gè)，2n為偶數(shù)，故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過(guò)1的累計(jì)數(shù)。同樣在后面部分0和1互換，使之成為由n個(gè)0和n個(gè)1組成的2n位數(shù)，即n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)必對(duì)應(yīng)一個(gè)不符合要求的數(shù)。

因而不合要求的2n位數(shù)與n+1個(gè)0，n－1個(gè)1組成的排列一一對(duì)應(yīng)。

顯然，不符合要求的方案數(shù)為c(2n,n+1)。由此得出輸出序列的總數(shù)目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n+1)。

轉(zhuǎn)載于:https://www.cnblogs.com/cquljw/archive/2013/03/09/2951579.html

總結(jié)

以上是生活随笔為你收集整理的（学习日记）关于a1,a2,a3,...,an共n个元素依次入栈其可能出栈的排列数的计算（catalan数）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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