Generalized Tree Inversions andk-Parking Functions

Kreweras studied a polynomialPn(q) which enumerates (labeled) rooted forests by number of inversions, as well as complements of parking functions by the sum of their terms. Moreover,Pn(1+q) enumerates labeled connected graphs by their number of excess edges. For any positive integerk, there are known notions ofk-parking functions and of (labeled) rootedk-forests, generating the casek=1 studied by Kreweras. We show that the enumeratorP(k)n(q) for complements ofk-parking functions by the sum of their terms is identical to the enumerator ofI(k)n(q) of rootedk-forests by the number of their inversions. In doing so we find recurrence relations satisfied byP(k)n(q) andI(k)n(q), and we introduce the concept of amultirooted k-graphwhose excess edges and roots are enumerated by a polynomial denotedC(k)n(q). We show thatC(k)n(q) satisfies the same recurrence relations as bothP(k)n(1+q) andI(k)n(1+q), proving thatP(k)n(q)=I(k)n(q).