One way road problem about combinatorics

Question

Along a one-way street there are $n$ parking lots. One-by-one $n$ cars numbered 1, 2, 3, ..., n enter the street. Each driver $i$ heads to their favourite parking lot $a_i$ and if it is free, they occupy it . Otherwise, they continue to the next free lot and occupy it. But if all succeeding lots are occupied, they leave for good. How many sequences $(a_1,a_2,...,a_n)$ are there such that every driver can park?

If the answer was known to me, I would have used induction but I can't find the answer. I tried recursion but I failed to make progress. I am still trying but if you have some good idea please let me know. If I am able to solve it I will post the answer.

Answer 1

There is something called the parking function. Please read this. http://www-math.mit.edu/~rstan/transparencies/parking.pdf The answer is $f(n) = (n+1)^{(n-1)}$

Answer 2

Let's call a sequence in which every driver can park a successful sequence. Let the number of successful sequences with $n$ parking spaces and $m$ cars be $f(n,m)$, so the original problem is to find $f(n,n)$.

As boundary values we have $f(n.0) = 1 \space \forall n \ge 0$ and $f(n,m) = 0 \space \forall m > n$.

Number the parking space from $1$ nearest the entrance to the street to $n$ nearest the exit. Suppose in a successful sequence $(a_i)$ there are $k$ cars such that $a_i=n$ i.e. $k$ cars that are happy to park in any space. Removing these cars from the sequence leaves a successful sequence with $m-k$ cars and $n-1$ parking spaces.

Conversely, each of the $f(n-1,m-k)$ sequences with $m-k$ cars and $n-1$ spaces can be extended to a successful sequence with $m$ cars and $n$ spaces by adding $k$ terms with $a_i=n$. These can be inserted anywhere in the sequence, so there are $\binom{m}{k}$ ways of extending the sequence.

This gives a recurrence relation

$f(n,m) = \sum_{k=0}^{m} f(n-1,m-k)\binom{m}{k} = \sum_{k=0}^{m} f(n-1,m)\binom{m}{k}$

Using the recurrence relation and the base case

$f(0,m) = 1 \text { if } m=0; \space 0 \text{ if } m>0$

we can prove by induction that

$f(n,m) = (n+1)^m - m(n+1)^{m-1} \quad 0 \le m \le n$

and when $m=n$ we have

$f(n,n) = (n+1)^n - n(n+1)^{n-1} = (n+1)^{n-1}$

Answer 3

For the purpose of the problem, add an $(n+1)^{th}$ parking lot and extend the street to a circuit leading from the $(n+1)^{th}$ to the first lot. Now each driver, if and when they find their favorite lot occupied, can go round and occupy the next free parking lot they encounter. There will always be one such, since there are $(n+1)$ lots and only $n$ cars. there are now $(n+1)^{n}$ sequences {$a_i$} since each driver has $(n+1)$ choices. One lot will remain empty. If the empty lot that remains happens to be the $(n+1)^{th}$ lot that we created, then that choice of sequence {$a_i$} solves the original problem. In this sense that sequence may be called a 'good' sequence.

A given sequence {$a_i$}, that is $a_1, a_2, ..., a_n$ may be cyclically shifted to $a_1+1, a_2+1, ..., a_n+1$ which itself can be cyclically shifted to another. All cyclically shifts of a given sequence may be considered to belong to a class of sequences of which only one will be 'good'. Each class has $(n+1)$ sequences. Thus the $(n+1)^n$ sequences divide into $(n+1)^n/(n+1)=(n+1)^{(n-1)}$ classes, each containing $(n+1)$ sequences. Each class contains one 'good' sequence. So the number of 'good' sequences (and therefore the answer to the problem) is $(n+1)^{(n-1)}$

Source: Challenge and Thrill of Pre-College Mathematics