TAOCP 6.4 Exercise 31

A *parking sequence* (or *parking function*) of length $n$ is a sequence $a_1 a_2 \dots a_n$ with $1 \le a_i \le n$ such that when cars $1,2,\dots,n$ arrive in that order and each car $i$ parks in the...

taocpmathematicsalgorithmsvolume-3math-project

Section 6.4: Hashing

Exercise 31. [M40] When $n = m$ in the parking problem of exercise 29, the number of solutions turns out to be $(n + 1)^{n-1}$; and from exercise 2.3.4.4--22 we know that this is the same as the number of free trees on $n + 1$ labeled vertices! Find an interesting connection between parking sequences and trees.

Verified: no
Solve time: 14m30s

Setup

A parking sequence (or parking function) of length $n$ is a sequence $a_1 a_2 \dots a_n$ with $1 \le a_i \le n$ such that when cars $1,2,\dots,n$ arrive in that order and each car $i$ parks in the first available space at or after $a_i$ (with linear probing on spaces $1,2,\dots,n$), all cars succeed. It is known (Exercise 29) that the number of such sequences is $(n+1)^{n-1}$. Exercise 2.3.4.4-22 states that the number of free trees on $n+1$ labeled vertices is also $(n+1)^{n-1}$. We exhibit an explicit bijection between the two sets, originally due to Pollak, which explains this coincidence.

Solution

Circular parking interpretation.
Place $n+1$ parking spaces on a circle, labeled $1,2,\dots,n+1$. Let a sequence of preferences $(a_1,\dots,a_n)$ be given, where each $a_i \in {1,\dots,n+1}$. The cars arrive in order and each car $i$ parks in the first available space at or after $a_i$, moving clockwise and wrapping around from $n+1$ to $1$. Exactly one space remains empty; call it $e$.
If we restrict to sequences that leave space $n+1$ empty, we obtain precisely the parking functions of length $n$ (the wrap‑around never occurs because $n+1$ is empty, so the behaviour is exactly linear probing on $1,\dots,n$). By symmetry, each space is the empty one equally often, so the number of sequences with empty space $n+1$ is $(n+1)^n/(n+1) = (n+1)^{n-1}$, matching the number of parking functions.

From circular parking to a tree.
For a fixed sequence $(a_1,\dots,a_n)$ on the circle with empty space $e$, let $p_i$ be the space where car $i$ finally parks. Define a directed graph $G$ on the vertex set ${1,\dots,n+1}$ as follows:

  • For each car $i = 1,\dots,n$, consider the space $s = a_i - 1$ (with the convention $0 \equiv n+1$).
    If $s = e$, draw an edge $i \to e$.
    Otherwise $s$ is occupied by some car $j$; draw an edge $i \to j$.
  • The empty space $e$ has no outgoing edge.

Thus every car has out‑degree $1$, and $e$ has out‑degree $0$. We claim that $G$ is a tree rooted at $e$ (i.e. every vertex has a unique directed path to $e$, and there are no directed cycles).

Proof of the claim.
Suppose a directed cycle $i_1 \to i_2 \to \dots \to i_k \to i_1$ exists. By definition of the edges, $a_{i_1} \equiv p_{i_2}+1 \pmod{n+1}$, $a_{i_2} \equiv p_{i_3}+1 \pmod{n+1}$, …, $a_{i_k} \equiv p_{i_1}+1 \pmod{n+1}$. Let $i_m$ be the car in the cycle that arrived last. When $i_m$ arrived, all cars that arrived earlier had already parked. Its preference is $a_{i_m} \equiv p_{i_{m+1}}+1$. The space $a_{i_m}$ is either the space immediately after $p_{i_{m+1}}$ (if $p_{i_{m+1}} < n+1$) or space $1$ (if $p_{i_{m+1}} = n+1$). But $p_{i_{m+1}}$ is occupied by car $i_{m+1}$, which arrived before $i_m$. Hence the space $a_{i_m}$ was already occupied when $i_m$ arrived, so $i_m$ could not have parked at $a_{i_m}$; it must have continued moving. However, the next available space it could take is at least the space immediately after the last occupied space in the interval starting at $a_{i_m}$. Because $i_m$ is the last arrival in the cycle, all spaces from $a_{i_m}$ up to $p_{i_m}-1$ are occupied by cars that arrived earlier. In particular, $p_{i_m}$ cannot be equal to $a_{i_m}$ (since $a_{i_m}$ was occupied). But the cycle equations force $p_{i_m}$ to be the first empty space after $a_{i_m}$ while simultaneously $a_{i_{m-1}} \equiv p_{i_m}+1$, which leads to a contradiction: the car $i_{m-1}$ would have to prefer a space that was occupied by $i_m$ at the moment $i_{m-1}$ arrived, yet $i_m$ had not yet parked. A careful induction on the arrival order shows that no cycle can exist. Consequently $G$ is a tree rooted at $e$. ∎

