Major index distribution over permutation classes. (English) Zbl 1344.05009
Summary: For a permutation \(\pi\) the major index of \(\pi\) is the sum of all indices \(i\) such that \(\pi_i > \pi_{i + 1}\). It is well known that the major index is equidistributed with the number of inversions over all permutations of length \(n\). In this paper, we study the distribution of the major index over pattern-avoiding permutations of length \(n\). We focus on the number \(M_n^m(\Pi)\) of permutations of length \(n\) with major index \(m\), avoiding the set of patterns \(\Pi\).
First we are able to show that for a singleton set \(\Pi = \{\sigma \}\) other than some trivial cases, the values \(M_n^m(\Pi)\) are monotonic in the sense that \(M_n^m(\Pi) \leq M_{n + 1}^m(\Pi)\). Our main result is a study of the asymptotic behaviour of \(M_n^m(\Pi)\) as \(n\) goes to infinity. We prove that for every fixed \(m\), \(\Pi\) and \(n\) large enough, \(M_n^m(\Pi)\) is equal to a polynomial in \(n\) and moreover, we are able to determine the degrees of these polynomials for many sets of patterns.
First we are able to show that for a singleton set \(\Pi = \{\sigma \}\) other than some trivial cases, the values \(M_n^m(\Pi)\) are monotonic in the sense that \(M_n^m(\Pi) \leq M_{n + 1}^m(\Pi)\). Our main result is a study of the asymptotic behaviour of \(M_n^m(\Pi)\) as \(n\) goes to infinity. We prove that for every fixed \(m\), \(\Pi\) and \(n\) large enough, \(M_n^m(\Pi)\) is equal to a polynomial in \(n\) and moreover, we are able to determine the degrees of these polynomials for many sets of patterns.
Online Encyclopedia of Integer Sequences:
Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i), where k ranges from 0 to A000217(n-1). Also enumerates permutations by their major index.References:
| [1] | Babson, E.; Steingrímsson, E., Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., 44, Article B44b pp. (2000), (electronic) · Zbl 0957.05010 |
| [2] | Bloom, J., A refinement of Wilf-equivalence for patterns of length 4, J. Combin. Theory Ser. A, 124, 166-177 (2014) · Zbl 1283.05012 |
| [3] | Bloom, J.; Saracino, D., On bijections for pattern-avoiding permutations, J. Combin. Theory Ser. A, 116, 8, 1271-1284 (2009) · Zbl 1181.05002 |
| [4] | Bloom, J.; Saracino, D., Another look at bijections for pattern-avoiding permutations, Adv. in Appl. Math., 45, 3, 395-409 (2010) · Zbl 1194.05001 |
| [5] | Claesson, A.; Jelínek, V.; Steingrímsson, E., Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns, J. Combin. Theory Ser. A, 119, 8, 1680-1691 (2012) · Zbl 1246.05002 |
| [6] | Claesson, A.; Kitaev, S., Classification of bijections between 321- and 132-avoiding permutations, Sém. Lothar. Combin., 60, Article B60d pp. (2008-2009) · Zbl 1179.05006 |
| [7] | Dokos, T.; Dwyer, T.; Johnson, B. P.; Sagan, B. E.; Selsor, K., Permutation patterns and statistics, Discrete Math., 312, 18, 2760-2775 (2012) · Zbl 1248.05004 |
| [8] | Elizalde, S., Fixed points and excedances in restricted permutations, Electron. J. Combin., 18, 2, Article P29 pp. (2011) · Zbl 1243.05018 |
| [9] | Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010 |
| [10] | Foata, D., On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., 19, 236-240 (1968) · Zbl 0157.03403 |
| [11] | Knuth, D. E., The Art of Computer Programming. Vol. 1: Fundamental Algorithms (1969), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, Mass.-London-Don Mills, Ont · Zbl 0191.17903 |
| [12] | MacMahon, P. A., Combinatory Analysis, Vols. 1 and 2 (1915), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, (reprinted by Chelsea, New York, 1955) · JFM 45.1271.01 |
| [13] | Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations, Ann. Comb., 6, 3-4, 427-444 (2002) · Zbl 1017.05014 |
| [14] | Rodrigues, O., Note sur les inversions, ou dérangements produits dans les permutations, J. Math. Pures Appl., 4, 236-240 (1839) |
| [15] | Sloane, N. J.A., The on-line encyclopedia of integer sequences, A008302, triangle of Mahonian numbers T(n,k) · Zbl 1274.11001 |
| [16] | Stanley, R., Problems and solutions: solutions of elementary problems: E2546, Amer. Math. Monthly, 83, 10, 813-814 (1976) |
| [17] | Stanley, R.; Bolis, T. S.; Klamkin, M. S.; Singmaster, D.; Schoenberg, I. J.; Montgomery, H. L., Problems and solutions: elementary problems: E2546-E2551, Amer. Math. Monthly, 82, 7, 755-756 (1975) |
| [18] | Stern, M. A., Aufgaben, J. Reine Angew. Math., 18, 100 (1838) · ERAM 018.0586cj |
| [19] | Yan, S. H.F.; Ge, H.; Zhang, Y., On a refinement of Wilf-equivalence for permutations, Electron. J. Combin., 22, 1, Article P1.20 pp. (2015) · Zbl 1307.05004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
