A combinatorial interpretation of the area of Schröder paths

E. Pergola ; R. Pinzani

The electronic journal of combinatorics, Tome 6 (1999)

Résumé

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.

Détail

DOI : 10.37236/1472

Classification : 05A15
Mots-clés : elevated Schröder path, lattice path, combinatorial interpretation