Major index distribution over permutation classes

Publication date 6 September 2016

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)

Describes a project that uses

Uses Software

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