A combinatorial interpretation of the area of Schröder paths (Q1806355): Difference between revisions

Summary: 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.