The study carried out along this dissertation fits into the field of enumerative combinatorics. The structures that have been investigated are families of discrete objects which display combinatorial properties. They are mainly subfamilies of well-known combinatorial structures, such as lattice paths, pattern-avoiding permutations, polyominoes (more specifically, parallelogram polyominoes), or inversion sequences. Furthermore, these combinatorial families are closely related to two famous number sequences known in the literature as the Catalan and Baxter numbers. We start defining and studying the properties of a combinatorial class whose elements appear as tilings of parallelogram polyominoes, and thus are called slicings of parallelogram polyominoes. This first combinatorial class results to be enumerated by Baxter numbers, and shows relations with Catalan and Schroder numbers. Then, we turn to two families of pattern-avoiding permutations. First, we study the semi-Baxter permutations, which reveal a natural generalisation of the Baxter numbers. Next, we deal with the strong-Baxter permutations, which are defined by restricting the Baxter numbers. Thereafter, some generalisations of Catalan numbers are presented. A first generalisation involves families of inversion sequences and lattice paths among the combinatorial structures enumerated, and is shown to be related to the sequence of Baxter numbers as well. Meanwhile, the family of fighting fish provide another generalisation of the Catalan numbers that appears to be independent from the Baxter numbers. These objects generalise the family of parallelogram polyominoes, and display remarkable probabilistic and enumerative properties. In this dissertation we tackle the problem of enumerating these combinatorial classes and exhibiting their combinatorial properties, resolving some conjectures and open problems. The methods used are rather diverse: for instance, establishing one-to-one correspondences with other structures, or combining the use of generating functions and succession rules. A succession rule is a powerful tool for counting discrete objects, and moreover it allows to generate them exhaustively. Owing to this remarkable fact succession rules, and equivalently generating trees, are largely used in our study of combinatorial structures.
Scheda prodotto non validato
Scheda prodotto in fase di analisi da parte dello staff di validazione
|Titolo:||On enumeration sequences generalising Catalan and Baxter numbers|
|Appare nelle tipologie:||8.1 Tesi Dottorato|