卡特兰数~
摘dalao：Ypuyu、長滿石楠的荒原
卡特蘭數(shù)是組合數(shù)學(xué)中一個常在各種計數(shù)問題中出現(xiàn)的數(shù)列。以比利時的數(shù)學(xué)家歐仁·查理·卡塔蘭（1814–1894）命名。歷史上，清代數(shù)學(xué)家明安圖(1692年－1763年)在其《割圜密率捷法》最早用到“卡塔蘭數(shù)”，遠(yuǎn)遠(yuǎn)早于卡塔蘭。有中國學(xué)者建議將此數(shù)命名為“明安圖數(shù)”或“明安圖-卡塔蘭數(shù)”。
即卡特蘭數(shù)是符合以下公式的一個數(shù)列！
公式（常見4個）：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2, h(0)=h(1)=1)
公式證明（摘自百度百科）
在2n位上填入n個0的方案數(shù)為
。而從
?中減去不符合要求的方案數(shù)即為所求答案。
在從左往右掃時，必然會在某一個奇數(shù)位2p+1上首先出現(xiàn)p+1個1，和p個0
此后的 [2p+2,2n]上的2n?(2p+1)位有n?p個0, n?p?1個1。如若把后面這部分2n?(2p+1)位的1與0互換，使之成為n?p個1，n?p?1個0，結(jié)果得1個由n+1個1和n?1個0組成的2n位數(shù)，即一個不合法的方案必定對應(yīng)著一個由n+1個1和n-1個0組成的一個排列。
可以倒過來反證：
任意一個由n+1個1和n-1個0組成的一個排列，由于1的個數(shù)多了2個，且2n為偶數(shù)，所以必定在某個奇數(shù)位2p+1上出現(xiàn)1的個數(shù)超過0的個數(shù)。同樣把后面部分1和0互換，成為了由n個0和n個1組成的2n位數(shù)。
由此，每一個不合法的方案總是與唯一一個由n+1個1和n?1個0組成的排列一一對應(yīng)。
于是，不合法的方案數(shù)就可以寫作：
例如 10100101
是由4個0和4個1組成的8位2進(jìn)制數(shù)。但從左而右掃描在第5位（顯示為紅色）出現(xiàn)0的累計數(shù)3超過1的累計數(shù)2，它對應(yīng)于由3個1，5個0組成的10100010。
反過來 10100010
對應(yīng)于 10100101
因而不合要求的2n位數(shù)與n+1個0，n－1個1組成的排列一一對應(yīng)，故有“卡塔蘭數(shù)”Catalan
敲一敲重點！！！
以下內(nèi)容摘自卡特蘭數(shù)
（1）卡特蘭數(shù)滿足以下性質(zhì)：
令h(0)=1,h(1)=1，catalan數(shù)滿足遞推式。h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)。也就是說，如果能把公式化成上面這種形式的數(shù)，就是卡特蘭數(shù)。
當(dāng)然，上面這樣的遞推公式太繁瑣了，于是數(shù)學(xué)家們又求出了可以快速計算的通項公式。h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,…)。這個公式還可以更簡單得化為h(n)=C(2n,n)/(n+1)。后一個公式都可以通過前一個公式經(jīng)過幾步簡單的演算得來，大家可以拿起筆試試，一兩分鐘就可以搞定。（2）卡特蘭數(shù)經(jīng)常出現(xiàn)在OI以及ACM中，在生活中也有廣泛的應(yīng)用。下面舉幾個例子。
進(jìn)出棧問題：棧是一種先進(jìn)后出（FILO，First In Last Out）的數(shù)據(jù)結(jié)構(gòu)．如下圖1，1,2,3,4順序進(jìn)棧，那么一種可能的進(jìn)出棧順序是：1In→2In→2Out→3In→4In→4Out→3Out→1Out, 于是出棧序列為1,3,4,2。
那么一個足夠大的棧的進(jìn)棧序列為1,2,3,?,n時有多少個不同的出棧序列？
我們可以這樣想，假設(shè)k是最后一個出棧的數(shù)。比k早進(jìn)棧且早出棧的有k-1個數(shù)，一共有h(k-1)種方案。比k晚進(jìn)棧且早出棧的有n-k個數(shù)，一共有h(n-k)種方案。所以一共有h(k-1)*h(n-k)種方案。顯而易見，k取不同值時，產(chǎn)生的出棧序列是相互獨立的，所以結(jié)果可以累加。k的取值范圍為1至n，所以結(jié)果就為h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0)。
出棧入棧問題有許多的變種，比如n個人拿5元、n個人拿10元買物品，物品5元，老板沒零錢。問有幾種排隊方式。熟悉棧的同學(xué)很容易就能把這個問題轉(zhuǎn)換為棧。值得注意的是，由于每個拿5元的人排隊的次序不是固定的，所以最后求得的答案要n!。拿10元的人同理，所以還要n!。所以這種變種的最后答案為h(n)*n!*n!。
二叉樹構(gòu)成問題。有n個結(jié)點，問總共能構(gòu)成幾種不同的二叉樹。
我們可以假設(shè)，如果采用中序遍歷的話，根結(jié)點第k個被訪問到，則根結(jié)點的左子樹有k-1個點、根結(jié)點的右指數(shù)有n-k個點。k的取值范圍為1到n。講到這里就很明顯看得出是卡特蘭數(shù)了。這道題出現(xiàn)在2015年騰訊實習(xí)生的在線筆試題中。
凸多邊形的三角形劃分。一個凸的n邊形，用直線連接他的兩個頂點使之分成多個三角形，每條直線不能相交，問一共有多少種劃分方案。
這也是非常經(jīng)典的一道題。我們可以這樣來看，選擇一個基邊，顯然這是多邊形劃分完之后某個三角形的一條邊。圖中我們假設(shè)基邊是p1pn，我們就可以用p1、pn和另外一個點假設(shè)為pi做一個三角形，并將多邊形分成三部分，除了中間的三角形之外，一邊是i邊形，另一邊是n-i+1邊形。i的取值范圍是2到n-1。所以本題的解c(n)=c(2)*c(n-1)+c(3)*c(n-2)+…c(n-1)*c(2)。令t(i)=c(i+2)。則t(i)=t(0)*t(i-1)+t(1)*t(i-2)…+t(i-1)*t(0)。很明顯，這就是一個卡特蘭數(shù)了。
有n+1個葉子的滿二叉樹的個數(shù)？事實上，向左記為+1，向右記為?1，按照向左優(yōu)先的原則，從根節(jié)點開始遍歷．例如第一個圖記為+1,+1,+1,?1,?1,?1,于是由卡特蘭數(shù)的含義可得滿二叉樹的個數(shù)為Cn。
在n*n的格子中，只在下三角行走，每次橫或豎走一格，有多少中走法？其實向右走相當(dāng)于進(jìn)棧，向左走相當(dāng)于出棧，本質(zhì)就是n個數(shù)出棧次序的問題，所以答案就是卡特蘭數(shù)。（利用這個模型，我們解決這個卡特蘭問題的變形問題，并順便給進(jìn)出棧問題的解法一個幾何解釋．）
將一個凸n+2邊形區(qū)域分成三角形區(qū)域的方法數(shù)？（答案卡特蘭數(shù)）
先介紹兩個關(guān)于卡特蘭數(shù)Cn的小引理，將問題一中的+1和?1分別看成左括號和右括號，我們得到
引理一 由nn對括號形成的合法括號表達(dá)式的個數(shù)為C．
比如n=3時，所有合法的括號表達(dá)式有 ?(())),(())(),()(()),()()(),(()()),共5個．
考慮n+1個數(shù)相乘，不同的相乘順序的數(shù)目．我們可以給出每一個合法的括號表達(dá)式和一種可能的相乘順序的對應(yīng)方式．如n=3時，先取44個數(shù)a,b,c,d，然后在第一個數(shù)下設(shè)一個指針，將一個左括號看成是指針右移一格，而將右括號看成是將指針當(dāng)前指向的數(shù)與其左側(cè)的一個數(shù)作乘積，并刪除左側(cè)的那個數(shù)，那么當(dāng)執(zhí)行完括號表達(dá)式，就得到了一種可能的相乘順序，如圖．
這樣我們就從引理一出發(fā)得到了
引理二 n+1個數(shù)連乘，不同的乘法順序數(shù)為Cn．
注 這樣也是RPN模式的計算機(jī)的工作模式，可以無需括號完成計算，從而節(jié)省按鍵的次數(shù)．這種計算器在財務(wù)計算中大量使用，如圖．
接下來解決卡特蘭問題，用1,2,3,?,n+2標(biāo)記凸n+2邊形的邊，從標(biāo)記為1的邊的起點（按逆時針方向）開始按未標(biāo)記的對角線均為向外標(biāo)記方向，如圖．
(分別標(biāo)記邊和對角線)
進(jìn)而，逆時針讀圖，將出的箭頭讀為左括號，進(jìn)的箭頭讀為右括號，就得到了剖分方式與連乘順序的對應(yīng)．上圖中的兩個圖對應(yīng)的連乘順序表達(dá)式分別為 ：1((2(34))5)6,(1(23))(45)6,
拋開6不計，每個連乘順序表達(dá)式實際上就是規(guī)定了n+1個數(shù)連乘時，不同的乘法順序，根據(jù)引理一，得到剖分方式的總數(shù)為Cn。
為了解決這個問題，我們重新解釋卡特蘭數(shù)的推導(dǎo)方式．先解決下面的輔助問題：(+1表示向左，-1表示向右)
圓周上有2n+1個點，其中n+1個點上標(biāo)“+1”，n個點上標(biāo)“?1”，如果可以找到某個標(biāo)有“+1”的點作為起點，當(dāng)順時針沿圓周前進(jìn)時將所遇到的點（包括起點）上標(biāo)的數(shù)相加得到的和始終為正數(shù)，就稱這種標(biāo)記法是好標(biāo)記法．求好標(biāo)記法的總數(shù)（注意考慮圓排列）．
輔助問題的解 對于任何一種標(biāo)記法，我們將順時針相鄰的“+1”“?1”（指順時針前進(jìn)時先遇到“+1”后遇到“?1”）同時抹去，可以證明抹去的前后對標(biāo)記法的好壞沒有影響．不停的重復(fù)這一過程，則最后只剩一個標(biāo)有“+1”的點，顯然此時標(biāo)記法為好的．因此所有的標(biāo)記法都是好標(biāo)記法，顯然其數(shù)目為 (1/2n+1)C(2n+1,n)-(1/n+1)C(2n,n)
問題的解 通過對輔助問題的進(jìn)一步探索可知，每一種將圓周上2n+1個點標(biāo)記為n+1個+1點，和n個?1點的方法唯一確定一個順時針前進(jìn)的方案（即起點）．我們將這個起點刪去，剩下的2n個點在順時針方向上一定為“+1”“?1”“+1”“?1”，…，此時將順時針相鄰的這些“+1”“?1”點用弦連接起來，就得到互不相交的n條弦．這樣我們就建立了從好標(biāo)記法到弦的連法的單射．
反過來，如果我們有了一種弦的連法，就可以從某條弦的端點出發(fā)順時針前進(jìn)，對每條弦的兩個端點都是先遇到的端點標(biāo)上“+1”，后遇到的端點標(biāo)上“?1”，然后在最后回到出發(fā)點時添上一個標(biāo)有“+1”的點．這樣我們就建立了從弦的連法到好標(biāo)記法的單射．
綜上，所求的不同連法數(shù)為(1/n+1)C(2n,n)．
?
總結(jié)
- 上一篇： Xmodem Ymodem Zmodem
- 下一篇： 浅谈数组和指针