Recursively counting a parking function

Question

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.

Answer 1

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)$$