Renzo Pinzani, Dipartimento di Sistemi e Informatica, UniversitÓ degli Studi di Firenze, Italy

From Motzkin to Catalan permutations: a ``discrete continuity''

A permutation $\pi$ contains a subsequence of type $ \tau$ iff $\pi$ contains a subsequence having all the same pairwise comparisons as $\tau$. In this talk, we consider the family of permutations $S^j$ where $j \geq 1$ is a parameter. A permutation belongs to~$S^j$ if it has length $n$, it does not contain a subsequence of type $321$ and all its subsequences of type $(j+1)(j+2)1\cdots j$ (i.e., $(j+2)(j+3)2\cdots(j+1)$ restricted on $\{1,\ldots,j+2 \}$) are of type $(j+2)1(j+3)2\cdots(j+1)$. The family of Motzkin permutations: $M_n(321,3 \bar 1 42)$ is obtained when $j=1$; the family of Catalan permutations $C_n(321)$ is obtained when $j= \infty$. Any other case, $1