Cars that park, and trees that grow

Sixteen trees on four points counted the ways to join $n$ labelled points into a tree and found $n^{n-2}$ — sixteen for four points, 125 for five — and explained the count by a code that turns each tree into a list of $n - 2$ labels. It ended by naming a third way to count the same objects, through “a problem about cars and parking spaces”. This essay is that problem, and the reason it has the same answer is a better argument than either of the other two: a single rotation of a circle.

A street with one-way traffic #

There are $n$ spaces along a one-way street, numbered 1 to $n$ in the direction of travel, and $n$ cars arrive one after another. Car $i$ has a preferred space $a_i$. It drives to that space and parks there if it is free; if not, it carries on and takes the first free space further along. If it reaches the end of the street without finding one, it leaves, and the parking has failed.

A list of preferences that lets every car park is a parking function. The five cars in the figure, wanting spaces 3, 1, 3, 2 and 1, all park: the first takes space 3, the second space 1, the third finds 3 taken and drives on to 4, the fourth takes 2, and the fifth finds 1, 2, 3 and 4 all taken and ends in 5, the last space on the street.

Whether a list is a parking function can be decided without driving at all. Sort the preferences into increasing order. The list parks everyone exactly when the $k$-th smallest preference is at most $k$, for every $k$. If some $k$-th smallest preference exceeded $k$, then at most $k - 1$ cars would want any of the first $k$ spaces, some space among the first $k$ would stay empty, and — since cars only move forward — too many cars would compete for the spaces after it. Conversely, if the sorted list stays at or below the diagonal, every space gets filled from the left. The order in which the cars arrive affects who ends where, but not whether everyone parks — which is why the count can treat a parking function as a list rather than as a story.

Sixteen out of twenty-seven #

With three cars there are $3^3 = 27$ lists of preferences, and the figure marks the sixteen that work. They include every arrangement of $(1, 2, 3)$ — six lists in which each car wants a different space — the three arrangements of $(1, 1, 2)$, three of $(1, 1, 3)$, three of $(1, 2, 2)$, and $(1, 1, 1)$, where all three cars want the first space and simply fill the street in order. They exclude anything with two cars wanting space 3, or with no car wanting space 1.

Sixteen is the number of labelled trees on four points. The coincidence continues: with four cars there are 125 parking functions and 125 labelled trees on five points, and in general

$$\#\{\text{parking functions of length } n\} = (n + 1)^{n-1} = \#\{\text{labelled trees on } n + 1 \text{ points}\}.$$

The table checks it for up to seven cars, 262,144 parking functions out of 823,543 lists, by testing every list, and for up to five cars it also builds every tree on $n + 1$ points and counts them. The two numbers agree on every row. The share of lists that work falls like $e/n$ — for seven cars, a little under a third — so a random set of preferences usually strands someone, and the ones that do not are precisely as numerous as trees. One reason is easy to see: a list fails at once if no car wants space 1, and the chance of that is $(1 - 1/n)^n$, which tends to $1/e$ — the same limit nobody gets their own hat finds for a random matching with no fixed point, although there the chances are not independent and here they are: $n$ cars, each missing space 1 with chance $1 - 1/n$, all of them missing it together. Two different mechanisms, one constant — which is how $1/e$ usually turns up.

Pollak’s circle #

Henry Pollak found the argument that explains the count, and it is the kind that makes a formula obvious once seen. Change the street. Instead of a line of $n$ spaces, make it a circle of $n + 1$ spaces, numbered 1 to $n + 1$, and let every car’s preference be any of the $n + 1$. A car that finds its space taken drives on round the circle until it finds one free.

On the circle nobody is ever turned away — the circle has no end to drive off — and since there are $n$ cars and $n + 1$ spaces, exactly one space is left empty. Now rotate a list of preferences: add the same amount to every preference, wrapping round the circle. The cars drive exactly as before, each shifted round by the same amount, so the empty space is shifted too. The $n + 1$ rotations of any list leave the empty space in each of the $n + 1$ positions exactly once.

