A new occurrence of Catalan numbers: cap permutations

This paper introduces a further combinatorial interpretation in terms of permutations of the well-known Catalan number sequence. The permutations we treat have been called cap permutations because of their look, and their family does not coincide with any permutation class defined by the avoidance of a pattern of length 3. Rather, they come from labeling parallelogram polyominoes in a way that resembles some operations defined on tree-like tableaux. Our main contribution is to provide a growth for such family of permutations that is ruled by an ECO operator and allows us to write a new, and non-trivial, succession rule for Catalan numbers. Then, we move on to characterize cap permutations: first, it is studied a simple subfamily of cap permutations that possesses nice properties, and then we extend them to the bigger family of all cap permutations.