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