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

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

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


References

Sloane, N. J. A. Sequence A006318/M1659 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.




© 1996-9 Eric W. Weisstein
1999-05-26