The dominance order for permutations

Castronuovo, Niccoló

doi:10.1515/puma-2015-0004

Abstract

We define an order relation over S_n considering the Robinson-Schensted bijection and the dominance order over Young tableaux. This order relation makes S_n(k k - 1...3 2 1) -the set of permutations of length n that avoid the pattern k k - 1...3 2 1, k ≤ n- a principal filter in Sn. We study in detail these order relations on Sn(321) and Sn(4321), finding order-isomorphisms between these sets and sets of lattice paths.

References

[1] R. M. Adin and Y. Roichman, Equidistribution and sign-balance on 321-avoiding permuta- tions, Sém. Lothar. Combin., 51 (2004) Article B51d.
Search in Google Scholar
[2] E. Barcucci, A. Bernini, L. Ferrari and M. Poneti, A distributive lattice structure con- necting Dyck paths, noncrossing partitions and 312-avoiding permutations, Order, 22 (2005) 311-328.
Search in Google Scholar
[3] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the Enumeration of Combinatorial Objects, J. Difference Equ. Appl., 5 (1999) 435-490.10.1080/10236199908808200
Search in Google Scholar
[4] M. Bóna, Combinatorics of Permutations, Discrete Mathematics and Its Applications, Chapman and Hall/CRC, 2004.
Search in Google Scholar
[5] A. Brini, Combinatorics, superalgebras, invariant theory and representation theory, Sém. Lothar. Combin., 55 (2007) Article B55g.
Search in Google Scholar
[6] T. Brylawski, The lattice of integer partitions, Discrete Math., 6 (1973) 201-219.10.1016/0012-365X(73)90094-0
Search in Google Scholar
[7] A. Claesson and S. Kitaev, Classiffcation of bijections between 321- and 132-avoiding per- mutations, Sém. Lothar. Combin., 60 (2008) Article B60d.10.46298/dmtcs.3594
Search in Google Scholar
[8] S. Elizalde and I. Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A, 105 (2004) 207-219.10.1016/j.jcta.2003.10.009
Search in Google Scholar
[9] L. Ferrari and R. Pinzani, Lattices of lattice paths, J. Statist. Plann. Inference, 135 (2005) 77-92.10.1016/j.jspi.2005.02.007
Search in Google Scholar
[10] W. Fulton, Young Tableaux, London Mathematical Society Student Text 35, Cambridge University Press, 1999.
Search in Google Scholar
[11] D. E. Knuth, The Art of Computer Programming, Vol. I, Addison-Wesley, Reading, Mass.- London-DonMills, 1969.
Search in Google Scholar
[12] D. E. Knuth, The Art of Computer Programming, vol. 3, Addison-Wesley, Reading, MA, 1973.
Search in Google Scholar
[13] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math., 27 (2001) 510-530.
Search in Google Scholar
[14] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math, 13 (1961) 179-191.
Search in Google Scholar

The dominance order for permutations

Abstract

Paradigm

My account