A Short Proof that the number of (a, b)-parking functions of length n is a(a + bn)^{n−1}

AJ BU and Doron ZEILBERGER

Abstract: We give a very short proof of the fact that the number of (a, b)-parking functions of length n equals a(a + bn)^{n−1}. This was first proved in 2003 by Kung and Yan, via a very long and torturous route, as a corollary of a more general result.

Recall [KoW] that a parking function of length n is a list of positive integers x = (x_{1}, …, x_{n}) whose non-decreasing rearrangement, x′_{1} ≤ … ≤ x′_{n} satisfies x′_{i} ≤ i, (1 ≤ i ≤ n). Their number is famously (n + 1)^{n−1}.

More generally, for any non-negative integers, a and b, an (a, b)-parking function of length n is a list of positive integers (x_{1}, …, x_{n}) whose non-decreasing rearrangement satisfies: x′_{i} ≤ a+b(i−1), (1 ≤ i ≤ n). Note that (1, 1)-parking functions are the usual ones.

In [KuY], after 13 pages of heavy-going math, as a corollary of a much more general result (Cor. 5.5 there), the authors proved the following fact.

Fact: The number of (a, b)-parking functions of length n is a(a + bn)^{n−1}.

Short Proof: Let P(n, a, b) be the set of (a, b)-parking functions of length n, and let p(n, a, b) := |P(n, a, b)|. For 0 ≤ r ≤ n, the subset consisting of those with exactly r 1s is in bijection with B_{n,r} × P(n − r, a + br − 1, b), where B_{n,r} is the set of r-element subsets of {1, …, n}. It is given by: x → (S, y), where S is the subset of locations of x where the 1s reside, and y is obtained from x by deleting the 1s, and then subtracting one from every remaining entry, and since x′_{r+1} − 1 ≤ a + b r − 1, the claim follows. Hence:

p(n, a, b) = ∑_{r=0}^{n} \binom{n}{r}p(n − r, a + br − 1, b) ,

that uniquely determines p(n, a, b), subject to the initial conditions p(0, a, b) = 1 and p(n, 0, b) = 0.

But q(n, a, b) := a(a + bn)^{n−1} satisfies the very same recurrence, where p is replaced by q, namely:

a(a + bn)^{n−1} = ∑_{r=0}^{n} \binom{n}{r}(a + br − 1)(a + bn − 1)^{n−r−1} ,

(Check!^{1}), and hence p(n, a, b) = q(n, a, b) follows by induction on n.

1 Write a + b r − 1 as (a + b n − 1) − b (n − r) , use (n − r)\binom{n}{r} = n\binom{n−1}{r} and then invoke the binomial

theorem twice.

Comment: We were unaware of this result, and found it ab initio, by using experimental mathematics, via the Maple package

https://sites.math.rutgers.edu/~zeilberg/tokhniot/GenPark.txt . We thank Lucy Mar-

tinez for telling us about [KuY]. References

[KoW] Alan G. Konheim and Benjamin Weiss, An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966), 1266-1274. [Available from JSTOR.]

[KuY] Joseph P.S. Kung and Catherine Yan, Gonc̆arov polynomials and parking functions, J. of Combinatorial Theory Ser. A, 102 (2003), 16-37.

AJ Bu and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ajbu131@gmail.com , DoronZeil@gmail.com .

Written: Dec. 15, 2024.