Generalized Tree Inversions andk-Parking Functions
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Kreweras studied a polynomial Pn(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 integer k, there are known notions of k-parking functions and of (labeled) rooted k-forests, generating the case k = 1 studied by Kreweras. We show that the enumerator P(k)n(q) for complements of k-parking functions by the sum of their terms is identical to the enumerator of I(k)n (q) of rooted k-forests by the number of their inversions. In doing so we find recurrence relations satisfied by P(k)n(q) and I(k)n(q), and we introduce the concept of a multirooted k-graph whose excess edges and roots are enumerated by a polynomial denoted C(k)n(q). We show that C(k)n(q) satisfies the same recurrence relations as both P(k)n(1 + q) and I(k)n(1+q), proving that P(k)n(q) = I(k)n(q). 1997 Academic Press.
