number of parking functions

Statement

The number of parking functions on $n$ cars and parking spots is

(n + 1)^{n - 1}

Proof 1

Consider the modified procedure where we have $n$ cars and $n + 1$ spots arranged on a circular road. Let $f : [n] \to [n + 1]$ with the same parking procedure (note that a car will always find a spot, and one of the spots will be empty).

Let $P_{i}$ be the set of preference functions $f$ such that the $i$ th spot is empty. We note the following:

$P_{n + 1}$ is exactly the set of normal parking functions (as this means that $f : [n] \to [n]$ AND no cars have to drive past $n$ th slot, so no cars drive away)
$| P_{i} | = | P_{j} |$ for all $i, j$ by symmetry

Furthermore, there are $(n + 1)^{n}$ preference functions, and so $| P_{1} | = \frac{1}{n + 1} \cdot (n + 1)^{n} = (n + 1)^{n - 1}$

Proof 2 (biject with labelled trees)

First, we biject with labelled Dyck paths: for every up step, we label them $1$ through $n$ such that consecutive up steps have increasing labels.

Given a labelled Dyck path, we can construct a parking function:

Draw the diagonals (with slope 1) and number them
If an up step labelled $j$ lies on the $i$ th diagonal, set $f_{i} = j$

example:
Pasted image 20260430141725.png|300

Finally, there is a bijection between labelled Dyck paths and labelled trees on $n + 1$ vertices.