The polynomial-form conjecture for lucky spots in parking functions

A polynomial formula for every lucky parking spot

A parking function of length $n$ is a preference word $(a_1,\ldots,a_n)\in\{1,\ldots,n\}^n$ for which all cars park: each car takes the first unoccupied spot at or to the right of its preference. A spot is lucky if its eventual occupant preferred that spot. Write $S_j(n)$ for the number of parking functions in which spot $j$ is lucky.

We prove the polynomial-form conjecture for every fixed $j$, not just the previously computed small values. More precisely, for each $j\ge2$ there is a polynomial $f_j\in\mathbb Q[n]$ of degree exactly $j-2$ such that, for every $n\ge j$, on putting $X=n-j+1$,

$$S_j(n)=\frac{j+1}{2j}(n+1)^{n-1}-f_j(n)X^X.$$

Its leading coefficient $r_j$ is positive, and

$$\lim_{n\to\infty}\frac{S_j(n)}{(n+1)^{n-1}} =\frac{j+1}{2j}-r_j e^{-j}.$$

The boundary $j=1$ is separate and immediate: spot $1$ is always lucky, so $S_1(n)=(n+1)^{n-1}$ and one may take $f_1=0$.

This proves Butler–Hadaway–Lenius–Martens–Moats, Conjecture 3.1, which is Conjecture 13 in the published paper. The partial-parking-function count used below is their Proposition 8. The new point is a uniform decomposition for arbitrary $j$; it also gives an explicit formula for $f_j$ and proves that its asserted degree cannot drop.

1. Words on a fixed initial segment

We will also run the parking procedure on arbitrary words with preferences in $\{1,\ldots,j\}$, allowing a car to leave if no spot is available. For a word of length $\ell$, let $L_{j,\ell}$ count those in which spot $j$ becomes lucky, and let $A_{j,\ell}$ count those in which, in addition, all $j$ spots become occupied. Define the exponential generating functions

$$\begin{aligned} L_j(x)&=\sum_{\ell\ge0}L_{j,\ell}\frac{x^\ell}{\ell!},\\ A_j(x)&=\sum_{\ell\ge0}A_{j,\ell}\frac{x^\ell}{\ell!}. \end{aligned}$$

In particular, $[x^\ell]A_j(x)=0$ for $\ell<j$.

Recall that $t$ cars can park successfully in $m$ spots in

$$(m-t+1)(m+1)^{t-1}$$

ways, for $0\le t\le m$, with value $1$ when $t=0$. Here is the usual circular proof. Put $m+1$ spots on a circle. Every preference word parks all $t$ cars and leaves $m+1-t$ empty spots. Rotational symmetry implies that a prescribed spot is empty in the fraction $(m+1-t)/(m+1)$ of the $(m+1)^t$ words. If that prescribed spot is the last one, its remaining empty is equivalent to successful linear parking in the first $m$ spots.

Before spot $j$ first becomes occupied, no car can leave. If this first happens at arrival $t+1$, the preceding $t$ cars have parked in the first $j-1$ spots, so there are $(j-t)j^{t-1}$ possible prefixes. To make spot $j$ lucky, the next preference must be $j$; every later preference is unrestricted. Summing over $t$ gives

$$L_{j,\ell}= \begin{cases} \dfrac{\ell(2j-\ell+1)}{2}j^{\ell-2},&0\le\ell<j,\\[4pt] \dfrac{j+1}{2j}j^\ell,&\ell\ge j. \end{cases}$$

Set $c_j=(j+1)/(2j)$. Thus

$$L_j(x)=c_j e^{jx}-Q_j(x),$$

where the polynomial recording the initial exceptions is

$$Q_j(x)=\frac12\sum_{\ell=0}^{j-1} (j-\ell)(j-\ell+1)j^{\ell-2}\frac{x^\ell}{\ell!}.$$

2. Decomposition at the last empty spot

For $h\ge1$, put

$$\begin{aligned} B_h(x)&=\sum_{\ell=0}^{h-1} (h-\ell)h^{\ell-1}\frac{x^\ell}{\ell!},\\ B_0(x)&=1. \end{aligned}$$

