Generalized Tree Inversions andk-Parking Functions

✍ Scribed by Catherine Huafei Yan

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 298 KB
• Volume: 79
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2784

✦ Synopsis

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 (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).