主題
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)。

另請參閱

括號, 卡塔蘭數, 整數序列素數, 施羅德數

使用 探索

參考文獻

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.

在 中被引用

超卡塔蘭數

請按如下方式引用

Weisstein, Eric W. “超卡塔蘭數。” 來自 ——Wolfram 網路資源。 https://mathworld.tw/SuperCatalanNumber.html

主題分類