This counts all successful partial parking words on the first $h-1$ spots.

Consider a word counted by $L_j$ but not by $A_j$, and let $h<j$ be its last empty spot. No car preferred $h$, and no car crossed it. The subsequence of preferences below $h$ is a successful partial parking word on $h-1$ spots. The subsequence above $h$, after subtracting $h$ from its preferences, fills all $j-h$ spots and makes the last one lucky. Conversely, any two such subsequences may be interleaved, preserving their internal orders. Hence

$$L_j(x)=\sum_{h=0}^{j-1}B_h(x)A_{j-h}(x).$$

The inverse of this convolution has a particularly simple form. Let $T=T(z)$ be the formal series satisfying

$$T=z e^{xT}.$$

Lagrange inversion gives, for $h\ge1$,

$$\begin{aligned} [z^h]T&=\tau_h x^{h-1},\\ \tau_h&=\frac{h^{h-1}}{h!}, \end{aligned}$$

and

$$\begin{aligned} [z^h]\frac1{1-T} &=\frac1h[u^{h-1}]\frac{e^{hxu}}{(1-u)^2}\\ &=B_h(x). \end{aligned}$$

Thus the generating series of the $B_h$ is $(1-T)^{-1}$, and multiplication by $1-T$ inverts the preceding convolution. It follows that

$$A_j(x)=L_j(x)-\sum_{h=1}^{j-1}\tau_h x^{h-1}L_{j-h}(x).$$

Substituting the expression for $L_j$ yields

$$\begin{aligned} A_j(x)={}&c_j e^{jx}\\ &-\sum_{h=1}^{j-1}\tau_h c_{j-h}x^{h-1}e^{(j-h)x} +P_j(x), \end{aligned}$$

where

$$P_j(x)=-Q_j(x) +\sum_{h=1}^{j-1}\tau_h x^{h-1}Q_{j-h}(x).$$

Consequently $\deg P_j\le j-1$. Write $p_{j,d}=[x^d]P_j(x)$.

3. Reinsert the preferences beyond spot $j$

Return to $n\ge j$ and $X=n-j+1$. Suppose exactly $\ell$ of the $n$ preferences are at most $j$. Their subsequence must fill the first $j$ spots and make spot $j$ lucky, so it has $A_{j,\ell}$ possibilities. The remaining $n-\ell$ cars form a successful partial parking word on the last $n-j$ spots, with

$$(\ell-j+1)X^{n-\ell-1}$$

possibilities. There are $\binom n\ell$ interleavings of these two subsequences.

To justify this separation, recall that success of a parking word is unchanged by permuting the cars; equivalently, if its preferences are sorted increasingly as $b_1\le\cdots\le b_n$, success means $b_i\le i$ for all $i$. Move the cars whose preferences exceed $j$ to the front, without changing either subsequence's internal order. They never affect the first $j$ spots. If they park successfully and the other subsequence fills the first $j$ spots, each excess car from that subsequence has preference at most $j$ and takes the next available spot beyond $j$. All cars therefore park. Conversely, any successful full word has both properties. Moreover, the lucky status of spot $j$ depends only on the relative order of preferences at most $j$, which this reordering preserves.

We obtain

$$S_j(n)=\sum_{\ell=j}^n\binom n\ell A_{j,\ell}(\ell-j+1)X^{n-\ell-1}.$$

For a formal series $F(x)$, define

