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.
$\endgroup$ 3 Reset to default
