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
![(1-x)G(x)-x[G(x)]^2=1](https://txtdot.deep-swarm.xyz/proxy/img?url=https%3A%2F%2Fmathworld.wolfram.com%2Fimages%2Fequations%2FSchroederNumber%2FNumberedEquation3.svg){kind=small} |
(3) |
and has closed-form solutions
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.
See also
Binomial Coefficient, Catalan Number, Delannoy Number, Lattice Path, Motzkin Number, p-Good Path, Super Catalan Number
Explore with Wolfram|Alpha
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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Schröder Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SchroederNumber.html