Let u be a sequence of non-decreasing positive integers. A u-parking function of length n is a sequence (x1, x2,...,xn) whose order statistics (the sequence (x(1), x(2),...,x(n)) obtained by rearranging the original sequence in non-decreasing order) satisfy x(i) ui. The Gonarov polynomials gn (x; a0, a1,..., an-1) are polynomials defined by the biorthogonality relation: E(ai Di gn(x; a0, a1,...,an-1) = n!in, where E(a) is evaluation at a and D is the differentiation operator. In this paper we show that Gonarov polynomials form a natural basis of polynomials for working with u-parking functions. For example, the number of u-parking functions of length n is (-1)n gn(0; u1, u2,..., un). Various properties of Gonarov polynomials are discussed. In particular, Gonarov polynomials satisfy a linear recursion obtained by expanding xn as a linear combination of Gonarov polynomials, which leads to a decomposition of an arbitrary sequence of positive integers into two subsequences: a "maximum" u-parking function and a subsequence consisting of terms of higher values. Many counting results for parking functions can be derived from this decomposition. We give, as examples, formulas for sum enumerators, and a linear recursion and Appell relation for factorial moments of sums of u-parking functions. 2003 Elsevier Science (USA). All rights reserved.
