Name
Abstract | ||
|---|---|---|
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 Goncarov 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 Goncarov 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(O; u1, u2, ..., un). Various properties of Goncarov polynomials are discussed. In particular, Goncarov polynomials satisfy a linear recursion obtained by expanding xn as a linear combination of Goncarov 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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0097-3165(03)00009-8 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
n gn,linear combination,goncarov polynomials gn,parking functions,positive integer,u-parking function,gonc̆arov polynomials,arbitrary sequence,original sequence,length n,goncarov polynomial,linear recursion,sum enumerators,satisfiability,differential operators,order statistic | Discrete mathematics,Wilson polynomials,Combinatorics,Orthogonal polynomials,Classical orthogonal polynomials,Macdonald polynomials,Discrete orthogonal polynomials,Gegenbauer polynomials,Hahn polynomials,Mathematics,Difference polynomials | Journal |
Volume | Issue | ISSN |
102 | 1 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
10 | 1.00 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joseph P. S. Kung | 1 | 78 | 20.60 |
| Catherine Yan | 2 | 64 | 7.41 |