Bijections for Permutation Tableaux

Abstract

In this paper we propose a new bijection between permutation tableaux and permutations. This bijection shows how natural statistics on the tableaux are equidistributed to classical statistics on permutations: descents, RL-minima and pattern enumerations. We then use the bijection, and a related encoding of tableaux by words, to prove results about the enumeration of permutations with a fixed number of 31-2 patterns, and to define subclasses of permutation tableaux that are in bijection with set partitions. An extended version of this work is available in [6].

Keywords

• enumeration
• bijections
• permutations
• tableaux
• permutation patterns
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]