Asymptotic bound for inversions of unit interval parking functions

The conjectured bound holds with an implied constant independent of both parameters. There is also a simple leading-term formula when the number of inversions is fixed.

Write $A_{n,k}=\operatorname{upf}_{n,k}^{\operatorname{inv}}$. Thus $A_{n,k}$ counts preference lists $(a_1,\ldots,a_n)\in\{1,\ldots,n\}^n$ for which the cars, arriving in order, all park either at their preferred spot or one spot farther along, and for which

$$\#\{(i,j):1\le i<j\le n,\ a_i>a_j\}=k.$$

We prove the uniform estimate

$$A_{n,k}\le \frac{e^8}{2}\,2^{n-2k}n^k \qquad \left(n\ge8,\quad 0\le k\le\frac{n(n-1)}2\right).$$

This proves Celano et al., Conjecture 4.5. For each fixed integer $k\ge0$, we additionally obtain

$$A_{n,k}\sim \frac{2^{n-k-1}}{k!}\,n^k \qquad(n\longrightarrow\infty).$$

The idea is to use the paper's existing encoding by inversion codes. A positive evaluation of their generating polynomial bounds every coefficient at once. For the sharper fixed-$k$ statement, almost all relevant codes have $k$ isolated entries equal to $1$.

1. The existing cipher formula

For $n\ge1$, let

$$E_{n,k}= \left\{ w=(w_1,\ldots,w_n): 0\le w_i\le i-1,\quad \sum_{i=1}^n w_i=k \right\},$$

and let

$$\operatorname{asc}(w) =\#\{i:1\le i<n,\ w_i<w_{i+1}\}.$$

Equation (28) of the cited paper gives

$$A_{n,k} =\sum_{w\in E_{n,k}}2^{n-1-\operatorname{asc}(w)}. \tag{1}$$

To recall the counting behind this formula, the paper's cipher bijection encodes a parking function by such a word with bars inserted between entries. Each rise requires a bar, and each other position admits either choice. There are therefore exactly $2^{n-1-\operatorname{asc}(w)}$ bar choices. We use this established bijection and do not need to modify it.

2. A bound uniform in the inversion number

The polynomial that counts the unbarred codes is

$$F_n(z) =\sum_{k\ge0}|E_{n,k}|z^k =\prod_{i=1}^n(1+z+\cdots+z^{i-1}).$$

All its coefficients are nonnegative. Consequently, for every real $z>0$,

$$|E_{n,k}|\le z^{-k}F_n(z).$$

Also, (1) gives $A_{n,k}\le2^{n-1}|E_{n,k}|$. If $0<z<1$, each factor in $F_n(z)$ is at most $(1-z)^{-1}$, and hence

$$A_{n,k} \le 2^{n-1}z^{-k}(1-z)^{-n}. \tag{2}$$

For $n\ge8$, take $z=4/n$. The elementary inequality

$$-\log(1-u)=\int_0^u\frac{dv}{1-v} \le\frac{u}{1-u} \qquad(0\le u<1)$$

implies

$$(1-4/n)^{-n} \le \exp\!\left(\frac{4}{1-4/n}\right) \le e^8.$$

Substituting into (2) yields

$$A_{n,k} \le e^8\,2^{n-1}\left(\frac n4\right)^k =\frac{e^8}{2}\,2^{n-2k}n^k.$$

The same constant works for every allowed $k$, including $k=0$ and the largest possible inversion number. The finitely many values $n<8$ do not affect the asserted asymptotic bound; if desired, an absolute constant can be enlarged to include those values as well.

3. The leading term for fixed inversion number

When $k=0$, the only code is the zero word, so (1) gives $A_{n,0}=2^{n-1}$ exactly.

Now fix $k\ge1$ and take $n\ge2k$. Consider the codes with exactly $k$ entries equal to $1$, all other entries zero, and with no two $1$'s adjacent. The first entry must be zero. Choosing $k$ nonadjacent positions from $\{2,\ldots,n\}$ gives

$$\binom{n-k}{k}$$

such codes. Every $1$ is preceded by a zero, so each code has exactly $k$ ascents. Their contribution to (1) is therefore

$$2^{n-k-1}\binom{n-k}{k}. \tag{3}$$

There are only $O_k(n^{k-1})$ other codes in $E_{n,k}$. Indeed, a code containing an entry at least $2$ has at most $k-1$ positive entries. There are $O_k(n^{k-1})$ choices for their positions, and only finitely many compositions of the fixed integer $k$ for their values. Otherwise, the code has $k$ entries equal to $1$ with an adjacent pair. For $k\ge2$, choose the start of one adjacent pair and then the remaining $k-2$ positions, giving again $O_k(n^{k-1})$ possibilities. For $k=1$ this second exceptional family is empty.

Each exceptional code contributes at most $2^{n-1}$. Combining this with (3) gives

$$A_{n,k} =2^{n-k-1}\binom{n-k}{k} +O_k(2^n n^{k-1}).$$

Finally, for fixed $k$,

$$\binom{n-k}{k} =\frac{n^k}{k!}+O_k(n^{k-1}).$$

Thus

$$A_{n,k} =\frac{2^{n-k-1}}{k!}\,n^k \left(1+O_k\!\left(\frac1n\right)\right).$$

The uniform estimate proves the full conjectured bound, while this last formula explains the leading terms of the paper's explicitly computed cases.