TOPICS
Search

Schröder Number


SchroderNumber

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., ->, ^, and ->. 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),
(1)

where S_0=1, and the first few are 2, 6, 22, 90, ... (OEIS A006318). The numbers of decimal digits in S_(10^n) for n=0, 1, ... are 1, 7, 74, 761, 7650, 76548, 765543, 7655504, ... (OEIS A114472), where the digits approach those of log_(10)(3+2sqrt(2))=0.765551... (OEIS A114491).

They have the generating function

 G(x)=(1-x-sqrt(1-6x+x^2))/(2x),
(2)

which satisfies

 (1-x)G(x)-x[G(x)]^2=1
(3)

and has closed-form solutions

S_n=2_2F_1(-n+1,n+2;2;-1)
(4)
=-1/2C_(n+1)^((-1/2))(3)
(5)
=1/2[-P_(n-1)(3)+6P_n(3)-P_(n+1)(3)],
(6)

where _2F_1(a,b;c;z) is a hypergeometric function, C_n^((k))(x) is a Gegenbauer polynomial, P_n(z) is a Legendre polynomial, and (5) holds for n>1.

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, Super Catalan Number

Explore with Wolfram|Alpha

References

Bonin, J.; Shapiro, L.; and Simion, R. "Some q-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. http://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. http://www.combinatorics.org/Volume_5/Abstracts/v5i1r47.html.

Referenced on Wolfram|Alpha

Schröder Number

Cite this as:

Weisstein, Eric W. "Schröder Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SchroederNumber.html

Subject classifications