A Human Proof for a Generalization of Shalosh B. Ekhad’s \(10^n\) Lattice Paths Theorem

Abstract

Consider lattice paths in \(\mathbb{Z}^2\) taking unit steps north (N) and east (E). Fix positive integers \(r,s\) and put an equivalence relation on points of \(\mathbb{Z}^2\) by letting \(v,w\) be equivalent if \(v-w = \ell(r,s)\) for some \(k \in \mathbb{Z}\). Call a lattice path \({valid}\) if whenever it enters a point \(v\) with an E-step, then any further points of the path in the equivalence class of \(v\) are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from \((0,0)\) to \((nr,ns)\) is \({\binom{r+s}{nr}}^n\). We prove this conjecture when \(s=2\).