catalan數證明

定理：n個1 和n個-1 構成的2n項a1,a2….a2n ,其部分和

滿足a1 + a2 + …aK >= 0 (k = 1 2 …2n ) 這個的條件的個數 為

證明：令An 為其中可以接受的系列Bn 為不可接受的系列

那麼An + Bn =  .An 是我們要求的，我們可以通過求出Bn來得到An 。

我們假設存在 一個最小的K 使得a1 + a2 +…+ak 為負，那麼 可以肯定a1+…+ak-1 = 0,且ak = -1.k 為奇整數。

對於每一種不符合條件的序列a1 + a2 +…+ak +…+a2n 將a1 a2 ak 都用-a1 –a2 –ak 代替，那麼新的數列

a1’a2’ …a2n’ 就有n+1 個+1 和n-1 個 –1  。即每一種 不符合條件的 數列經過上述過程都將變為

  n+1 個+1 和n-1 個 –1   的排列 。那麼現在要證明n+1 個+1 和n-1 個 –1   的排列數== Bn

n+1 個+1 和n-1 個 –1   的排列 肯定存在一個 最小的k 使得a1 + a2 + …aK <  0   而將這部分也用-a1 –a2 –ak 代替 ，也就成為了n個1 和n個-1 構成的2n項a1,a2….a2n   而Bn的排列就好求了

==》

應用： 有2n個人要去劇場，入場5角，有n個人有1元，n個人有5角，劇場的賣票處剛開始沒有零錢，那麼存在多少種隊列方式。

粗體的證明 ，我感覺有些牽強，呵呵 大家有好的方法，請指正。