題目：給定進(jìn)棧順序1浩销，2贯涎，……，n慢洋，求出棧序列個(gè)數(shù)塘雳。
分析：關(guān)鍵點(diǎn)就是空棧不能出棧。以“1”表示進(jìn)棧普筹，“0”表示出棧败明，則n個(gè)數(shù)總共進(jìn)棧n次，出棧n次太防。一個(gè)進(jìn)出棧序列可以唯一表示成110011…01妻顶， 此時(shí)酸员，進(jìn)出棧問題變成了排列問題。
如果不考慮合理性（即空棧出棧）讳嘱，此時(shí)共有C(2n,n)個(gè)序列幔嗦。
那么不合理的序列有多少種？有C(2n,n-1)種沥潭。
所以總的出棧序列個(gè)數(shù)就是上面兩個(gè)數(shù)相減C(2n,n) - C(2n,n-1) =?C(2n,n) /(n+1) 邀泉，也就是卡特蘭數(shù)。
下面解釋不合理序列個(gè)數(shù)C(2n,n-1)怎么來的：
????????????對(duì)于一個(gè)不合理的進(jìn)出棧序列比如1101000……10钝鸽，從左到右汇恤，必然在某一奇數(shù)位2m+1首先出現(xiàn)m+1個(gè)0，和m個(gè)1拔恰。（為什么不是偶數(shù)位因谎，因?yàn)檫@個(gè)數(shù)之前都是合理的，合理的數(shù)必然是0和1個(gè)數(shù)相等（椦瞻茫空）财岔，或者1比0多。第一種情況下出現(xiàn)0饭冬，此時(shí)恰好不合理使鹅，恰好在奇數(shù)位，第二種情況出現(xiàn)0昌抠，序列仍然合理） 此后的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組成的排列，即C(2n,n-1)
為什么能這么算侨艾？ 如果我們把原不合理序列稱作序列①执虹，由n+1個(gè)0和n-1個(gè)1組成的的序列稱作序列②，可以發(fā)現(xiàn)①和②是一一映射的：
每一個(gè)序列①都可以唯一地?fù)Q成序列②唠梨。充分性：必然充分袋励。唯一性：①中不同的序列1和2，映射后必然不同当叭，故①->②是單射
任一序列②都可以唯一地?fù)Q成序列①茬故。充分性：對(duì)于任一序列②度帮，由n+1個(gè)0和n-1個(gè)1組成的2n位序列菲盾，由于0的個(gè)數(shù)多2個(gè)，2n為偶數(shù)是尖，故必在某一個(gè)奇數(shù)位上出現(xiàn)0的累計(jì)數(shù)超過1的累計(jì)數(shù)醉箕，當(dāng)我們找到不合理奇數(shù)位時(shí)钾腺，將其后的0徙垫，1互換，即可還原成①放棒。唯一性：對(duì)于②中不同序列1和2姻报，如果某兩位不同（不會(huì)出現(xiàn)只有一位不同的情況），映射后仍然會(huì)不同哨查，故②到①只能是單射逗抑。
結(jié)論：②的個(gè)數(shù)（由n+1個(gè)0和n-1個(gè)1組成的2n位序列的排列C(2n,n-1)）也就是①的個(gè)數(shù)剧辐。
