TOPICS
Search

Super Catalan Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The super Catalan number S(n), for a positive integer n, counts the lattice paths from (n-1,n-1) to (0,0) using steps (-1,0), (0,-1), and (-1,-1) that stay on or below the diagonal y=x and have no diagonal step lying on it.

The super Catalan numbers are given by the recurrence relation

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

for n>=3 (Comtet 1974), with S(1)=S(2)=1. (Note that the expression in Vardi (1991, p. 198) contains two errors.) A closed form expression in terms of Legendre polynomials P_n(x) for n>1 is

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). The values for n=1, 2, ... are 1, 1, 3, 11, 45, 197, ... (OEIS A001003). These are often called the "little" Schröder numbers. The usual ("large") Schröder numbers R_m satisfy R_m=2S(m+1) for m>=1, while R_0=1. The values for m=1, 2, ... are 2, 6, 22, 90, ... (OEIS A006318).

The first few prime super Catalan numbers have indices 3, 4, 6, 10, 216, ... (OEIS A092839), with no others less than 10^4 (Weisstein, Mar. 7, 2004), corresponding to the numbers 3, 11, 197, 103049, ... (OEIS A092840).

See also

Bracketing, Catalan Number, Integer Sequence Primes, Schröder Number

Explore with Wolfram|Alpha

References

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. https://doi.org/10.1090/S0002-9904-1948-09002-4.Schröder, E. "Vier combinatorische Probleme." Z. Math. Phys. 15, 361-376, 1870.Sloane, N. J. A. Sequences A001003/M2898, A006318, 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.

Referenced on Wolfram|Alpha

Super Catalan Number

Cite this as:

Weisstein, Eric W. "Super Catalan Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SuperCatalanNumber.html

Subject classifications