TOPICS

# Schröder Number

The Schröder number is the number of lattice paths in the Cartesian plane that start at (0, 0), end at , contain no points above the line , and are composed only of steps (0, 1), (1, 0), and (1, 1), i.e., , , and . The diagrams illustrating the paths generating , , and are illustrated above.

The numbers are given by the recurrence relation

 (1)

where , and the first few are 2, 6, 22, 90, ... (OEIS A006318). The numbers of decimal digits in for , 1, ... are 1, 7, 74, 761, 7650, 76548, 765543, 7655504, ... (OEIS A114472), where the digits approach those of (OEIS A114491).

They have the generating function

 (2)

which satisfies

 (3)

and has closed-form solutions

 (4) (5) (6)

where is a hypergeometric function, is a Gegenbauer polynomial, is a Legendre polynomial, and (5) holds for .

The Schröder numbers bear the same relation to the Delannoy numbers as the Catalan numbers do to the binomial coefficients.

Binomial Coefficient, Catalan Number, Delannoy Number, Lattice Path, Motzkin Number, p-Good Path, Super Catalan Number

## Explore with Wolfram|Alpha

More things to try:

## References

Bonin, J.; Shapiro, L.; and Simion, R. "Some -Analogs of the Schröder Numbers Arising from Combinatorial Statistics on Lattice Paths." J. Stat. Planning Inference 34, 35-55, 1993.Moser, L. and Zayachkowski, W. "Lattice Paths with Diagonal Steps." Scripta Math. 26, 223-229, 1963.Pergola, E. and Sulanke, R. A. "Schröder Triangles, Paths, and Parallelogram Polyominoes." J. Integer Sequences 1, No. 98.1.7, 1998. http://www.math.uwaterloo.ca/JIS/VOL1/PergolaSulanke/.Rogers, D. G. "A Schröder Triangle." Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference. New York: Springer-Verlag, pp. 175-196, 1977.Rogers, D. G. and Shapiro, L. "Some Correspondences involving the Schröder Numbers." Combinatorial Mathematics: Proceedings of the International Conference, Canberra, 1977. New York: Springer-Verlag, pp. 267-276, 1978.Schröder, E. "Vier kombinatorische Probleme." Z. Math. Phys. 15, 361-376, 1870.Sloane, N. J. A. Sequences A006318/M1659, A114472, and A114491 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Hipparchus, Plutarch, Schröder, Hough." Amer. Math. Monthly 104, 344-350, 1997.Sulanke, R. A. "Bijective Recurrences Concerning Schröder Paths." Electronic J. Combinatorics 5, No. 1, R47, 1-11, 1998. http://www.combinatorics.org/Volume_5/Abstracts/v5i1r47.html.

Schröder Number

## Cite this as:

Weisstein, Eric W. "Schröder Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SchroederNumber.html