An Experimental Mathematics Approach to the Area Statistic of Parking Functions

By Yukun Yao and Doron Zeilberger

.pdf   .ps   .tex
Version with pictures: .pdf   LaTeX

[Appeared in Mathematical Intelligencer volume 41, issue 2 (June 2019), pp. 1-8]

First Written: June 5, 2018; This version: Aug. 29, 2018.

Last update of this web-page (but not the article): Dec. 11, 2019.

We illustrate the experimental, empirical, approach to mathematics (that contrary to popular belief, is often rigorous), by using parking functions and their "area" statistic, as a case study. Our methods are purely finitistic and elementary, taking full advantage, of course, of our beloved silicon servants.

Added Dec. 11, 2019: We just got the following message from guru Donald Knuth:

Hi Doron,

I enjoyed, as usual, your recent contribution to the Intelligencer.

Conversely, you might enjoy the discussion of these issues in Volume 3 of The Art of Computer Programming, in the answers to exercises 6.4--29ff on pages 732--734.

The footnote on page 536 also explains why this was, in a sense, the problem that originally got me hooked on analysis of algorithms in the first place!

Cordially, Don

# Maple package

• ParkingStatistics.txt, a Maple package for automatically deriving explicit expressions for moments of the random variable "Sum of Entries" (and the equivalent r.v. "area") defined on parking functions, and for computing the limiting scaled distribution.

# Sample Input and Output for ParkingStatistics.txt

• If you want to see explicit polynomial expressions for the first thirty factorial moments of the random variable "area" (i.e. n(n+1)/2-sum of entries) defined on the "sample space" of all (n+1)^(n-1) parking functions of length n, as polynomial expressions in n and the expectation A1 (that equals [in Maple notation])

the input file generates the output file.

• If you want to see the first 70 terms of the sequence of weight-enumerators for parking functions, according to the sum, and the statistical information for those between 60 and 70,

the input file generates the output file.

• If you want to statistical information about the random variable "sum of the parking function" and the statistical information for those between 121 and 130,

the input file generates the output file.

• If you want to see EXPLICIT expressions for the second through 20th FACTORIAL moments of the random variable "sum of the parking function" , for (simple) parking functions of length n, in terms of n and the Expectation

the input file generates the output file.

• If you want to see EXPLICIT expressions for the second through 20th CENTRALIZED moments of the random variable "sum of the parking function" , for (simple) parking functions of length n, in terms of n and the Expectation

the input file generates the output file.

• If you want to see EXPLICIT expressions for the second through 20th Limits (as n goes to infinity) of the SCALED moments of the random variable "sum of the parking function" , for (simple) parking functions of length n, in terms of n and the Expectation

the input file generates the output file.

• If you want to see EXPLICIT expressions for the second through 10th FACTORIAL moments of the random variable "sum of the parking function" , for a-parking functions of length n, in terms of n, a and the Expectation

the input file generates the output file.

• If you want to see EXPLICIT expressions for the second through 10th FACTORIAL moments of the random variable AREA of a-parking functions , for a-parking functions of length n, in terms of the symbols , n, a and E (where E stands for the expectation)

the input file generates the output file.

Added Jan. 15, 2019: Yukun Yao and myself I giving a talk at the JMM on Jan. 19, 2019. Since we will mention briefly Henry Pollack's clever proof, I have written a short Maple package to experiment with it. The Maple package is ParkingPollack.txt and