Parking functions, allowable pairs, and a symmetry in trees

We explore the connections between parking functions and two of other sets of objects. First, we describe a bijection between parking functions and allowable pairs of permutations of a priority queue, which have been studied by Atkinson. The bijection preserves breakpoints, which are closely related to the idea of prime parking functions. We then provide an interpretation of the inversion enumerator for labeled trees using allowable pairs; Kreweras has previously interpreted the inversion enumerator for parking functions. We also obtain a generalization of the inversion enumerator using allowable pairs. Furthermore, we define valet functions, a variant of parking functions, and demonstrate a bijection between them and allowable pairs of permutations of a multiset. We next discuss a symmetry in trees and its connection to parking functions. Gessel showed that the number of trees on $\{0,1,2,\ldots, n\}$ with $i$ descents and $j+1$ leaves equals the number of trees with $j$ descents and $i+1$ leaves. We provide a new proof of this by using recursions obtained from decompositions of trees. The method of proof leads to a generalization of a functional equation found by Knuth concerning trees in which every vertex is either a leaf or a descent. We use an analogous decomposition to show a symmetry in parking functions between descents and ``disfavored spaces'' of the parking function. The results in this talk are part of the doctoral thesis of the presenter written under the direction of Professor Ira Gessel.