Generalized tree inversions and k-parking functions

[摘要] Kreweras studied a polynomial P-n(q) which enumerates (labeled) rooted forests by number of inversions, as well as complements of parking functions by the sum of their terms. Moreover, P-n(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)over bar ((k)(n))>(q) for complements of k-parking functions by the sum of their terms is identical to the enumerator of I-n((k))(q) of rooted k-forests by the number of their inversions. In doing so we find recurrence relations satisfied by <(P)over bar ((k)(n))>(q) and I-n((k))(q), and we introduce the concept of a multirooted k-graph whose excess edges and roots are enumerated by a polynomial denoted C-n((k))(q). We show that C-n((k))(q) satisfies the same recurrence relations as both <(P)over bar ((k)(n))>(1 + q) and I-n((k))(1 + q), proving that <(P)over bar ((k)(n))>(q) = I-n((k))(q). (C) 1997 Academic Press.

[发布日期] 1997-08-01