info prev up next book cdrom email home

Schröder Number

\begin{figure}\begin{center}\BoxedEPSF{SchroderNumber.epsf scaled 800}\end{center}\end{figure}

The Schröder number $S_n$ is the number of Lattice Paths in the Cartesian plane that start at (0, 0), end at $(n, n)$, contain no points above the line $y=x$, and are composed only of steps (0, 1), (1, 0), and (1, 1), i.e., $\rightarrow$, $\uparrow$, and $\nearrow$. The diagrams illustrating the paths generating $S_1$, $S_2$, and $S_3$ are illustrated above. The numbers $S_n$ are given by the Recurrence Relation

S_n=S_{n-1}+\sum_{k=0}^{n-1} S_kS_{n-1-k},

where $S_0=1$, and the first few are 2, 6, 22, 90, ... (Sloane's A006318). 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


Sloane, N. J. A. Sequence A006318/M1659 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein