主題
Search

卡塔蘭數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
CatalanPolygons

非負整數上的卡塔蘭數 n 是一組出現在樹計數問題中的數字，例如，“有多少種方法可以將一個正 n 邊形劃分為 n-2 個三角形，如果不同的方向被單獨計數？”（尤拉多邊形劃分問題）。解是卡塔蘭數 C_(n-2) (Pólya 1956; Dörrie 1965; Honsberger 1973; Borwein 和 Bailey 2003, pp. 21-22)，如上圖所示（Dickau）。

卡塔蘭數通常表示為 C_n (Graham et al. 1994; Stanley 1999b, p. 219; Pemmaraju 和 Skiena 2003, p. 169; 本文) 或 c(n) (Goulden 和 Jackson 1983, p. 111)，較少見的表示為 u_n (van Lint 和 Wilson 1992, p. 136)。

卡塔蘭數在 Wolfram 語言中實現為CatalanNumber[n].

前幾個卡塔蘭數，對於 n=1, 2, ... 是 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... (OEIS A000108)。

CatalanNumber

C_n 的顯式公式包括

C_n=1/(n+1)(2n; n)
(1)
=((2n)!)/((n+1)!n!)
(2)
=(2^n(2n-1)!!)/((n+1)!)
(3)
=(4^nGamma(n+1/2))/(sqrt(pi)Gamma(n+2))
(4)
=(-1)^n2^(2n+1)(1/2; n+1)
(5)
=1/n(2n; n-1)
(6)
=_2F_1(1-n,-n;2;1),
(7)

其中 (n; k) 是一個二項式係數， n! 是一個階乘， n!! 是一個雙階乘， Gamma(z) 是伽瑪函式，並且 _2F_1(a,b;c;z) 是一個超幾何函式。

CatalanNumberReIm
CatalanNumberContours

卡塔蘭數可以推廣到複平面，如上圖所示。

給出 C_n 的求和包括

C_n=sum_(k=0)^(n-1)C_kC_(n-k-1)
(8)
=sum_(k=0)^(n-1)C_k2^(n-2k-1)(n-1; 2k)
(9)
=1/nsum_(k=0)^(n-1)C_(n-k+1)(2k+1; k+1)
(10)
=sum_(k=0)^(n)(-1)^k2^(n-k)(n; k)(k; |_k/2_|)
(11)
=sum_(k=0)^(|_n/2_|)[(n-2k+1)/(n-k+1)(n; n-k)]^2,
(12)

其中 |_x_| 是向下取整函式，並且 C_n 的乘積由下式給出

C_n=1/((n+1)!)product_(k=1)^n(4k-2).
(13)

涉及 C_n 的求和包括生成函式

2/(1+sqrt(1-4x))=sum_(n=0)^(infty)C_nx^n
(14)
=1+x+2x^2+5x^3+14x^4+...
(15)

(OEIS A000108)，指數生成函式

e^(2x)[I_0(2x)-I_1(2x)]=sum_(n=0)^(infty)C_n(x^n)/(n!)
(16)
=1+x+x^2+5/6x^3+7/(12)x^4+7/(20)x^5+...
(17)

(OEIS A144186 和 A144187)，其中 I_n(x) 是第一類修正貝塞爾函式，以及

sum_(n=1)^(infty)(C_n)/(4^n)=1
(18)
sum_(n=0)^(infty)(C_nx^(2n))/((2n)!)=(I_1(2x))/x.
(19)

卡塔蘭數的漸近形式是

C_x∼(4^x)/(sqrt(pi))(x^(-3/2)-9/8x^(-5/2)+(145)/(128)x^(-7/2)+...)
(20)

(Vardi 1991, Graham et al. 1994)。

C_(10^n) 中十進位制數字的位數，對於 n=0, 1, ... 是 1, 5, 57, 598, 6015, 60199, 602051, 6020590, ... (OEIS A114466)。這些數字收斂於 log_(10)4=0.602059991... 的十進位制展開中的數字 (OEIS A114493)。

C_n 的遞推關係從下式獲得

(C_(n+1))/(C_n)=(2(2n+1))/(n+2),
(21)

