The University of Michigan Combinatorics Seminar
A number of combinatorial objects--labeled trees, allowable pairs of
input-output permutations for priority queues, factorizations of an
n-cycle into transpositions, and parking functions--are all
enumerated by the same formula: nn-2.
A series of bijections--some of them related--have been constructed
between two or more of these.
Here we introduce and prove a direct bijection between priority queue
allowable pairs and labeled trees that has an additional property not
present in previous direct bijections: our bijection maps increasing
sequences in the output permutation of the priority queue allowable pair
to leaves in the tree. This gives us a full understanding of the
underlying tree structure of priority queue allowable pairs. For
instance, we could use this understanding to construct the analogue of a
Prufer code for allowable pairs. This is joint work with A. Yong.