Priority Queue Sorting and Labeled Trees

A.M. Hamel

Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo Ontario, N2L 3C5, Canada

ahamel@wlu.ca

Annals of Combinatorics 7 (1) p.49-54 March, 2003

Abstract:

We construct a bijection between labeled trees and allowable pairs of permutations sorted by a priority queue. These are also the pairs of permutations that avoid the pattern pairs (12,21) and (321,132). Our bijection has the additional property that it maps leaves in the tree to descents in the output permutation in the allowable pair and, more generally, preserves the edge-deletion distribution of the tree.

References:

1. M.D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994) 1225每1230.

2. M.D. Atkinson, S.A. Linton, and L.A. Walker, Priority queues and multisets, Elect. J. Combin. 2 (1995) #R24.

3. M.D. Atkinson and M. Thiyagarajah, The permutational power of a priority queue, BIT 33 (1993) 2每6.

4. N.L. Biggs, Chip-firing and the critical group of a graph, J. Algebraic Combin. 9 (1999) 25每45.

5. J. D赤nes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, Publ. Math. Inst. Hung. Acad. Sci. 4 (1959) 63每70.

6. I.M. Gessel and K.-Y. Wang, A bijective approach to the permutational power of a priority queue, preprint.

7. J. Gilbey and L. Kalikow, Parking functions, valet functions, and priority queues, Discrete Math 197/198 (1999) 351每375.

8. M. Golin and S. Zaks, Labelled trees and pairs of input-output permutations in priority queues, Theoret. Comput. Sci. 205 (1998) 99每114.

9. I.P. Goulden and S. Pepper, Labelled trees and factorizations of a cycle into transpositions, Discrete Math. 113 (1993) 263每268.

10. I.P. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory, Ser. A 98 (2002) 106每117.

11. L. Kalikow, Enumeration of parking functions, allowable permutation pairs, and labeled trees, Ph.D. Thesis, Brandeis University, 1999.

12. L. Kalikow, Symmetries in trees and parking functions, Discrete Math. 256 (2002), 719每741.

13. D.E. Knuth, The Art of Computer Programming, Vols. 1 and 3, 2nd Ed., Addison-Wesley, Reading, MA, 1997 and 1998.

14. G. Kreweras, Une famille de polynômes ayant plusieurs propri谷t谷s 谷numeratives, Period. Math. Hungar. 11 (1980) 309每320.

15. S.N. Majumdar and D. Dhar, Equivalence between the Abelian sandpile model and the q↙0 limit of the Potts model, Physica A 185 (1992) 129每145.

16. R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

17. R.P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge University Press, Cambridge, UK, 1999.

18. D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, New York, 1986.