3
$\begingroup$

Problem: Let $n \leq m \leq 2n$. Find the number of all parking functions on $[n]$ so that $\sum_{i=1}^n f(i)=m$.

Background:

Background: A shopping center has n parking spots along a one-way street. One morning, exactly n cars will arrive at the shopping center at various times. Once a car is parked, it does not leave before all other cars arrive. Each of the cars has a favorite parking spot, and a rather short-sighted strategy about it. namely,, each car first goes to its favorite spot. If it is free, the car will take it; if it is not, it will go to the next spot. Then, if the next spot is not free, the car will go to the next spot, and so on, until it finds a free spot. If no spots are free after (and including) the favorite spot of a car, then that car will not have a spot, and we will say that the parking process was unsuccessful. If each car finds a spot, then we will say that the parking process was successful. Denote the set of the n cars by the lements of $[n]$, and denote the n parking spots in the order they follow along the one-way street, also by the lements of $[n]$. Let $f(i)$ be the favorite spot of car $i$, then $f:[n] \rightarrow [n]$ is a function. If the parking procesudre i successful, say f is a parking function on $[n]$.

Some results I am thinking about:

Lemma: The function $f:[n] \rightarrow [n]$ is a parking function iff for all $k \in [n]$, there are at most k values $i \in [n]$ so that $f(i) \geq n-k+1$.

Theorem: For all positive integers n , $P(n)=(n+1)^{n-1}$.

I am not sure how to make use of these results and the approach of this problem. Can someone direct an approach? Thanks a lot for the help!

$\endgroup$
2
$\begingroup$

This problem is from the $1997$ argentinian mathematical olympiad.

Here is a solution from Pablo Soberon's book.

The idea is to instead consider $n+1$ parking spots which are placed in a circle (in increasing order) and allow any possible function. Then each function manages to park every car (since the positions are now in a circle a car can go back to the start ). The functions that we want are the ones that leave the position $n+1$ empty.

Consider the equivalence relation in which two functions $f$ and $g$ are the same if there is $k$ such that $f(i) = g(i) +k\bmod n+1$.

This equivalence relation splits all the possible functions into classes of size $n+1$ in which each member leaves a different position empty (because adding $k$ to each value also adds $k$ to the spot that is empty at the end).

It follows exactly one of each $n+1$ of the functions leave position $n+1$ empty.

Since there are $(n+1)^n$ in total the answer is $(n+1)^{n-1}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.