Abstract
Consider lattice paths in Z2 with three step types: the up diagonal (1, 1), the down diagonal (1, -1), and the double horizontal (2, 0). For n ≥ 1, let Sn denote the set of such paths running from (0, 0) to (2n, 0) and remaining strictly above the x-axis except initially and terminally. It is well known that the cardinalities, rn = |Sn|, are the large Schröder numbers. We use lattice paths to interpret bijectively the recurrence (n+1)rn+1 = 3(2n-1)rn - (n-2)rn-1, for n ≥ 2, with r1 = 1 and r2 = 2. We then use the bijective scheme to prove a result of Kreweras that the sum of the areas of the regions lying under the paths of Sn and above the x-axis, denoted by AS n, satisfies ASn+1 = 6ASn - ASn-1; for n ≥ 2, with AS1 = 1, and AS2 = 7. Hence AS n = 1, 7, 41, 239, 1393, . . .. The bijective scheme yields analogous recurrences for elevated Catalan paths.
| Original language | English |
|---|---|
| Pages (from-to) | 48DUMMY |
| Journal | Electronic Journal of Combinatorics |
| Volume | 5 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1998 |
Fingerprint
Dive into the research topics of 'Bijective Recurrences concerning Schröder paths'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver