關(guān)于catalan數(shù)，筆者有很多想說的，也籌劃過一段時間了。

catalan數(shù)最常見的問題如以下幾種：

1.出棧序列

棧作為計算機中一種數(shù)據(jù)結(jié)構(gòu)，與隊列不同，此處不做介紹。

有一進(jìn)棧序列為1~n的正整數(shù)列，問其出棧序列有多少種。

2.whitworth路線

從原點(0,0)沿坐標(biāo)網(wǎng)走到格點(n,n)的路線，不在直線y=x上方出現(xiàn)的路線稱為whitworth路線，后文簡稱W線，問W線有多少種。

3.排序

在一串由n個0與n個1構(gòu)成的序列中，前k項和≤k/2恒成立，問該類序列有多少種。

上述三中問題的答案均為標(biāo)準(zhǔn)的catalan數(shù)，在本文中以大寫英文字母C來表示catalan數(shù)。

易得上述三個問題可以構(gòu)成雙射，此處不作贅述，先擺出答案。

斜線上的數(shù)均為標(biāo)準(zhǔn)catalan數(shù)，如上所述用C(n)來表示。格點上的數(shù)用C(i,j)（注意與組合數(shù)區(qū)分）來表示。定義如下：

C(n,0)=0, C(i,j)=C(i-1,j)+C(i,j-1) (i＞j＞0), C(n)=C(n,n)=C(n,n-1)

那C(i,j)的意義是什么呢，先給出結(jié)論，就是從原點(0,0)到格點(i,j)的W線數(shù)。

筆者提供一種常見證明如下：

該類問題還可以使用母函數(shù)

以下引用兩例：

eg1.甲、乙打乒乓球，最后甲以11：6獲勝，求在比賽過程中甲一直領(lǐng)先的比分序列的個數(shù)。

易證其為C(11,6)，過于簡單，此處省略證明。

eg2.求1,2,?,n的排列(a?,a?,?,a?)的個數(shù)，使得不存在1≤i<j<k≤n，滿足ai<aj<ak。

留給讀者自行證明。