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
![(1-x)G(x)-x[G(x)]^2=1](/images/equations/SchroederNumber/NumberedEquation3.gif) |
(3)
|
and has closed-form solutions
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  | ![1/2[-P_(n-1)(3)+6P_n(3)-P_(n+1)(3)],](/images/equations/SchroederNumber/Inline23.gif) |
(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.
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. https://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. https://www.combinatorics.org/Volume_5/Abstracts/v5i1r47.html.
Weisstein, Eric W. "Schröder Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SchroederNumber.html
Contact the MathWorld Team
141(2^141) + 1
