Parking Functions and the Binomial Theorem

Question

Cross-post from https://math.stackexchange.com/questions/808490/parking-functions-and-the-binomial-theorem

A parking function is a function $f: \{1, \ldots n\} \rightarrow \{1, \ldots n\}$ which has the property that the list $(f(1), f(2), \ldots f(n))$ can be rearranged in some order $(a_{1}, a_{2}, \ldots a_{n})$ so that $a_{i} \leq i$ for each $i$. That is, for each $i$, $$ \left| \{ 1 \leq j \leq n | f(j) \geq i \} \right| \leq n+1-i. $$ The term "parking function" means that we imagine $n$ cars wanting to park in $n$ spaces. Each car has a preferred spot tracked by the function. Car 1 parks in its preferred spot $f(1)$. Car 2 tries to park in its preferred spot $f(2)$. If that spot is taken, it parks in the next (higher-numbered) spot. The other cars continue in this fashion. The function $f$ is a valid parking function if and only if all the cars can park without anyone have to turn around and park in a lower-numbered spot than their preferred spot. Often, we just think about parking functions as the string $(f(1), f(2), \ldots f(n))$. There are 16 parking functions when $n=3$: 111,112,121,211,113,131,311,221,212,122, 123,132,213,231,312, and 321.

The number of parking functions is well-known to be $(n+1)^{(n-1)}$. We can obviously expand this using the binomial theorem, and the terms seems to be combinatorial. In $\sum_{i=0}^{n-1} \binom{n-1}{i} n^{i}$, the term corresponding to $i$ counts the number of parking functions that take the value 1 exactly $n-i$ times (at least for the small cases I've looked at). But it's hard to actually prove that. Any ideas on a proof?

I'm fairly certain that we want to start with $\binom{n-1}{i} n^{i} = \binom{n}{i} (n-i) n^{i-1}$, but I don't really see where to go from there.

Answer 1

I'll use this lovely argument for the formula $\# PF = (n+1)^{n-1}$ that you mentioned as inspiration (see pg. 5 of the document).

First of all, we have to choose the $n- i$ slots for the $1$'s. So we really want to show that there are $(n-i)n^{i-1}$ ways to assign numbers from $\{2, \ldots, n\}$ to the remaining $i$ arguments that produce parking functions.

The cars with preference $1$ obviously never need to back up, so we can focus on the other $i$ cars. As in the original argument, invent an extra parking spot $n+1$ and let the cars go round in a circle. For any function $f: \{ 1,\ldots, i\} \to \{2, \ldots, n+1\}$, consider $f+k$ $\mod n$, for $k=0,1, \ldots, n-1$. The parking functions among these are exactly those for which spot $n+1$ remains unoccupied. Since there are $i$ cars and $n$ spots, this is a fraction $(n-i)/n$ of these functions. Thus we obtain $$ \frac{n-i}{n}\, n^i = (n-i)n^{i-1} $$ admissible assignments, as claimed.