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.
Pictures produced by ParkingStatistics.txt
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])
1/2*(n+1)!/(n+1)^n*add((n+1)^k/k!,k=0..n-1) - n/2
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
Yukun Yao's Home Page
Articles of Doron Zeilberger
Doron Zeilberger's Home Page