1
$\begingroup$

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$
  • 1
    $\begingroup$ I don't know what a parking function is. $\endgroup$ – Gerry Myerson May 25 '14 at 11:49
  • 1
    $\begingroup$ Edited to add the first paragraph explaining parking functions. $\endgroup$ – coolpapa May 25 '14 at 20:16
  • $\begingroup$ Now posted to MO, mathoverflow.net/questions/168870/… $\endgroup$ – Gerry Myerson Jun 2 '14 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.