2
$\begingroup$

Definition: Parking Function

A parking function of order $n$ is a function $f:\{1,2,\ldots,n\}\rightarrow\{1,2,\ldots,n\}$ such that

$$|\{x:f(x)\le i\}|\ge i\qquad \textrm{for $1\le i\le n$}$$

It is often described using the following scenario:

$n$ cars $\{1,2,\ldots,n\}$ enter a one way street (or parking lot) with $n$ parking spaces. Each car enters the street one at a time in numerical order. They each proceed along the spaces $\{1,2,\ldots , n\}$ in order so that each successive car $x$ either fills its preferred space $f(x)$ or the next available space after $f(x)$. If all cars manage to find a space before exiting the parking lot at the far end then $f$ is called a "parking function". If any car cannot find a space after its preferred space then $f$ is not a parking function.


My task is to provide a combinatoric argument for the recursive formula that counts the number of parking functions on $[n+1]$. The formula is given by $$P(n+1)=\sum_{i=0}^{n} \binom{n}{i} (i+1) P(i)P(n-i)$$


I know that explicit formula for counting the number of parking function is given by $$P(n) = (n+1)^{n-1}$$ Providing a explanation for the recursion seems to be relate to the concept of dividing the "parking spots" into halves. With the first half having $i$ spots and the second half having $n-i$ spots, but I can't fully relate.

$\endgroup$
  • 1
    $\begingroup$ Can you define what a parking function is? $\endgroup$ – sku Apr 2 '18 at 4:46
  • $\begingroup$ Defined here: www-math.mit.edu/~rstan/transparencies/parking.pdf $\endgroup$ – B.Li Apr 2 '18 at 5:34
  • 1
    $\begingroup$ Can you edit your question such that it contains a definition of "parking function"? We like questions to be reasonably self-contained. $\endgroup$ – hmakholm left over Monica Apr 3 '18 at 0:02
  • $\begingroup$ @HenningMakholm. I have edited the question to include the definition, I hope that's clear enough. $\endgroup$ – N. Shales Apr 3 '18 at 1:10
2
$\begingroup$

When car $n+1$ arrives at the parking lot of $n+1$ spaces, space $i+1$ is empty.

  • Spaces $1$ to $i$ are filled with a subset $S$ of the cars, this means the parking preferences of these cars form a parking function on spaces $1$ to $i$. There are $P(i)$ such parking functions on spaces $1$ to $i$.

  • No car in the complement set of $S$ ($S'$) can have parking preferences from $1$ to $i$, otherwise space $i+1$ would already be taken. Therefore the parking preferences of these cars forms a parking function on spaces $i+2$ to $n+1$. There are $P(n-i)$ such parking functions.

  • There are $\binom{n}{i}$ ways to split these $n$ cars between the two sets $S$ and $S'$.

  • Lastly, for any parking function where space $i+1$ is empty when car $n+1$ arrives, we must have that car $n+1$ has $i+1$ possible parking preferences: $1$ to $i+1$.

The number of possible parking functions when car $n+1$ arrives and space $i+1$ is empty is the product of these factors:

$$\binom{n}{i}(i+1)P(i)P(n-i)$$

Summing over all possible spaces for $i+1\in\{1,\ldots,n+1\}$ gives the number of parking functions $P(n+1)$:

$$P(n+1)=\sum_{i=0}^{n}\binom{n}{i}(i+1)P(i)P(n-i)$$

$\endgroup$

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.