6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean $n -i$ times? $\endgroup$ – Christian Remling Jun 2 '14 at 22:06
  • $\begingroup$ Silly mistake. Yes, I'll edit. Thanks for the correction. $\endgroup$ – coolpapa Jun 2 '14 at 22:10
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ FWIW: Though the $(n+1)^{n-1}$ argument given there is already 40 years old, its originator - Henry Pollak - still enjoys posing the related problem when the topic of "mathematical modeling" arises... $\endgroup$ – Benjamin Dickman Jun 3 '14 at 0:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.