A family of bijections between \(G\)-parking functions and spanning trees (Q1775544): Difference between revisions

Let \(G\) be a directed graph with \(\{0,1,\dots,n\}\) as vertex set. A \(G\)-parking function is a sequence \((b_1,\dots,b_n)\) of non-negative integers satisfying the following condition: for each subset \(U\) of \(\{1,2,\dots,n\}\), there exists a vertex \(j\in U\) such that the number of edges from \(j\) to vertices outside of \(U\) is greater than \(b_j\). We denote the collection of all \(G\)-parking functions by \(\mathcal P_G\) and we denote the collection of all spanning trees for \(G\), rooted at 0, by \(\mathcal T_G\). The authors construct a family of bijections between \(\mathcal T_G\) and \(\mathcal P_G\), thus providing a combinatorial proof that \(|\mathcal T_G|=|\mathcal P_G|\).