Expected Sums of General Parking Functions

Joseph P.S. Kung^{1} and Catherine Yan^{2}

kung@unt.edu

cyan@math.tamu.edu

Annals of Combinatorics 7 (4) p.481-493 December, 2003

Abstract:

A (*u*_{1}, *u*_{2}, ...)-parking function of length *n* is a sequence (*x*_{1}, *x*_{2}, ..., *x*_{n}) whose order statistics (the sequence (*x*_{(1)}, *x*_{(2)}, ..., *x*_{(n)}) obtained by rearranging the original sequence in non-decreasing order)
satisfy *x*_{(i)} *u*_{i}. The Gončarov polynomials
*g*_{n}(*x*; *a*_{0}, *a*_{1}, ..., *a*_{n-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 *u*_{i} = *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 *u*_{i+1} - *u*_{i}. Finally, we give analogues of our
results for real-valued parking functions.

References:

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.