7
$\begingroup$

This exercise is taken from the site of Queen Mary University of London:

A car park has $n$ spaces, numbered from $1$ to $n$, arranged in a row. $n$ drivers each independently choose a favourite parking space in the park. As each driver enters the park, he drives to his favourite space. If it is empty, he parks there. Otherwise, he continues along the line and parks in the first free space. If all spaces between his favourite and $n$ are taken, he leaves in disgust.

Show that, out of the $n^n$ choices of favourite spaces that the drivers can make, just $(n+1)^{n-1}$ lead to all drivers parking successfully.

Now, my question is whether my (attempt of ) solution is wrong and what a different approach could be. Here's my idea: proving the claim by (a kind of) induction. It is easy to verify truthfulness for $n=1$ and $n=2$, so having this base case, we shall prove that if the claim holds for all $1\le n\le k$, then it does also for $n=k+1$.

Let us assume WLOG there is an already established order of appearance of the drivers, since a different order yields the same number of successful choices: it just suffices to swap the drivers. Let us call $d_m$ the space chosen by the $m$-th driver.

Now, consider the cases in which $d_1=1$. By inductive hypothesis, the other drivers have $n^{n-2}$ successful choices. In fact, the same goes for all the other $n-1$ choices of the first driver, so that in total, as a "first outcome", we have $\color\red{n^{n-1}}$ successful choices. We somewhat can do the same reasoning with the second driver, but we must keep in mind that for each of his choices, we have already counted those in which the first driver occupies the other spaces. For example, we need to subtract the successful cases in which at the same time $d_2=1$ and $d_1=2$: that is $(n-1)^{n-2}$. This happens for all the spaces not chosen by the second driver, and so we actually need to subtract $(n-1)^{n-1}$. Finally, letting vary $d_2$ yields the "second outcome" $\color\red{n^{n-1}-n(n-1)^{n-1}}$. And so on, and so on. The final outcome would be the sum of all the red expressions. However I'm afraid no nice power would be a result of this. Is there a mistake in my reasoning?

$\endgroup$
7
  • 1
    $\begingroup$ The classical proof by Pollak uses the following direct argument: for any $(a_1,\ldots, a_n)$ where $a_j\in\{0,\ldots, n\}$, there exists only one $i$ mod $n+1$ such that $(a_0+i \bmod (n+1), \ldots, a_n+i\bmod (n+1))$ is a parking function, leading to the count $(n+1)^n/(n+1)$ possibilities. A sketch of proof can be found in the following slides by Stanley: www-math.mit.edu/~rstan/transparencies/parking.pdf $\endgroup$
    – emeu
    Commented Aug 23, 2015 at 15:40
  • $\begingroup$ @emeu: Woah, thank you. Do you happen to know other proofs? And, did you find a mistake in my reasoning? $\endgroup$ Commented Aug 23, 2015 at 17:11
  • $\begingroup$ @Vincenzo: Your first step is off. After the first driver parks, the remaining $n-1$ drivers have $n^{n-2}$ successful choices if none of them chooses the first driver’s spot. However, there are other successful choices for them in which one or more of them prefers first driver’s spot. $\endgroup$ Commented Aug 24, 2015 at 20:42
  • $\begingroup$ @Brian: Oh dear, you're absolutely right. Thank you. And, I guess no other proofs are known? $\endgroup$ Commented Aug 24, 2015 at 23:53
  • $\begingroup$ @Vincenzo: Parking functions and labeled trees [PDF], by António Guedes de Oliveira & Michel Las Vergnas, exhibits a bijection between parking functions of size $n$ and labelled rooted trees with $n+1$ vertices. Now apply Cayley’s result that there are $(n+1)^{n-1}$ such trees; it has a variety of different proofs. I’ve not seen the original proof by Pyke (1959) or the proof by Konheim & Weiss (1966), but they were different from Pollak’s. $\endgroup$ Commented Aug 25, 2015 at 1:48

1 Answer 1

5
$\begingroup$

This solution is paraphrased from http://www-math.mit.edu/~rstan/transparencies/parking.pdf.

Imagine that the parking spaces are instead arranged in a circle, and an $(n+1)^{st}$ spot is added. Each of the $n$ cars chooses a favorite space between $1$ and $n+1$. Each car tries to park in their preferred space, but if they find it occupied, they inspect adjacent spaces in increasing order until they find an empty space. Now, every car will be able to find a spot with certainty. Furthermore, the sequence $(a_1,a_2,\dots,a_n)$ is valid in the original problem if and only if the unused space is $n+1$ in the modified problem.

There are $(n+1)^n$ choices for the sequence of space preferences. Furthermore, if the unused spot for $(a_1,\dots,a_n)$ is $k$, then the unused spot for $(a_1+1,\dots,a_n+1)$ is $k+1$, where all addition is modulo $n+1$. Therefore, these $(n+1)^{n}$ sequences are partitioned into sets of size $n+1$ where there is exactly one valid sequence for the original problem, so the number of valid sequences is $$\frac{(n+1)^n}{n+1}=(n+1)^{n-1}.$$

$\endgroup$
1
  • 1
    $\begingroup$ Posting so future questions can be closed as dupes. $\endgroup$ Commented Feb 12, 2019 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .