作者：寒小陽 時間：2013年9月。
出處：http://blog.csdn.net/han_xiaoyang/article/details/11596001芋簿。
聲明：版權所有，轉載請注明出處，謝謝敲才。

0挪拟、前言

當年博主自己參加校招筆試面試時就遇到過幾次catalan數(shù)相關的題目击你，今年又到了互聯(lián)網(wǎng)招聘季玉组，翻看下近期各大公司的筆試面試題丁侄，發(fā)現(xiàn)它依舊是很容易被考察的點。尷尬的是鸿摇，博主自己覺得catalan數(shù)相關的題目不好歸類到某種具體的數(shù)據(jù)結構或者算法里面(計算catalan數(shù)的那個小程序不算算法吧吨凑。。户辱。)庐镐，而是比較偏數(shù)學題。

不管怎么說怠堪，它是筆試面試中容易出現(xiàn)的東西名眉，而有一部分同學可能不大熟悉。這里把catalan數(shù)的由來和筆試面試中涉及它的相關問題整理了一下陌粹，單獨發(fā)一篇文吧福压，不熟悉的童鞋們看看，可能會有幫助蒙幻。

一邮破、catalan數(shù)由來和性質

1）由來
catalan數(shù)（卡塔蘭數(shù)）取自組合數(shù)學中一個常在各種計數(shù)問題中出現(xiàn)的數(shù)列。以比利時的數(shù)學家歐仁·查理·卡塔蘭 (1814–1894)命名队询。

卡塔蘭數(shù)的一般項公式為

我們從中取出的Cn就叫做第n個Catalan數(shù)范嘱，前幾個Catalan數(shù)是：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, …咋看之下沒什么特別的，但是Catalan數(shù)卻是許多計數(shù)問題的最終形式叠聋。

2）性質
1受裹、Catalan數(shù)的基本公式就是上面列出的式子棉饶，但是卻有一些變形和具體的性質：

二起愈、Catalan數(shù)的程序求解

//函數(shù)功能: 計算Catalan數(shù)列的第n項
//函數(shù)參數(shù): 項數(shù)n
//返回值:   第n個Catalan數(shù)
long Catalan(int n)
{
if(n <= 1)
return 1;
long *h = new long[n+1]; //保存臨時結果
h[0] = h[1] = 1;        //h(0)和h(1)
for(int i = 2; i <= n; i++)    //依次計算h(2),h(3)...h(n)
{
h[i] = 0;
for(int j = 0; j < i; j++) //根據(jù)遞歸式計算 h(i)= h(0)*h(i-1)+h(1)*h(i-2) + ... + h(i-1)h(0)
h[i] += (h[j] * h[i-1-j]);
}
long result = h[n]; //保存結果
delete [] h;       //注意釋放空間
return result;
}

三、Catalan數(shù)的應用場景和筆試面試中出現(xiàn)過的題目

1坤次、括號匹配問題

n對括號相當于有2n個符號疤剑，n個左括號闷堡、n個右括號杠览，可以設問題的解為f(2n)。第0個符號肯定為左括號管钳，與之匹配的右括號必須為第2i+1字符软舌。因為如果是第2i個字符，那么第0個字符與第2i個字符間包含奇數(shù)個字符醇滥，而奇數(shù)個字符是無法構成匹配的鸳玩。

通過簡單分析演闭，f(2n)可以轉化如下的遞推式 f(2n) = f(0)f(2n-2) + f(2)f(2n - 4) + ... + f(2n - 4)f(2) + f(2n-2)f(0)船响。簡單解釋一下，f(0) * f(2n-2)表示第0個字符與第1個字符匹配见间，同時剩余字符分成兩個部分，一部分為0個字符菱蔬，另一部分為2n-2個字符，然后對這兩部分求解魏身。f(2)*f(2n-4)表示第0個字符與第3個字符匹配蚪腐，同時剩余字符分成兩個部分回季，一部分為2個字符，另一部分為2n-4個字符颤殴。依次類推鼻忠。

假設f(0) = 1帖蔓，計算一下開始幾項，f(2) = 1, f(4) = 2, f(6) = 5芥永。結合遞歸式钝吮，不難發(fā)現(xiàn)f(2n) 等于h(n)。

2棘催、進棧出棧問題

這個與加括號的很相似，進棧操作相當于是左括號雳灵，而出棧操作相當于右括號闸盔。n個數(shù)的進棧次序和出棧次序構成了一個含2n個數(shù)字的序列蕾殴。第0個數(shù)字肯定是進棧的數(shù)岛啸，這個數(shù)相應的出棧的數(shù)一定是第2i+1個數(shù)坚踩。因為如果是2i，那么中間包含了奇數(shù)個數(shù)批幌，這奇數(shù)個肯定無法構成進棧出棧序列嗓节。

設問題的解為f(2n)拦宣， 那么f(2n) = f(0)f(2n-2) + f(2)f(2n-4) + f(2n-2)f(0)。f(0) * f(2n-2)表示第0個數(shù)字進棧后立即出棧绸罗，此時這個數(shù)字的進棧與出棧間包含的數(shù)字個數(shù)為0珊蟀，剩余為2n-2個數(shù)外驱。f(2)f(2n-4)表示第0個數(shù)字進棧與出棧間包含了2個數(shù)字昵宇，相當于1 2 2 1，剩余為2n-4個數(shù)字绽诚。依次類推。

假設f(0) = 1卒落，計算一下開始幾項蜂桶，f(2) = 1, f(4) = 2, f(6) = 5扑媚。結合遞歸式，不難發(fā)現(xiàn)f(2n) 等于h(n)费坊。

3旬痹、二叉樹的種類問題

可以這樣考慮，根肯定會占用一個結點意蛀，那么剩余的n-1個結點可以有如下的分配方式峰鄙，T(0, n-1),T(1, n-2),...T(n-1, 0)吟榴，設T(i, j)表示根的左子樹含i個結點，右子樹含j個結點兜看。

設問題的解為f(n)细移，那么f(n) = f(0)f(n-1) + f(1)f(n-2) + .......+ f(n-2)f(1) + f(n-1)f(0)熊锭。假設f(0) = 1，那么f(1) = 1, f(2) = 2, f(3) = 5精绎。結合遞推式代乃，不難發(fā)現(xiàn)f(n)等于h(n)。

4原茅、網(wǎng)格路徑問題

5、凸多邊形分割問題

以凸多邊形的一邊為基也祠，設這條邊的2個頂點為A和B近速。從剩余頂點中選1個，可以將凸多邊形分成三個部分崎场，中間是一個三角形遂蛀，左右兩邊分別是兩個凸多邊形李滴，然后求解左右兩個凸多邊形。

設問題的解f(n)谆扎，其中n表示頂點數(shù)芹助，那么f(n) = f(2)f(n-1) + f(3)f(n-2) + ......f(n-2)f(3) + f(n-1)f(2)状土。f(2)*f(n-1)表示三個相鄰的頂點構成一個三角形蒙谓，那么另外兩個部分的頂點數(shù)分別為2和n-1。

設f(2) = 1酣倾，那么f(3) = 1, f(4) = 2, f(5) = 5躁锡。結合遞推式置侍，不難發(fā)現(xiàn)f(n) 等于h(n-2)墅垮。

6、集合劃分問題

這里解釋一下不交叉劃分峡钓，我們對于集合{a,b}和{c,d}，假設他們組成了兩個區(qū)間[a,b]和[c,d]寞宫，我們假設兩個區(qū)間不重合辈赋，那么以下四種情況當做是不交叉的：a<c<d<b膏燕，a<b<c<d坝辫，c<a<b<d與c<d<a<b近忙，就是說兩個區(qū)間可以包含或者相離，那么此時我們稱集合{a,b}和{c,d}是不交叉的未辆。

對于集合{1,2,3...2n}击纬，將里面元素兩兩分為一子集更振，共n個肯腕，若任意兩個子集都是不交叉的钥平，那么我們稱此時的這個劃分為一個不交叉劃分涉瘾。此時不交叉的劃分數(shù)就是我們的了，證明也很容易负敏，我們將每個子集中較小的數(shù)用左括號代替其做，較大的用右括號代替，那么帶入原來的1至2n的序列中就形成了合法括號問題驹沿，就是我們之前得到過的結論渊季。例如我們的集合{1,2,3,4,5,6}的不交叉劃分有五個：{{1,2},{3,4},{5,6}}梭域，{{1,2},{3,6},{4,5}}搅轿，{{1,4},{2,3},{5,6}}璧坟，{{1,6},{2,3},{4,5}}和{{1,6},{2,5},{3,4}}。

7幻工、階梯切分問題

這個證明是怎么進行的呢囊颅？我們先繪制如下的一張圖片踢代，即n為5的時候的階梯：

我們注意到每個切割出來的矩形都必需包括一塊標示為的小正方形胳挎，那么我們此時枚舉每個與#標示的兩角作為矩形溺森，剩下的兩個小階梯就是我們的兩個更小的子問題了屏积，于是我們的C5 = C0 * C4 + C1 * C3 + C2 * C2 + C1 * C3 + C0 * C4炊林，注意到這里的式子就是我們前面的性質3,因此這就是我們所求的結果了。

8隔显、乘積重組問題

我們這樣考慮竞思，首先通過括號化盖喷，將P分成兩個部分难咕，然后分別對兩個部分進行括號化余佃。比如分成(a1)×(a2×a3.....×an)，然后再對(a1)和(a2×a3.....×an)分別括號化沾歪；又如分成(a1×a2)×(a3.....×an)，然后再對(a1×a2)和(a3.....×an)括號化立润。

