Aequationes Mathematicae, 10, 1974, 10-22.
Dominique Foata and John Riordan
Mappings of acyclic and parking functions
Abstract.
The two functions in question are mappings of the set of integers 1,2,...,n into itself. The acyclic function may be represented by forests of labeled rooted trees, or by free trees with n + 1 points; the parking functions are associated with the simplest ballot problem. The total number of each is (n+1) to the power of (n-1). The first of two mappings given is based on a simple mapping, due to H. O. Pollak, of parking functions on tree codes. In the second, each kind of function is mapped on permutations, arising naturally from characterizations of the functions. Several enumerations are given to indicate uses of the mappings.
foata at unistra dot fr
The following version is available: