A Combinatorial Interpretation of the Area of Schröder Paths

Abstract

An elevated Schröder path is a lattice path that uses the steps $(1,1)$, $(1,-1)$, and $(2,0)$, that begins and ends on the $x$-axis, and that remains strictly above the $x$-axis otherwise. The total area of elevated Schröder paths of length $2n+2$ satisfies the recurrence $f_{n+1}=6f_n-f_{n-1}$, $n \geq 2$, with the initial conditions $f_0=1$, $f_1=7$. A combinatorial interpretation of this recurrence is given, by first introducing sets of unrestricted paths whose cardinality also satisfies the recurrence relation and then establishing a bijection between the set of these paths and the set of triangles constituting the total area of elevated Schröder paths.