Enumerative Combinatorics

5.49. a. [2] There are n parking spaces 1, 2,..., n (in that order) on a one-way street. Cars C₁,..., C_n enter the street in that order and try to park. Each car C_i has a preferred space a_i. A car will drive to its preferred space and try to park there. If the space is already occupied, the car will park in the next available space. If the car must leave the street without parking, then the process fails. If α = (a₁,...,a_n) is a sequence of preferences that allows every car to park, then we call α a parking function. Show that a sequence (a₁,..., a_n) ∈ [n]ⁿ is a parking function if and only if the increasing rearrangement b₁ ≤ b₂ ≤ · · · ≤ b_n of a₁, a₂,..., a_n satisfies b_i ≤ i. In other words, α = (a₁, ...,a_n) is a parking function if and only ...