Bijective Recurrences concerning Schröder Paths

Abstract

Consider lattice paths in Z$^2$ with three step types: the up diagonal $(1,1)$, the down diagonal $(1,-1)$, and the double horizontal $(2,0)$. For $n \geq 1$, let $S_n$ 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, $r_n = |S_n|$, are the large Schröder numbers. We use lattice paths to interpret bijectively the recurrence $ (n+1) r_{n+1} = 3(2n - 1) r_{n} - (n-2) r_{n-1}$, for $n \geq 2$, with $r_1=1$ and $r_2=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 $S_n$ and above the x-axis, denoted by $AS_n$, satisfies $ AS_{n+1} = 6 AS_n - AS_{n-1}, $ for $n \geq 2$, with $AS_1 =1$, and $AS_2 =7$. Hence $AS_n = 1, 7, 41, 239 ,1393, \ldots$. The bijective scheme yields analogous recurrences for elevated Catalan paths.