Platzproblem

The Platzproblem, also known as the "parking problem" or "parking function," is a combinatorial concept introduced by Donald E. Knuth in 1968. It describes a method for generating permutations of a set of elements with specific constraints, particularly useful in computer science and discrete mathematics.

The problem is framed as follows: imagine a one-way street with *n* parking spots, each labeled from 1 to *n*. *n* cars arrive in random order and attempt to park in the first available spot. If a spot is already taken, the car moves to the next available one. The Platzproblem studies the resulting permutation of parking assignments, where each car ends up in a unique spot.

A permutation is considered a valid parking function if, for every prefix of the permutation, the number of distinct elements is at least as large as the length of the prefix. For example, the sequence (2, 1, 3) is a valid parking function for *n* = 3, while (3, 2, 1) is not, as the first car cannot park in spot 3 without first checking spots 1 and 2.

Parking functions have applications in various fields, including graph theory, where they model certain types of labeled trees, and in computer science, particularly in algorithms for generating random permutations or simulating network routing. The number of valid parking functions for *n* cars is known to be *n* raised to the power of (*n* − 1), a result derived by Knuth.

The concept is also related to the study of random walks and has been extended to more complex scenarios, such as multi-dimensional parking problems or probabilistic models of parking behavior. Despite its simple formulation, the Platzproblem remains a fundamental tool in understanding structured permutations and their applications in theoretical and applied mathematics.