Combinatorial Theory

For \(0\leq k\leq n-1\), we introduce a family of \(k\)-skeletal paths which are counted by the \(n\)th Catalan number for each \(k\), and specialize to Dyck paths when \(k=n-1\). We similarly introduce \(k\)-skeletal parking functions which are equinumerous with spanning trees on the complete graph with \(n+1\) vertices for each \(k\), and specialize to classical parking functions for \(k=n-1\). The preceding constructions are generalized to paths lying in a trapezoid with base \(c › 0\) and southeastern diagonal of slope \(1/m\); \(c\) and \(m\) need not be integers. We give bijections among these families when \(k\) varies with \(m\) and \(c\) fixed. Our constructions are motivated by chip firing and have connections to combinatorial representation theory and tropical geometry.

Mathematics Subject Classifications: 05A15, 05A19, 05C57

Keywords: Chip firing, skeletal objects, lattice paths, Dyck paths, parking functions, Catalan numbers, ballot numbers