設n個矩陣的括號化方案的種數(shù)為f(n)桑腮，那么問題的解為

f(n) = f(1)f(n-1) + f(2)f(n-2) + f(3)f(n-3) + f(n-1)f(1)蛉幸。f(1)*f(n-1)表示分成(a1)×(a2×a3.....×an)兩部分，然后分別括號化烫沙。

計算開始幾項隙笆，f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5锌蓄。結合遞歸式，不難發(fā)現(xiàn)f(n)等于h(n-1)撑柔。

9瘸爽、連線不想交問題

我們這樣考慮剪决，以其中一個點為基點，編號為0檀训，然后按順時針方向將其他點依次編號。那么與編號為0相連點的編號一定是奇數(shù)肢扯，否則妒茬，這兩個編號間含有奇數(shù)個點，勢必會有個點被孤立蔚晨，即在一條線段的兩側分別有一個孤立點乍钻，從而導致兩線段相交。設選中的基點為A铭腕，與它連接的點為B银择，那么A和B將所有點分成兩個部分，一部分位于A累舷、B的左邊浩考，另一部分位于A、B的右邊被盈。然后分別對這兩部分求解即可析孽。

設問題的解f(n)，那么f(n) = f(0)f(n-2) + f(2)f(n-4) + f(4)f(n-6) + ......f(n-4)f(2) + f(n-2)f(0)只怎。f(0)f(n-2)表示編號0的點與編號1的點相連袜瞬，此時位于它們右邊的點的個數(shù)為0，而位于它們左邊的點為2n-2身堡。依次類推邓尤。

f(0) = 1, f(2) = 1, f(4) = 2。結合遞歸式，不難發(fā)現(xiàn)f(2n) 等于h(n)汞扎。

10季稳、高矮排隊問題

先將2n個人從低到高排列，然后澈魄，用0表示對應的人在第一排,用1表示對應的人在第二排,那么含有n個0,n個1的序列,就對應一種方案.
比如00...011...1就對應著
第一排:1 2 3 ...n
第二排:n+1 n+2 n+3 ...2n

而010101...01對應著

第一排:1 3 5 ...2n-1
第二排:2 4 6 ...2n

觀察1的出現(xiàn),我們考慮它能不能放在第二排,顯然,在這個1之前出現(xiàn)的那些0和1對應的人 要么是在這個1左邊,要么是在這個1前面景鼠。而即使前面0和1剛好配對，也一定要留出一個0在這個1前面一忱，也就是要求之前的0的個數(shù)大于1的個數(shù).

如果把0看成入棧操作,1看成出棧操作,就是說給定2n個元素,合法的入棧出棧序列有多少個莲蜘。這就是catalan數(shù),其通項是c(2n, n)/(n+1).

11、格子填數(shù)問題
在一個2*n的格子中填入1到2n這些數(shù)值使得每個格子內的數(shù)值都比其右邊和上邊的所有數(shù)值都小的情況數(shù)

這一題和上一題排隊是一樣的思路帘营。

12票渠、門票找錢問題

可以將持5元買票視為進棧算途，那么持10元買票視為5元的出棧塞耕。這個問題就轉化成了棧的出棧次序數(shù)。由應用三的分析直接得到結果嘴瓤，f(2n) 等于h(n)扫外。

四、Catalan數(shù)的一個變形應用

上面第12小題的一個延伸：n+m個人排隊買票廓脆，并且滿足n>= m筛谚，票價為5元，其中n個人各手持一張5元鈔票停忿，m個人各手持一張10元鈔票驾讲，除此之外大家身上沒有任何其他的錢幣，并且初始時候售票窗口沒有錢席赂，問有多少種排隊的情況數(shù)能夠讓大家都買到票吮铭。

這個題目是Catalan數(shù)的變形，不考慮人與人的差異颅停，如果m=n的話那么就是我們初始的Catalan數(shù)問題沐兵，也就是將手持5元的人看成是入棧，手持10元的人看成是出棧便监，出棧序列的個數(shù)。

這個題目區(qū)別就在于n>m的情況，此時我們仍然可以用原先的證明方法考慮烧董，假設我們要的情況數(shù)是D(n+m)毁靶，無法讓每個人都買到的情況數(shù)是U(n + m)，那么就有D(n+m) + U(n +m) = C(m+n, n)逊移，此時我們求U(n + m)预吆，我們假設最早買不到票的人編號是k，他手持的是10元并且售票處沒有錢胳泉，那么將前k個人的錢從5元變成10元拐叉，從10元變成5元，這時候就有n+1個人手持5元扇商，m-1個手持10元的凤瘦，所以就得到U(n + m) = C(n + m, n + 1)，于是我們的結果就因此得到了案铺，表達式是D(n + m) = C(n + m, n) - C(n + m, n + 1)蔬芥。