Gonc̆arov polynomials and parking functions

AbstractLet 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 Gonc̆arov polynomials gn(x;a0,a1,…,an−1) are polynomials defined by the biorthogonality relation:ε(ai)Dign(x;a0,a1,…,an−1)=n!δin,where ε(a) is evaluation at a and D is the differentiation operator. In this paper we show that Gonc̆arov 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)ngn(0;u1,u2,…,un). Various properties of Gonc̆arov polynomials are discussed. In particular, Gonc̆arov polynomials satisfy a linear recursion obtained by expanding xn as a linear combination of Gonc̆arov 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