====== 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 (x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>) whose order statistics (the sequence (x<sub>(1)</sub>,x<sub>(2)</sub>,...,x<sub>(n)</sub>) obtained by rearranging the original sequence in non-decreasing order) satisfy x<sub>(i)</sub> <= u<sub>i</sub>. The Goncharov polynomials g<sub>n</sub>(x; a<sub>0</sub>,a<sub>1</sub>,...,a<sub>n-1</sub>) are polynomials defined by the biorthogonality relation:\\
\\


epsilon(a<sub>i</sub>) D<sup>i</sup> g<sub>n</sub>(x; a<sub>0</sub>,a<sub>1</sub>,...,a<sub>n-1</sub>) = n! delta<sub>in</sub> ,

\\
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)<sup>n</sup> g<sub>n</sub>(0; u<sub>1</sub>,u<sub>2</sub>, ...,u<sub>n</sub>).

Goncharov polynomials also satisfy a linear recursion obtained by expanding x<sup>n</sup> 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.