<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue4" %>
Expected Sums of General Parking Functions
Joseph P.S. Kung1 and Catherine Yan2
1Department of Mathematics, University of North Texas, Denton, TX 76203, USA
2Department of Mathematics, Texas A & M University, College Station, TX 77843, USA
Annals of Combinatorics 7 (4) p.481-493 December, 2003
AMS Subject Classification: 05A15, 05A19, 05A20, 05E35
A (u1, u2, ...)-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 Gončarov polynomials gn(x; a0, a1, ..., an-1) are polynomials biorthogonal to the linear functionals , where is evaluation at a and D is differentiation. In this paper, we give explicit formulas for the first and second moments of sums of u-parking functions using Gončarov polynomials by solving a linear recursion based on a decomposition of the set of sequences of positive integers. We also give a combinatorial proof of one of the formulas for the expected sum. We specialize these formulas to the classical case when ui = a + (i-1)b and obtain, by transformations with Abel identities, different but equivalent formulas for expected sums. These formulas are used to verify the classical case of the conjecture that the expected sums are increasing functions of the gaps ui+1 - ui. Finally, we give analogues of our results for real-valued parking functions.
Keywords: parking functions, Gončarov polynomials, Abel identities


1. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, 2nd Edition, Wiley, New York, 1971.

2. I.M. Gessel and B.E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Elect. J. Combin. 3 (2) (1996) #R9.

3. D.E. Knuth, Linear probing and graphs, average-case analysis for algorithms, Algorithmica 22 (1998) 561–568.

4. A.G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Appl. Math. 14 (1966) 1266–1274.

5. J.P.S. Kung, A probabilistic interpretation of the Goncarov and related polynomials, J.Math. Anal. Appl. 79 (1981) 349–351.

6. J.P.S. Kung and C.H. Yan, Gončarov polynomials and parking functions, J. Combin. Theory, Ser. A 102 (2003) 16–37.

7. J.P.S. Kung and C.H. Yan, Exact formulas for moments of sums of classical parking functions, Adv. Appl. Math. 31 (2003) 215–241.

8. H. Niederhausen, Sheffer polynomials for computing exact Kolmogorov-Smirnov and Rényi type distributions, Ann. Statist. 9 (1981) 923–944.

9. J. Pitman and R. Stanley, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (2002) 603–634.

10. J. Riordan, Combinatorial Identities, Wiley, New York, 1968.

11. G.P. Steck, The Smirnov two-sample tests as rank test, Ann. Math. Statist. 40 (1968) 1449– 1466.