Joseph P.S. Kung

Goncharov Polynomials and Parking Functions

Abstract for the Combinatorics and Number Theory Seminar
2001 December 14

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 Goncharov polynomials gn(x; a0,a1,...,an-1) are polynomials defined by the biorthogonality relation:

epsilon(ai) Di gn(x; a0,a1,...,an-1) = n! deltain ,

where epsilon(a) is evaluation at a. Goncharov 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).

Goncharov polynomials also satisfy a linear recursion obtained by expanding xn as a linear combination of Goncharov polynomials. The combinatorial structure underlying this recursion is 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. From this combinatorial decomposition, we derive linear recursions for sum enumerators, expected sums of u-parking functions, and higher moments of sums of u-parking functions. These recursions yield explicit formulas for these quantities in terms of Goncharov polynomials.

This is joint work with Catherine Yan.