The Abstract

	Annals of Combinatorics 10 (2006) 237-254 Permutation Factorizations and Prime Parking Functions Amarpreet Rattan Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada arattan@math.uwaterloo.ca Received October 13, 2004 AMS Subject Classification: 05A15, 05C05, 05E15 Abstract. Permutation factorizations and parking functions have some parallel properties. Kim and Seo exploited these parallel properties to count the number of ordered, minimal factorizations of permutations of cycle type (n) and (1, n-1). In this paper, we use parking functions, new tree enumerations and other necessary tools, to extend the techniques of Kim and Seo to the cases (2, n-2) and (3, n-3). Keywords: permutation factorizations, trees, parking functions References 1. J.S. Beissinger and U.N. Peled, A note on major sequences and external activity, Electron. J. Combin. 4 (2) (1997) #R2. 2. D. Foata and J. Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974) 10–22. 3. I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, JohnWiley & Sons, New York, 1983. 4. I.P. Goulden and D.M. Jackson, Transitive factorisations into transpositions and holomorphic mappings on the sphere, Proc. Amer. Math. Soc. 125 (1997) 51–60. 5. I.P. Goulden and S. Pepper, Labelled trees and factorizations of a cycle into transpositions, Discrete Math. 113 (1993) 263–268. 6. I.P. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory Ser. A 98 (2002) 106–117. 7. D. Kim and S. Seo, Transitive cycle factorizations and prime parking functions, J. Combin. Theory Ser. A 104 (1) (2003) 125–135. 8. G. Kreweras, Une famille de polynômes ayant plusieurs propriétés énumeratives, Period. Math. Hungar. 11 (1980) 309–320. 9. P. Moszkowski, A solution to a problem of Dénes: a bijection between trees and factorizations of cycle permutations, European J. Combin. 10 (1989) 13–16. 10. R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1998. 11. C.H. Yan, Generalized tree inversions and k-parking functions, J. Combin. Theory Ser. A 79 (2) (1997) 268–280. Get the DVI \| PS \| PDF file of this abstract. back

Annals of Combinatorics 10 (2006) 237-254

Permutation Factorizations and Prime Parking Functions

Amarpreet Rattan

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
arattan@math.uwaterloo.ca

Received October 13, 2004

AMS Subject Classification: 05A15, 05C05, 05E15

Abstract. Permutation factorizations and parking functions have some parallel properties. Kim and Seo exploited these parallel properties to count the number of ordered, minimal factorizations of permutations of cycle type (n) and (1, n-1). In this paper, we use parking functions, new tree enumerations and other necessary tools, to extend the techniques of Kim and Seo to the cases (2, n-2) and (3, n-3).

Keywords: permutation factorizations, trees, parking functions

References

1. J.S. Beissinger and U.N. Peled, A note on major sequences and external activity, Electron. J. Combin. 4 (2) (1997) #R2.

2. D. Foata and J. Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974) 10–22.

3. I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, JohnWiley & Sons, New York, 1983.

4. I.P. Goulden and D.M. Jackson, Transitive factorisations into transpositions and holomorphic mappings on the sphere, Proc. Amer. Math. Soc. 125 (1997) 51–60.

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

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

7. D. Kim and S. Seo, Transitive cycle factorizations and prime parking functions, J. Combin. Theory Ser. A 104 (1) (2003) 125–135.

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

9. P. Moszkowski, A solution to a problem of Dénes: a bijection between trees and factorizations of cycle permutations, European J. Combin. 10 (1989) 13–16.

10. R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1998.

11. C.H. Yan, Generalized tree inversions and k-parking functions, J. Combin. Theory Ser. A 79 (2) (1997) 268–280.

Get the DVI | PS | PDF file of this abstract.

back