因此

C_(n+1)=(2(2n+1))/(n+2)C_n.
(22)

塞格納遞推公式，由 Segner 在 1758 年給出，給出了尤拉多邊形劃分問題的解

E_n=E_2E_(n-1)+E_3E_(n-2)+...+E_(n-1)E_2.
(23)

當 E_1=E_2=1 時，上述遞推關係給出了卡塔蘭數 C_(n-2)=E_n。

從卡塔蘭數的定義來看， C_n 的每個素因子都小於 2n。另一方面，對於 C_n>2n-1 對於 n>4。因此， C_3 是最大的卡塔蘭素數，使得 C_2=2 和 C_3=5 是唯一的卡塔蘭素數。（當然，關於 C_n 的因式分解可以說的遠不止這些。）

唯一的奇數卡塔蘭數是形式為 C_(2^k-1) 的那些。前幾個是 1, 5, 429, 9694845, 14544636039226909, ... (OEIS A038003)。

奇數卡塔蘭數 C_n 以 5 結尾，除非 2^n-1 的 5 進位制展開僅使用數字 0、1、2，因此一個本質上隨機的 5 進位制數字的長序列僅包含 0、1 和 2 將極其罕見。事實上，奇數卡塔蘭數的最後一位數字是 1、5、9、5、9、5、9、7、5、5、5、5、5、... (OEIS A094389)，所以 5 是所有 n 的最後一位數字，至少到 n=10^5 為止，除了 1、3、5、7 和 8。

CatalanTrees

卡塔蘭數出現在許多其他相關型別的問題中。卡塔蘭數 C_(n-1) 也給出了 n 個字母的二叉括號表示 (卡塔蘭問題)，選票問題的解，三價植根平面樹的數量（Dickau；如上圖所示），n-屈曲面中可能的狀態數，具有 n+1 行的帶狀圖案中不同對角線的數量，具有 n 筆畫的迪克路徑的數量，形成 n 重指數形式的方式數，具有 n 個內部節點的有根平面二叉樹的數量，具有 n 個圖的邊的有根平面灌木叢的數量，具有 n 個內部節點的擴充套件二叉樹的數量，以及可以用 n 個上升筆畫和 n 個下降筆畫繪製的山的數量，在 n 對人之間圍繞圓桌可能進行的不相交的握手的數量 (Conway 和 Guy 1996)！

卡塔蘭數的推廣定義為

_pd_k=1/k(pk; k-1)
(24)
=1/((p-1)k+1)(pk; k)
(25)

對於 k>=1 (Klarner 1970, Hilton 和 Pedersen 1991)。通常的卡塔蘭數 C_k=_2d_k 是 p=2 的特殊情況。 _pd_k 給出了具有 p-元樹，具有 k 個源節點的數量，給定 k 次p-元算符應用的結合方式的數量，將凸多邊形劃分為 k 個不相交的 (p+1) 邊形的方式的數量，以及從 (0, -1) 到 (k,(p-1)k-1) 的p-好路徑的數量 (Hilton 和 Pedersen 1991)。

進一步的推廣如下。設 p 是一個整數 >1，設 P_k=(k,(p-1)k-1)，其中 k>=0，且 q<=p-1。然後定義 _pd_(q0)=1，並讓 _pd_(qk) 為從 (1, q-1) 到 P_k 的p-好路徑的數量 (Hilton 和 Pedersen 1991)。 _pd_(qi) 的公式包括廣義的約拿公式

(n-q; k-1)=sum_(i=1)^k_pd_(qi)(n-pi; k-i)
(26)

和顯式公式

_pd_(qk)=(p-q)/(pk-q)(pk-q; k-1).
(27)

遞推關係由下式給出

_pd_(qk)=sum_(i,j)_pd_(p-r,i)_pd_(q+r,j)
(28)

其中 i,j,r>=1, k>=1, q<p-r, 並且 i+j=k+1 (Hilton 和 Pedersen 1991)。

另請參閱

