Major index distribution over permutation classes

Abstract: For a permutation

p i

the major index of

p i

is the sum of all indices

i

such that

p i_{i} > p 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

M_{n}^{m} (P i)

of permutations of length

n

with major index

m

and avoiding the set of patterns

P i

. First we are able to show that for a singleton set

P i = s i g m a

other than some trivial cases, the values

M_{n}^{m} (P i)

are monotonic in the sense that

M_{n}^{m} (P i) l e q M_{n + 1}^{m} (P i)

. Our main result is a study of the asymptotic behaviour of

M_{n}^{m} (P i)

as

n

goes to infinity. We prove that for every fixed

m

and

P i

and

n

large enough,

M_{n}^{m} (P i)

is equal to a polynomial in

n

and moreover, we are able to determine the degrees of these polynomials for many sets of patterns.

Recommendations

Cites Work

Cited In (7)

Uses Software

This page was built for publication: Major index distribution over permutation classes