Enumeration of polyominoes defined by combinatorial constraints
Samanta Socci · 2015
After an introductory part, where some basic definitions are provided and some motivations for the investigation are presented, the thesis is divided into two chapters. The first chapter concerns particular classes of polyominoes. After a presentation of the background and the introduction of notations, we introduce a unified approach to obtain generating functions for different statistics on directed convex polyominoes. The problem of counting k-convex polyominoes according to their semi-perimeter is a difficult problem: it is solved for k=1,2. In the last part of the first chapter we introduce two particular classes of k-convex polyominoes, namely k-parallelogram and directed k-convex polyominoes, and we solve completely the corresponding enumeration problem. The second chapter deals with permutominoes (polyominoes defined by pairs of permutations). It begins with a background and some classical enumerative results for particular permutominoes. We introduce a naturel generalization of permutominoes to any dimension and we obtain new enumerative results and other already known are recovered by a unified approach. Concerning the two dimensional case, we solve the open problem of the characterization of the pairs of permutations defining the column-convex permutominoes and we find a bijective proof for the number of directed column-convex permutominoes, that we know to be counted by factoriel numbers.