Leaves in labeled trees and increasing sequences in permutation pairs
Angele Hamel
(Wilfrid Laurier U.)
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: (n+1)^(n-1). A series of related bijections 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.