從這節(jié)開始，我們遇到的組合數(shù)可能會比較大，大到long long存不下哗讥，那怎么辦嚷那？c++大數(shù)板子歡迎你...c++大數(shù)板子有好多版本胞枕，自己寫的舒服直接保存下來備用即可，這里我不再提供魏宽，不過腐泻，這里我給大家準(zhǔn)備了Java大數(shù)運(yùn)算的簡單代碼，Java自帶大數(shù)運(yùn)算這個(gè)實(shí)屬良心之舉队询，可以關(guān)注我博客派桩，傳送門，只是簡單介紹哦蚌斩，深入探討咨詢度娘铆惑。
開始正題，Catalan數(shù)是一組比較神奇的數(shù)字1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670,不要小看這組數(shù)字送膳，他的神秘之處在于：我們記C[n]為Catalan數(shù)列第n+1個(gè)數(shù)员魏，從0開始，也就是說C[0] = 1 , C[1] = 1 , C[2] = 2 ... 結(jié)果你會發(fā)現(xiàn)：
- 1 如果序列1叠聋，2撕阎，...，n入棧碌补，那么C[n] 就是這組數(shù)字出棧的排列種數(shù)虏束，也就是對應(yīng)的Catalan數(shù)棉饶。
- 2 對一個(gè)有N + 2 條邊的凸多邊形(N>=1)用連接頂點(diǎn)的不相交對角線將該多邊形拆分成若干三角形，那么C[n]就是拆分的方法數(shù)镇匀，也就是對應(yīng)的Catalan數(shù)照藻。
- 3 具有n個(gè)節(jié)點(diǎn)的二叉樹有多少種呢？C[n]個(gè)坑律，也就是對應(yīng)的Catalan數(shù)岩梳。
- 4 給出n對括號，括號正確配對的字符串個(gè)數(shù)就是C[n]對應(yīng)的Catalan數(shù)晃择。
- 更多Catalan數(shù)的應(yīng)用可以查詢百度冀值。
那么重點(diǎn)來了，既然Catalan數(shù)這么神奇宫屠，這Catalan數(shù)有什么共性呢列疗？其實(shí)是有的:
Catalan數(shù)的計(jì)算公式是 C[0] = 1 , C[1] = 1 , C[n] = C[0] * C[n-1] + C[1] * C[n-2] + C[2] * C[n-3]+....+C[n-1] * C[0].
Catalan數(shù)的遞推公式為C[n] = C[n-1](4n-2)/(n+1)，這樣我們就可以愉快的遞推了浪蹂。
這里我選擇將入棧數(shù)這個(gè)應(yīng)用講一下證明抵栈，其它的應(yīng)用，大家也可以在百度上找到坤次，網(wǎng)上關(guān)于這些的博客也有很多古劲，我就不一一講解了，其實(shí)我自己也并不掌握很好缰猴，避免誤人子弟（??逃....
??N個(gè)數(shù)出棧排列數(shù)的證明
設(shè)C[n]是序列1产艾，2....N入棧后，出棧的排列數(shù)滑绒。顯然闷堡，C[0] = 1 C[1] = 1 C[2] = 2 ; 對于C[n] (n>=2) 如果第一個(gè)出棧的數(shù)是K，則K這個(gè)數(shù)字將序列1.....N分成兩個(gè)子序列：序列1....K-1(長度為K-1疑故，已經(jīng)入棧) 和序列 K+1.....N(長度為N-K杠览，尚未入棧)，則由乘法原理纵势，如果第一個(gè)出棧數(shù)是K踱阿，則出棧的排列數(shù)為F[k] = C[k-1] * C[n-k]；钦铁，因?yàn)?<=K<=N,則N個(gè)數(shù)總的排列方法為K從1取值到N软舌，即F[1]+F[2].....+F[N] ；即C[N] = C[0]C[n-1]+C[1]C[n-2]+....+C[n-1]*C[0]育瓜；即Catalan數(shù)的公式葫隙。
碼到這里累死我了.....??.....插播一條廣告吧：有沒有對機(jī)器學(xué)習(xí)，物聯(lián)網(wǎng)躏仇，大數(shù)據(jù)恋脚，云計(jì)算感興趣的童鞋腺办，我有個(gè)交流群，想把它建設(shè)起來糟描，大家來助力哇怀喉，有想法的私聊我，咱們大二大三的時(shí)候一塊做項(xiàng)目??
廣告之后船响，馬上回來躬拢，接下來，我給出一道Catalan數(shù)列應(yīng)用的題见间，大家看一下：
題面：
這是一個(gè)很小但是很古老的游戲聊闯。請您以順時(shí)針順序在地上寫下連續(xù)的數(shù)字：1，2米诉，3.....2N-1菱蔬，2N。這2N個(gè)數(shù)字形成一個(gè)圓圈史侣；然后拴泌，你來畫一些線段，將這些書連接成整數(shù)的數(shù)對惊橱，每一個(gè)數(shù)都要連到另一個(gè)數(shù)字上蚪腐，而且沒有兩個(gè)線段是相交的。這是個(gè)簡單的游戲是不是税朴？當(dāng)您寫完這些數(shù)字的時(shí)候回季，您來告訴大家，對于輸入的N可以有多少種不同的方式將這些數(shù)字連成數(shù)對掉房？（1<=N<=100）
解析
先確定一個(gè)點(diǎn)茧跋，然后枚舉其它的點(diǎn)P與這個(gè)點(diǎn)相連慰丛，構(gòu)成一條線段卓囚，保證這條線段把所有的點(diǎn)分成兩部分，且都是偶數(shù)個(gè)诅病，也就是整數(shù)對個(gè)哪亿。那么這樣的點(diǎn)P有N個(gè)，（到時(shí)候我可以畫圖演示贤笆，這里不懂現(xiàn)在可以私聊我）蝇棉，設(shè)這條線段左邊有i對點(diǎn)，那么這條線段左邊的點(diǎn)的連接方法數(shù)就有C[i]種芥永，而線段右邊有n-i-1對點(diǎn)篡殷，（因?yàn)橛幸粭l線段已經(jīng)連接了一對點(diǎn)，所以剩下n-1對點(diǎn)埋涧，也就是2*n-2個(gè)點(diǎn)）板辽，所以我們可以得到遞推公式：C[n] = C[i] * C[n-i-1] ( i從0到n-1) , 而這一遞推公式正是Catalan數(shù)的遞推公式奇瘦。
為了提高效率，我們先離線計(jì)算出前110個(gè)Catalan數(shù)來劲弦，由于Catalan數(shù)的上限超過了long long的范圍耳标，所以我們得采用用高精度計(jì)算了。
Java高精度簡單學(xué)習(xí)??傳送門
Java代碼：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String []args){
Scanner in = new Scanner(System.in);
int k = in.nextInt();
while(k!=-1){
BigInteger a,b;
a = BigInteger.valueOf(1);
b = BigInteger.valueOf(1);
for(int i = 2; i <= k; i++) {
b = a.multiply(BigInteger.valueOf(4*i-2));
b = b.divide(BigInteger.valueOf(i+1));
a = b;
}
System.out.println(b);
k = in.nextInt();
}
in.close();
}
}
其實(shí)無非就是用了一個(gè)遞推公式C[n] = C[n-1](4n-2)/(n+1)邑跪，這是Catalan數(shù)的遞推公式次坡，問題在于大數(shù)運(yùn)算，如果選擇Java的話画畅，在程序編寫上應(yīng)該就比較輕松砸琅。
注意，這里只是簡單介紹了Catalan數(shù)列轴踱，如果深入研究可以參考其他大牛的Blog明棍，深入探討已經(jīng)超出了我這個(gè)組合數(shù)學(xué)小白的能力（菜是原罪）。有問題可以私聊我寇僧，歡迎指正摊腋，謝謝啦...
大家對于Catalan數(shù)列其它應(yīng)用的理解也可以找我討論，僅討論而已??