The connection to the line is the last observation. A list parks everyone on the straight street of $n$ spaces exactly when, on the circle, space $n + 1$ is the one left empty — because then no car ever needed to pass space $n$, which is the same as never driving off the end of the street. So among the $n + 1$ rotations of any list, exactly one is a parking function. The $(n + 1)^n$ lists on the circle fall into groups of $n + 1$ rotations, each group contains one parking function, and

$$\#\{\text{parking functions}\} = \frac{(n + 1)^n}{n + 1} = (n + 1)^{n-1}.$$

The hero figure runs the argument on one list, $(2, 4, 2)$, and its four rotations: the empty space moves round the circle, 1, 2, 3, 4, and the rotation $(1, 3, 1)$, which leaves space 4 empty, is the one that parks on the line. Behind the figure every one of the 64 lists of three preferences on four spaces was checked the same way: each leaves one space empty, and each rotation class of four contains exactly one parking function.

The sixteen trees, beside the sixteen lists #

The sixteen trees on four points come in two shapes: twelve paths, one for each way of ordering the four points along a line with the two directions identified, and four stars, one centred on each point. The sixteen parking functions of length three come in shapes too, if a list is read by its sorted form: six rearrangements of $(1, 2, 3)$, three each of $(1, 1, 2)$, $(1, 1, 3)$ and $(1, 2, 2)$, and one $(1, 1, 1)$.

The two partitions do not match — twelve and four against six, three, three, three and one — and that is a useful warning. A bijection between two sets of the same size need not respect any structure either set has, and the natural statistics on the two sides are different. What the counts share is the total, and the circle explains the total without mentioning trees at all. A bijection that does respect structure has to be built with care — the one described below matches the number of cars that are displaced from their preference to a statistic on trees — and there are several such maps in the literature, each carrying a different pair of statistics across. That multiplicity is typical of a count with many explanations: every proof of Cayley’s formula, from the Prüfer code to Pollak’s circle, suggests its own correspondence, and the correspondences do not agree with each other.

The increasing ones, and the Catalan numbers #

Sort a parking function and it becomes a weakly increasing parking function: a list $a_1 \le a_2 \le \cdots \le a_n$ with $a_k \le k$ for every $k$. Draw it as a path on a grid — a step right for each car, a step up whenever the preference increases — and the condition $a_k \le k$ says that the path never rises above the diagonal. Such paths are counted by the Catalan numbers: 1, 2, 5, 14, 42 for $n = 1$ to 5, the sequence one sequence counting everything finds under a dozen disguises.

So every parking function is a rearrangement of one of the Catalan-many increasing ones, and the full count is a sum over paths of the number of ways to rearrange each. For $n = 3$ the five increasing lists are $(1,1,1)$, $(1,1,2)$, $(1,1,3)$, $(1,2,2)$ and $(1,2,3)$, and their rearrangements number $1 + 3 + 3 + 3 + 6 = 16$. The two famous sequences are related by exactly this sum: the Catalan numbers count the parking functions up to reordering the cars, and $(n + 1)^{n-1}$ counts them with the cars distinguished.

The Catalan numbers have their own one-in-$(n + 1)$ argument, the cycle lemma, and it is the ballot-counting cousin of Pollak’s circle — the path folded at its first touch derives the same numbers by reflection instead. Both counts divide a larger, obvious count by $n + 1$, and in both the division is justified by the same kind of symmetry.

Why rotation divides so cleanly #

The argument is a counting of orbits under a symmetry, the same move necklaces that prove a theorem makes when it counts necklaces of $p$ beads by grouping them into rotation classes of size $p$. There the classes all have size $p$ because $p$ is prime; here they all have size $n + 1$ for a different reason — rotating a list by any amount other than a full turn moves its empty space, so no list is fixed by a proper rotation. A symmetry that moves every object gives classes of equal size, and a count divides.

The same device, a circle with one more position than necessary, is the cycle lemma of ballot counting: among the rotations of a sequence of votes, exactly one keeps one candidate ahead throughout. Counting the paths that go wrong uses it to count the Catalan numbers, $\binom{2n}{n}/(n + 1)$, where the division by $n + 1$ is the same division by the number of rotations. It is the reason $n + 1$ appears in so many formulae for objects of size $n$: the objects are the one-in-$n + 1$ representatives of classes on a slightly larger circle.

From cars to trees, directly #

