1，概念

? ? ? ? 卡特蘭數(shù)（英語(yǔ)：Catalan number），又稱卡塔蘭數(shù)，明安圖數(shù)。是組合數(shù)學(xué)中一種常出現(xiàn)于各種計(jì)數(shù)問(wèn)題中的數(shù)列。它在不同的計(jì)數(shù)問(wèn)題中頻繁出現(xiàn)。

2，公式

? ? ? ?卡特蘭數(shù)的遞推公式為：f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ... + f(n - 1) * f(0)，其中初始值f(0) = f(1) = 1。

????????這個(gè)數(shù)列的前幾項(xiàng)為：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452...。

3，卡特蘭數(shù)代碼實(shí)現(xiàn)

遞歸

int catalan1(int n)
{
?? ?if (n <= 1) return 1;

?? ?int res = 0;
?? ?for (int i = 1; i <= n - 1; i++)
?? ??? ?res += catalan1(i)*catalan1(n-i);

?? ?return res;
}

非遞歸

int catalan2(int n)
{
?? ?if (n <= 1) return 1;

?? ?int* h = new int[n];
?? ?h[0] = h[1] = 1;
?? ?for (int i = 2; i < n ; i++)
?? ?{
?? ??? ?h[i] = 0;
?? ??? ?for (int j = 0; j < i; j++)
?? ??? ??? ?h[i] += (h[j] * h[i - 1 - j]); //f[i]=f[0]*f[i-1]+f[1]*f[i-2]+...+f[i-1]*f[0]
?? ?}
?? ?int result = h[n-1];
?? ?delete[] h;
?? ?return result;?

}

4，卡特蘭數(shù)的應(yīng)用?

? ? ? ? 對(duì)于卡特蘭數(shù)的介紹，我們只知道了它是組合數(shù)學(xué)中的一種規(guī)律，并沒(méi)有具體意義，是一個(gè)常見的數(shù)學(xué)規(guī)律。

????????對(duì)于卡特蘭數(shù)的初步理解：有一些操作，這些操作有一定的限制，如一種操作數(shù)不能超過(guò)另一種操作數(shù)，或兩種操作數(shù)不能有交集，求這些操作的合法數(shù)量。

應(yīng)用1：出棧次序（進(jìn)出棧問(wèn)題）

【問(wèn)題描述】

一個(gè)無(wú)窮大的棧，進(jìn)展序列為1，2，3，......，n,問(wèn)出棧順序有多少種？

【問(wèn)題分析】

設(shè)f(n)=序列個(gè)數(shù)為n的出棧序列種數(shù)。假定，從開始到棧第一次出空為止，這段過(guò)程中第一個(gè)出棧的序數(shù)是k，如果棧直到整個(gè)過(guò)程結(jié)束時(shí)，才為空，那么k=n；首次出空之前，第一個(gè)出棧序數(shù)k，將1~n的序列劃分成兩部分。其中一個(gè)是1~k-1，一共k-1個(gè)數(shù)；另一部分是k+1~n，一共n-k個(gè)數(shù)。

此時(shí)，我們把k看作是一個(gè)序數(shù)，根據(jù)乘法原理，f(n)就等價(jià)于 序列個(gè)數(shù)為k-1的出棧序列種樹*序列個(gè)數(shù)為n-k的出棧序列種樹。即f(n)=f(k-1)*f(n-k)。而k可以從1選到n，再根據(jù)加法原理，將k取不同的值，然后求和，得到總序列種數(shù)為：f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)。就是卡特蘭數(shù)的規(guī)律，再令f(0)=f(1)=1求解即可。

應(yīng)用2：括號(hào)匹配

【問(wèn)題描述】

由一對(duì)括號(hào)，可以組成一種合法序列：（）

由兩對(duì)括號(hào)，可以組成兩種合法序列：()()，(())

問(wèn):由n對(duì)括號(hào)組成的合法括號(hào)序列一共有多少中？

【問(wèn)題分析】

? ? ? ? 首先，n對(duì)括號(hào)我們看成是2n個(gè)字符，n個(gè)左括號(hào)，n個(gè)右括號(hào)。設(shè)問(wèn)題的解為f(2n)。第0個(gè)字符肯定為左括號(hào)，而第2*i+1個(gè)字符肯定為右括號(hào)，如果第2*i個(gè)字符為右括號(hào)，那么0~2*i一共由2*i+1奇數(shù)個(gè)字符，而奇數(shù)個(gè)字符是 無(wú)法匹配的。

????????f(2n)可以轉(zhuǎn)化如下的遞推式 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個(gè)字符和第1個(gè)字符匹配，剩余兩部分，一部分0個(gè)字符，一部分2n-2個(gè)字符。f(2)*f(2n-4)表示 第0個(gè)字符和第3個(gè)字符匹配，剩余兩部分，一部分2個(gè)字符，一部分2n-4個(gè)字符。以此類推可得出遞推式。

? ? ? ? f(0)=1，分別計(jì)算出f(1),f(2),f(3),f(4),f(5)，得出f(2n)就是一個(gè)卡特蘭數(shù)的數(shù)列。

應(yīng)用3：二叉樹生成問(wèn)題

【問(wèn)題描述】

n個(gè)節(jié)點(diǎn) 構(gòu)成的二叉數(shù)，共有多少情形？

【問(wèn)題分析】

? ? ? ? 設(shè)題解為f(n)，T(i,j)表示：一顆二叉樹，它的左子樹有i個(gè)節(jié)點(diǎn)，右子樹有j個(gè)節(jié)點(diǎn)。

? ? ? ? 根肯定會(huì)占用一個(gè)節(jié)點(diǎn)，那么它的左右子樹：T(0,n-1),T(1,n-2),T(2,n-3),...,T(n-1,0)。

? ? ? ? 那么f(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*f(n-3)+...+f(n-1)*f(0)。假設(shè) f(0)=1,那么f(1)=1,f(2)=2,f(3)=5,滿足卡特蘭數(shù)的規(guī)律。

應(yīng)用4：矩陣鏈乘

【問(wèn)題描述】

矩陣鏈乘： P=a1×a2×a3×……×an，依據(jù)乘法結(jié)合律，不改變其順序，只用括號(hào)表示成對(duì)的乘積，試問(wèn)有幾種括號(hào)化的方案？

【問(wèn)題分析】

????????首先通過(guò)括號(hào)化，將P分成兩個(gè)部分，然后分別對(duì)兩個(gè)部分進(jìn)行括號(hào)化。比如分成(a1)×(a2×a3.....×an)，然后再對(duì)(a1)和(a2×a3.....×an)分別括號(hào)化；又如分成(a1×a2)×(a3.....×an)，然后再對(duì)(a1×a2)和(a3.....×an)括號(hào)化。

????????設(shè)n個(gè)矩陣的括號(hào)化方案的種數(shù)為f(n)，那么問(wè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)兩部分，然后分別括號(hào)化。

????????計(jì)算開始幾項(xiàng)，f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5。結(jié)合遞歸式，滿足卡特蘭數(shù)規(guī)律。