Abstract : The study of patterns in permutations is currently one of the most active trends of research in combinatorics. A permutationπ is a pattern of another permutation σ (written in one-line notation) when σ contains a (non-necessarily consecutive) substring whose items are in the same relative order as the items of π. The notion of pattern in a permutation historically emerged from the problem of sorting permutations with certain devices, however the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as mathematics, computer science and biology. In this talk we will present an enumerative result about permutations avoiding a particular vincular pattern. In more detail, we will construct a single label generating tree for these permutations, showing that they grow according to powered Catalan succession rule and thus providing an explanation for a recursive formula which counts them. Finally, we will describe some combinatorial objects counted by the same sequence and provide some interesting conjectures.
Matteo Cervetti est post-doctorant au LIB, équipe Combinatoire-Réseaux, sous la direction de Vincent Vajnovszki