Pushes in permutations

Abstract

We define the push statistic on permutations and multipermutations and use this to obtain various results measuring the degree to which an arbitrary permutation deviates from sorted order. We study the distribution on permutations for the statistic recording the length of the longest push and derive an explicit expression for its first moment and generating function. Several auxiliary concepts are also investigated. These include the number of cells that are not pushed; the number of cells that coincide before and after pushing (i.e., the fixed cells of a permutation); and finally the number of groups of adjacent columns of the same height that must be reordered at some point during the pushing process.