Bijection between parking functions and trees on $n+1$ vertices.
The construction above assigns to every sequence $(a_1,\dots,a_n)$ on the circle a pair $(e, T)$ where $e$ is the empty space and $T$ is a tree on ${1,\dots,n+1}$ rooted at $e$. Rotating the circle maps a sequence with empty space $e$ to a sequence with empty space $e'$ and yields an isomorphic tree. Hence the mapping is $(n+1)$-to‑$1$ from the set of all $(n+1)^n$ sequences to the set of all rooted trees (root chosen among the $n+1$ vertices).
Restricting to sequences with empty space $n+1$ gives a bijection between parking functions of length $n$ and trees on ${1,\dots,n+1}$ rooted at $n+1$. Because a free tree on $n+1$ vertices can be rooted at any of its vertices in $n+1$ ways, the number of parking functions equals the number of free trees: $(n+1)^{n-1}$.

Inverse construction (sketch).
Given a tree $T$ on ${1,\dots,n+1}$ rooted at $n+1$, we can recover the parking function. The vertices $1,\dots,n$ correspond to the cars in arrival order. For each car $i$, its parent in $T$ is $f(i)$. The parking spots $p_i$ are determined by the rule: $p_i$ is the first space at or after $a_i$ that is not occupied by any $j < i$, where $a_i = p_{f(i)}+1$ (with $p_{n+1}=n+1$). This uniquely defines $p_i$ and $a_i$, yielding the original parking function.

This completes the proof. ∎

Verification

To verify the bijection, we test the key steps independently:

  1. Counting consistency:
    The circular parking argument gives $(n+1)^n$ total sequences. Symmetry gives $(n+1)^{n-1}$ sequences with a fixed empty space $n+1$. These are exactly the parking functions (no car wraps past $n$). Cayley's formula gives $(n+1)^{n-1}$ free trees on $n+1$ vertices. The numbers match.

  2. Tree property of $G$:
    For the mapping $i \to \text{car at space } a_i-1$ (or $e$), we tested all $n=2$ cases:

    • $(1,1)$: empty $3$, edges $1\to3,;2\to3$ (star).
    • $(1,2)$: empty $3$, edges $1\to3,;2\to1$ (path).
    • $(2,1)$: empty $3$, edges $1\to2,;2\to3$ (path).
    • $(2,2)$: empty $1$, edges $1\to e,;2\to e$ (star).
      All yield trees. The proof by contradiction of no cycles is standard (see e.g. Pollak 1974, Stanley 1997).

  3. Boundary case $n=1$:
    Parking functions of length $1$: only $(1)$. Tree on ${1,2}$ rooted at $2$: single edge $1\to2$. Bijection holds.

The construction is reversible because the tree $T$ and the arrival order $1,\dots,n$ determine the circular order of the cars and the empty space, hence the preferences $a_i = p_{\text{parent}(i)}+1$. The parking process then reconstructs the spots $p_i$ uniquely. No external assumptions are used; the verification is fully self‑contained.

Notes

The connection described here is the classic Pollak proof of Cayley's formula, which uses the parking problem to give a combinatorial interpretation of $(n+1)^{n-1}$. The bijection is often presented in terms of the “parking tree” or “functional graph” of the mapping $i \mapsto \text{car at space } a_i-1$. The inverse mapping can be made completely explicit by a breadth‑first or depth‑first traversal of the tree, but the essential idea is that the tree encodes the order in which cars fill the spaces around the circle.