主题
Search

超卡塔兰数

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

虽然 卡塔兰数 是从 (n,n) 到 (0,0) 且不穿过对角线的 p-好路径 的数量，但超卡塔兰数计算的是从 (n,n) 到 (0,0) 且不接触对角线 x=y 的具有对角步的格路的数量。

超卡塔兰数由以下递推关系给出

S(n)=(3(2n-3)S(n-1)-(n-3)S(n-2))/n
(1)

(Comtet 1974)，其中 S(1)=S(2)=1。(注意 Vardi (1991, p. 198) 中的表达式包含两个错误。) 对于 n>1，用 勒让德多项式 P_n(x) 表示的闭式表达式为

S(n)=(3P_(n-1)(3)-P_(n-2)(3))/(4n)
(2)
=1/4[-P_n(3)+6P_(n-1)(3)-P_(n-2)(3)]
(3)

(Vardi 1991, p. 199)。前几个超卡塔兰数是 1, 1, 3, 11, 45, 197, ... (OEIS A001003)。这些通常被称为“小”施罗德数。乘以 2 得到通常的（“大”）施罗德数 2, 6, 22, 90, ... (OEIS A006318)。

前几个素数超卡塔兰数的索引为 3, 4, 6, 10, 216, ... (OEIS A092839)，没有其他小于 10^4 的素数超卡塔兰数 (Weisstein, 3 月 7 日, 2004)，对应的数字为 3, 11, 197, 103049, ... (OEIS A092840)。

另请参阅

括号, 卡塔兰数, 整数序列素数, 施罗德数

使用 Wolfram|Alpha 探索

参考文献

Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 56, 1974.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Exercise 7.50 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Motzkin, T. "Relations Between Hypersurface Cross Ratios and a Combinatorial Formula for Partitions of a Polygon for Permanent Preponderance and for Non-Associative Products." Bull. Amer. Math. Soc. 54, 352-360, 1948.Schröder, E. "Vier combinatorische Probleme." Z. Math. Phys. 15, 361-376, 1870.Sloane, N. J. A. Sequences A001003/M2898, A092839, and A092840 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 198-199, 1991.

在 Wolfram|Alpha 中被引用

超卡塔兰数

请按如下方式引用

Weisstein, Eric W. “超卡塔兰数。” 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/SuperCatalanNumber.html

主题分类