The maximal-inversion statistic and pattern-avoiding permutations

AbstractWe define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in Sn with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in Sn is uniquely determined by its maximal-inversion set MI(π). We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns