Castronuovo, Niccolò
Combinatorics of pattern avoiding permutations, Dyck paths and Young tableaux
Dottorato in Matematica conseguito nel 2016 presso l'Università di Ferrara. Ciclo 29.
Relatore/i: Prof. Arrigo Bonisoli
Fulltext tesi: pdf (size: 0.88 MB) | djvu (size: 0.89 MB)
Sunto
This thesis concerns the study of some combinatorial aspects of pattern avoiding permutations, Dyck paths and Young tableaux.
We consider the pattern $\tau = 3 \, 2 \, 1$ and, more generally, a descending pattern $\tau$ of the form $k\, k-1 \ldots 3 \, 2\, 1$. Our aim is to study in details some properties of $\tau$-avoiding permutations, involutions and centrosymmetric permutations and to obtain new enumerative results about their cardinalities and about the distribution of some well-known statistics over these sets. We investigate how these permutations are related to lattice paths, in particular Dyck paths, to standar Young tableaux and to particular order relations defined over these sets.
To this end, we use classical bijections between the set $S_n(\tau)$ of $\tau$-avoiding permutations of length $n$ and the above mentioned sets as, for example, the Robinson-Schensted correspondence and the Knuth's map. By means of deep results as the Sch\"utzenberger theorem, the Schensted theorem and the Knuth equivalence relations, we can translate properties of paths and tableaux in the context of pattern avoiding permutations. We define also new maps, study in details their behaviour and their properties. We employ this material to get new results about the structure of the sets of combinatorial objects we are intereted in.