主题
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 贡献

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

卡塔兰数

请引用为

Stanley, Richard 和 Weisstein, Eric W. "卡塔兰数。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/CatalanNumber.html

主题分类