卡塔蘭數
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/f/f9/Catalan_number.png)
卡塔蘭數(英語:Catalan number)是組合數學中一個常在各種計數問題中出現的數列,以比利時數學家歐仁·查理·卡特蘭命名。歷史上,清朝數學家明安圖在其《割圜密率捷法》中最先發明這種計數方式,早於卡塔蘭[1][2][3]。有中國學者建議將此數命名為「明安圖數」或「明安圖-卡塔蘭數」[4]。
卡塔蘭數的一般項公式為
第0項到第19項的卡塔蘭數為:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...(OEIS數列A000108)
性質
Cn的另一個表達形式為
,
所以,Cn是一個自然數;這一點在先前的通項公式中並不顯而易見。這個表達形式也是André對前一公式證明的基礎。
它也滿足
這提供了一個更快速的方法來計算卡塔蘭數。
卡塔蘭數的漸近增長為
它的含義是當n → ∞時,左式除以右式的商趨向於1。(這可以用n!的斯特靈公式來證明。)
所有的奇卡塔蘭數Cn都滿足。所有其他的卡塔蘭數都是偶數。
而且
母函數
若卡塔蘭數的母函數是
則[6]
解是
應用
組合數學中有非常多的組合結構可以用卡塔蘭數來計數。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一書的習題中包括了66個相異的可由卡塔蘭數表達的組合結構。以下用n=3和n=4舉若干例:
- 將上例的X換成左括號,Y換成右括號,Cn表示所有包含n組括號的合法運算式的個數:
- Cn表示有n個節點組成不同構二叉樹的方案數。下圖中,n等於3,圓形表示節點,月牙形表示什麼都沒有。
- Cn表示有2n+1個節點組成不同構滿二叉樹的方案數。下圖中,n等於3,圓形表示內部節點,月牙形表示外部節點。本質同上。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/0/01/Catalan_number_binary_tree_example.png)
證明:令1表示進棧,0表示出棧,則可轉化為求一個2n位、含n個1、n個0的二進制數,滿足從左往右掃描到任意一位時,經過的0數不多於1數。顯然含n個1、n個0的2n位二進制數共有個,下面考慮不滿足要求的數目。
考慮一個含n個1、n個0的2n位二進制數,掃描到第2m+1位上時有m+1個0和m個1(容易證明一定存在這樣的情況),則後面的0-1排列中必有n-m個1和n-m-1個0。將2m+2及其以後的部分0變成1、1變成0,則對應一個n+1個0和n-1個1的二進制數。反之亦然(相似的思路證明兩者一一對應)。
從而。證畢。
- Cn表示所有在n × n格點中不越過對角線的單調路徑的個數。一個單調路徑從格點左下角出發,在格點右上角結束,每一步均為向上或向右。計算這種路徑的個數等價於計算Dyck word的個數:X代表「向右」,Y代表「向上」。下圖為n = 4的情況:
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Catalan_number_4x4_grid_example.svg/450px-Catalan_number_4x4_grid_example.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
- Cn表示對{1, ..., n}依序進出棧的置換個數。一個置換w是依序進出棧的當S(w) = (1, ..., n),其中S(w)遞歸定義如下:令w = unv,其中n為w的最大元素,u和v為更短的數列;再令S(w) = S(u)S(v)n,其中S為所有含一個元素的數列的單位元。
- Cn表示集合{1, ..., n}的不交叉劃分的個數。那麼, Cn永遠不大於第n項貝爾數. Cn也表示集合{1, ..., 2n}的不交叉劃分的個數,其中每個段落的長度為2。綜合這兩個結論,可以用數學歸納法證明:在 魏格納半圓分布定律 中度數大於2的情形下,所有 自由的 累積量s 為零。 該定律在自由概率論和隨機矩陣理論中非常重要。
- Cn表示用n個長方形填充一個高度為n的階梯狀圖形的方法個數。下圖為n = 4的情況:
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/6/63/Catalan_stairsteps_4.svg/400px-Catalan_stairsteps_4.svg.png)
- Cn表示表為2×n的矩陣的標準楊氏矩陣的數量。 也就是說,它是數字 1, 2, ..., 2n 被放置在一個2×n的矩形中並保證每行每列的數字升序排列的方案數。同樣的,該式可由勾長公式的一個特殊情形推導得出。
- Cn表示n個無標號物品的半序的個數。
漢克爾矩陣
無論n的取值為多少,n×n的漢克爾矩陣:的行列式為1。例如,n = 4 時我們有
- 。
進一步,無論n的取值為多少,如果矩陣被移動成,它的行列式仍然為1。例如,n = 4 時我們有
- 。
同時,這兩種情形合在一起唯一定義了卡塔蘭數。
參考文獻
- ^ 吳文俊主編 《中國數學史大系》第7卷 474-475頁
- ^ 明安图第发明卡塔兰数之第一人. [2014-06-24]. (原始內容存檔於2020-01-31).
- ^ 中国人在18世纪发现卡塔兰数 (PDF). [2014-06-24]. (原始內容存檔 (PDF)於2021-02-24).
- ^ 吳文俊主編 《中國數學史大系》 第七卷 476頁
- ^ Bowman, Douglas; Regev, Alon. Counting symmetry classes of dissections of a convex regular polygon. Advances in Applied Mathematics. 2014-05, 56: 35–55 [2020-02-23]. doi:10.1016/j.aam.2014.01.004. (原始內容存檔於2020-02-23) (英語).
- ^ Weisstein, Eric W. (編). Catalan Number. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-23]. (原始內容存檔於2019-06-18) (英語).
- ^ DyckPaths. www.findstat.org. [2020-02-23]. (原始內容存檔於2020-12-03).