دانلود رایگان مقاله توزیع شاخص عمده بر طبقات جایگشت

abstract

For a permutation π the major index of π is the sum of all indices i such that πi>π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 View the MathML source of permutations of length n with major index m, avoiding the set of patterns Π. First we are able to show that for a singleton set Π={σ} other than some trivial cases, the values View the MathML source are monotonic in the sense that View the MathML source. Our main result is a study of the asymptotic behaviour of View the MathML source as n goes to infinity. We prove that for every fixed m, Π and n large enough, View the MathML source is equal to a polynomial in n and moreover, we are able to determine the degrees of these polynomials for many sets of patterns.

5. Conclusion and further directions

In Section 3, we proved the monotonicity of the numbers Mm n (σ) for a single pattern σ other than 12 ··· k (recall Theorem 3.4) and showed an example of a set Π for which the monotonicity does not hold even though Mm n (Π) tends to infinity. The natural question to ask would be whether we can in general characterize such sets Π for which the monotonicity of columns does not hold even though deg(m, Π) ≥ 1. Based on computing the values Mm n (Π) for small n and various sets Π, it seems to us that these cases are rather rare. In Section 4, we analysed the asymptotic behaviour of the numbers Mm n (Π) for many types of Π in the sense of the degree deg(m, Π). The most natural way to extend this study is to cover the remaining cases. For example, it remains to be shown whether the sets Π that contain permutations with both finite and infinite magnitude obey any general rules. Another open problem is to determine exactly for which sets Π the values Mm n (Π) are eventually equal to zero.