# Parking function problem

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!

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}$$