卡特蘭數(shù)（Catalan number），又稱卡塔蘭數(shù)、明安圖數(shù)，是組合數(shù)學(xué)中一種常出現(xiàn)于各種計(jì)數(shù)問題中的數(shù)列。它以比利時(shí)數(shù)學(xué)家歐仁·查理·卡特蘭的名字命名，但值得注意的是，這一數(shù)列的首次發(fā)現(xiàn)可以追溯到1730年，由清代蒙古族數(shù)學(xué)家明安圖在對(duì)三角函數(shù)冪級(jí)數(shù)的推導(dǎo)過程中得出，并在1774年被發(fā)表在《割圜密率捷法》中。

定義與性質(zhì)

卡特蘭數(shù)的前幾項(xiàng)為（從第0項(xiàng)開始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …。它有多種數(shù)學(xué)表示方式，包括但不限于以下幾種：

• 通項(xiàng)公式：$f(n)=\frac{C_{2n}^n}{n+1}=C_{2n}^n?C_{2n}^{n?1}$，其中$C_{2n}^n$表示從2n個(gè)不同元素中取出n個(gè)元素的組合數(shù)。
• 遞推公式：$f(n)=\frac{4n?2}{n+1}f(n?1)$，對(duì)于$n\ge 1$，且$f(0)=1$。
• 遞歸公式：$f(n)=f(0)?f(n?1)+f(1)?f(n?2)+\dots +f(n?1)?f(0)$，表示n個(gè)點(diǎn)的二叉樹構(gòu)成問題。

應(yīng)用領(lǐng)域

卡特蘭數(shù)在組合數(shù)學(xué)和計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用，包括但不限于以下幾個(gè)方面：

1. 網(wǎng)格路徑問題：在$n\times n$的網(wǎng)格中，從點(diǎn)$(0,0)$到點(diǎn)$(n,n)$，每次只能向右或向上移動(dòng)一步，且在任何時(shí)候向右走的次數(shù)都不少于向上走的次數(shù)，這樣的路徑總數(shù)即為卡特蘭數(shù)。
2. 括號(hào)匹配問題：有n個(gè)左括號(hào)和n個(gè)右括號(hào)，能夠組成的合法括號(hào)序列的數(shù)量是卡特蘭數(shù)。
3. 進(jìn)出棧問題：給定一個(gè)棧，有n次進(jìn)棧和n次出棧操作，所有可能的進(jìn)出棧序列中，合法的序列數(shù)量是卡特蘭數(shù)。
4. 二叉樹構(gòu)成問題：有n個(gè)點(diǎn)，能夠構(gòu)成的不同二叉樹的數(shù)量是卡特蘭數(shù)。
5. 凸多邊形劃分問題：凸n+2邊形用其n-1條對(duì)角線分割為互不重疊的三角形的分法總數(shù)也是卡特蘭數(shù)。

證明方法

由于卡特蘭數(shù)的定義和性質(zhì)涉及較深的組合數(shù)學(xué)知識(shí)，其證明方法通常較為復(fù)雜，且依賴于多種數(shù)學(xué)工具和技巧。這里以網(wǎng)格路徑問題為例，簡(jiǎn)要說明其證明思路：

• 首先，考慮所有從$(0,0)$到$(n,n)$的路徑，總數(shù)為$C_{2n}^n$，因?yàn)槊恳徊蕉加邢蛴一蛳蛏蟽煞N選擇，且總共要走2n步。
• 然后，考慮不合法的路徑，即存在某個(gè)時(shí)刻向上走的次數(shù)多于向右走的次數(shù)的路徑。這樣的路徑在碰到直線$y=x+1$后會(huì)繼續(xù)向上走，直到到達(dá)某個(gè)點(diǎn)$(k,k+1)$（其中$k<n$）。
• 接著，將這條不合法的路徑沿直線$y=x+1$對(duì)稱，其終點(diǎn)會(huì)變?yōu)?span id="vxwlu0yf4" class="katex--inline">$(n?1,n+1)$。
• 通過對(duì)稱操作，我們可以發(fā)現(xiàn)，每一條不合法的路徑都唯一對(duì)應(yīng)著一條從$(0,0)$到$(n?1,n+1)$的路徑。
• 因此，不合法的路徑總數(shù)為$C_{2n}^{n?1}$。
• 最后，合法的路徑總數(shù)即為所有路徑總數(shù)減去不合法的路徑總數(shù)，即$C_{2n}^n?C_{2n}^{n?1}$，這與卡特蘭數(shù)的通項(xiàng)公式一致。

需要注意的是，以上僅為網(wǎng)格路徑問題的一個(gè)證明思路示例，卡特蘭數(shù)的其他性質(zhì)和應(yīng)用領(lǐng)域的證明方法則可能有所不同。