The counts agree, and a bijection exists that turns each parking function into a labelled tree on $\{0, 1, \ldots, n\}$. One version reads the parking process as a search. Put a root labelled 0 in space “zero”, before the street. Cars that prefer space 1 become children of the root; a car that prefers space $s > 1$ becomes a child of whichever car parked in space $s - 1$. Reading the parking in order builds a tree on the root and the $n$ cars, and the preferences can be recovered from the tree — a fact that needs an argument about the order in which the tree is searched, which the figures here do not check — so every parking function gives a different tree and every tree arises.

What makes the bijection more than a curiosity is what it carries across. The number of cars that had to drive past their preferred space — the total displacement — corresponds, under a suitable version of the bijection, to a count of inversions in the tree, and its generating function is the same polynomial that counts connected graphs by their number of edges. Parking functions turned out to be a way into the combinatorics of hashing, where each key is sent to a slot and probes forward on collision: a table of $n$ keys in $n + 1$ slots with linear probing is exactly Pollak’s circle, and Knuth analysed its average probe count with these same numbers in the 1960s. Collisions in a hash table — two keys sent to the same slot — are the event a collision that finds a factor turns into a factoring method, and they arrive, as the birthday problem predicts, after only about the square root of the table’s size; linear probing is one way of living with them, and the parking count is the exact accounting of what it costs.

What the table and the circles cannot show #

The bijection with trees is described, not drawn. The figures establish that the counts agree, by enumerating both sides for small $n$ and by Pollak’s argument for every $n$; the explicit map from parking functions to trees is given in words, and no figure checks it list by list.

The circle’s rotations were checked for one size. The claim that each rotation class contains exactly one parking function was verified on all 64 lists for three cars; the proof for general $n$ is the argument above, which the figure illustrates rather than replaces.

The Catalan connection is quoted. The sum over increasing lists was carried out by hand above for three cars; the general statement that increasing parking functions are counted by the Catalan numbers is the standard lattice-path argument, not checked by a figure here.

And the street is one-way and the cars never leave. Parking problems with two-way streets, with cars that depart, or with preferences drawn from a larger street all have their own counts, and most of them have no formula as clean as this one; the $(n + 1)^{n-1}$ is special to the exact rules drawn.

Still open: parking with more than one kind of car #

The parking function count generalises in many directions, and some of the most natural are open. When cars of different lengths each need a run of consecutive free spaces — parking sequences — the number of successful lists has a product formula in some cases and none known in others. When the street is a tree rather than a line, with cars driving towards the root and parking at the first free vertex, counts are known for particular trees but no formula covers every tree.

The best known open problem in the area comes from its algebraic side. Parking functions of length $n$ index a basis of a space of polynomials — the diagonal harmonics — whose dimension is $(n + 1)^{n-1}$, a fact proved by Haiman in 2002 with methods from algebraic geometry. Refinements of that count by pairs of statistics on parking functions were conjectured to have strong symmetry and positivity properties, and the “shuffle conjecture” describing them was proved by Carlsson and Mellit in 2018. One consequence is that the $q,t$-Catalan numbers — the Catalan numbers refined by two statistics — are symmetric under exchanging $q$ and $t$. No combinatorial proof of that symmetry is known: nobody has found a map on the underlying paths that exchanges the two statistics, although the algebra guarantees that the two counts agree.

One count, three stories #

Labelled trees on $n + 1$ points, codes of $n - 1$ labels, parking functions for $n$ cars: three kinds of object, one count, $(n + 1)^{n-1}$. The Prüfer code explained the first by a bijection with lists. Pollak’s circle explains the third by a symmetry: on a circular street with one extra space, every list of preferences parks, one space stays empty, and rotating the list rotates the empty space, so exactly one rotation in $n + 1$ is a parking function.

A parking function is a small object — a list of $n$ numbers — and it carries a surprising amount: a tree, a path under a diagonal, a hash table with one spare slot. The street is the picture that holds them together, and the circle is the argument that counts them.

When a count is a power divided by the base, look for a circle with one extra position — a symmetry whose orbits all have the same size, and a condition that picks out exactly one member of each. The street needed one more space than it had cars; the formula needed the same thing, and the circle supplies it.