# 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 $i+1$ times. 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.

• I don't know what a parking function is. – Gerry Myerson May 25 '14 at 11:49
• Edited to add the first paragraph explaining parking functions. – coolpapa May 25 '14 at 20:16
• Now posted to MO, mathoverflow.net/questions/168870/… – Gerry Myerson Jun 2 '14 at 23:33