O'Reilly logo

Enumerative Combinatorics by Sergey Fomin, Richard P. Stanley

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5.49. a. [2] There are n parking spaces 1, 2,..., n (in that order) on a one-way street. Cars C1,..., Cn enter the street in that order and try to park. Each car Ci has a preferred space ai. 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 α = (a1,...,an) is a sequence of preferences that allows every car to park, then we call α a parking function. Show that a sequence (a1,..., an) ∈ [n]n is a parking function if and only if the increasing rearrangement b1b2 ≤ · · · ≤ bn of a1, a2,..., an satisfies bii. In other words, α = (a1, ...,an) is a parking function if and only ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required