Generalized parking functions, tree inversions, and multicolored graphs
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
A generalized x-parking function associated to a positive integer vector of the form (a, b, b, , b) is a sequence (a1, a2, , an) of positive integers whose nondecreasing rearrangement b1 b2 bn satisfies bi a + (i - 1)b. The set of x-parking functions has the same cardinality as the set of sequences of rooted b-forests on [n]. We construct a bijection between these two sets. We show that the sum enumerator of complements of x-parking functions is identical to the inversion enumerator of sequences of rooted b-forests by generating function analysis. Combinatorial correspondences between the sequences of rooted forests and x-parking functions are also given in terms of depth-first search and breadth-first search on multicolored graphs. 2001 Academic Press.
