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.svg) |
(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.svg) |
(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.
-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.