令1表示進(jìn)棧，0表示出棧，則可轉(zhuǎn)化為求一個(gè)2n位、含n個(gè)1、n個(gè)0的二進(jìn)制數(shù)，滿足從左往右掃描到任意一位時(shí)，經(jīng)過的0數(shù)不多于1數(shù)。顯然含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù)共有個(gè)，下面考慮不滿足要求的數(shù)目。

考慮一個(gè)含n個(gè)1、n個(gè)0的2n位二進(jìn)制數(shù)，掃描到第2m+1位上時(shí)有m+1個(gè)0和m個(gè)1（容易證明一定存在這樣的情況），則后面的0-1排列中必有n-m個(gè)1和n-m-1個(gè)0。將2m+2及其以后的部分0變成1、1變成0，則對(duì)應(yīng)一個(gè)n+1個(gè)0和n-1個(gè)1的二進(jìn)制數(shù)。

反過來，任何一個(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ù)超過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)。

從而。證畢。