Schröder Number

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

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.