User Tools

Site Tools


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.

seminars/comb/abstract.200112kung.txt · Last modified: 2020/01/29 14:03 (external edit)