Gončarov polynomials and parking functions (Q1873811): Difference between revisions

In this paper it is shown that the Gončarov polynomials are the natural basis of polynomials for working with parking functions, even in the ordinary case, and the enumerative theory of ordinary parking functions can be generalized to \(u\)-parking functions using these polynomials. The paper is organized as follows: In \S 2 a discussion of a general theory of biorthogonal polynomials is given and this theory is specialized to Gončarov polynomials in \S 3. A combinatorial description of the coefficients of Gončarev polynomials in terms of rankings on ordered partitions is presented in \S 4. The key idea connecting Gončarov polynomials to parking functions is given in \S 5. An immediate application yields formulas for a number of parking functions. In \S 6 linear recursions and generating function identities for sum enumerators of \(u\)-parking functions are obtained. Finally in \S 7 the authors derived a linear recursion for moments of sums of \(u\)-parking functions. Such moments have applications in the analysis of probing algorithms and the enumeration of sparsely edged graphs.