Bijective Recurrences concerning Schröder paths

  • Robert A. Sulanke

Research output: Contribution to journalReview articlepeer-review

30 Scopus citations

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 languageEnglish
Pages (from-to)48DUMMY
JournalElectronic Journal of Combinatorics
Volume5
Issue number1
DOIs
StatePublished - 1998

Fingerprint

Dive into the research topics of 'Bijective Recurrences concerning Schröder paths'. Together they form a unique fingerprint.

Cite this