PERMUTATIONS WITH NON-DECREASING TRANSPOSITION ARRAYS AND PATTERN AVOIDANCE

PERMUTATIONS WITH NON-DECREASING TRANSPOSITION ARRAYS AND PATTERN AVOIDANCE

F. Beyene, R. Mantaci

[PDF]

Abstract

We give some results about a bijection associating each permutation with a subexcedant function (i.e., a function f : [n] ! [n] such that f(i)   i; 1   i   n). This function is related to a particular decomposition of the permutation as a product of transpositions and therefore it has been called transposition array in the literature. In particular, we identify anti-excedance positions of the permutation through its trans- position array and we give an expression of the bijection in terms of the cycle structure of the permutation. We give a characterization of a family of permutations having a non-decreasing transposition array and study length 3 pattern avoidance therein.

Keywords

Permutation; Subexcedant function; Transposition array; Pattern avoidance; Integer partition.