選票問題, 二叉括號表示, 二叉樹, 卡塔蘭問題, 卡塔蘭三角形, 中心二項式係數, 德蘭諾數, 迪克路徑, 尤拉多邊形劃分問題, 屈曲面, 帶狀圖案, 莫茨金數, p-好路徑, 植根平面樹, 施羅德數, 階梯多邊形, 超級卡塔蘭數

此條目的部分內容由 Richard Stanley 貢獻

使用 探索

參考文獻

Alter, R. "Some Remarks and Results on Catalan Numbers." Proc. 2nd Louisiana Conf. Comb., Graph Th., and Comput., 109-132, 1971.Alter, R. and Kubota, K. K. "Prime and Prime Power Divisibility of Catalan Numbers." J. Combin. Th. A 15, 243-256, 1973.Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.Campbell, D. "The Computation of Catalan Numbers." Math. Mag. 57, 195-208, 1984.Chorneyko, I. Z. and Mohanty, S. G. "On the Enumeration of Certain Sets of Planted Trees." J. Combin. Th. Ser. B 18, 209-221, 1975.Chu, W. "A New Combinatorial Interpretation for Generalized Catalan Numbers." Disc. Math. 65, 91-94, 1987.Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 96-106, 1996.Dershowitz, N. and Zaks, S. "Enumeration of Ordered Trees." Disc. Math. 31, 9-28, 1980.Dickau, R. M. "Catalan Numbers." http://mathforum.org/advanced/robertd/catalan.html.Dörrie, H. "Euler's Problem of Polygon Division." §7 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 21-27, 1965.Eggleton, R. B. and Guy, R. K. "Catalan Strikes Again! How Likely is a Function to be Convex?" Math. Mag. 61, 211-219, 1988.Gardner, M. "Catalan Numbers." Ch. 20 in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, pp. 253-266, 1988.Gardner, M. "Catalan Numbers: An Integer Sequence that Materializes in Unexpected Places." Sci. Amer. 234, 120-125, June 1976.Gould, H. W. Bell & Catalan Numbers: Research Bibliography of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae, 1985.Goulden, I. P. and Jackson, D. M. Combinatorial Enumeration. New York: Wiley, 1983.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Exercise 9.8 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Guy, R. K. "Dissecting a Polygon Into Triangles." Bull. Malayan Math. Soc. 5, 57-60, 1958.Hilton, P. and Pedersen, J. "Catalan Numbers, Their Generalization, and Their Uses." Math. Int. 13, 64-75, 1991.Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 130-134, 1973.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 146-150, 1985.Klarner, D. A. "Correspondences Between Plane Trees and Binary Sequences." J. Comb. Th. 9, 401-411, 1970.Mays, M. E. and Wojciechowski, J. "A Determinant Property of Catalan Numbers." Disc. Math. 211, 125-133, 2000.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Pólya, G. "On Picture-Writing." Amer. Math. Monthly 63, 689-697, 1956.Rogers, D. G. "Pascal Triangles, Catalan Numbers and Renewal Arrays." Disc. Math. 22, 301-310, 1978.Sands, A. D. "On Generalized Catalan Numbers." Disc. Math. 21, 218-221, 1978.Singmaster, D. "An Elementary Evaluation of the Catalan Numbers." Amer. Math. Monthly 85, 366-368, 1978.Sloane, N. J. A. A Handbook of Integer Sequences. Boston, MA: Academic Press, pp. 18-20, 1973.Sloane, N. J. A. Sequences A000108/M1459, A038003, A094389, A114466, A114493, A144186, and A144187 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M1459 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999a.Stanley, R. P. Enumerative Combinatorics, Vol. 2. Cambridge, England: Cambridge University Press, pp. 219-229, 1999b.Stanley, R. P. "Catalan Addendum." 19 Nov. 2003. http://www-math.mit.edu/~rstan/ec/catadd.ps.gz.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 187-188 and 198-199, 1991.Wells, D. G. The Penguin Dictionary of Curious and Interesting Numbers. London: Penguin, pp. 121-122, 1986.

在 中被引用

卡塔蘭數

請引用為

Stanley, Richard 和 Weisstein, Eric W. "卡塔蘭數。" 來自 —— 資源。 https://mathworld.tw/CatalanNumber.html

主題分類