## 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.