首先來自百度百科
Q：一個棧(無窮大)的[進棧]序列為1，2，3，…，n，有多少個不同的[出棧]序列?
A1：首先，我們設f（n）=序列個數(shù)為n的出棧序列種數(shù)。（我們假定，最后出棧的元素為k，顯然，k取不同值時的情況是相互獨立的，也就是求出每種k最后出棧的情況數(shù)后可用加法原則，由于k最后出棧，因此，在k入棧之前，比k小的值均出棧，此處情況有f(k-1)種，而之后比k大的值入棧，且都在k之前出棧，因此有f(n-k)種方式，由于比k小和比k大的值入棧出棧情況是相互獨立的，此處可用乘法原則，f(n-k)*f(k-1)種，求和便是Catalan遞歸式。
f(0)=1；而且顯然，n=1時只有一種出棧方式，f(1)=1。n=2時，有兩種出棧方式，f(2)=2。

A2：對于每一個數(shù)來說，必須進棧一次、出棧一次。我們把[進棧]設為狀態(tài)‘1’，出棧設為狀態(tài)‘0’。n個數(shù)的所有狀態(tài)對應n個1和n個0組成的2n位[二進制數(shù)]。由于等待入棧的操作數(shù)按照1‥n的順序排列、入棧的操作數(shù)b大于等于[出棧]的操作數(shù)a(a≤b)，因此輸出序列的總數(shù)目=由左而右掃描由n個1和n個0組成的2n位二進制數(shù)，1的累計數(shù)不小于0的累計數(shù)的方案種數(shù)。
在2n位二進制數(shù)中填入n個1的方案數(shù)為c(2n,n),不填1的其余n位自動填0。從中減去不符合要求（由左而右掃描，0的累計數(shù)大于1的累計數(shù)）的方案數(shù)即為所求。
不符合要求的數(shù)的特征是由左而右掃描時，必然在某一奇數(shù)位2m+1位上首先出現(xiàn)m+1個0的累計數(shù)和m個1的累計數(shù)，此后的2(n-m)-1位上有n-m個 1和n-m-1個0。如若把后面這2(n-m)-1位上的0和1互換，使之成為n-m個0和n-m-1個1，結(jié)果得1個由n+1個0和n-1個1組成的2n位數(shù)，即一個不合要求的數(shù)對應于一個由n+1個0和n-1個1組成的排列。
反過來，任何一個由n+1個0和n-1個1組成的2n位[二進制數(shù)]，由于0的個數(shù)多2個，2n為[偶數(shù)]，故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面部分0和1互換，使之成為由n個0和n個1組成的2n位數(shù)，即n+1個0和n-1個1組成的2n位數(shù)必對應一個不符合要求的數(shù)。
因而不合要求的2n位數(shù)與n+1個0，n－1個1組成的排列一一對應。
顯然，不符合要求的方案數(shù)為c(2n,n+1)。由此得出輸出序列的總數(shù)目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。

類似問題：

Q1：有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少中方法使得只要有10元的人買票，售票處就有5元的鈔票找零？
A1：將持5元者到達視作將5元入棧，持10元者到達視作使棧中某5元出棧。

Q2：12個高矮不同的人，排成兩排，每排必須是從矮到高排列，而且第二排比對應的第一排的人高，問排列方式有多少種？
A2：我們先把這12個人從低到高排列,然后,選擇6個人排在第一排,那么剩下的6個肯定是在第二排.
用0表示對應的人在第一排,用1表示對應的人在第二排,那么含有6個0,6個1的序列,就對應一種方案.
比如1 2 3 4 5 6 7 8 9 10 11 12
000000111111就對應著
第一排：0 1 2 3 4 5
第二排：6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11 12
010101010101就對應著
第一排：0 2 4 6 8 10
第二排：1 3 5 7 9 11
類似于ctci9.5中的打印n對括號的有效組合，何時可以使用左括號呢？何時可以使用右括號呢？
(1)左括號：只要左括號沒有用完，就可以插入左括號
(2)右括號：只要不造成語法錯誤，就可以使用右括號。何時會出現(xiàn)語法錯誤？如果右括號比左括號還多，就會出現(xiàn)語法錯誤。
Q3：n對括號的有效組合數(shù)