$$\mathcal F(F)=\frac{n!}{X}[x^n]e^{Xx} \bigl(xF'(x)-(j-1)F(x)\bigr).$$

Since $A_j$ has no coefficients below degree $j$, the counting formula says exactly $S_j(n)=\mathcal F(A_j)$.

The exponential term of highest rate gives

$$\mathcal F(e^{jx})=(n+1)^{n-1}.$$

All the other exponential terms in $A_j$ vanish under $\mathcal F$. Indeed, take $1\le r\le j-1$ and $d=j-r-1$. Then

$$\begin{aligned} &x(x^d e^{rx})'-(j-1)x^d e^{rx}\\ &\qquad=r(x^{d+1}-x^d)e^{rx}. \end{aligned}$$

Here $X+r=n-d$. With $M=n-d\ge1$, the two relevant coefficients are equal:

$$\frac{M^{M-1}}{(M-1)!}=\frac{M^M}{M!}.$$

Therefore $\mathcal F(x^d e^{rx})=0$.

Finally, for $0\le d\le j-1$, write $n^{\underline d}=n(n-1)\cdots(n-d+1)$, with $n^{\underline0}=1$. Direct coefficient extraction gives

$$\mathcal F(x^d)=(d-j+1)n^{\underline d}X^{n-d-1}.$$

The term with $d=j-1$ vanishes. The desired formula follows with the explicit polynomial

$$f_j(n)=\sum_{d=0}^{j-2} (j-1-d)p_{j,d}\,n^{\underline d}X^{j-d-2}.$$

Here $X=n-j+1$ as before. Every summand has degree at most $j-2$. It remains to exclude cancellation of the leading terms.

4. Positive coefficients in the polynomial basis

We show that $p_{j,d}>0$ for $0\le d\le j-2$. This will also give a direct finite formula for every coefficient needed above.

For $0\le m\le d$, define the positive numbers

$$W_m=\binom dm(m+1)^{m-1}(j-m-1)^{d-m}.$$

Since $[x^d]A_j=0$ in this range, its exponential decomposition gives

$$\begin{aligned} 2d!p_{j,d}={}&-(j+1)j^{d-1}\\ &+\sum_{m=0}^d\frac{j-m}{j-m-1}W_m. \end{aligned}$$

We use the classical Abel identity, which in this notation is

$$\sum_{m=0}^d W_m=j^d.$$

For completeness, this identity follows from the same tree-series calculation. Let $R(y)=y e^{R(y)}$. Lagrange inversion gives

$$\frac{R(y)}y=\sum_{m\ge0}(m+1)^{m-1}\frac{y^m}{m!}.$$

The exponential generating function in $d$ of the left side of Abel's identity is

$$e^{(j-1)z}\frac{R(ze^{-z})}{ze^{-z}}=e^{jz},$$

because $R(ze^{-z})=z$ as formal series. Comparing coefficients proves the identity.

Using $\sum_m W_m=j^d$ and splitting $j-m=(j-m-1)+1$ in the expression for $p_{j,d}$ now gives

$$2d!p_{j,d}=\sum_{m=0}^d\frac{W_m}{j-m-1}-j^{d-1}.$$

For $0\le m\le d\le j-2$, each denominator lies strictly between $0$ and $j$. Thus

$$\sum_{m=0}^d\frac{W_m}{j-m-1} >\frac1j\sum_{m=0}^d W_m=j^{d-1},$$

which proves $p_{j,d}>0$. Negative exponents occurring at $d=0$ or $m=d$ cause no problem: their bases are positive integers, so these are ordinary rational numbers.

Each polynomial $n^{\underline d}(n-j+1)^{j-d-2}$ is monic of degree $j-2$. Hence $f_j$ has degree exactly $j-2$, with positive rational leading coefficient

$$r_j=\sum_{d=0}^{j-2}(j-1-d)p_{j,d}>0.$$

For example, the formula reproduces

$$\begin{aligned} f_2(n)&=\frac14,\\ f_3(n)&=\frac{2n-1}{3},\\ f_4(n)&=\frac{13n^2-26n+9}{8}. \end{aligned}$$

5. The limiting probability

There are $(n+1)^{n-1}$ parking functions of length $n$, by the circular count above with $m=t=n$. For fixed $j\ge2$,

$$\begin{aligned} \frac{n^{j-2}X^X}{(n+1)^{n-1}} &=\left(\frac n{n+1}\right)^{j-2}\\ &\quad\cdot\left(1-\frac j{n+1}\right)^{n-j+1}\\ &\longrightarrow e^{-j}. \end{aligned}$$

Since $f_j(n)/n^{j-2}\to r_j$, division of the exact counting formula by $(n+1)^{n-1}$ gives the asserted limit. The count holds for every $n\ge j$, including $n=j$, and the separate $j=1$ case was established at the outset. This proves the entire polynomial-form conjecture.