The University of Michigan Combinatorics Seminar


Abstract 

A number of combinatorial objectslabeled trees, allowable pairs of
inputoutput permutations for priority queues, factorizations of an
ncycle into transpositions, and parking functionsare all
enumerated by the same formula: n^{n2}.
A series of bijectionssome of them relatedhave 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.
