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

Annals of Combinatorics 10 (2) p. 237-254 June, 2006

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

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.