Generalized parking functions, tree inversions, and multicolored graphs

A generalized x-parking function associated to a positive integer vector of the form (a, b, b,..., b) is a sequence (a(1), a(2),.... a(n)) of positive integers whose nondecreasing rearrangement b(1) less than or equal to b(2) less than or equal to ... less than or equal to b(n) satisfies b(i) less t han or equal to a + (i - 1)b. The set of x-parking functions has the same c ardinality 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 com plements of x-parking functions is identical to the inversion enumerator of sequences of rooted b-forests by generating function analysis. Combinatori al correspondences between the sequences of rooted forests and x-parking fu nctions are also given in terms of depth-first search and breadth-first sea rch on multicolored graphs. (C) 2001 Academic Press.