Super Catalan Number

While the Catalan Numbers are the number of p-Good Path from $(n,n)$ to (0,0) which do not cross the diagonal line, the super Catalan numbers count the number of Lattice Paths with diagonal steps from $(n,n)$ to (0,0) which do not touch the diagonal line $x=y$.

The super Catalan numbers are given by the Recurrence Relation

$$S(n)={3(2n-3)S(n-1)-(n-3)S(n-2)\over n}$$

(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)$ is

$$S(n)={3P_{n-1}(3)-P_{n-2}(3)\over 4n}$$

(Vardi 1991, p. 199). The first few super Catalan numbers are 1, 1, 3, 11, 45, 197, ... (Sloane's A001003).

See also Catalan Number

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.

Schröder, E. ``Vier combinatorische Probleme.'' Z. Math. Phys. 15, 361-376, 1870.

Sloane, N. J. A. Sequence A001003/M2898 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 198-199, 1991.