In the figure below, rectangles are cars, labeled in the order of arrival.
The cars leave a "layer of sediment" between the place where they initially
wanted to park, and the place where they finally park.
The total amount of sediment is known as "TOTAL DISPLACEMENT"
(Knuth, Flajolet Viola and Poblete, Spencer ...)
or "portee d'une suite majeure", "inversion number of a Cayley tree" (Kreweras)
and has beautiful combinatorial
properties (previous authors and also
Foata & Riordan, Francon, Gessel, Stanley, Haiman, Bergeron ...)
The total displacement, once renormalized,
converges to the Airy law (Flajolet Viola and Poblete, Algoritmica 1999)
also known as the area below the Brownian excursion.
The profile of the small hills of sediments (see the figure below,
at the last arrival ‹ full parking lot) turns out to converge
to the Brownian excursion (C. & Marckert, C. & Louchard, C. & Janson).
Coalescence of parking blocks, as cars arrive, provides,
asymptotically, a NEW CONSTRUCTION
(Bertoin,
A fragmentation process
related to Brownian motion, see also
C. & Louchard, Section 8)
of the
additive coalescent (Aldous & Pitman, 1999).
Last modified: Tue Feb 8 MET 2000 -->