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_k S_(n - 1 - k), 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).

binomial coefficient | Catalan number | Delannoy number | lattice path | Motzkin number | p-good path | super Catalan number