Enumeration of certain subsets of uprooted trees and spherical parking functions

Abstract

Spherical $G$-parking functions are a distinguished subset of standard monomials, arising from the skeleton ideals of the $G$-parking function ideal. Explicit enumeration formulas for spherical $G$-parking functions are known only for a few classes of graphs. In this paper, we consider a family of graphs $G_{\ell }$ ($1\le \ell \le n-2$), obtained from the complete graph $K_{n+1}$ by deleting the $\ell$ edges joining vertex $1$ to the vertices in $F_{\ell }=\{n-\ell +1,\dots ,n\}$. The uprooted spanning trees of $G_{\ell }-\{0\}$ correspond to the set ${\mathcal{U}}_n^{1\nsim F_{\ell }}$ of uprooted trees with vertex set $[n]$ in which vertex $1$ is not adjacent to any vertex in $F_{\ell }$, and we establish that $|{\mathcal{U}}_n^{1\nsim F_{\ell }}|=(n-1{)}^{n-\ell -2}(n-2{)}^{\ell }(n-\ell -1)$. We derive this formula combinatorially and independently recover it as an application of the matrix tree theorem, obtaining some combinatorial identities as consequences. Finally, we determine the number of spherical $G_{\ell }$-parking functions as $|\mathrm{sPF}(G_{\ell })|=(n-1{)}^{n-3}(n-\ell -1{)}^2$.