Prof Simone Rinaldi

Prof Marc Jean

Prof Fédou

Daniela Battaglino

Prof Elena Barcucci

Prof Marilena Barnabei

Prof Srečko Brlek

Prof Enrica Duchi

Simone Rinaldi

Enumeration of polyominoes deined in terms of pattern avoidance or convexity constraints

Introduction

This dissertation discusses some topics and applications in combinatorics.

Combinatorics is a branch of mathematics which concerns the study of families of discrete objects which are often designed as models for real objects. The motivations for studying these objects may arise from informatics (models for data structures, analysis of algorithms, ...), but also from biology -in particular molecular and evolutive biology [START_REF] Denise | Structures aléatoires, modèles et analyse de génomes[END_REF] -from physics as in [START_REF] Baxter | Exactly solved models in statistical mechanics[END_REF] or from chemistry [START_REF] Bouvel | Combinatorial search on graphs motivated by bioinformatics applications: A brief survey[END_REF].

Combinatorialists are particularly interested in several aspects of a family of objects: its diferent characterisations, the description of its properties, the enumeration of its elements, and their generation both randomly or exhaustively, by the use of algorithms, the deinition of some relations (as for example order relations) between the elements belonging to the same family.

We have taken into consideration two remarkable subields of combinatorics, which have often been considered in the literature. These two aspects are closely related, and they give a deep insight on the nature of the combinatorial structures which are being studied: enumerative combinatorics and the study of patterns into combinatorial structures.

Enumerative Combinatorics. An unavoidable step for understanding the structure of a family of objects is certainly the capability of counting its elements. Among the many ways of describing sets of objects, the list of its elements is the basic one and convenient for inite and small sets.

For larger sets this is obviously problematic, and mathematicians developed this ield in several directions in order to "understand" the meaning of their observations. Recently in the history of mankind, enumerative combinatorics emerged as a powerful tool. As enumerative combinatorics deal with inite families of objects, it is convenient to look for bijections with inite subsets of integers, in other words counting the number of its elements in an exact way if possible, and approximate otherwise. Various problems arising from diferent ields can be solved by analysing them from a combinatorial point of view. Usually, these problems have the common feature to be represented by simple objects suitable to enumerative techniques of combinatorics. Given a family O of objects and a parameter on this family, called the size, we focus on the set O n of objects for which the value of the parameter is equal to , where is a nonnegative integer. The parameter is discriminating if, for each non negative integer , the number of objects of O n is inite. Then, we ask for the cardinality n of the set O n for each possible . Enumerative combinatorics answers to this question. Only in rare cases the answer will be a completely explicit closed formula for n , involving only well known functions, and free from summation symbols. However, a recurrence for n may be given in terms of previously calculated values k , thereby giving a simple procedure for calculating n for any ∈ N. Another approach is based on generating functions: whether we do not have a simple formula for n , we can hope to get one for the formal power series () = n n n , which is called the generating function of the family O according to the parameter . Notice that the -th coeicient of the Taylor series of () is just the term n . In some cases, once that the generating function is known, we can apply standard techniques in order to obtain the required coeicients n (see for instance [START_REF] Goulden | Combinatorial Enumeration[END_REF][START_REF] Graham | Concrete Mathematics[END_REF]). Otherwise we can obtain an asymptotic value of the coeicients through the analysis of the singularities in the generating function (see [START_REF] Flajolet | Analytic Combinatorics[END_REF]).

Several methods for the enumeration, using algebraic or analytical tools, have been developed in the last forty years. A irst general and empirical approach consists in calculating the irst terms of n and then try to deduce the sequence. For instance, one can use the book by Sloane and Ploufe [103,[START_REF] Sloane | The encyclopedia of integer sequences[END_REF] in order to compare the irst numbers of the sequence with some known sequences and try to identify n . More advanced techniques (Brak and Guttmann [START_REF] Brak | Algebraic approximants: a new method of series analysis[END_REF]) start from the irst terms of the sequence and ind an algebraic or diferential equation satisied by the generating function of the sequence itself. A more common approach consists in looking for a construction of the studied family of objects and successively translating it into a recursive relation or an equation, usually called functional equation, satisied by the generating function (). The approach to enumeration of combinatorial objects by means of generating functions has been widely used (see for instance Goulden and Jackson [START_REF] Goulden | Combinatorial Enumeration[END_REF] and Wilf [START_REF] Wilf | Generatingfunctionology[END_REF]). Another technique which has often been applied to solve combinatorial problems is the Schützenberger methodology, also called DSV [START_REF] Schützenberger | On context-free languages and push-down automata[END_REF], which can be decomposed into three steps. The irst one consists in constructing a bijection between the objects and the words of an algebraic language in such a way that for every object the parameter to the length of the words of the language. At the next step, if the language is generated by an unambiguous context-free grammar, then it is possible to translate the productions of the grammar into a system of functional equations. Finally one deduces an equation for which the generating function of the sequence n is the unique and algebraic solution (Schützenberger and Chomsky [START_REF] Chomsky | The Algebraic Theory of Context-Free Languages[END_REF]). A variant of the DSV methodology are the operator grammars (Cori and Richard [51]). These grammars take in account some cases in which the language encoding the objects is not algebraic. The theory of combinatorial species described by Joyal [START_REF]Une théorie combinatoire de séries formelles[END_REF], is the irst unifying presentation of a combinatorial theory of formal power series, where operations on species relect on the generating functions and vice versa. A comprehensive exposition can be found in Bergeron, Labelle and Leroux [START_REF] Bergeron | Theory of species and tree like structures[END_REF], with numerous examples: arithmetic operations on power series correspond to natural transformations on species, building a powerful calculus for the decomposition or substitution in species. A variant is the theory of decomposable structures (Flajolet, Salvy, and Zimmermann [START_REF] Flajolet | Lambda-upsilon-omega: The 1989 cook-book[END_REF][START_REF] Flajolet | Automatic average-case analysis of algorithms[END_REF]), which also describes recursively the objects in terms of basic operations between them. These operations are directly translated into operations between the corresponding generating functions, cutting of the passage to words. A nice presentation of this theory appears in the book of Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF]. An elegant formalization of decomposable structures was introduced in [START_REF] Dutour | Object grammars and random generation[END_REF] by Dutour and Fédou: it is based on the notion of object grammars and describe objects using very general operators.

A signiicantly diferent way of recursively describing objects appears in the ECO methodology, introduced by Barcucci, Del Lungo, Pergola, and Pinzani [START_REF] Barcucci | ECO: a methodology for the enumeration of combinatorial objects[END_REF]. In the ECO method each object is obtained from a smaller object by making some local expansions. Usually these local expansions are very regular and can be described in a simple way by a succession rule. Then a succession rule can be translated into a functional equation for the generating function. It has been shown that this method is very efective on large number of combinatorial structures. Succession rules (under the name of generating trees) had however been applied to enumeration problems, previously [START_REF] Barcucci | ECO: a methodology for the enumeration of combinatorial objects[END_REF], in [START_REF] Chung | The number of Baxter permutations[END_REF] and [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF]. We also cite [START_REF] Banderier | Generating functions for generating trees[END_REF] in which we ind an analysis of the links between the structural properties of the generating trees and the rationality, algebraicity, or transcendence of the corresponding generating function.

Another approach is to ind a bijection between the studied family of objects and another one, simpler to count. In order to have consistent enumerative results, the bijection has to preserve the size of the objects. Moreover, a bijective approach also permits a better comprehension of some properties of the studied family and to relate them to the family in bijection with it.

Patterns in combinatorial structures. A possible strategy to understand more about the nature of some combinatorial structures and which provides a diferent way to look at a combinatorial object, is to describe it by the containment or avoidance of some given substructures, which are commonly known as patterns. The concept of pattern within a combinatorial structure is central in combinatorics. It has been deeply studied for permutations, starting irst with [START_REF] Knuth | The Art of Computer Programming[END_REF]. More precisely, given a permutation we can say that contains a certain pattern if such a pattern can be seen as a sort of "subpermutation" of . If does not contain we say that avoids .

In particular, the concept of pattern containment on the set of all permutations can be seen as a partial order relation, and it was used to deine permutation classes, i.e. families of permutations downward closed under such pattern containment relation. So, every permutation class can be deined in terms of a set of avoided patterns, and the minimal of this sets is called the basis of the permutation class.

These permutation classes can then be regarded as objects to be counted.

We can ind many results concerning this research guideline in the literature.

For instance, we quote two works that collect a large part of the obtained results. The irst is the thesis of Guibert [START_REF] Guibert | Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF] and the second is the work of Kitaev and Mansour [START_REF] Kitaev | A survey on certain pattern problems[END_REF]. In the second, in addition to the list of the obtained results regarding the enumeration of set of permutations that avoid a set of patterns, the authors also take into account the study of the number of objects containing a ixed number of occurrences of a certain pattern and make an interesting parallel between the concept of pattern on the set of permutations and the concept of pattern on the set of words.

Concerning the results obtained on the enumeration of classes avoiding patterns of small size, we mention the work of Simion and Schmidt [START_REF] Simion | Restricted permutations[END_REF], in which we can ind an exhaustive study of all cases with patterns of length less than or equal to three. However, for results concerning patterns of size four we refer the reader to the work of Bóna [START_REF] Bóna | Combinatorics of permutations[END_REF]. Another remarkable work of Bóna is [START_REF] Bóna | The absence of a pattern and the occurrences of another[END_REF], in which he studies the expected number of occurrences of a given pattern in permutations that avoid another given pattern. One of the most important recent contributions is the one by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF], consisting in the proof of the so-called Stanley-Wilf conjecture, thus deining an exponential upper bound to the number of permutations avoiding any given pattern. Later, given the enormous interest in this area, not only patterns by the classical deinition were taken into consideration, but also patterns deined under the imposition of some constraints. [START_REF] Babson | Generalized permutation patterns and a classiication of the Mahonian statistics[END_REF] introduced the notion of generalised patterns, which requires that two adjacent letters in a pattern must be adjacent in the permutation. The authors introduced such patterns to classify the family of Mahonian permutation statistics, which are uniformly distributed with the number of inversions. Several results on the enumeration of permutation classes avoiding generalised patterns have been achieved. Claesson obtained the enumeration of permutations avoiding a generalised pattern of length three [START_REF] Claesson | Generalized pattern avoidance[END_REF] and the enumeration of permutations avoiding two generalised patterns of length three [START_REF] Claesson | Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns[END_REF]. Another result in terms of permutations avoiding a set of generalised patterns of length three was obtained by Bernini et al. in [START_REF] Bernini | Some statistics on permutations avoiding generalized patterns[END_REF][START_REF] Bernini | Enumerating permutations avoiding three Babson-Steingrímsson patterns[END_REF], where one can ind the enumeration of permutation avoiding set of generalised patterns as a function of its length and another parameter.

Babson and Steingrímsson

Another kind of patterns, called bivincular patterns, was introduced in [START_REF] Bousquet-Mélou | 2 + 2)free posets, ascent sequences and pattern avoiding permutations[END_REF] with the aim to increase the symmetries of the classical patterns. A bijection between permutations avoiding a particular bivincular pattern was derived, as well as several other families of combinatorial objects. Finally, we mention the mesh patterns, which were introduced in [START_REF] Brändén | Mesh patterns and the expansion of permutation statistics as sums of permutation patterns[END_REF] to generalise several varieties of permutation patterns.

Otherwise, from the algorithmic point of view, a challenging problem is to ind an eicient way to establish whether an element belongs to a permutation class C. More precisely, if we know the elements of the basis of C, and especially if the basis is inite, this problem consists in verifying if a permutation contains an element of the basis. Generally the complexity of the algorithms is high, but there are some special cases in which linear algorithms have been found, for instance in [START_REF] Knuth | The Art of Computer Programming[END_REF].

Another remarkable problem is to calculate the basis of a given permutation class. A very useful result in this direction was obtained by Albert and Atkinson in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF], namely a necessary and suicient condition to ensure that a permutation class has a inite basis.

As we have previously mentioned, some deinitions analogous to those given for permutations were provided in the context of many other combinatorial structures, such as set partitions [START_REF] Goyt | Avoidance of partitions of a three element set[END_REF][START_REF] Klazar | On abab-free and abba-free sets partitions[END_REF][START_REF] Sagan | Pattern avoidance in set partitions[END_REF], words [START_REF] Björner | The Möbius function of subword order, Invariant theory and tableaux[END_REF][START_REF] Burstein | Enumeration of Words with Forbidden Patterns[END_REF], trees [START_REF] Dairyko | Non-contiguous pattern avoidance in binary trees[END_REF][START_REF] Dotsenko | Pattern avoidance in labelled trees, Séminaire Lotharingien de Combinatoire[END_REF][START_REF] Flajolet | Analytic variations on the common subexpression problem, Automata, Languages and Programming[END_REF][START_REF] Gabriel | Pattern avoidance in ternary trees[END_REF][START_REF] Khoroshkin | On generating series of initely presented operads[END_REF][START_REF] Pudwell | Noncontiguous Pattern Containment in Binary Trees[END_REF][START_REF] Rowland | Pattern avoidance in binary trees[END_REF][START_REF] Steyaert | Patterns and pattern-matching in trees: an analysis[END_REF], and paths [START_REF] Bernini | The Dyck pattern poset[END_REF].

In the present thesis we examine the two previously quoted general issues, on a rather remarkable family of combinatorial objects, i.e. the polyominoes. These objects arise in many scientiic areas of research, for instance in combinatorics, physics, chemistry,... (more explicit details are given in Chapter 1). In particular, in this thesis, we consider under a combinatorial and an enumerative point of view families of polyominoes deined by imposing several types of constraints.

The irst type of constraint, which extends the well-known convexity constraint [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF], is the -convexity constraint, introduced by Castiglione and Restivo [START_REF] Castiglione | Reconstruction of -convex Polyominoes[END_REF]. A convex polyomino is said to be -convex if every pair of its cells can be connected by a monotone path with at most changes of direction. The problem of enumerating -convex polyominoes was solved only for the cases = 1, 2 (see [START_REF] Castiglione | Enumeration ofconvex polyominoes by rows and columns[END_REF][START_REF] Duchi | The number of -convex polyominoes[END_REF]), while the case > 2 is yet open and seems diicult to solve. To address it, we have investigated a particular subfamily of -convex polyominoes, the -parallelogram polyominoes, i.e. the -convex polyominoes that are also parallelogram.

The second type of constraint extends, in a natural way, the concept of pattern avoidance on the set of polyominoes. Since a polyomino can be represented as a binary matrix, we can say that a polyomino is a pattern of a polyomino when the binary matrix representing is a submatrix of that representing . Our attempt is to reconsider the problems treated within permutation classes for the case of pattern avoiding polyominoes.

Using this idea, we have deined a polyomino class to be a set of polyominoes which are downward closed w.r.t. the containment order. Then we have given a characterisation of some known families of polyominoes, using this new notion of pattern avoidance. This new approach also allowed us to study a new deinition of permutations that avoid submatrices, and to compare it with the classical notion of pattern avoidance.

In details, the thesis is organized as follows.

Chapter 1 provides the basic deinitions of the most important combinatorial structures considered in the thesis and contains a brief state of the art. In this work we study three main families of objects. The irst one is the family of -parallelogram polyominoes, studied from an enumerative viewpoint. The second one is the family of permutations: in particular we present the concept of patterns avoidance. The third and last family we have focused on is the one of partially ordered sets (p.o.sets or simply posets).

In Chapter 2, we deal with the problem of enumerating the subfamily of -parallelogram polyominoes. More precisely we provide an unambiguous decomposition for the family of the -parallelogram polyominoes, for any ≥ 1. Then, we also translate this decomposition into a functional equation satisied by their generating function for any . We are then able to express such a generating function in terms of the Fibonacci polynomials and thanks to this new expression we ind a bijection between the family of -parallelogram polyominoes and the family of rooted plane trees having height less than or equal to + 2.

In Chapter 3 we study the concept of pattern avoidance on sets of permutations and polyominoes both seen as matrices. In particular, this approach allows us to deine these classes of objects as the sets of elements that are downward closed under the pattern relation, that is a partial order relation. We then study the poset of polyominoes, from an algebraic and a combinatorial viewpoint. Moreover, we introduce several notions of bases, and we study the relations among these. We investigate families of polyominoes described by the avoidance of matrices, and families which are not. In this latter case, we consider some possible extensions of the concept of submatrix avoidance to be able to represent also these families.

Chapter 1

Polyominoes, permutations and posets This thesis studies the combinatorial and enumerative properties of some families of polyominoes, deined in terms of particular constraints of convexity and connectivity. Before we discuss these concepts in depth, we need to summarise the main deinitions and classiications of polyominoes. More speciically, we introduce the notions of polyomino, permutation and posets (partially ordered set). The chapter is organised as follows. In Section 1.1 we briely introduce the history of polyominoes; in Section 1.2 we discuss some of the most important families of polyominoes; in Section 1.3 we focus on permutations; Section 1.4 concludes the chapter by discussing posets.

Polyominoes

The enumeration of polyominoes on a regular lattice is one of the most studied topics in Combinatorics. The term polyomino was introduced by Golomb in 1953 during a talk at the Harvard Mathematics Club (which was published one year later [START_REF] Golomb | Checkerboards and Polyominoes[END_REF]) and popularized by Gardner in 1957 [74]. A polyomino is deined as follows.

Deinition 1. In the plane Z × Z a cell is a unit square and a polyomino is a inite connected union of cells having no cut point.

Polyominoes are deined up to translations. Polyominoes can be similarly deined in other two-dimensional lattices (e.g. triangular or honeycomb); however, in this work we will focus exclusively on the square lattice.

A column (resp. row) of a polyomino is the intersection between the polyomino and an ininite strip of cells whose centers lie on a vertical (resp. horizontal) line. A polyomino is often studied with respect to the following four parameters: area, width, height and perimeter. The area is the number of elementary cells of the polyomino; the width and height are respectively the number of columns and rows; the perimeter is the length of the polyomino's boundary.

As we already observed, polyominoes have been studied for a long time in Combinatorics, but they have also drawn the attention of physicists and chemists. The former in particular established a relationship with polyominoes by deining equivalent objects named animals [START_REF] Dhar | Equivalence of two-dimensional directed animal problem to a one-dimensional path problem[END_REF][START_REF] Hakim | Exact result for 2 directed lattice animals on a strip of inite width[END_REF], obtained by taking the center of the cells of a polyomino as shown in Figure 1.1. These models allowed to simplify the description of phenomena like phase transitions [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF] [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF]) or percolation (Hammersely, [START_REF] Hammersley | Percolation processes II: the connective constant[END_REF]). Other important problems concerned with polyominoes are the problem of covering a polyomino with rectangles [START_REF] Chaiken | Covering regions by rectangles[END_REF] or problems of tiling regions by polyominoes [START_REF] Beauquier | On translating one polyomino to tile the plane[END_REF][START_REF] Conway | Tiling with polyominoes and combinatorial group theory[END_REF].

In this work we are mostly interested in the problem enumerating polyominoes with respect to the area or perimeter. Several important results were obtained in the past in this ield. For example, in [START_REF] Klarner | Some results concerning polyominoes[END_REF] Klarner proved that, given n polyominoes of area , the limit

lim n→∞ 1 n
n tends to a growth constant such that:

3.72 < < 4.64 .
Moreover, in 1995 Conway and Guttmann [START_REF] Conway | On two-dimensional percolation[END_REF] adapted a method previously used for polygons to calculate n for ≤ 25. Further reinements by Jensen and Guttman [START_REF] Jensen | Statistics on lattice animals (polyominoes) and polygons[END_REF] and Jensen [START_REF] Jensen | Counting polyominoes: A parallel implementation for cluster computing[END_REF] allowed to reach respectively = 46 and = 56. Despite these important results, the enumeration of general polyominoes still represents an open problem whose solution is not trivial but can be simpliied, at least for certain families of polyominoes, by introducing some constraints such as convexity and directedness.

Some families of polyominoes

In this section we briely summarize the basic deinitions concerning some families of convex polyominoes. More speciically, we focus on the enumeration with respect to the number of columns and/or rows, to the semiperimeter and to the area. Given a polyomino we denote with:

1. ( ) the area of and with the corresponding variable;

2. ( ) the semi-perimeter of and with the corresponding variable;

3. ( ) the number of columns (width) of and with the corresponding variable;

4. ℎ( ) the number of rows (height) of and with the corresponding variable.

Deinition 2. A polyomino is said to be column-convex (row-convex) when its intersection with any vertical (horizontal) line is connected.

Examples of column-convex and row-convex polyominoes are provided in Figure 1.2 () and (). In [START_REF] Temperley | Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules[END_REF], Temperley proved that the generating function of column-convex polyominoes with respect to the perimeter is algebraic and established the following expression according to the number of columns and to the area:

(, ) = (1 -) 3 (1 -) 4 -(1 -) 2 (1 + ) -2 3 . (1.1)
Inspired by this work, similar results were obtained in 1964 by Klarner [START_REF] Klarner | Some results concerning polyominoes[END_REF] and in 1988 by Delest [START_REF] Delest | Genereting function for column-convex polyominoes[END_REF]. The former was able to deine the generating function of column-convex polyominoes according to the area, by means of a combinatorial interpretation of a Fredholm integral; the latter derived the expression for the generating function of column-convex polyominoes as a function of the area and the number of columns, by means of the Schützemberger methodology [START_REF] Chomsky | The Algebraic Theory of Context-Free Languages[END_REF].

In the same years, Delest [START_REF] Delest | Genereting function for column-convex polyominoes[END_REF] derived the generating function for columnconvex polyominoes according to the semi-perimeter by means of context-free languages and using the computer software for algebra MACSYMA 1 . Such function is deined as follows:

() = (1 -) ⎛ ⎜ ⎜ ⎝ 1 - 2 √ 2 3 √ 2 -  1 + +  (t 2 -6t+1)(1+t) 2 (1-t) 2 ⎞ ⎟ ⎟ ⎠ . (1.2)
In Equation (1.2), the number of column-convex polyominoes with semiperimeter +2 is the coeicient of n in (); these coeicients are an instance of sequence 005435 [103], whose irst few terms are: and they count, for example, the number of permutations avoiding 13 -2 that contain the pattern 23 -1 exactly twice, but there is no combinatorial explanation of this fact. Several studies were carried out in an attempt to improve the above formulation or to obtain a closed expression not relying on software, including: a generalisation by Lin and Chang [START_REF] Chang | Rigorous results for the number of convex polygons on the square and honeycomb lattices[END_REF]; an alternative proof by Feretić [START_REF] Feretić | A new way of counting the column-convex polyominoes by perimeter[END_REF]; an equivalent result obtained by means of Temperley's methodology and the Mathematica software2 by Brak et al. [START_REF] Brak | Exact solution of the row-convex polygon perimeter generating function[END_REF]. Deinition 3. A polyomino is convex if it is both column and row convex.

It is worth noting that the semi-perimeter of a convex polyomino is equivalent to the sum of its rows and columns (see Figure 1.2 ()).

Bousquet-Mélou derived several expressions for the generating function of convex polyominoes according to the area, the number of rows and columns, among which we cite the one obtained in collaboration with Fédou [START_REF] Bousquet-Mélou | The generating function of convex polyominoes: the resolution of a -diferential system[END_REF] and the one in [START_REF] Bousquet-Mélou | A method for the enumeration of various classes of column-convex polygons[END_REF].

The generating function for convex polyominoes indexed by semi-perimeter obtained by Delest and Viennot in 1984 [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF] is the following:

() = 2 (1 -8 + 21 2 -19 3 + 4 4 ) (1 -2)(1 -4) 2 - 2 4 (1 -4) √ 1 -4 .
(1.3)

The above expression is obtained by subtracting two series with positive terms, whose combinatorial interpretation was given by Bousquet-Mélou and Guttmann in [START_REF] Bousquet-Mélou | Enumeration of three-dimensional convex polygons[END_REF]. The closed formula for the convex polyominoes is:

n+2 = (2 + 11)4 n -4(2 + 1)  2  , (1.4)
with ≥ 0, 0 = 1 and 1 = 2. Note that this is an instance of sequence 005436 [103], whose irst few terms are: In [START_REF] Chang | Rigorous results for the number of convex polygons on the square and honeycomb lattices[END_REF], Lin and Chang derived the generating function for the number of convex polyominoes with + 1 columns and + 1 rows, where , ≥ 0. Starting from their work, Gessel [START_REF] Gessel | On the number of convex polyominoes[END_REF] was able to infer that the number of such polyominoes is:

+ + +  2 + 2 2  -2( + )  + -1  + -1  .
(1.5)

Finally, in [START_REF] Del Lungo | Enumeration of convex polyominoes using the ECO method[END_REF] the authors obtained the generating function of convex polyominoes according to the semi-perimeter using the ECO method [START_REF] Barcucci | ECO: a methodology for the enumeration of combinatorial objects[END_REF]. Deinition 4. A polyomino is said to be directed convex when every cell of can be reached from a distinguished cell, called source (usually the leftmost cell at the lowest ordinate), by a path which is contained in and uses only north and east unit steps.

An example of a directed convex polyomino is depicted in Figure 1. The number of directed convex polyominoes with semi-perimeter + 2 is equal to n-2 , where n is the central binomial coeicients:

n =  2  ,
giving an instance of sequence 000984 [103].

The enumeration with respect to the semi-perimeter of this set was irst obtained by Lin and Chang in 1988 [START_REF] Chang | Rigorous results for the number of convex polygons on the square and honeycomb lattices[END_REF] as follows:

() = 2 √ 1 -4 .
(1.6)

Furthermore, the generating function of directed convex polyominoes according to the area and the number of columns and rows, was derived by M. Bousquet-Mélou and X. G. Viennot [START_REF] Bousquet-Mélou | Empilements the segments eténumération de polyominos convexes dirigés[END_REF]:

(, , ) = 1 0 (1.7)
where

1 =  n≥1 n n () n n-1  m=0 (-1) m ( m 2 ) () m ( m+1 ) n-m-1 (1.8) and 0 =  n≥0 (-1) n n ( n+1 2 ) () n () n , (1.9)
with () n = (;

) n =  n-1 i=0 (1 -i ).

Deinitions of polyominoes according to cells

It is also possible to discriminate between diferent families of polyominoes by looking at the sets of cells , , and uniquely deined by a convex polyomino and its minimal bounding rectangle, i.e. the minimum rectangle that contains the polyomino itself (see Figure 1.4). For instance, a polyomino is directed convex when is empty i.e., the lowest leftmost vertex belongs to . We now review the most important results concerning the enumeration of the aforementioned sets of polyominoes.

(a) Ferrer diagrams (Figure 1.3 ()) provide a graphical representation of integers partitions. The generating function with respect to the area, that was already known by Euler [START_REF] Euler | Introductio in analysin ininitorum, Marcum-Michaelem Bousquet[END_REF], is:

() = 1 () ∞ , (1.10)
while the generating function according to the number of columns and rows is:

(, ) = 1 -- .
(1.11)

The generating function of the Ferrer diagrams with respect to the semiperimeter can be easily derived by setting all the variables of Equation (1.11) equal to .

(b) Stack polyominoes (Figure 1.3 ()) can be seen as a composition of two Ferrer diagrams. Their generating function according to the number of columns, rows and area, is [START_REF] Wright | Stacks[END_REF]:

(, , ) =  n≥1 n n () n-1 () n .
(1.12)

The generating function with respect to semi-perimeter is rational [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF]:

() = 2 (1 -) 1 -3 + 2 =  n≥2 2n-4 n , (1.13)
where n denotes the th number of Fibonacci. For more details on the sequence of Fibonacci 000045 the reader is referred to [103]. By deinition, the irst two numbers of the Fibonacci sequence are 0 = 0 and 1 = 1, and each subsequent number is the sum of the previous two. Consequently, their recurrence relation can be expressed as follows:

n = n-1 + n-2 with ≥ 2 .
( It is known from [START_REF] Stanley | Enumerative Combinatorics[END_REF] that the number of parallelogram polyominoes with semi-perimeter ≥ 2 is equal to the (-1)-th Catalan number. The sequence of Catalan numbers is widely used in several combinatorial problems across diverse scientiic areas, including Mathematical Physics, Computational Biology and Computer Science. This sequence of integers was introduced in the 18ℎ Century by Leonhard Euler in an attempt to determine the diferent ways to divide a polygon into triangles. The sequence is named after the Belgian mathematician Eugène Charles Catalan, who discovered the connection with the parenthesised expression of the Towers of Hanoi puzzle. Each number of the sequence is obtained as follows 3 :

n = 1 + 1  2  .
The generating function of parallelogram polyominoes with respect to the number of columns and rows is:

(, ) = 1 ---  2 + 2 -2 -2 -2 + 1 2 .
(1.15)

The corresponding function depending on the semi-perimeter is straightforwardly derived by setting all the variables equal to . It is also worth noting that the function in Equation (1.15) is algebraic. Delest and Fédou [START_REF] Delest | Attribute grammars are useful for combinatorics[END_REF] enumerated this set of polyominoes according to the area by generalising the results of Klarner and Rivest [START_REF] Klarner | Asymptotic bounds for the number of convex -ominoes[END_REF] as follows:

() = 1 0 , (1.16)
where:

1 =  n≥1 (-1) n-1 n ( n+1 2 ) () n-1 () n (1.17)
and 0 is the same of Equation (1.9).

-convex polyominoes

The studies of Castiglione and Restivo [START_REF] Castiglione | Reconstruction of -convex Polyominoes[END_REF] pushed the interest of the research community towards the characterisation of the convex polyominoes whose internal paths satisfy speciic constraints. We recall the following deinition of internal path of a polyomino. Deinition 5. A path in a polyomino is a self-avoiding sequence of unit steps of four types: north = (0, 1), south = (0, -1), east = (1, 0), and west = (-1, 0), entirely contained in the polyomino.

A path connecting two distinct cells and of the polyomino starts from the center of , and ends at the center of as shown in Figure 1.5. We say that a path is monotone if it consists only of two types of steps, as in Figure 1.5 (). Given a path = 1 . . . k , each pair of steps i i+1 such that i ̸ = i+1 , 0 < < , is called a change of direction.

In [START_REF] Castiglione | Reconstruction of -convex Polyominoes[END_REF], it has been observed that in convex polyominoes each pair of cells is connected by a monotone path; therefore, a classiication of convex polyominoes based on the number of changes of direction in the paths connecting any two cells of the polyomino was proposed. Deinition 6. A convex polyomino is said to be -convex if every pair of its cells can be connected by a monotone path with at most changes of direction. The minimal ℎ ≥ 0 such that is ℎ-convex is referred to as the convexity degree of . For = 1, we have the -convex polyominoes, where any two cells can be connected by a path with at most one direction change. Such objects can also be characterised by means of their maximal rectangles. Deinition 7. Let [, ] be a rectangular polyomino with rows and columns, for every , ≥ 1. For any polyomino we say that [, ] is a maximal rectangle in if

∀ [ ′ , ′ ], [, ] ⊆ [ ′ , ′ ] then [, ] = [ ′ , ′ ] .
Deinition 8. Two rectangles [, ] and [ ′ , ′ ] contained in a polyomino have a crossing intersection if their intersection is a non-trivial rectangle whose basis is the smallest of the two bases and whose height is the smallest of the two heights, i.e.

[, ] ∩

[ ′ , ′ ] = [min(, ′ ), min(, ′ )] .
Some examples of rectangles having non-crossing and crossing intersections are shown in Figure 1 In recent literature, several aspects of the -convex polyominoes have been studied: in [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF], it has been shown that they are a well-ordering according to the sub-picture order; in [START_REF] Castiglione | A tomographical characterization of -convex polyominoes[END_REF], -convex polyominoes are uniquely determined by their horizontal and vertical projections; inally, in [START_REF] Castiglione | Combinatorial aspects of -convex polyominoes[END_REF][START_REF] Castiglione | Enumeration ofconvex polyominoes by rows and columns[END_REF] the number n of -convex polyominoes having semi-perimeter equal to + 2 satisies the recurrence relation: with 3, 0 = 1, 1 = 2 and 2 = 7. They have a rational generating function:

n+2 = 4 n+1 -2 n , (1.18) (a) (b) (c)
() = 1 -2 + 2 1 -4 + 2 2 .
(1.19) For = 2, we have 2-convex (or -convex) polyominoes, where each pair of cells can be connected by a path with at most two direction changes. Unfortunately, -convex polyominoes do not inherit most of the combinatorial properties of -convex polyominoes. In particular, standard enumeration techniques cannot be applied to the enumeration of -convex polyominoes, even though this problem has been tackled in [START_REF] Duchi | The number of -convex polyominoes[END_REF] by means of the so-called inlation method. The authors were able to demonstrate that the generating function with respect to the semi-perimeter

() = 2 4 (1 -2) 2 () (1 -4) 2 (1 -3)(1 -) + 2 (1 -6 + 10 2 -2 3 -4 ) (1 -4)(1 -3)(1 -) , (1.20)
where () = 1/2(1 -2 -√ 1 -4), is algebraic and the sequence asymptotically grows as 4 n , that is the same growth as the whole family of the convex polyominoes.

As the solution found for the -convex polyominoes cannot be directly extended to a generic , the problem of enumerating -convex polyominoes for > 2 is yet open and diicult to solve. An attempt to study the asymptotic behaviour is proposed by Micheli and Rossin in [START_REF] Micheli | Asymptotics of -convex[END_REF]. In this thesis we contribute to this topic by enumerating the particular family of -parallelogram polyominoes.

1.3

Permutations

In this section we describe the family of permutations, which have an important role in several areas of Mathematics such as Computer Science ( [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Tarjan | Sorting using networks of queues and stacks[END_REF][START_REF] West | Permutations with forbidden subsequences and stack-sortable permutations[END_REF]) and Algebraic Geometry ( [START_REF] Lakshmibai | Criterion for smoothness of Schubert varieties in ()[END_REF]). Even though the existing literature on permutations is indeed vast, we are particularly interested on the topic of pattern avoidance (mainly of permutations but also of other families of objects). Therefore, we provide the deinitions concerning permutations that will enable us to extend the concept of permutation to the set of polyominoes in Chapter 3.

The topic of pattern-avoiding permutations (also known as restricted permutations) has raised a some interest in the last twenty years and led to remarkable results including enumerations and new bijections. One of the most important recent contributions is the one by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF], consisting in the proof of the so-called Stanley-Wilf conjecture, establishing an exponential upper bound to the number of permutations avoiding any given pattern. Moreover, the study of statistics on restricted permutations increased recently, in particular towards the introduction of new kinds of patterns.

Basic deinitions

In the sequel we denote by [] the set {1, 2, ..., } and by S n the symmetric group on []. Moreover, we use a one-line notation for a permutation ∈ S n , that is then written as = 1 2 • • • n . There are two common interpretations of the notion of permutation, which can be regarded as a word or as a bijection : [] ↦ → []. The concept of pattern avoidance stems from the irst interpretation.

A permutation of length can be represented in three diferent ways:

1. Two-lines notation: this is perhaps the most widely used method to represent a permutation and consists in organizing in the top row the numbers from 1 to in ascending order and their image in the bottom row, as shown in Figure 1.7 ().

2. One-line notation: in this case only the second row of the corresponding two-lines notation is used.

3. Graphical representation: it corresponds to the graph

() = {(, i ) : 1 ≤ ≤ } ⊆ [1, ] × [1, ] .
An example of () is displayed in Figure 1.7 (). Let be a permutation; is a ixed point of if i = and an exceedance of if i > . The number of ixed points and exceedances of are indicated with () and () respectively.

An element of a permutation that is neither a ixed point nor an exceedance, i.e. an for which i < , is called deiciency. Permutations with no ixed points are often referred to as derangements.

We say that ≤ -1 is a descent of ∈ S n if i > i+1 . Similarly, ≤ -1 is an ascent of ∈ S n if i < i+1 . The number of descents and ascents of are indicated with () and () respectively.

Given a permutation , we can deine the following subsets of points [START_REF] Bóna | Combinatorics of permutations[END_REF]:

1. the set of right-to-left minima as the set of points:

{(, i ) : i < j ∀, 1 ≤ < } ;
2. the set of right-to-left maxima as the set of points:

{(, i ) : i > j ∀, 1 ≤ < } ;
3. the set of left-to-right minima as the set of points:

{(, i ) : i < j ∀, < ≤ } ;
4. the set of left-to-right maxima as the set of points: An example of each of the sets deined above is provided in Figure 1.8.

{(, i ) : i > j ∀, 1 < ≤ } . (a) (b) (c) (d)
Let () denote the length of the longest increasing subsequence of , i.e., the largest for which there exist indexes

1 < 2 < • • • < m such that i 1 < i 2 < • • • < im .
Deine the rank of , denoted (), to be the largest such that i > for all ≤ . For example, if = 63528174, then () = 1, () = 4, () = 4 and () = 2.

We say that a permutation ∈ S n is an involution if = -1 . The set of involutions of length is indicated with I n .

Pattern avoiding permutations

The concept of permutation patterns proved useful in many branches of Mathematics literature, as supported by the several works produced in the last decades. A comprehensive overview, "Patterns in Permutations", has been proposed by Kitaev in [START_REF] Kitaev | Patterns in Permutations and Words[END_REF].

Deinition 10. Let , be two positive integers with ≤ , and let ∈ S n and ∈ S m be two permutations. We say that contains if there exist indexes In other terms, a family of permutations is a permutation class if it is an order ideal of the poset (S, S ). We remark that a permutation class is also known as a closed class, or pattern class, or simply class of permutations, see for example in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF][START_REF] Atkinson | Restricted permutations[END_REF].

1 < 2 < • • • < m such that i 1 i 2 • • • im is in the same relative order as 1 2 • • • m (that
It is a natural generalisation to consider permutations that avoid several patterns at the same time. If B ⊆ S k , ≥ 1, is any inite set of patterns, we denote by n (B), also called B-avoiding permutation, the set of permutations in S n that avoid simultaneously all the patterns in B. For example, if B = {123, 231}, then 4 (B) = {1432, 2143, 3214, 4132, 4213, 4312, 4321}. We remark that for every set B, n (B) is a permutation class.

The sets of permutations pairwise-uncomparable with respect to the order relation ( S ) are called antichains. Proposition 14. A permutation class C is a family of pattern-avoiding permutations and so it is characterised by its basis.

One can ind more details and in particular the proofs of the previous propositions in [START_REF] Bóna | Combinatorics of permutations[END_REF].

Even though the majority of permutation classes analysed in literature are characterised by inite bases, there exist permutation classes with ininite basis (e.g. the pin permutations in [START_REF] Bouvel | Quelques probèmes combinatoires et algorithmiques sur le classes de permutations[END_REF]). Deciding whether a certain permutation class is characterised by a inite or ininite basis is not an entirely solved problem; some hints on the decision criteria can be found in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF][START_REF] Atkinson | Restricted permutations and the wreath product[END_REF]. [START_REF] Richards | Ballot sequences and restricted permutations[END_REF][START_REF] Simion | Restricted permutations[END_REF][START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF].

Results on pattern avoidance

By extension, we can deine the strongly Wilf equivalence as follows.

Deinition 16. Two patterns and are strongly Wilf equivalent if they have the same distribution on the set of permutations of length for each , that is, if for each nonnegative integer the number of permutations of length with exactly occurrences of is the same as that for .

For example, = 132 is strongly Wilf equivalent to = 231, since the bijection deined by reversing a permutation turns an occurrence of into an occurrence of and conversely. On the other hand, 132 and 123 are not strongly Wilf equivalent, although they are Wilf equivalent. Furthermore, the permutation 1234 has four occurrences of 123, but there is no permutation of length 4 with four occurrences of 132.

A thoroughly investigated problem is the enumeration of elements in a given permutation class C for any integer . Recent results in this direction can be found in [START_REF] Guibert | Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF][START_REF] Kitaev | Patterns in Permutations and Words[END_REF] (respectively, 1995 and 2003). However, such an enumeration problem was already known since 1973 thanks to the work of Knuth [START_REF] Knuth | The Art of Computer Programming[END_REF], where permutations avoiding the pattern 231 were considered.

As for the case of patterns of length three, for length four we can reduce the problem by considering the seven symmetrical classes in order to obtain the sequences of enumeration. Some results relatively to these patterns appear in [START_REF] Bóna | Combinatorics of permutations[END_REF]. Only the problem of enumerating permutations avoiding 4231 (or 1324) remains unsolved.

In 1990, Stanley and Wilf conjectured that, for all classes C, there exists a constant such that for all integers the number of elements in C n = C ∩ S n is less than or equal to n . In 2004, Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF] proved the Stanley-Wilf conjecture. Before that result, Arratia [START_REF] Arratia | On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern[END_REF] showed that, being C n = n (), the conjecture was equivalent to the existence of the limit:

() = lim n→∞ n () ,
which is called the Stanley-Wilf limit for .

The Stanley-Wilf limit is 4 for all patterns of length three, which follows from the fact that the number of avoiders of any one of these is the th Catalan number n , as mentioned above. This limit is known to be 8 for the pattern 1342 (see [START_REF] Bóna | Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps[END_REF]). For the pattern 1234, the limit is 9; such limit was obtained as a special case of a result of Regev [START_REF] Regev | Asymptotic values for degrees associated with strips of Young diagrams[END_REF][START_REF] Regev | Asymptotics of young tableaux in the strip, the -sums[END_REF], who provided a formula for the asymptotic growth of the number of standard Young tableaux with at most rows. The same limit can also be derived from Gessel's general result [START_REF] Gessel | Symmetric functions and -recursiveness[END_REF] for the number of avoiders of an increasing pattern of any length. The only Wilf class of patterns of length four for which the Stanley-Wilf limit is unknown is represented by 1324, although a lower bound of 9.47 was established by Albert et al. [START_REF] Albert | On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia[END_REF]. Later, Bóna [START_REF] Bóna | A new upper bound for 1324-avoiding permutations[END_REF] was able to reine this bound by resorting to the method in [START_REF] Claesson | Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns[END_REF]; inally, Madras and Liu [START_REF] Madras | Random pattern-avoiding permutations[END_REF] estimated that the limit for the pattern1324 lies, with high likelihood, in the interval [10.71, 11.83] 4 .

Finally, considering a permutation as a bijection we can look at notions such as ixed points and exceedances. This new way to see a permutation makes relevant the study of statistics together with the notion of pattern avoidance. There is a lot of literature devoted to permutation statistics (see for example [START_REF] Ehrenborg | The excedance set of a permutation[END_REF][START_REF] Foata | Major index and inversion number of permutations[END_REF][START_REF] Garsia | Permutation statistics and partitions[END_REF][START_REF] Gessel | Counting permutations with given cycle structure and descent set[END_REF]).

1.3.3

Generalised patterns and other new patterns Babson and Steingrímsson [7] introduced the notion of generalised patterns, which requires that two adjacent letters in a pattern must be adjacent in the permutation, as shown in Figure 1.9 (). The authors introduced such patterns to classify the family of Mahonian permutation statistics, which are uniformly distributed according to the number of inversions. A generalised pattern is written as a sequence wherein two adjacent elements may or may not be separated by a dash. With this notation, we indicate a classical pattern with dashes between any two adjacent letters of the pattern (for example, 1423 as 1 -4 -2 -3). If we omit the dash between two letters, we mean that the corresponding elements of have to be adjacent. For example, in an occurrence of the pattern 12 -3 -4 in a permutation , the entries in that correspond to 1 and 2 are adjacent. The permutation = 3542617 has only one occurrence of the pattern 12 -3 -4, namely the subsequence 3567, whereas has two occurrences of the pattern 1 -2 -3 -4, namely the subsequences 3567 and 3467.

If is a generalised pattern, n () denotes the set of permutations in S n that have no occurrences of in the sense described above. Throughout this chapter, a pattern represented with no dashes will always denote a classical pattern, i.e. one with no requirement about elements being consecutive, unless otherwise speciied.

Several enumerative results on permutations classes avoiding generalised patterns have been achieved. Claesson obtained the enumeration of permutations avoiding a generalised pattern of length three [START_REF] Claesson | Generalized pattern avoidance[END_REF] and of permutations avoiding two generalised patterns of length three [START_REF] Claesson | Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns[END_REF]. Another result in terms of permutations avoiding a set of generalised patterns of length three was obtained by Bernini et al. in [START_REF] Bernini | Some statistics on permutations avoiding generalized patterns[END_REF][START_REF] Bernini | Enumerating permutations avoiding three Babson-Steingrímsson patterns[END_REF], where the enumeration of permutations avoiding sets of generalised patterns as a function of its length and another parameter.

Another kind of patterns, called bivincular patterns, was introduced by Bousquet-Mélou et al. in [START_REF] Bousquet-Mélou | 2 + 2)free posets, ascent sequences and pattern avoiding permutations[END_REF] with the aim to increase the symmetries of the classical patterns. A bijection between permutations avoiding a particular bivincular pattern was derived, as well as several other families of combinatorial objects. Deinition 17. Let = (, , ) be a triple where is a permutation of S n and and are subsets of {0}

∪ []. An occurrence of in is a subsequence = ( i 1 , • • • , i k ) such that is an occurrence of in and, with ( 1 < 2 < • • • < k ) being the set { i 1 , • • • , i k } ordered (so 1 = m im etc.
), and 0 = 0 = 0 and k+1 = k+1 = + 1,

x+1 = x + 1 ∀ ∈ and y+1 = y + 1 ∀ ∈ .
Bivincular patterns are graphically represented by graying out the corresponding columns and rows in the Cartesian plane as shown in Figure 1.9 (). Clearly, bivincular patterns (, ∅, ∅) coincide with the classical patterns, while bivincular patterns (, , ∅) coincide with the generalised patterns (hence, we refer to them as vincular in the sequel).

We now give the deinition of Mesh patterns, which were introduced in [START_REF] Brändén | Mesh patterns and the expansion of permutation statistics as sums of permutation patterns[END_REF] to generalise multiple varieties of permutation patterns. To do so, we extend the above prohibitions determined by grayed out columns and rows to graying out an arbitrary subset of squares in the diagram. Deinition 18. A mesh pattern is an ordered pair (, ), where is a permutation of S k and is a subset of the (+1) 2 unit squares in [0, +1]×[0, +1], indexed by they lower-left corners.

Thus, in an occurrence of (3142, ) in a permutation , where = {(0, 2), [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF][START_REF] Atkinson | Restricted permutations[END_REF], (4, 2)}) in Figure 1.9 (), for example, there cannot be a letter in that precedes all letters in the occurrence and lies between the values of those corresponding to the 1 and the 3. This is illustrated by the shaded square in the leftmost column. For example, in the permutation 425163, 5163 is not an occurrence of (3142, ), since 4 precedes 5 and lies between 5 and 1 in value, whereas the subsequence 4263 is an occurrence of this mesh pattern.

The reader may ind an extension of mesh patterns in [START_REF] Tenner | Mesh patterns with superluous mesh[END_REF], where are characterised all mesh patterns in which the mesh is superluous.

The results on Wilf equivalent classes have then been extended to bivincular patterns and mesh patterns. For example there is in [START_REF] Parviainen | Wilf classiication of bi-vincular permutation patterns[END_REF] the classiication of all bivincular patterns of length two and three according to the number of permutations avoiding them, and a partial classiication of mesh patterns of small length in [START_REF] Hilmarsson | Partial Wilf-classiication of small mesh patterns[END_REF]. 1.4 Partially ordered sets

In this section we recall the basic notions and the most important deinitions on partially ordered sets (posets). For a more in-depth presentation, the interested reader may consult [START_REF] Stanley | Enumerative Combinatorics[END_REF].

Deinition 19. A partially ordered set or poset is a pair = (; ≤) where is a set and ≤ is a relexive, antisymmetric, and transitive binary relation on .

is referred to as the ground set, while ≤ is a partial order on . Elements of the ground set are also called points. A poset is inite if the ground set is inite.

In our work, we consider only inite posets. Of course, the notation < in means ≤ in and ̸ = . When a poset does not change throughout some analysis, we ind convenient to abbreviate ≤ in with ≤ P . If , ∈ and either ≤ or ≤ , we say that and are comparable in ; otherwise, we say that and are uncomparable in . Deinition 23. Let = (, ≤) be a poset and let and be distinct points of . We say that " is covered by " in when < in , and there is no point ∈ for which < in and < in .

In some cases, it may be convenient to represent a poset with a diagram of the cover graph in the Euclidean plane. To do so, we choose a standard horizontal/vertical coordinate system in the plane and require that the vertical coordinate of the point corresponding to be larger than the vertical coordinate of the point corresponding to whenever covers in . Each edge in the cover graph is represented by a straight line segment which contains no point corresponding to any element in the poset other than those associated with its two endpoints. Such diagrams, called Hasse diagrams, are deined as follows.

Deinition 24. The Hasse diagram of a partially ordered set is the (directed) graph whose vertices are the elements of and whose edges are the pairs (, ) for which covers . It is usually drawn so that elements are placed higher than the elements they cover.

The Boolean algebra n is the set of subsets of [], ordered by inclusion ( ≤ means ⊆ ). Generalising n , any collection of subsets of a ixed set is a partially ordered set ordered by inclusion. In particular, Hasse diagrams are useful to visualize various properties of posets.

: → {1, 2, • • • , ||} such that < in implies () < (). Deinition 26. If = (, ≤) is a poset and ⊆ , then P ( ) = { ∈ : ∀ ∈ , > } and P ( ) = { ∈ : ∀ ∈ , < }
are called respectively the ilter and the ideal of generated by .

An ideal or ilter is principal when it is generated by a singleton. Then

D P = { P ({}) : ∈ }
and

U P = { P ({}) : ∈ }
are respectively the set of principal ideals of and the set of principal ilters of . An equivalence relation ≡ on X is built as follows:

≡ ⇐⇒ ({}) = ({}) and P ({}) = P ({}) .

Operations on partially ordered sets

Given two partially ordered sets and , we deine the following new partially ordered sets:

1. Disjoint union. + is the disjoint union set Note that the ordinal sum operation is not commutative: in ⊕ , everything in is less than everything in .

The posets that can be described by using the operations ⊕ and + starting from the single element poset (usually denoted by 1) are called series parallel orders [START_REF] Stanley | Enumerative Combinatorics[END_REF]. This set of posets has a nice characterisation in terms of subposet avoiding.

⊆ , with = { 0 , • • • , } with 0 ≤ • • • ≤ l . The quantity = || -1
is the length of the chain and is equal to the number of edges in its Hasse diagram.

If 1 denotes the single element poset, then a chain composed by elements is the poset obtained by performing the ordinal sum exactly times:

1 ⊕ 1 ⊕ • • • ⊕ 1 . Deinition 28. A chain is maximal if there exist no other chain strictly containing it.
Deinition 29. The rank of is the length of the longest chain in .

The set of all permutations forms a poset with respect to classical pattern containment. That is, a permutation is smaller than (written S ) if occurs as a pattern in . This poset is the underlying object of all studies on pattern avoidance and containment.

Chapter 2

-parallelogram polyominoes: characterisation and enumeration

In this chapter we consider the problem of enumerating a subfamily ofconvex polyominoes. We recall (see Section 1.1 for more details) that a convex polyomino is -convex if every pair of its cells can be connected by means of a monotone path, internal to the polyomino (see Figure 2.1 () and ()), and having at most direction changes. In the literature we ind some results regarding the enumeration of -convex polyominoes of given semi-perimeter, but only for small values of , precisely = 1, 2, see again Chapter 1 for more details.

As counting -convex polyominoes seems diicult, we tackle the problem of counting the set P k of -parallelogram ones. The family P k of -parallelogram polyominoes can be treated in a simpler way than -convex polyominoes, since we can use the fact that a parallelo-gram polyomino is -convex if and only if there exists at least one monotone path having at most direction changes running from the lower leftmost cell to the upper rightmost cell of the polyomino. Indeed, this property is used to partition the family P k into three subfamilies, namely the lat, right, and up -parallelogram polyominoes, and we will provide an unambiguous decomposition for each of them. Doing so we obtain the generating functions of the three families and then of -parallelogram polyominoes. An interesting fact is that, while the generating function of parallelogram polyominoes is algebraic, for every the generating function of -parallelogram polyominoes is rational. Moreover, we are able to express such generating function as continued fractions, and then in terms of the known Fibonacci polynomials.

Since we are able to express the generating function of P k in terms of Fibonacci polynomials, we have been able to ind a simpler proof, using rooted plane trees. More precisely, in [START_REF] De Bruijn | The average height of planted plane trees[END_REF] it is proved that the generating function of plane trees having height less than or equal to a ixed value can be expressed using Fibonacci polynomials and so we found a bijection between these two objects. Some of the topics of this chapter have been treated in [START_REF] Battaglino | The number ofparallelogram polyominoes[END_REF].

To our opinion, this work is a irst step towards the enumeration ofconvex polyominoes, since it is possible to apply our decomposition strategy to some larger families of -convex polyominoes (such as, for instance, directed -convex polyominoes).

Classiication and decomposition of P

Let us start by ixing some terminology which is useful in the rest of the section.

Following Deinition 5 in Section 1.1 we can represent an internal path as a sequence of cells. Deinition 30. Let be and ′ two distinct cells of a polyomino; an internal

path from to ′ , denoted AA ′ , is a sequence of distinct cells ( 1 , • • • , n ) such that 1 = , n = ′
and every two consecutive cells in this sequence are edge-connected.

Henceforth, since polyominoes are deined up to translation, we assume that the center of each cell of a polyomino corresponds to a point of the plane Z × Z, and that the center of the lower leftmost cell of the minimal bounding rectangle (denoted by m.b.r.) of a polyomino corresponds to the origin of the axes. In our case, since we work with parallelogram polyominoes, the lower leftmost cell of the m.b.r belongs to the polyomino. So, according to the respective position of the cells i and i+1 , we say that the pair ( i , i+1 ) forms:

1. a north step in the path if ( i+1 , i+1 ) = ( i , i + 1); 2. an east step in the path if ( i+1 , i+1 ) = ( i + 1, i ); 3. a west step in the path if ( i+1 , i+1 ) = ( i -1, i ); 4. a south step in the path if ( i+1 , i+1 ) = ( i , i -1).
Moreover, since our polyominoes are also convex, for obvious reasons of symmetry, we will deal only with monotone paths using steps or . Deinition 31. Let be a parallelogram polyomino and an internal path.

We call side every maximal sequence of steps of the same type into .

Remark 32. Let be a parallelogram polyomino. We denote by and the lower leftmost cell and the upper rightmost cell of , respectively. Deinition 33. The vertical (horizontal) path ( ) (respectively ℎ( )) is an internal path -if it exists-running from to , and starting with a step (respectively ), where every side has maximal length (see Figure 2.3).

From now on, in the graphical representation, the path will be represented using lines rather than cells. In practice, to represent the path we use a line joining the centers of the cells, more precisely a dashed line to represent ( ) and a solid one for ℎ( ). Observe that our deinition does not work if the irst column (resp. row) of is made of one cell, and in this case by convention ( ) and ℎ( ) coincide (Figure 2.3 ()). Henceforth, if there are no ambiguity we write (resp. ℎ) in place of ( ) (resp. ℎ( )). So, by deinition, a cell i of (or i of ℎ) could correspond to one of two possible types of direction changes, more precisely to a change e-n if

( V i + 1, V i ) / ∈ (resp. ( H i + 1, H i ) / ∈ ); -to a change n-e if ( V i , V i + 1) / ∈ (resp. ( H i , H i + 1) / ∈ ).
These two paths distinguish two types of cells into the polyomino at every direction change. So, considering ℎ(

) = ( 1 = , • • • , n = ) (respectively ( ) = ( 1 = , • • • , n = ))
, we can characterise each cell of that is not in ℎ( ) (or ( )) as follows: for every cell ∈ , / ∈ ℎ( ) (resp. / ∈ ( )), there exists an index , 1 < ≤ , such that

B < H i and B = H i or B > H i and B = H i (resp. B > V i and B = V i or B < V i and B = V i ).
We say that in the irst case is a cell of type left-top, and in the second case that is a cell of type right-bottom. The reader can observe in Figure 2.2 that the cell is an example of cell right-bottom, in fact B < V 4 and B = V 4 and that ′ is an example of cell left-top, in fact B ′ > V 8 and

B ′ = V 8 .
= ( 1 = , 2 , • • • , 20 = ).
Now, we are ready to prove the following important property.

Proposition 34. The convexity degree of a parallelogram polyomino is equal to the minimal number of direction changes required to any path running from to .

Proof. Let be a polyomino and let be the minimal number of direction changes among ℎ and . We want to prove that for every two cells of , and ′ diferent from and , exists a path AA ′ having at most direction changes. We have to take into consideration three diferent cases.

1. Both and ′ belong to (or ℎ). This case is trivial because the path running from to ′ , AA ′ , is a subpath of (or ℎ), so the number of direction changes is less than or equal to .

Only one between and ′ belongs to (or ℎ).

We can assume without loss of generality that ′ is the cell that belongs to (or ℎ) and that is a cell of type left-top. Then, there exists an index such that A > V i and A = V i (or A < H i and A = H i ), so with V i -A (or H i -A ) steps (or ) we can reach the path (or ℎ) with only one direction change but after (or ℎ) have changed its direction at least once. At this point it is easy to see that the path AA ′ has at most direction changes, the irst to reach the path (or ℎ) and the subsequent ones are those made by the subpath of (or of ℎ) to reach the cell ′ .

Neither nor ′ belong to (or ℎ).

The proof is similar to that one of the previous case.

Proposition [START_REF] Burstein | Enumeration of Words with Forbidden Patterns[END_REF]. The number of direction changes that ℎ and require to run from to may difer at most by one.

The proof is similar to the proof above and it is left to the reader. Also the following property is straightforward. Proposition 36. A polyomino is -parallelogram if and only if at least one among ( ) and ℎ( ) has at most direction changes.

We begin our study with the family P k of -parallelogram polyominoes where the convexity degree is exactly equal to ≥ 0. Then the enumeration of P k will readily follow, in fact P k = ∪ k i=1 P i . According to our deinition, P 0 is made of horizontal and vertical bars of any length.

In any given parallelogram polyomino , let ( ) (briely, ) be the earliest point in the two paths ℎ and such that the tails coincide (see Figure 2.3 (), ()). Clearly may even coincide with (see Figure 2 According to this deinition all rectangles having width and height greater than one belong to P 1 . Now we present a unique decomposition of polyominoes in P k , based on the following idea: given a polyomino , we are able to detect -using the paths ℎ and -a set of paths on the boundary of , that uniquely identify the polyomino itself.

More precisely, let be a polyomino of P k ; the cells of the path ℎ (resp. ) that correspond with a direction change have at least one edge on the boundary of . In particular if a cell corresponds to a direction change e-n (resp. n-e) then it individuates an (resp. ) step on the upper (resp. lower) path of . So we can say that the path ℎ (resp. ) determines (resp. ′ ) steps where (resp. ′ ) is equal to the number of direction changes of ℎ (resp. ) plus one. To refer to these steps we agree that the step encountered by ℎ (resp. ) for the th time is called i or i according if it is a horizontal or vertical one (see Fig. 2

.4).

We point out that if is lat all steps i and i are distinct, otherwise there may be some indices for which i = i+1 (or i = i+1 ), and this happens precisely with the steps determined after (see Fig. 2

.5 (), ()).

The case = can be seen as a degenerate case where the initial sequence of steps (resp. ) of (resp. ℎ) has length zero and we have to give an alternative deinition of these steps, see Figure 2.5 (): i) if the irst column is made of one cell, i.e. coincides with ℎ, we set 1 to be equal to the leftmost step of the upper path of , and 2 , 3 , . . . are determined as usual by ℎ; ii) if the lowest row is made of one cell, i.e. ℎ coincides with , we set 1 to be equal to the leftmost step of the lower path of , and 2 , 3 , . . . are determined as usual by .

1 X 3 X 4 X Y 1 Y 2 Y 3 Y 4 Y 5 5 X = 2 X α 4 α 3 α 2 α 1 β 1 β 4 β 3 β 2 β :
X 1 Y 1 Y 2 Y 3 Y 4 X 2 X 4 X 3 α 3 α 2 α 1 β 2 β 3 β 1 X 1 β 2 α 3 α 1 β 1 α=Ο 2 3 β=Ο 4 X=X 5 Y=Y 3 4 Y=Y 2 1 2 X=X 3 X 1 4 X=X 5 Y=Y 3 4 Y 1 Y 2 2 X=X 3 α 1 α 3 α=Ο 2 β 1 β 2 β 3 (a) (b) (c)
Figure 2.5: () A polyomino ∈ P 3 in which 1 and 1 are lat and each other path is non empty and non lat. () A polyomino ∈ P U 3 where: 3 is empty, 2 is empty and 1 is equal to a step . () A polyomino ∈ P U Our aim is now to provide a unique decomposition of the upper (resp. lower) path of a parallelogram polyomino. To do this, we adopt the following notation: given two steps on the upper (resp. lower) path of , 1 and 2 , 2 not preceding 1 , by 1 2 we denote the subpath running from the start of 1 to the end of 2 . To indicate the path 1 2 from which we have removed the initial (resp. inal) step 1 (resp. 2 ) we write 1 2 (resp. 1 2 ).

Using this convention we decompose the upper (resp. lower) path of in (possibly empty) subpaths 1 , . . . , k (resp. 1 , . . . , k ) using the following rule:

❼ 1 = k k+1 (resp. 1 = k k+1 );
❼ let us consider now the -1 (possibly empty) subpaths. For = 2 . . .

we have i = k+1-i k+2-i (resp. i = k+1-i k+2-i ).
We observe that these paths are ordered from the right to the left of . For simplicity we say that a path is lat if it is composed of steps of just one type.

Moreover, we remark that for all ≥ 1, if i (resp. i ) is lat then

| i | n = 0 (resp. | i | e = 0)
. Furthermore, from our deinition of the two paths ℎ and , it follows directly that:

Remark 38. for all ≥ 2 -the steps i and i-1 lie on cells having the same abscissa; -the steps i and i-1 lie on cells having the same ordinate.

As a consequence of this remark we can write:

| i i+1 | e = | i-1 i | e + 1
and

| i i+1 | n = | i-1 i | n + 1 , (2.1)
| i i+1 | e = | i i+1 | e + 1
and

| i i+1 | n = | i i+1 | n , (2.2)
| i i+1 | e = | i i+1 | e and | i i+1 | n = | i i+1 | n + 1 . (2.
3)

The following proposition provides a characterisation of the polyominoes of P k in terms of the paths 1 , . . . , k , 1 , . . . , k (see Figure 2.4). Proposition 39. A polyomino in P k is uniquely determined by a sequence of (possibly empty) paths ( 1 , . . . , k , 1 , . . . , k ). Moreover, these paths have to satisfy the following properties:

-| i | e = | i+1 | e , for every ̸ = 1; if = 1, then 1 is always non empty and | 1 | e = | 2 | e + 1; -| i | n = | i+1 | n , for every ̸ = 1; if = 1, then 1 is always non empty and | 1 | n = | 2 | n + 1;
-if i (resp. i ) is non empty then it starts with a step (resp. ), 1. In particular, for = 1, if 1 ( 1 ) is diferent from a unit step (resp. ), then it must start and end with a step (resp. ).

Proof. For this proof we use 2.1 in Remark 38, and the deinition of i and i . We only show how we get the irst statement of this proposition, the other ones can be proved in a similar way. Thus, for every ̸ = 1 we have:

| i | e = | k+1-i k+2-i | e = | k+1-i k+2-i | e -1 = = | k+1-(i+1) k+2-(i+1) | e = | k+1-(i+1) k+2-(i+1) | e = | i+1 | e .
If = 1 then:

| 1 | e = | k k+1 | e = | k-1 k | e + 1 = | k-1 k | e + 1 = | 2 | e + 1 .
Observe that the semi-perimeter of is obtained as the sum

| 1 |+| 2 | e + . . . + | k | e + | 1 | + | 2 | n + . . . + | k | n ,
and that follows directly from our construction.

The reader can see an example of the decomposition of a polyomino of

P U 4 in Figure 2.4.
It is then natural to encode every ∈ P k by the two sequences of paths ( 1 , . . . , k ), and ( 1 , . . . , k ) corresponding to the upper and the lower path of , respectively. For clarity sake, we need to remark the following consequence of Proposition 39: Corollary 40. Let ∈ P k be encoded by the two sequences of paths ( 1 , . . . , k ), and ( 1 , . . . , k ). Then:

-for every > 1, i ( i ) is empty if and only if i+1 ( i+1 ) is empty or lat; -1 = (resp. 1 = ) if and only if 2 ( 2 ) is empty or lat. Proof. Let us consider i = k+1-i k+2-i , for every ≥ 2. If | i | = 0 then
the step k+1-i coincides with the step k+2-i . Based on Remark 38 we can deduce that the steps k+1-(i+1) and k+2-(i+1) lie on the same cell or on cells having the same abscissa. In the irst case we have

| k+1-(i+1) k+2-(i+1) | = | i+1 | = 0. In the second case we have | i+1 | e = 0 but | k+1-(i+1) k+2-(i+1) | = | i+1 | ≥ 1, then i+1 is lat.
On the other side, let us assume that i+1 = k+1-(i+1) k+2-(i+1) is empty or lat. This means that k+1-(i+1) and k+2-(i+1) lie on the same cell or on cells having the same abscissa. From Remark 38 we know that in both cases the steps k+1-i and k+2-i coincide, and then

| k+1-i k+2-i | = | i | = 0.
The case = 1, i.e. 1 = k k+1 , difers from the one just seen, just because the inal step k+1 is included in the path 1 . For the paths i the procedure is similar. Figure 2.5 () shows the decomposition of a lat polyomino, 2.5 () shows the case in which = , so we have that 3 is empty, then 2 is empty, hence 1 is a step . Figure 2.5 () shows the case in which ℎ and coincide after the irst direction change, then 3 is lat, therefore 2 is empty and 1 is equal to a step . Now we provide another characterisation of the families of lat, up, and right polyominoes of P k which follows directly from Corollary 40 and will be used for the enumeration of these objects.

Proposition 41. Let be a polyomino in P k . We have: i) is lat if and only if 1 and 1 are lat and they have length greater than one. ii) is up (right) if and only if 1 ( 1 ) is lat and 1 ( 1 ) is non lat.

It follows from Corollary 40 that in a lat polyomino, for = 2, . . . , , i and i are non empty paths.

The reader can see examples of the statement of Proposition 41 i) in Figure 2.5 (), and of Proposition 41 ii) in Figure 2.5 () and ().

Proof. Let us proceed to prove Proposition 41 ii) (the proof of Proposition 41 i) is quite similar). Let be a polyomino belonging to P U k (resp. P R k ). From Deinition 37 is distinct from , and one among ℎ and makes + 1 direction changes. Let us assume, without loss of generality, that the path ℎ determines + 2 steps on the boundary of . More precisely, the steps determined by ℎ and are:

1 , 2 , . . . , k+1 , k+2 , 1 , 2 , . . . , k , k+1 (resp. 1 , 2 , . . . , k , k+1 , 1 , 2 , . . . , k+1 , k+2 ).
We know that the steps after coincide and in particular:

k+1 = k+2 (resp. k+1 = k+2 ),
and 1 = k k+1 (resp. 1 = k k+1 ) contains at least a step (resp. ). From k+1 = k+2 (resp. k+1 = k+2 ) and from Remark 38 we know that k and k+1 (resp. k and k+1 ) lie on cells having the same abscissa (resp. ordinate), then 1 (resp. 1 ) is lat. Moreover, the cell on which the step k+1 (resp. k+1 ) lies, is diferent from , otherwise k+2 (resp. k+2 ) would not exist against the hypothesis. For this last consideration and from Remark 38 we can deduce that the cells having k and k+1 (resp. k and k+1 ) as edges are not at the same ordinate (resp. abscissa), then

| 1 | n = | k k+1 | n ̸ = 0 (resp. | 1 | e = | k k+1 | e ̸ = 0), i.e. 1 (resp. 1 ) non lat.
On the other side, let us assume that 1 (resp. 1 ) is lat, and 1 (resp. 1 ) is not lat. We can express the hypothesis as follows:

| 1 | e = | k k+1 | e = 0 (resp. | 1 | n = | k k+1 | n = 0) , and
| 1 | n = | k k+1 | n ̸ = 0 (resp. | 1 | e = | k k+1 | e ̸ = 0 .
The irst implies that the cells having k and k+1 (resp. k and k+1 ) as edges have the same abscissa (resp. ordinate). The second one implies that the cells having k and k+1 (resp. k and k+1 ) as edges are not at the same ordinate (resp. abscissa). From Remark 38 and from the above considerations we can prove that the cells having k+1 and k+1 as edges are not at the same ordinate but they have the same abscissa, then belongs to

P U k (resp. P R k ).
As a consequence of Proposition 39, from now every polyomino ∈ P k is encoded with the two sequences:

A( ) = ( 1 , 2 , 3 , . . . , k ) , with = if is odd, otherwise = , and B( ) =  1 , 2 , 3 , . . . , k  ,
where = if and only if = . We set the dimension of A (resp. B) to be equal to

| 1 | + | 2 | n + | 3 | e + . . . (resp. | 1 | + | 2 | e + | 3 | n + . . .).
It follows that the semi-perimeter of is obtained by summing the dimensions of A and B. In particular, if = and is an up (resp. right) polyomino then

B( ) = ( 1 , ∅, . . . , ∅), (resp. A( ) = ( 1 , ∅, . . . , ∅))
where 1 (resp. 1 ) is the step (resp. ).

2.2

Enumeration of the family P This section is organized as follows: irst, we describe a method to pass from the generating function of the family P k to the generating function of P k+1 , for every > 1. Then, we provide the enumeration of the trivial cases, i.e. = 0, 1, and inally apply the inductive step to determine the generating function of P k . The enumeration of P k is readily obtained by summing all the generating functions of the families P s , ≤ .

Generating function of the family P k

The following theorem establishes a criterion for translating the decomposition of Proposition 39 into generating functions.

Theorem 42.

i) A polyomino belongs to P 2 if and only if it is obtained from a polyomino of P 1 by adding two new paths 2 and 2 , which cannot be both empty, where

| 2 | n = | 1 | n -1, and | 2 | e = | 1 | e -1.
ii) A polyomino belongs to P k , > 2, if and only if it is obtained from a polyomino of P k-1 by adding two new paths k and k , which cannot be both empty, where

| k | n = | k-1 | n and | k | e = | k-1 | e .
Proof. The reason why we have considered separately the two cases = 2 and > 2, follows directly from our decomposition and from Proposition 39. In particular, Proposition 39 states that the diference between the two cases is due to the exclusion of the inal step in the subpaths i and i , for > 2. Let us assume that is a polyomino belonging to P R 2 (the cases

∈ P U
2 and ∈ P 2 are similar). Using our decomposition we are able to identify, on the upper and the lower path of , the four subpaths 1 , 2 , 1 , and 2 . These subpaths have the properties described in Proposition 39, in particular 2 and 2 are never both empty at the same time. Furthermore

| 2 | n = | 1 | n -1 and | 2 | e = | 1 | e -1.
We denote with ′ the polyomino obtained by removing 2 and 2 from , and joining 1 and 1 in such a way that the cell of ′ has the same ordinate (resp. abscissa) of the cell with 2 (resp. 2 ) as an edge. Our construction guarantees that ′ belongs to P R 1 .

On the other side, if we have a polyomino of P R 1 and two paths 2 and 2 not both empty at the same time and such that

| 2 | n = | 1 | n -1 and | 2 | e = | 1 | e -1,
we can obtain a polyomino ′ ∈ P R 2 by adding 2 and 2 to . From Proposition 41 we know that 1 is lat and 1 is not lat, then | 1 | n ≥ 2 and as a consequence | 2 | n ≥ 1. Moreover, 2 contains at least a step by deinition, more precisely the initial step that we call 0 . We construct ′ by joining 2 and 2 in such a way that the cell of ′ has the same abscissa of the cell with 0 as an edge. Also in this case, our construction guarantees that ′ belongs to P R 2 .

We can see an example of the statement i) of Theorem 42 in Figure 2.6. In () we have a polyomino ∈ P R 2 obtained adding to ′ ∈ P R 1 a path 2 such that | 2 | e = 3 and a path 2 such that | 2 | n = 2. While, in () we have a polyomino ∈ P R 2 obtained adding to ′ ∈ P R 1 a lat path 2 , and a path 2 such that | 2 | n = 2. Let us observe that in this last case 2 could also be empty.

β 1 1 α β 1 α 2 β 2 α 2 β 2 α 2 β 2 α 2 β 2 1 α (a) (b)
Figure 2.6: () A polyomino ∈ P R 2 in which 1 is lat and 1 are lat and every other path is non empty and non lat. () A polyomino ∈ P R 2 in which 1 is equal to step .

We would like to point out that if belongs to P k , then neither k nor k can be empty or lat.

Following the statement of Theorem 42, to pass from ≥ 1 to + 1 we need to introduce the following generating functions: i) the generating function of the sequence A( ). Such a function is denoted by k (, , ) for up, and by k (, , ) for lat -parallelogram polyominoes, respectively, and, for each function, + keeps track of the dimension of A( ), and keeps track of the width of k if is odd and of the height of k if is even.

ii) the generating function of the sequence B( ). Such a function is denoted by k (, , ) for up, and by k (, , ) for lat -parallelogram polyominoes, respectively, and here + keeps track of the dimension of B( ), and the variable keeps track of the height of k if is odd and of the width of k if is even.

By Proposition 39, the generating functions U k (, , , ), R k (, , , ) and k (, , , ), of the families P U k , P R k , and P k , respectively, are obtained as follows:

U k (, , , ) = k (, , ) • k (, , ) (2.4) k (, , , ) = k (, , ) • k (, , ) (2.5) k (, , , ) = U k (, , , ) + R k (, , , ) + k (, , , ) (2.6)
Then, setting = = = , we have the generating functions according to the semi-perimeter. Since U k (, , , ) = R k (, , , ), for all , then from now on we restrict the study to the lat and the up families.

To encode the path components of the sequences A( ) and B( ) we use regular expressions,which are then used to pass to the corresponding generating functions, via standard methods, such as, for instance, the so called Schützenberger methodology [START_REF] Chomsky | The Algebraic Theory of Context-Free Languages[END_REF].

The case = 0. The family P 0 is made of horizontal and vertical bars of any length. We keep this case distinct from the others since it is not useful for the inductive step, so we simply use the variables and , which keep track of the width and the height of the polyomino, respectively. The generating function is equal to

0 (, ) = + 2 1 - + 2 1 - ,
where the term corresponds to the unit cell, and the other terms to the horizontal and vertical bars, respectively.

The case = 1. Following our decomposition and Figure 2.7, we easily obtain

1 (, , ) = 2 (1 --)(1 -) , 1 (, , ) = + 2 1 - .
We point out that we have written 1 as the sum of two terms because, according to Corollary 40, we have to treat the case where 1 is equal to a step separately from the other cases. To this aim, we set 1 (, , ) = t 2 1-t . Moreover, we have According to (2.4) and (2.5), we have

1 (, , ) = 2 1 - , 1 (, , ) = 2 1 - . t + z + z * t * y(z+y)* (
U 1 (, , , ) = 2 (1 -)(1 -)(1 --) 1 (, , , ) = 2 2 (1 -)(1 -) .
Now, according to (2.6), and setting all variables equal to , we have the generating function of 1-parallelogram polyominoes

1 () = 4 (2 -3) (1 -) 2 (1 -2)
.

The case = 2. Now we can use the inductive step, recalling that the computation of the case = 2 is slightly diferent from the other cases, as explained in Theorem 42. Using the decomposition in Figure 2.8 we calculate the generating functions We observe that the performed substitutions allow us to add the contribution of the terms 2 and 2 from the generating functions obtained for = 1. Then, using formulas (2.4), (2.5) and (2.6), and setting all variables equal to , it is straightforward to obtain the generating function according to the semi-perimeter:

2 (, , ) = • 1  , , 1
-  = 2 (1 ---+ )(1 --) 2 (, , ) = 1 - + • 1  , , 1
-  = -2 (1 --) = + 1 -- 2 (, , ) = • 1  , , 1
-  = 2 (1 -)(1 --) 2 (, , ) = • 1  , , 1
-  = 2 (1 -)(1 --) . 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 t + z + t + z + * t
2 () = 5 (2 -5 + 3 2 -3 ) (1 -) 2 (1 -2) 2 (1 -3 + 2 )
.

The case > 2. The generating functions for the case > 2 are obtained in a similar way. Here, for simplicity sake, we set k (, , ) = k (, , ) -; this trick allows to separately carry out the case 1 = . Then we have

k (, , ) = 1 - • k-1  , , 1 -  (2.7) k (, , ) = 1 - • k-1  , , 1 -  (2.8) k (, , ) = 1 - • k-1  , , 1 -  (2.9) k (, , ) = 1 - + 1 - • k-1  , , 1 -  .
(2.10)

We remark that (2.7), (2.8), (2.9) and (2.10) slightly difer from the respective formulas for = 2, according to the statement of Theorem 42.

The performed calculations and in particular the substitutions suggest that the above formulas can be also written using continued fractions [START_REF] Flajolet | Combinatorial aspects of continued fractions[END_REF], which is a less compact way, but can give a diferent combinatorial interpretation to these formulas. For example, instead of (2.7) we can write:

k (, , ) = k • ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 1 - x 1- . . . 1-x 1-z ⎫ ⎪ ⎬ ⎪ ⎭ (k -2)-times ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 2 • 1 1 - x 1- . . . 1-x 1-z ⎫ ⎪ ⎬ ⎪ ⎭ (k -1)-times
.

The other expressions are quite similar.

2.2.2

A formula for the number of -parallelograms

The formulas found in the previous section allow us in principle to obtain an expression for the generating function of P k (), for all > 2. However, the continued fractions representation suggests to express the generating function of the sequences k , k , k and k as a quotient of polynomials, using the Fibonacci polynomials.

First we need to give the following recurrence relation: Deinition 43.

⎧ ⎨ ⎩ 0 (, ) = 1 (, ) = 1 2 (, ) = 1 - k (, ) = k-1 (, ) -k-2 (, ) .
Remark 44. Let us observe that the use of three initial conditions instead of two is required to obtain the desired sequence 0 , 1 , • • • . In particular setting only 0 = 1 = 1 we would have 2 = 1 -instead of 1 -and we also need of the term 0 because it appears in the inal expression of the generating function.

These polynomials are already known as Fibonacci polynomials [START_REF] De Bruijn | The average height of planted plane trees[END_REF] Remark 45. To avoid any confusion, let us recall that Fibonacci polynomials are perhaps more often seen as

 0 () = 1 () = 1 k () = k-1 () + k-2 () .
In the sequel, unless otherwise speciied, we write k (, ) for k . Notice that k (-1, -1) gives the th Fibonacci number.

The closed formula for k is obtained by using standard methods:

k = () k+1 -() k+1 √ 1 -4 ,
where () and () are the solutions of the equation 2 -+ = 0, i.e.

()

=  1- √ 1-4x 2  and () =  1+ √ 1-4x 2
 . These polynomials have been widely studied, and have several combinatorial properties. Below we list just a few of these properties, the ones that are necessary to provide alternative expressions for formulas k , k , k and k .

Proposition 46. For any ≥ 1 the following relations hold

2 k -2 k-1 = 2k k+1 -k-1 = F 2k+1 F k 2 k-1 = k+1 + k k+2 F k F k+1 = 1 1- x 1- . . . 1-x 1-z            (k -1)-times
.

Proof. These identities are obtained by performing standard computation, and using the following:

⎧ ⎨ ⎩ () + () = 1 () -() = √ 1 -4 () • () = .
Thus, we only show how we get the irst equality, then the other ones can be proved in a similar way. For brevity sake we write instead of () and instead of ().

2 k -2 k-1 = (b k+1 -a k+1 ) 2 ( √ 1-4x) 2 -• (b k+1 -a k+1 ) 2 ( √ 1-4x) 2 = = b 2k+2 +a 2k+2 -2b k+1 +2xb k a k -xb 2k -xa 2k 1-4x = = b 2k+1 (b-a)-a 2k+1 (b-a) 1-4x = = b-a √ 1-4x • b 2k+1 -a 2k+1 √ 1-4x = 2k .
In order to express the functions k , k , k , and k in terms of the Fibonacci polynomials we need to state the following lemma:

Lemma 47. For every ≥ 1 k  , 1 -  = k+1 (, ) 1 - .
Proof. The proof is easily obtained by induction.

Basis: We show that the statement holds for = 1.

1  , 1 -  = 1 = 1 - 1 - = 2 (, ) 1 - .
Inductive: Assume that Lemma 47 holds for -1. Let us show that it holds also for , i.e.

k  , 1 -  = k+1 (, ) 1 - .
Using the deinition of k (, ) the left-hand side of the above equation can be rewritten as

k-1  , 1 -  -k-2  , 1 -  .
Now, using the induction hypothesis, we obtain:

k (, ) 1 - - k-1 (, ) 1 - = k (, ) -k-1 (, ) 1 - = k+1 (, ) 1 - .
Letting = , we can write 1 (, ) = z) . Now, iterating Formula (2.7), and using Lemma 47, we obtain

xz 2 F 2 (x,z)F 3 (x,
k (, ) = k+1 k+1 (, ) k+2 (, )
.

Performing the same calculations on the other functions we obtain:

k (, ) = k k+1 (, ) k (, ) = k (, ) = k k (, ) • k+1 (, )
.

From these new expressions for the functions k , k , k , and k , by setting all variables equal to , we can calculate the generating function of the family P k in an easier way:

k () = 2 k (, ) k (, ) + ( k ) 2 (, ) k () = 2 k+3 k 2 k+1 k+2 + 2k+2 2 k k+1
.

Then we have the following:

Theorem 48. The generating function of -parallelogram polyominoes P k is given by

k () = k  n=0 n () = 2 •  k+1 k+2  2 -2 •  k+1 k+2 - k k+1  2 .
As an example, for the irst values of we have:

0 () = x 2 (1+x) 1-x 1 () = x 2 (1-2x+2x 2 ) (-1+x) 2 (1-2x) 2 () = x 2 (1-x)(1-4x+4x 2 +x 3 ) (1-2x) 2 (1-3x+x 2 ) 3 () = x 2 (1-2x)(1-6x+11x 2 -6x 3 +2x 4 ) (1-x)(1-3x)(1-3x+x 2 ) 2
The coeicients of 1 are an instance of sequence 000247 [103], whose irst few terms are: As one would expect we have the following corollary:

Corollary 49. Let () = 1- √ 1-4x 2x
be the generating function of Catalan numbers, we have:

lim k→∞ k () = () .
Proof. We know that () satisies the equation () = 1 + 2 (), and ()() = , () = (), so we can write

k = 1 -k+1 2(k+1) () k+1 () √ 1 -4 .
Now we can prove the following statements:

lim k→∞ k k+1 = () ,
(2.11)

lim k→∞ k 2 k+1 2 = () -1 ,
(2.12)

lim k→∞ k k+2 = () -1 .
(2.13)

Using the previous identities we can write in an alternative way the argument of Limit 2.11

lim k→∞ 1-x k+1 C 2(k+1) (x) C k+1 (x) √ 1-4x 1-x k+2 C 2(k+2) (x) C k+2 (x) √ 1-4x = lim k→∞ () • 1 -k+1 2(k+1) () 1 -k+2 2(k+2) () ,
and so Equation 2.11 holds. In a similar way one obtains Equations 2.12 and 2.13. From Theorem 48, and using the above results, we obtain the desired result.

2.3

A bijective proof for the number of

-parallelogram polyominoes

In [START_REF] De Bruijn | The average height of planted plane trees[END_REF] it is proved that • F k F k+1 is the generating function of rooted plane trees having height less than or equal to +1. Hence, the generating function obtained for k () in (2.11) can be expressed as the diference between the generating functions of pairs of rooted plane trees having height at most +2, and pairs of rooted plane trees having height exactly equal to + 2.

We recall that a rooted plane tree is a rooted tree embedded in the plane so that the relative order of subtrees at each branch is part of its structure. Henceforth we shall say simply tree instead of rooted plane tree. Let be a tree, the height of , denoted by | |, is the number of nodes on a maximal simple path starting at the root. Figure 2.9 depicts the seven trees having exactly 6 nodes and height equal to 5. Our aim is now proceed trying to provide a combinatorial explanation to this fact, by establishing a bijective correspondence between -parallelogram polyominoes and trees having height less than or equal to a ixed value; irst we show how to build the tree associated with a given parallelogram polyomino and then we show what is the link between the convexity degree of and the corresponding tree.

2.3.1

From parallelogram polyominoes to rooted plane trees In the following is presented the construction of the bijection based on [START_REF] Aval | Combinatorics of non-ambiguous trees[END_REF].

Given a parallelogram polyomino we begin by labelling:

-each step of the upper path of with the integer numbers from 1 to the width of and moving from right to left;

-each step of the lower path of with marked integer numbers from 1 to the height of and moving from top to bottom.

The labelling is depicted in Figure 2.10 (). Observe that the labelling of a polyomino is uniquely determined by construction and that every label (resp. ) identiies a column (resp. a row) into . Let be a parallelogram polyomino. We denote by [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF] the array of labels (except for the label 1), which are an edge of a cell belonging to the row determined by 1. For every label ≥ 1 (resp. ≥ 2) we take into consideration the column (resp. the row) determined by it. We denote by () (resp. ()) the array of labels which corresponds to an edge of a cell belonging to this column (resp. row). Note that each label in the array () (resp. ()) corresponds to a step (resp. ) on the lower (resp. upper) path of .

For instance in Figure 2.10 we have: 6) and (5) = [START_REF] Barcucci | ECO: a methodology for the enumeration of combinatorial objects[END_REF][START_REF] Bassino | Enumeration of Pin-Permutations[END_REF][START_REF] Battaglino | Permutation classes and polyomino classes with excluded submatrices[END_REF] .

(7) = (5,
At this point we are able to construct the corresponding tree called ( ) as follows (see Figure 2.10 ()):

-we associate to any label of one node in ( ), in particular the root will be the node labelled with 1;

-the children of the node 1 are exactly the ones labelled with the labels in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF], ordered from left to right. In general the children of a node with label (resp. ) are exactly the ones labelled with the labels () (resp. ()), ordered from left to right.

Let P n and T n be respectively the sets of parallelogram polyominoes with semi-perimeter and of trees with nodes. The following proposition holds.

Proposition 50. The function T which maps a polyomino ∈ P n into ( ) is a bijection.

Proof. The injectivity directly follows from our construction. T is also surjective. The number of nodes of ( ) is equal to the semi-perimeter of . In fact, the number of nodes is equal to the number of labels, that is, equal to the sum of steps on the upper path and of steps on the lower path of . Since we are considering parallelogram polyominoes which are irst of all convex polyominoes, such a sum corresponds exactly to the semi-perimeter of . Therefore, given a tree we build the corresponding parallelogram polyomino, denoted by ( ), in the following way. We start from a ixed point of the plane and we proceed to construct the upper path and the lower path of ( ) in two diferent phases:

1. we start with a step which corresponds to the root. For every node labelled with , with ≥ 1, we draw as many steps as the number of its children and one step .

2. For every node labelled with , with ≥ 1, we draw as many steps as the number of its children and one step .

This construction guarantees that the upper path and the lower path of ( ) have the same length and they are disjoint except at their common endpoints, otherwise would not be a tree.

Moreover, observe that:

-in every tree obtained by our correspondence, the root labelled with 1 has at least the node labelled with 1 as a child;

-the nodes labelled with and are at alternate levels;

-the labelling is uniquely determined as in the case of parallelogram polyominoes. So, from now on, when we deal with trees, we mean labelled trees.

2.3.2

The link between the -convexity degree and the height of a tree

We want to highlight that in our construction given a polyomino and its associated tree ( ), the node with the largest label (resp. ) corresponds to a cell in in which the path (resp. ℎ) takes the irst direction change. Let be a tree having height equal to . According to the parity of we deine two sequences of nodes.

❼ case (odd):

we call T (resp. ℎ T ) the sequence of nodes of the simple path starting from the rightmost node at the height (resp. -1) and ending when reaching either the node 1 or 1.

❼ case (even):

we call ℎ T (resp. T ) the sequence of nodes of the simple path starting from the rightmost node at the height (resp. -1) and ending when reaching either the node 1 or 1.

For example, let be the tree in Figure 2.10 (). | | is equal to 6, so we are in the even case, and following the previous deinition we have ℎ T = (8, 10, 5, 7, 3, 1) and T = [START_REF] Battaglino | Permutation classes and polyomino classes with excluded submatrices[END_REF][START_REF] Atkinson | Restricted permutations and the wreath product[END_REF][START_REF] Babson | Generalized permutation patterns and a classiication of the Mahonian statistics[END_REF][START_REF] Arratia | On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern[END_REF][START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF].

The sequences T and ℎ t have an important property: the nodes of ℎ T (resp. T ) correspond to the cells of ( ) in which ℎ (resp. ) makes a direction change. Hence, there are exactly the (resp. ′ ) steps determined by the path ℎ (resp. ) that we denoted, in our decomposition 2.1, i or i depending on whether it is a horizontal or vertical one (see Fig. 2.4). Thus, the convexity degree of ( ) is equal to the minimal number of nodes among the two paths ℎ T (P ) and T (P ) minus one.

In general, the height of is closely related to the number of nodes of ℎ T and T and by deinition ℎ T and T can be referred to the node 1 or 1. Then, the height of is equal to the maximal number of nodes among the two paths plus one, and the following proposition holds. Proposition 51. Let be a polyomino in P k . The height of ( ) is less than or equal to + 3.

The proof follows directly from our construction.

As we said before, Equation (2.11) suggests to consider a pair of trees. Consequently, we identify every tree ( ) with a pair of trees 1 and 2 , denoted by ( 1 , 2 ). They are the ones obtained taking the subtree of ( ) having the node labelled with 1 as a root, and the remaining subtree of ( ) having the node labelled with 1 as a root, respectively. Formally: Let 1 and 2 be a pair of trees. We denote with = ( 1 , 2 ) the tree obtained putting 1 as a left subtree of 2 . In general the pairs = ( 1 , 2 ) and ′ = ( 2 , 1 )

correspond to distinct trees. Proposition 52. The number of -parallelogram polyominoes is equal to the number of pairs of trees having height less than or equal to + 2 minus the number of pairs of trees having height equal to + 2.

Proof. Let be a polyomino of P k with ≥ 0. We start with the assumption that is even (for the odd case the procedure is similar). Based on Proposition 51 we have | ( )| ≤ + 3. According to Deinition 2.11 in general for each tree = ( 1 , 2 ) with | | ≤ + 3 we have:

| 1 | ≤ + 2 and | 2 | ≤ + 3 .
The set P k contains all the polyominoes having convexity degree less than or equal to . We restrict our analysis by assuming that has convexity degree exactly equal to . Hence

+ 1 ≤ | 1 | ≤ + 2 and + 1 ≤ | 2 | ≤ + 3 .
Given the above condition and previous considerations, we have to consider only these four cases:

1. | 1 | ≤ + 2 and | 2 | ≤ + 3.
We take into account the borderline case

| 1 | = + 2, | 2 | = + 3, and | ( )| = |( 1 , 2 )| = + 3 (even).
Both nodes with the greatest labels and belong to 2 . Then the number of nodes of ℎ T (P ) is equal to + 3 and the number of nodes of T (P ) is equal to + 2. As we said before, the convexity degree of is equal to the minimal number of nodes among ℎ T (P ) and T (P ) minus one. For this case the convexity degree of is equal to

min( + 3, + 2) -1 = + 1
consequently belongs to P k+1 and not to P k against the hypothesis. To illustrate this case see Figure 2.12 where = 3,

| 1 | = 5, | 2 | = 6, | | = |( 1 , 2 )| = 6
, and ℎ T = (16, 11, 10, 7, 4, 1) and T = (11, 10, 7, 4, 1) .

So, the convexity degree of ( ) is equal to min(6, 5) -1 = 4 = + 1 (see Figure 2.13).

|

1 | ≤ + 2 and | 2 | ≤ + 2.
Here, the borderline case is

| 1 | = + 2, | 2 | = + 2, and | ( )| = |( 1 , 2 )| = +3.
Since the height of is even we deduce that the node with the greatest label belongs to 1 . Then, the number of nodes of ℎ T is equal to + 3. The node with the greatest label belongs to 2 , and the number of nodes of T is equal to + 2. As we said before, the convexity degree of is equal to the minimal number of nodes among ℎ T and T minus one, this means min( + 3, + 2) -1 = + 1

and so belongs to P k+1 and not to P k against the hypothesis. An example of case 2. is depicted in Figure 2.14 and in Figure 2.15.

3. | 1 | ≤ + 1 and | 2 | ≤ + 2.
As in the previous cases, we analyse the borderline situation

| 1 | = + 1, | 2 | = + 2, and | | = |( 1 , 2 )| = + 2.
Both nodes with the greatest labels and belong to 1 . It is possible to inspect such a situation in Figure 2.16. According to the parity of | ( )| (odd), we know that the number of nodes of T is equal to + 2 and the number of nodes of ℎ T is equal to + 1. The convexity degree of is equal to the minimal number of nodes among ℎ T and T minus one, then min( + 1, + 2) -1 = , so belongs to P k (see Figure 2.17 We know that both nodes with the greatest label and the greatest label belong to 1 . Since the height of is even the number of nodes of ℎ T is equal to + 2, and the number of nodes of T is equal to + 1. As before, the convexity degree of is equal to the minimal number of nodes among ℎ T and T minus one min( + 2, + 1) -1 = so, as in the previous case, belongs to P k (see Figure 2.19).

Therefore, we have shown that in cases 3. and 4. is a -parallelogram polyomino according to the hypothesis. While in cases 1. and 2. is a parallelogram polyomino which is exactly ( + 1)-parallelogram and this is a contradiction. We conclude that the number of polyominoes in k () will be given by considering only the cases 3. and 4.. Then we have the claim. Given a tree = ( 1 , 2 ) we can deduce some properties of ( ).

Let us consider T = ( 1 , • • • , j ) and ℎ T = (ℎ 1 , • • • , ℎ j ′ ), where = ′ or | -′ | = 1.
We remark that 1 and ℎ 1 are equal to the greatest label of type and , respectively. Based on and ′ we have:

-= ′ then ( ) is a lat -parallelogram polyomino;
-̸ = ′ and odd (resp. ′ is even) then ( ) is an up -parallelogram polyomino; -̸ = ′ and even (resp. ′ is odd) then ( ) is a right -parallelogram polyomino.

Suppose that we are in the second or in the third case, in particular when = ′ + 1 (resp. ′ = + 1). There exists an index , 2 ≤ ≤ (resp. 2 ≤ ≤ ′ ), such that starting from the th and the ( -1)th element of T and ℎ T (resp. of ℎ T and T ), respectively, the sequences coincide. In particular, the node with the label c-1 (resp. ℎ c-1 ) corresponds to the cell (deined in Section 2.1) in ( ).

For example if we consider that is the tree in Figure 2.10 (), we have T = (11, 5, 7, 3, 1) and ℎ T = (8, 10, 5, 7, 3, 1) then = 5 and ′ = 6. Starting from the second and the third element of T and ℎ T respectively, the sequences coincide. As a consequence, the node with the label ℎ T (2) = 10 corresponds in ( ) to the cell , as we can see in Figure 2.10 (). Therefore, we are in the case where is odd then ( ) is an up -parallelogram polyomino.

Further work

We have extended some of our previous results for the family of -parallelogram polyominoes to another remarkable subfamily of convex polyominoes, theconvex polyominoes which are also directed polyominoes. We call them for short -directed polyominoes, denoted by D k .

More precisely, we were able to apply our decomposition, explained in Section 2.1, to the set of -directed polyominoes. This is due mainly to the fact that we have an analogous of Proposition 34 holding also for this new considered family. Indeed, to ind out the convexity degree of a directed convex polyomino it is suicient to check the direction changes required to any path running from the source to the "furthest cells" of . Then, giving a -directed polyomino , we can provide a deinition of two paths ℎ( ) and ( ), which is analogous to that of Deinition 33. These two paths -as shown in Figure 2.20 -identify some vertical/horizontal steps on the boundary of . These steps are called, analogously to the case of -parallelogram polyominoes (see 2.1), i or i depending on whether it is a horizontal or vertical one. Furthermore, we can apply the same decomposition technique, which is graphically shown in Figure 2.20.

Remark 53. Let be a -directed polyomino. We can prove that the cells of which require the maximal number of direction changes to be reached are the ones on the right of the step k and over the step k . These cells are the ones shaded in Figure 2.20. The three families have to be enumerated separately. Then the generating function of D k can be obtained by summing the three generating functions.

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 X 1 X 2 X 3 Y 3 Y 1 α 1 β 1 β 2 β 1 β 2 α 2 α 1 X 1 X 2 X 3 Y 3 Y 2 Y 1 α 1 α 2 β 2 β 1 β 2 β 1 α 1 α 2 X 3 Y 3 Y 2 Y 1 X 1 X 2 X 1 X 2 Y 1 Y 2 X 3 Y 3 α 2 Y 2 (b) (a) (c) (d)
Unfortunately, unlike the case of -parallelogram polyominoes, each of these families has to be split in several subfamilies in order to consider all possible conigurations which can occur. It follows that the obtained formulas have a rather complex expression. In particular, we have not been able to express them using the Fibonacci polynomials, as it was for parallelogram polyominoes.

Another problem, that remains to be explored, is to determine the asymptotic behaviour of the family of -parallelogram polyominoes. Starting from our expression of the generating function, given in Theorem 48, and basing on some results from [START_REF] Flajolet | Analytic Combinatorics[END_REF], we have conidence that it is possible to obtain a general solution for all .

Chapter 3 Permutation and polyomino classes

The concept of a pattern within a combinatorial structure plays an important role in combinatorics. It has been deeply studied for permutations, starting irst with [START_REF] Knuth | The Art of Computer Programming[END_REF]. Analogous deinitions were provided in the context of many other structures, such as set partitions [START_REF] Goyt | Avoidance of partitions of a three element set[END_REF][START_REF] Klazar | On abab-free and abba-free sets partitions[END_REF][START_REF] Sagan | Pattern avoidance in set partitions[END_REF], words [START_REF] Björner | The Möbius function of subword order, Invariant theory and tableaux[END_REF][START_REF] Burstein | Enumeration of Words with Forbidden Patterns[END_REF], trees [START_REF] Dairyko | Non-contiguous pattern avoidance in binary trees[END_REF][START_REF] Rowland | Pattern avoidance in binary trees[END_REF], and paths [START_REF] Bernini | The Dyck pattern poset[END_REF], see Section 1.3.

In the following section we recall some important deinitions that allow to better understand the work described in this chapter. Moreover, we have already studied some of the topics discussed below in [START_REF] Battaglino | Permutation classes and polyomino classes with excluded submatrices[END_REF].

Permutation classes and polyomino classes

The relation of containment S is a partial order relation on the set S of all permutations. Moreover, properties of the poset (S, S ) have been described in the literature [START_REF] Steingrìmsson | The Möbius Function of the Permutation Pattern Poset[END_REF]. We recall some of the most well-known here: (S, S ) is a well founded poset (i.e. it does not contain ininite descending chains), but it is not well ordered, since it contains ininite antichains (i.e. ininite sets of pairwise uncomparable elements); moreover, it is a graded poset (the rank function being the size of the permutations).

Deinition 54. A permutation class is a set of permutations C that is downward closed for

S : for all ∈ C, if S , then ∈ C.
We remark that a permutation class is also known as a closed class, or pattern class, or simply class of permutations, see for example in [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF][START_REF] Atkinson | Restricted permutations[END_REF].

For any set B of permutations, denoting S (B) the set of all permutations that avoid every pattern in B, we have that S (B) is a permutation class. The converse statement is also true. Proposition 55. For every permutation class C, there is a unique antichain B such that C = S (B). The set B consists of all minimal permutations (in the sense of S ) that do not belong to C.

The reader can ind more details about this proposition in Section 1.3.2. In the usual terminology, B is called the basis of C. Here, we shall rather call B the permutation-basis (or -basis for short), to distinguish it from other kinds of bases that we introduce later.

Notice that because (S, S ) contains ininite antichains, the basis of a permutation class may be ininite, as in the case of pin permutations introduced in [START_REF] Bassino | Enumeration of Pin-Permutations[END_REF].

Actually, Proposition 55 does not hold only for permutation classes, but for all well-founded posets, which are important for our purpose. First of all we recall the notion of well-founded poset:

Deinition 56. A poset (X, ) is called well-founded, if X has no ininite descending chain { 0 , 1 , • • • , n , • • • } with 0 > 1 > • • • > n > • • • .
Proposition 57. For any well-founded poset (X, ), for any subset C of X that is downward-closed for , there exists a unique antichain B of X such that C = X (B) = { ∈ X : for all ∈ B, does not hold}. The set B consists of all minimal elements of X (in the sense of ) that do not belong to C.

Proof. Let C be a subset of X that is downward closed for . The complement X ∖ C of C with respect to X is upward closed for . Let us deine B to be the set of minimal elements of

X ∖ C: B = { ∈ X ∖ C | ∀ ∈ X ∖ C, if then = }.
This is equivalent to characterising B as the set of minimal elements of X (in the sense of ) that do not belong to C. Because X is well-founded, we have that ∈ X ∖ C if and only if ∃ ∈ B such that . By contraposition, we immediately get that C = X (B). In addition, by minimality, the elements of B are pairwise uncomparable, so that B is indeed an antichain.

To further ensure uniqueness, it is enough to notice that for two diferent antichains B and B ′ the sets C = X (B) and C ′ = X (B ′ ) are also diferent.

Permutation classes have been extensively studied from the Seventies until now, see Section 1.3. Nowadays, the research on permutation classes is being developed into several directions. One of them is to state analogous of Deinition 10 (see Section 1.3.2) for other combinatorial objects, and to ind out which of the nice properties of permutation classes, or of the order S , or of the associated poset (S, S ), . . . extend to a more general setting. The work presented here goes into this direction, and it is speciically focused on matrix patterns in polyominoes and in permutations. Let M be the family of binary matrices (i.e. with entries in {0, 1}). We denote by the usual submatrix order on M, i.e. ′ if ′ may be obtained from by deleting any collection of rows and/or columns.

Whenever S , we have that π is a submatrix of σ . Notice however that not all submatrices of σ are permutation matrices, and we discuss in Subsection 3.2 some consequences of this fact in the study of permutation classes.

Another consequence of the matrix representation of permutations is that we may rephrase the deinition of classes as follows: a set C of permutations is a class if and only if, for every ∈ C, every submatrix of which is a permutation is in C. This does not say much by itself, but it allows to deine analogues of permutation classes for other combinatorial objects that are naturally represented by matrices, like polyominoes.

Polyominoes and polyomino classes

A polyomino may be represented by a binary matrix whose dimensions are those of the minimal bounding rectangle of : drawing in the positive quarter plane, in the unique way that has contacts with both axes, an entry (, ) of is equal to

1 if the unit square [ -1, ] × [ -1, ] of Z × Z
is a cell of , 0 otherwise (see Figure 3.2). Notice that, according to this deinition, in a matrix representing a polyomino the irst (resp. the last) row (resp. column) contains at least a 1. Let us denote by P the set of polyominoes, viewed as binary matrices as explained above. We can consider the restriction of the submatrix order on P. This deines the poset (P, P ) and the pattern order between polyominoes: a polyomino is a pattern of a polyomino (which we denote P ) when the binary matrix representing is a submatrix of that representing .

0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 (a) (b)
We point out that the order P has already been studied in [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF] under the name of subpicture order. The main point of focus of [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF] is the family ofconvex polyominoes deined by the same authors in [START_REF] Castiglione | Reconstruction of -convex Polyominoes[END_REF]. But [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF] also proves that P is not a partial well-order, since (P, P ) contains ininite antichains. We remark also that (P, P ) is a graded poset (the rank function being the semi-perimeter of the bounding box of the polyominoes).

This implies in particular that (P, P ) is well-founded.

Notice that these properties are shared with the poset (S, S ) of permutations. This allows to introduce a natural analogue of permutation classes for polyominoes: Deinition 58. A polyomino class is a set of polyominoes C that is downward closed for P : for all polyominoes and , if ∈ C and P , then

∈ C.
The reader can exercise in inding simple examples of polyomino classes, such as, for instance: the family of polyominoes having at most three columns, the family of polyominoes having a rectangular shape, or the whole family of polyominoes. Some of the most famous families of polyominoes are indeed polyomino classes, like the convex polyominoes and the -convex polyominoes. This will be investigated more precisely in Section 3.5. However, there are also well-known families of polyominoes which are not polyomino classes, like: the family of polyominoes having a square shape, the family of polyominoes having exactly three columns, or the family of polyominoes with no holes (i.e. polyominoes whose boundary is a simple path). Figure 3.3 shows that a polyomino in this family may contain a polyomino with a hole. Similarly to the case of permutations, for any set B of polyominoes, let us denote by P (B) the set of all polyominoes that do not contain any element of B as a pattern. Every such set P (B) of polyominoes deined by pattern avoidance is a polyomino class. Conversely, as in the case of permutation classes, every polyomino class may be characterised in this way. Proposition 59. For every polyomino class C, there is a unique antichain B such that C = P (B). The set B consists of all minimal polyominoes (in the sense of P ) that do not belong to C.

1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 (a) (b)
Proof. Follows immediately from Proposition 57 and the fact that (P, P ) is a well-founded poset.

As in the case of permutations we call B the polyomino-basis (or -basis for short), to distinguish it from other kinds of bases.

Recall that (P, P ) contains ininite antichains [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF], then there are polyomino classes with ininite -basis. We will show an example of a polyomino class with an ininite -basis in Proposition 86. However, we are not aware of natural polyomino classes whose -basis is ininite.

3.2

Classes with excluded sub-matrices

We have noticed in Subsection 3.1.1 that not all submatrices of permutation matrices are themselves permutation matrices . More precisely:

Remark 60. The submatrices of permutation matrices are exactly those that contain at most one 1 in each row and each column. We call such matrices quasi-permutation matrices in the rest of this section.

For polyominoes, it also holds that not all submatrices of polyominoes are themselves polyominoes. However, the situation is very diferent from that of permutations: Remark 61. Every binary matrix is a submatrix of some polyomino. Indeed, for every binary matrix , it is always possible to add rows and columns of 1 to in such a way that all 1 entries of the resulting matrix are connected.

From Remarks 60 and 61, it makes sense to examine sets of permutations (resp. polyominoes) that avoid submatrices that are not themselves permutations (resp. polyominoes). Deinition 62. For any set M of quasi-permutation matrices (resp. of binary matrices), let us denote by S (M) (resp. P (M)) the set of all permutations (resp. polyominoes) that do not contain any submatrix in M.

In Deinition 62, in the case of permutations, we may as well consider sets M containing arbitrary binary matrices. But from Remark 60, excluding a matrix which is not a quasi-permutation matrix does not actually introduce any restriction: no permutation contains as a submatrix. Therefore, in our work, when considering S (M), we always take M to be a set of quasipermutation matrices. Figure 3.4 illustrates Deinition 62 in the polyomino case.

The followings facts, although immediate to prove, will be useful in our work: Remark 63. When M contains only permutations (resp. polyominoes), these deinitions of S (M) and P (M) coincide with the ones given in Section 3.1. We reckon it is quite natural to characterise some permutation or polyomino classes by avoidance of submatrices. We provide several examples in Sections 3.4 and 3.5. In the present section, we investigate further the description of permutation and polyomino classes by avoidance of matrices, and in particular we focus on how canonical and concise such a description can be.

1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 S = 1 (a) (b) (c)
Remark on a diferent notion of containment/avoidance of binary matrices in permutation matrices.

To avoid any confusion, let us notice that another deinition of containment of a binary matrix in a permutation matrix (diferent from the submatrix containment) has been around in the permutation patterns literature. It has been used in particular in the Marcus-Tardos proof of the Stanley-Wilf conjecture [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF], and it should be read as follows: a binary matrix = ( i,j ) is contained in a permutation matrix if contains a submatrix = ( i,j ) of the same dimension as such that i,j = 1 as soon as i,j = 1.

This notion of containment of binary matrices in permutations is different, but related to the classical submatrix containment. Indeed, being contained in in the Marcus-Tardos sense means that contains a submatrix that is either or some ′ obtained from by replacing some 0 entries in by 1. Actually, from Remark 60, this statement can be restricted w.l.o.g. to matrices ′ obtained from by replacing some uncovered 0 entries in by 1. By uncovered 0 entry, we mean a 0 entry which does not have any entry 1 in the same row nor in the same column.

Speciically, the set of permutations that avoid all the binary matrices in the set B in the Marcus-Tardos sense is a permutation class, which may be described by the set of excluded submatrices B ′ , where B ′ = { ′ obtained from ∈ B by replacement of some (uncovered) 0 entries by 1}. In this work, we view the Marcus-Tardos deinition of avoidance of a matrix as a shortcut to indicate avoidance in the submatrix sense of a set of matrices. From now on, we focus on the (usual) notion of submatrix avoidance.

Matrix bases of permutation and polyomino classes

We have seen in Propositions 55 and 59 that for each permutation (resp. polyomino) class C, the set of excluded permutation (resp. polyomino) patterns that characterises C is uniquely determined. In view of Proposition 57, it is not hard to associate with every permutation (resp. polyomino) class C a set M of matrices such that C = S (M) (resp. C = P (M)). Given a class C, we can deine such a set M in a canonical way (see Deinition 66). However, we shall see in the following that for some permutation (resp. polyomino) classes C, there exist several antichains M ′ such that C = S (M ′ ) (resp. C = P (M ′ )).

Deinition 66. Let C be a permutation (resp. polyominoe) class. Denote by C + the set of matrices that appear as a submatrix of some element of C, i.e.

C + = { ∈ M | ∃ ∈ C, such that }.
Denote by M the set of all minimal matrices in the sense of that do not belong to C + . M is called the canonical matrix-basis (or canonical -basis

for short) of C.
Of course, the canonical -basis of a class C is uniquely deined, and is always an antichain for . Moreover, Proposition 67 shows that it indeed provides a description of C by avoidance of submatrices. Proposition 67. Let C be a permutation (resp. polyominoe) class, and denote by M its canonical -basis. We have C = S (M) (resp. C = P (M)).

T + =   0  ,  1  ,  1 0  ,  0 1  ,  1 0  ,  0 1  ,  1 0 0 1  ,  0 1 1 0   and the canonical -basis of T is   0 0  ,  0 0  . Example 69. Let A be the permutation class S (321, 231, 312). The canon- ical -basis of A is { 1 , 2 }, with 1 = ⎡ ⎣ 1 0 0 0 0 1 ⎤ ⎦ and 2 =  1 0 0 0 0 1  .
Indeed, it can be readily checked that 1 and 2 do not belong to A + and are minimal for this property. Conversely if M / ∈ A + then contains one of the permutation matrices of 321, 231 and 312, and hence contains 1 or 2 (and actually contains both of them).

Example 70. Let V be the polyomino class made of exactly one column (i.e.

vertical bars). The canonical -basis

of V is {  0  ,  1 1  }.
Example 71. Let R be the polyomino class of rectangular shape. The canonical -basis of R consists only of the matrix  0  .

There is one important diference between -basis and canonical -basis. Every antichain of permutations (resp. polyominoes) is the -basis of a class. On the contrary, every antichain M of binary matrices describes a permutation (resp. polyomino) class S (M) (resp. P (M)), but not every such antichain is the canonical -basis of the corresponding permutation (resp. polyomino) class -see Examples 73 to 76 below. Imposing the avoidance of matrices taken in an antichain being however a natural way of describing permutation and polyomino classes, let us deine the following weaker notion of basis. Example 73. Consider the set M consisting of the following four matrices:

1 =  1 0 0 0  , 2 =  0 1 0 0  , 3 =  0 0 1 0  , 4 =  0 0 0 1  .
We may check that every permutation of size 3 contains a matrix pattern ∈ M, and that it actually contains each of these four i . Moreover, M is an antichain, and so is obviously each set { i }. Therefore, T = S (M) = S ( i ), for each 1 ≤ ≤ 4, even though these antichains characterising T are not the canonical -basis of T (see Example 68).

Example 74. As explained in Example

69, A = S ( 1 ) = S ( 2 ) even though the canonical -basis of A is { 1 , 2 }.
Example 75. Recall from Example 70 that the canonical -basis of the class

V of vertical bars is {  0  ,  1 1  }. But, we also have P  1 1  = V.
Example 76. Consider the sets

M 1 =   1 0  ,  0 1  ,  0 0  ,  0 0  ,  1 0  ,  0 1  and M 2 =   1 0  ,  0 1  ,  1 0  ,  0 1

We may easily check that M 1 and M 2 are antichains, and that their avoidance characterise the rectangular polyominoes of Example 71: R = P (M 1 ) = P (M 2 ).

Examples 73, 74 and 75 show in addition that the canonical -basis is not always the more concise way of describing a class of permutations or of polyominoes by avoidance of submatrices. This motivates the following deinition: Deinition 77. Let C be a permutation (resp. polyominoe) class. A minimal -basis of C is an -basis of C satisfying the following additional conditions:

(1.) M is a minimal subset subject to C = S (M) (resp. P (M)), i.e. for every proper subset M ′ of M, C ̸ = S (M ′ ) (resp. P (M ′ ));

(2.) for every submatrix ′ of some matrix ∈ M, we have

. ′ = or . with M ′ = M ∖ { } ∪ { ′ }, C ̸ = S (M ′ ) (resp. P (M ′ )).
Condition (1.) ensures minimality with respect to inclusion, while Condition (2.) ensures that it is not possible to replace a matrix of the minimal -basis by another one of smaller dimensions. For future reference, let us notice that with the notations of Deinition 77, the statement

C ̸ = S (M ′ ) (resp. P (M ′ )) in Condition 2.. is equivalent to C S (M ′ ) (resp. P (M ′ ))
, since the other inclusion always holds. To illustrate the relevance of Condition (2.), consider for instance the -basis { 1 } of T (see Example 73), with

1 =  1 0 0 0  .
Of course it is minimal (w.r.t. inclusion), however noticing that

T = S  0 0  = S  0 0  ,
with these excluded submatrices being submatrices of 1 , it makes sense not to consider { 1 } as a minimal -basis. This is exactly the point of Condition (2.). Actually, and (2.), i.e. are minimal -basis of T. This also illustrates the somewhat undesirable property that a class may have several minimal -bases. This is not only true for the trivial class T, but also for instance for A: the -bases { 1 } and { 2 } of A (see Example 74) are minimal -bases of A. We can see in the following some examples of polyomino classes in which the minimal -basis is not unique.

Example 78 (Injections). Let I be the family of injections, i.e. polyominoes having at most one zero entry for each row and column such as, for instance

1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1
The set I is a polyomino class, and its -basis is given by the minimal polyominoes which are not injections, i.e. the twelve polyominoes on the top of Fig. 3.5. An -basis of I is given by set

M =   0 0  ,  0 0  .
Moreover, consider the sets

M 1 = ⎧ ⎨ ⎩  0 1 0  ,  1 0 0  ,  0 0 1  , ⎡ ⎣ 0 1 0 ⎤ ⎦ , ⎡ ⎣ 0 0 1 ⎤ ⎦ , ⎡ ⎣ 1 0 0 ⎤ ⎦ ⎫ ⎬ ⎭ and M 2 = ⎧ ⎨ ⎩  0 1 0  ,  1 0 0  ,  0 0 1  , ⎡ ⎣ 0 1 0 ⎤ ⎦ , ⎡ ⎣ 0 0 1 ⎤ ⎦ , ⎡ ⎣ 1 0 0 ⎤ ⎦ , ⎡ ⎣ 0 0 0 ⎤ ⎦ ⎫ ⎬ ⎭
We may easily check that M 1 and M 2 are antichains (see Fig. 3.5), and that their avoidance characterises injections: I = P (M 1 ) = P (M 2 ). So, also M 1 and M 2 are -bases. Proof. For simplicity of the notations, let us forget the indices and write (B) instead of S (B) (resp. P (B)).

Consider a subset B of M that is minimal for inclusion under the condition C = (B), and let us prove that B is a minimal -basis of C. B is an -basis of C satifying Condition (1.). Assume that B does not satisfy Condition (2.): there is some ∈ B and some proper submatrix ′ of , such that C = (B ′ ) for B ′ = B ∖ { } ∪ { ′ }. By deinition of the canonical -basis, ′ ∈ C + (or would not be minimal for ), so there exists a permutation (resp. polyomino

) ∈ C such that ′ . But then / ∈ (B ′ ) = C
bringing the contradiction that ensures that B satisies Condition (2.).

Conversely, consider a minimal -basis B of C and a matrix ∈ B, and let us prove that belong to M. Because of Condition (1.), this is enough to conclude the proof. First, notice that / ∈ C + . Indeed, otherwise there would exist a permutation (resp. polyomino) ∈ C such that , and we would also have / ∈ (B) = C, a contradiction. By deinition, C + = M (M), so there exists ′ ∈ M such that ′ . Since B is a minimal -basis we either have = ′ , which proves that ∈ M, or we have (B ′ ) C for B ′ = B ∖ { } ∪ { ′ }, in which case we derive a contradiction as follows. If (B ′ ) C, then there is some permutation (resp. polyomino) ∈ C which has a submatrix in B ′ . It cannot be some submatrix in B ∖ { }, because C = (B). So ′ , which is a contradiction to

∈ C = (M).

 0

).

A natural question is then to ask for a characterisation of the permutation (resp. polyomino) classes which have a unique minimal -basis. In this direction we give the following remark.

Remark 81. Given a permutation (resp. polyominoe) class C, if the -basis of C is a minimal -basis of C, then the condition of Proposition 79 trivially holds and so the -basis is the unique minimal -basis of C. This happens, for instance, in the case of the class V of vertical bars (see Example 75) or in the case of parallelogram polyominoes (in Section 3.5).

3.3

Relations between the -basis and the - From an -basis to the -basis A permutation (resp. polyomino) class being now equipped with several notions of basis, we investigate how to describe one basis from another, and focus here on describing the -basis from any -basis. In the case of permutation classes, Proposition 82 allows to compute the -basis of any class C, given a -basis of C. Indeed, the minimal permutations (in the sense of S ) that contain a given matrix pattern are easily described: Proposition 84. Let be a quasi-permutation matrix. The minimal permutations that contain are exactly those that may be obtained from by insertions of rows (resp. columns) with exactly one entry 1, which should moreover fall into a column (resp. row) of 0 of .

In particular, if has rows, of which are rows of 0, and ℓ columns, of which are columns of 0, then minimal permutations containing have size + = ℓ + . The situation is more complex if we consider polyomino classes. The description of the polyominoes containing a given submatrix is not as straightforward as in Proposition 84, and the analogue of Corollary 85 does not hold for polyomino classes. Proof. It is enough to exhibit an ininite sequence of polyominoes containing , and that are minimal (for P ) for this property. By minimality of its elements, such a sequence is necessarily an antichain, and it forms an ininite subset of the -basis of C. The irst few terms of such a sequence are depicted in Figure 3.8, and the deinition of the generic term of this sequence should be clear from the igure. We check by comprehensive veriication that every polyomino of this sequence contains , and additionaly that occurrences of in always involve the two bottommost rows of , its two leftmost columns, and its rightmost column. Moreover, comprehensive veriication also shows that every polyomino of this sequence is minimal for the condition P , i.e. that every polyomino ′ occurring in such a as a proper submatrix avoids . Indeed, the removal of rows or columns from such a polyomino either disconnects it or removes all the occurrences of .

..... For instance, the class I of injections, considered in Example 78, is not robust, since there are -bases disjoint from the -basis.

The -basis of a robust class has remarkable properties.

Proposition 88. Let C be a robust class, and let P be the -basis. Then, P is the unique minimal -basis.

Proof. The proof directly follows by Deinition 77.

Remark 89. We notice that if P is the -basis of a robust class C, as a consequence of Proposition 88, P is also the minimal -basis of C.

Example 90. Let be C = P (, ′ ), where , ′ are depicted in Figure 3.9.

The class C is not robust, in fact there is an -basis disjoint from the -basis:

In practice, and ′ are precisely the minimal polyominoes which contain as a pattern, then by Proposition 82, P (, ′ ) = P ( ). We also notice that the meet of and ′ in the poset of polyominoes, denoted ∧ ′ , is {, 1 , 2 }, but P ( 1 , 2 ) C. In this section, we try to establish some criteria to test the robustness of a polyomino class. First, we prove that it is easy to test robustness of a class whose basis is made of just one element: Proposition 91. Let be a pattern. Then, P ( ) is robust if and only if is a polyomino.

Proof. If is not a polyomino, then its -basis is clearly diferent from , so P ( ) is not robust. On the other side, let us assume that is a polyomino and that P ( ) is not robust. Let us assume that an -basis of ( ) is made of a (non polyomino) matrix ′ such that ′ P . Since ′ is not a polyomino then it contains at least two disconnected elements and , and there are at least two possible ways to connect and (by rows or by columns). So, there exists at least another polyomino ̸ = such that ′ P , and belongs to the -basis of P ( ′ ). Thus, P ( ) ⊆ P ( ′ ). The same technique can be used to prove that an -basis of ( ) cannot be made of more than one matrix. Thus, according to Proposition 91, the class

P  1 1 0 1  is robust.
Now, it would be interesting to extend the previous result to a generic set of polyominoes, i.e. ind suicient and necessary conditions such that, given set of polyominoes P, the class P (P) is robust.

( 2 ) every chain from to 1 (resp. from to 2 ) contains at least a polyomino ′ (resp. ′′ ), diferent from 1 (resp. 2 ), such that P ′ P 1 (resp. P ′′ P 2 ), then C is robust.

One can ind a graphical representation of the conditions of the above proposition in Figure 3.10. Proof. Condition (1.) follows directly by Proposition 82. Let us assume that Condition (2.) does not hold, i.e. there exists a proper submatrix ′ of some matrix ∈ P such that C = P (P ′ ), with P ′ = P ∖ { } ∪ { ′ }. So we have that P ′ P P and P ′ is an -basis of C. Since C is a robust class we have that P P P ′ and then P = P ′ , in particular = ′ . Suppose that there exists another -basis M ̸ = P satisfying (1.) and (2.). By Proposition 82, every pattern of M is contained in some pattern of P, thus P contains M. Since C is a robust class, then P ⊆ M, so P = M. Here, as shown in the picture, 1 ∧ 2 contains six elements, and four of them are not polyominoes. However, one can check that, for each item of these four matrices, there is a polyomino in the chain from to 1 (resp. from to 2 ). Thus, by Proposition 92, the class C is robust.

However, the statement of Proposition 92 cannot be inverted, as we can see in the following example. polyominoes can be represented by the avoidance of the submatrices:

1 =  1 0 1 1  , 2 =  1 1 0 1  .
These two patterns form a -basis for the class P of parallelogram polyominoes, and

1 ∧ 2 =   1 1  ,  1 1  ,  0   .
If P is not robust, then =  0  would belong to an -basis of P; precisely, we would have P ( ) = P. But this is not true, since P ( ) is the class of rectangles. Thus, P is robust. Observe that the set { 1 , 2 , [ 1 0 1 ]} forms an -basis of the class, but it is not minimal w.r.t. set inclusion.

Some families of permutations deined by submatrix avoidance

Many notions of pattern avoidance in permutations have been considered in the literature. Nevertheless, we have considered yet another notion of submatrix avoidance. In this section, we start by explaining how it relates to other notions of pattern avoidance. Then, using this approach to pattern avoidance, we give simpler proofs of the enumeration of some permutation classes. Finally, we show how these proofs can be brought to a more general level, to prove Wilf-equivalences of many permutation classes. In some sense, the avoidance of submatrices in permutation is a dual notion to the avoidance of vincular and bivincular patterns. Indeed, in an occurrence of some vincular (resp. bivincular) pattern in a permutation , we impose that some elements of must be adjacent (resp. have consecutive values). Whereas if there is a column (resp. row) of 0 in a quasi-permutation matrix , then an occurrence of in is an occurrence of the largest permutation contained in in where some elements of are not allowed to be adjacent (resp. to have consecutive values).

For instance, As noticed in Remark 65, sets of permutations deined by avoidance of submatrices are permutation classes. On the contrary, sets of permutations deined by avoidance of vincular or bivincular patterns are not downward closed for in general. This shows that, even though they are very useful for characterising important families of permutations, like Baxter permutations [START_REF] Baxter | On ixed points of the composite of commuting functions[END_REF], the adjacency constraints introduced vincular and bivincular pattern do not it really well in the study of permutation classes. The above discussion suggests that, with this regard, it is more convienent to introduce instead non-adjacency constraints in permutation patterns, which corresponds to rows and columns of 0 in quasi-permutation matrices.

Let us consider now another generalisation of permutation patterns, the Mesh patterns. It has itself been generalised in several way, in particular by Úlfarsson who introduced in [START_REF] Úlfarsson | A uniication of permutation patterns related to Schubert varieties, to appear[END_REF] the notion of marked mesh patterns. It is very easy to see that the avoidance of a quasi-permutation matrix with no uncovered 0 entries can be expressed as the avoidance of a special form of marked-mesh pattern. Indeed, a row (resp. consecutive rows) of 0 in a quasi-permutation matrix with no uncovered 0 entries corresponds to a mark, spanning the whole pattern horizontally, indicating the presence of at least one (resp. at least ) element(s). The same holds for columns and vertical marks. Figure 3.12 shows an example of a quasi-permutation matrix with no uncovered 0 entries with the corresponding marked-mesh pattern.

A diferent look at some known permutation classes

Several permutation classes avoiding three patterns of size 3 or four patterns of size 4 that have been studied in the literature (and are referenced in Guibert's catalogue [83, Appendix A]) are easier to describe with the avoidance of just one submatrix, as we explain in the following. For some of these classes, the description by submatrix avoidance also allows to provide a simple proof of their enumeration.

In this paragraph, we do not consider classes that are equal up to symmetry (reverse, inverse, complement, and their compositions). But the same results of course apply (up to symmetry) to every symmetry of each class considered.

The class F = S [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF]132,213). This class was studied in the Simion-Schmidt article [START_REF] Simion | Restricted permutations[END_REF], about the systematic enumeration of permutations avoiding patterns of size 3. An alternative description of F is

F = S ( F ) where F =  0 0 1 1 0 0  .
It follows immediately since 123, 132 and 213 are exactly the permutations which cover F in the sense of Propositions 82 and 84. [START_REF] Simion | Restricted permutations[END_REF] shows that F is enumerated by the Fibonacci numbers. Of course, it is possible to use the description of F by the avoidance of F to see that every permutation ∈ F decomposes as = 1 • 2 • • • k , where the sequences i are either or ( + 1) for some integer , and are such that for < the elements of i are larger that those of j . And from this description, an easy induction shows that F is enumerated by the Fibonacci numbers. However, this is just rephrasing the original proof of [START_REF] Simion | Restricted permutations[END_REF].

The class G = S [START_REF] West | Generating trees and the Catalan and Schröder numbers[END_REF]132,231). This class is also studied in [START_REF] Simion | Restricted permutations[END_REF], where it is shown that there are permutations of size in G. The enumeration is obtained by a simple inductive argument, which relies on a recursive description of the permutations in G.

For the same reasons as in the case of F, G is alternatively described by

G = S ( G ) where G =  0 1 0 1 0 0  .
Any occurrence of a pattern 12 in a permutation can be extended to an occurrence of G , as long as it does not involve the last element of . So from this characterisation, it follows that the permutations of G are all decreasing sequences followed by one element. This describes the permutations of G non-recursively, and give immediate access to the enumeration of G.

The classes H = S (1234, 1243, 1423, 4123), J = S (1324, 1342, 1432, 4132)

and K = S (2134, 2143, 2413, 4213). These three classes have been studied in [START_REF] Guibert | Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young[END_REF]Section 4.2], where it is proved that they are enumerated by the central binomial coeicients. The proof irst gives a generating tree for these classes, and then the enumeration is derived analytically from the corresponding rewriting system. In particular, this proof does not provide a description of the permutations in H, J and K which could be used to give a combinatorial proof of their enumeration. Excluded submatrices can be used for that purpose.

As before, because the -basis of H, J and K are exactly the permutations which cover the matrices H , J and K given below, we have

H = S ( H ) where H = ⎡ ⎢ ⎢ ⎣ 0 0 0 0 0 1 0 1 0 1 0 0 ⎤ ⎥ ⎥ ⎦ , J = S ( J ) where J = ⎡ ⎢ ⎢ ⎣ 0 0 0 0 1 0 0 0 1 1 0 0 ⎤ ⎥ ⎥ ⎦ , K = S ( K ) where K = ⎡ ⎢ ⎢ ⎣ 0 0 0 0 0 1 1 0 0 0 1 0 ⎤ ⎥ ⎥ ⎦ .
Similarly to the case of G, any occurrence of a pattern 123 (resp. 132, resp. 213) in a permutation can be extended to an occurrence of H (resp. J , resp. K ), as long as it does not involve the maximal element of . Conversely, if a permutation contains H (resp. J , resp. K ), then there is an occurrence of 123 (resp. 132, resp. 213) in that does not involves its maximum. Consequently, the permutations of H (resp. J, resp. K) are exactly those of avoiding 123 (resp. 132, resp. 213) to which a maximal element has been added. This provides a very simple description of the permutations of H, J and K. Moreover, recalling that for any permutation ∈ S 3 S () is enumerated by the Catalan numbers, it implies that the number of permutations of size in H (resp. J, resp.

K) in × n-1 =  2n-2 n-1  .

Some families of polyominoes deined by submatrix avoidance

In this section, we show that several families of polyominoes studied in the literature can be characterised in terms of submatrix avoidance. For more details on these families of polyominoes we address the reader to Section 1.2.

We also use submatrix avoidance to introduce new classes of polyominoes.

Characterising known families of polyminoes by submatrix avoidance

There are plenty of examples of families of polyominoes that can be described by the avoidance of submatrices. We provide a few of them here, however without giving detailed deinitions of these families. Figure 3.13 shows examples of polyominoes belonging to the families that we study. More precisely, the avoidance of the matrix (resp. ) indicates the ℎ-convexity (resp. -convexity). Because removing columns (resp. rows) preserves the ℎ-convexity (resp. -convexity), {, } is the canonicalbasis, and hence by Proposition 79 the unique minimal -basis, of the class of convex polyominoes. From Proposition 82, it is also possible to determine the -basis of this class: it is the set of four polyominoes { 1 , 2 , 1 , 2 } depicted in Figure 3.14. We advise the reader that, in the rest of the section, for each polyomino class, we provide only a matrix description of the basis. Indeed, in all these examples the -basis can easily be obtained from the given -basis with Proposition 82, like in the case of convex polyominoes.

p-basis canonical m-basis

V = 1 V = 2 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 V = 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 H = H = 1 H = 2
Directed-convex polyominoes. Directed-convex polyominoes are deined using the notion of internal path to a polyomino. An (internal) path of a polyomino is a sequence of distinct cells ( 1 , . . . , n ) of the polyomino such that every two consecutive cells in this sequence are edge-connected; according to the respective positions of the cells i and i+1 , we say that the pair ( i , i+1 ) forms a north, south, east or west step in the path, respectively. Figure 3.13() depicts a directed polyomino. The reader can check that the set of directed polyominoes is not a polyomino class. However, the set of directed-convex polyominoes (i.e. of polyominoes that are both directed and convex -see Figure 3.13()) is a class. First, let ∈ P (, , ). is a convex polyomino and avoids the submatrix . Let be its source, necessarily the leftmost cell at the lower ordinate. Let us proceed by contradiction assuming that is not directed, i.e. there exists a cell of such that all the paths from to contain either a south step or a west step. Let us consider one of these paths with minimal length (deined as the number of cells), say , and having at least a south step (if has at least a west step, a similar reasoning holds). If lies at the same ordinate as or below it, then the presence of a south step in implies that there exist two cells i and j of , with 1 ≤ < ≤ , where crosses the ordinate of with a north and a south step, respectively. Since is minimal, then the row of cells containing i and j is not connected, contradicting that is ℎ-convex. Otherwise, lies above , and there exists a point i ̸ = with 1 < < , having the same ordinate as , and such that it forms with the cell i+1 a south step. So, the four cells , i , i+1 and the empty cell below form the pattern , giving the desired contradiction.

Conversely, let be a directed convex polyomino. We proceed by contradiction assuming that contains the pattern . Let 1 and 2 be the cells of that correspond to the upper left and to the lower right cells of , respectively. Two cases have to be considered: if the source cell of lies above 2 , then each path leading from to 2 has to contain at least one south step, which contradicts the fact that is directed. On the other hand, if lies in the same row of 2 or below it, then each path leading from to 1 either runs entirely on the left of 1 , so that contains the pattern , which is against the ℎ-convexity of , or it contains a west step, which again contradicts the fact that is directed.

Parallelogram polyominoes.

Another widely studied family of polyominoes -that can also be deined using a notion of path, this time of boundary path-is that of parallelogram polyominoes.

Parallelogram polyominoes (see Figure 3.13()) form a polyomino class. The proof of this fact mimics that of Proposition 99.

. This is also the -basis of the class of parallelogram polyominoes.

-convex polyominoes. Parallelogram polyominoes and directed-convex polyominoes form subfamilies of the family of convex polyominoes that are both deined in terms of paths. The relationship between these two notions is closer than it may appear.

Let us consider the 1-convex polyominoes are more commonly calledconvex polyominoes, (see Figure 3.13()).

Here, we study how the constraint of being -convex can be represented in terms of submatrix avoidance. In order to reach this goal, let us present some basic deinitions and properties from the ield of discrete tomography [START_REF] Ryser | Combinatorial Mathematics, The Carus Mathematical Monographs[END_REF]. Given a binary matrix, the vector of its horizontal (resp. vertical) projections is the vector of the row (resp. column) sums of its elements. In 1963 Ryser [START_REF] Ryser | Combinatorial Mathematics, The Carus Mathematical Monographs[END_REF] established a fundamental result which, using our notation, can be reformulated as follows: -convex polyominoes are characterised by the avoidance of the submatrices , , 1 and 2 . In other words, L = P (, , 1 , 2 ).

Proof. First, let be a convex polyomino that avoids the submatrices 1 and 2 . Let us proceed by contradiction assuming that is not -convex. It means that there exists a pair of cells 1 and 2 of such that all the paths from 1 to 2 are not -paths, i.e. they have at least two directions changes. Suppose that 2 lies below 1 , on its right (if not, similar reasonings hold). Consider the path from 1 that goes always right (resp. down) until it encounters a cell ′ (resp. ′′ ) which does not belong to . This happens before reaching the abscissa (resp. ordinate) of 2 , otherwise by convexity there would be a path from 1 to 2 with one direction change. By convexity, all the cells on the right of ′ (resp. below ′′ ) do not belong to , so the four cells having the same abscissas and ordinates of 1 and 2 form the pattern 1 , giving the desired contradiction.

Conversely, let be an -convex polyomino. By convexity, does not contain the submatrices and . Moreover, in [START_REF] Castiglione | A tomographical characterization of -convex polyominoes[END_REF] it is proved that an -convex polyomino is uniquely determined by its horizontal and vertical projections, so by Theorem 101 it cannot contain 1 or 2 .

Generalised pattern avoidance

Unfortunately not all the families of polyominoes are a polyomino class. Unlike -convex polyominoes, 2-convex polyominoes do not form a polyomino class. Indeed, the 2-convex polyomino in Figure 3.15() contains the 3-butnot-2-convex polyomino () as a submatrix. Similarly, the set of -convex polyominoes is not a polyomino class, for ≥ 2. In practice, this means that 2-convex polyominoes cannot be described in terms of pattern avoidance. In order to be able to represent 2-convex polyominoes we extend the notion of pattern avoidance, introducing the generalised pattern avoidance. Our extension consists in imposing the adjacency of two columns or rows by introducing special symbols, i.e. vertical/horizontal lines: being a pattern, a vertical line between two columns of , i and i+1 (a horizontal line between two rows i and i+1 ), will be read as i and i+1 (respectively i and i+1 ) must be adjacent. When the vertical (resp. horizontal) line is external, it means that the adjacent column (resp. row) of the pattern must touch the minimal bounding rectangle of the polyomino. Moreover, we use the * symbol to denote 0 or 1 indiferently. Remark 104. In a 2-convex polyomino, due to the convexity constraints,we have that for each two cells, there is a monotone path connecting them, which uses only two types of steps among , , , , see Section 1.2.1. More precisely, after the irst direction change the two types of steps are determined.

Another important fact is that, given two cells of a polyomino 1 and 2 , the minimal number of direction changes to go from 1 to 2 can be obtained studying two paths, the ones starting with a vertical/horizontal step, in which every side has maximal length. Proof. Let M be the set of generalised patterns of Proposition 105 and let be a polyomino.

(⇒) If is a 2-convex polyomino then avoids M.

Let us assume by contradiction that is a 2-convex polyomino but it contains one of the patterns of M. avoids the two patterns and otherwise it would not be a convex polyomino. For simplicity sake, we can consider only two patterns of M, for instance where the 0, 1, * are the elements of 1 and the dots can be replaced by 0, 1 indiferently, in agreement with the convexity and polyomino constraints.

Among all the polyominoes which can be obtained from ′ , the one having the minimal convexity degree is that, called ′ , where we have replaced any dot with a 1 entry. So, given ′ = 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 , it is possible to verify that the minimal number of direction changes requested to run from the leftmost lower cell of ′ to the rightmost bottom cell of ′ is three, so ′ is a 3-convex polyomino, then we reach our goal.

Similarly, If contains 2 then it has to contain a submatrix ′ of this type where the vertical/horizontal lines have been drawn to mean that in this position there is a direction change. Also in this case we can consider the polyomino ′ , in which we have replaced any dot with a 1 entry. It is possible to verify that the minimal number of direction changes requested to run from the leftmost lower cell of ′ to the rightmost bottom cell of ′ is three, so ′ and as consequence are a 3-convex polyominoes against the hypothesis. (⇐) If avoids M then is a 2-convex polyomino.

Let us assume that, on the contrary, avoids M but it is a 3-convex polyomino, i.e. there exist two cells of , 1 and 2 , such that any paths from 1 to 2 requires at least three direction changes.

Let us take into consideration the two paths, deined in Remark 104, which use only steps of type and to prove that contains at least one of the patterns of M. We have to analyse the following situations:

-the two paths running from 1 to 2 are distinct, see Figure 3 Here, we consider only the irst situation (which is the most general), because in all the other cases we can use an analogous reasoning.

So, we have that the two cells 1 and 2 are connected by two distinct paths, see Figure 3 The submatrix obtained from ′ , deleting all the rows and columns containing dots, is one among the various that we can obtain replacing appropriately the symbol * in the pattern 2 . Thus, contains 2 against the hypothesis.

We remark that the pattern 1 , and its rotations, can be obtained from the pattern 2 (or its rotation) replacing appropriately the * entries, but we need to include them to consider them in order to exclude the 3-convex polyominoes having three rows or columns.

We can point out that the pattern 1 , and its rotation, can be obtained from the pattern 2 (or its rotation) replacing appropriately the * entries. We need to consider them in order to exclude the 3-convex polyominoes of dimension × , with one among and less than 4.

Let us just observe, referring to Fig. 3.17, that the pattern () is not contained in the 2-convex polyomino (), but it is contained in the 3-convex polyomino ().

It is possible to generalise the previous result and give a characterisation of the family of -convex polyominoes, with > 2, using generalised patterns.

As we observed in 3.5.1 it is not possible to describe the set of directed polyominoes in terms of submatrix avoidance, but also in this case the introduction of generalised patterns will be useful. .17: () a 2-convex polyomino ; () a pattern of that is not a 2-convex polyomino; () a generalised pattern, which is not contained in (), but is contained in the 3-convex polyomino (non 2-convex) ().

We would like to point out that there are families of polyominoes which cannot be described, even using generalised pattern avoidance. For instance, one of these families is that of polyominoes having a square shape.

Deining new families of polyominoes by submatrix avoidance

In addition to characterising known families, the approach of submatrix avoidance may be used to deine new families of polyominoes, the main question being then to give a combinatorial/geometrical characterisation of these families. We present some examples of such families, with simple characterisations and interesting combinatorial properties. These examples illustrate that the submatrix avoidance approach in the study of families of polyominoes is promising.

-polyominoes. Proposition 102 states that -convex polyominoes can be characterised by the avoidance of four matrices: and , which impose the convexity constraint; and 1 and 2 , which account for the -property, or equivalently (by Theorem 101) indicate the uniqueness of the polyomino w.r.t its horizontal and vertical projections. So, it is quite natural to study the class P ( 1 , 2 ), which we call the class of -polyominoes. From Theorem 101, it follows that: Proposition 106. Every -polyomino is uniquely determined by its horizontal and vertical projections.

From a geometrical point of view, the -polyominoes can be characterised using the concept of (geometrical) inclusion between rows (resp. columns) of a polyomino. For any polyomino with columns, and any rows 1 = ( 1;1 . . . 1;n ), 2 = ( 2;1 . . . 2;n ) of the matrix representing , we say that 1 is geometrically included in 2 (denoted 1 2 ) if, for all 1 ≤ ≤ we have that 1;i = 1 implies 2;i = 1. Geometric inclusion of columns is deined analogously. Two rows (resp. columns) 1 , 2 (resp. 1 , 2 ) of a polyomino are said to be comparable if 1 2 or 2 1 (resp. 1 2 or 2 1 ). These deinitions are illustrated in Figure 3.18.

The avoidance of 1 and 2 has an immediate interpretation in geometric terms, proving that: Proposition 107. The class of -polyominoes coincides with the set of the polyominoes where every pair of rows (resp. columns) are comparable. () a -polyomino, where every pair of rows and columns are comparable; for instance, 1 2 ; () an example of a polyomino which is not an -polyomino, where the row 1 is not comparable both with rows 2 and 3 .

We leave open the problem of studying further the class of -polyominoes, in particular from an enumerative point of view (enumeration w.r.t. the area or the semi-perimeter). A hollow stack (polyomino) is a polyomino obtained from a stack polyomino by removing from a stack polyomino ′ which is geometrically contained in and whose basis lies on the basis of the minimal bounding rectangle of . In both cases permutation and polyomino classes, we have described several notions of bases for these classes: -basis, -basis, canonical -basis, minimal -basis. Section 3.3 explains how to describe the -basis from any -basis. Conversely, we may ask how to transform the -basis into an "eicient" -basis. Of course, the -basis is itself an -basis, but we may wish to describe the canonical one, or a minimal one.

Many questions may also be asked about the canonical and minimalbases themselves. For instance: When does a class have a unique minimalbasis? Which elements of the canonical -basis may belong to a minimalbasis? May we describe (or compute) the minimal -bases from the canonical -basis?

Finally, we can study the classes for which the -basis is itself a minimal -basis of the class (see the examples of the polyomino classes of vertical bars, or of parallelogram polyominoes).

Submatrix avoidance in permutation classes has allowed us to derive a statement (Corollary 97) from which ininitely many Wilf-equivalences follow.

Such general results on Wilf-equivalences are rare in the permutation patterns literature, and it would be interesting to explore how further we can go in the study of Wilf-equivalences with the submatrix avoidance approach.

The most original concept of this work is certainly the introduction of the polyomino classes, which opens many directions for future research.

One is a systematic study of polyomino classes deined by pattern avoidance. As enumeration is the biggest open question about polyominoes, we should study the enumeration of such classes, and see whether some interesting bounds can be provided. Notice that the Stanley-Wilf-Marcus-Tardos theorem [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF] on permutation classes implies that permutations in any given class represent a negligible proportion of all permutations. We don't know if a similar statement holds for polyomino classes.

As we have reported in Section 3.1.2, the poset (P, P ) of polyominoes was introduced in [START_REF] Castiglione | Ordering and Convex Polyominoes[END_REF], where the authors proved that it is a ranked poset, and contains ininite antichains. There are however some combinatorial and algebraic properties of this poset which are still to explore, in particular w.r.t. characterising some simple intervals in this poset.

Finally, we have used binary matrices to import some questions on permutation classes to the context of polyominoes. But a similar approach could be applied to any other family of combinatorial objects which are represented by binary matrices.

Figure 1 . 1 :

 11 Figure 1.1: A polyomino in () and the corresponding animal in ().

Figure 1 . 2 :

 12 Figure 1.2: (): A column-convex polyomino; (): A row-convex polyomino; (): A convex polyomino.

  3 ().

Figure 1 . 3 :

 13 Figure 1.3: (): A Ferrer diagram; (): A stack polyomino; (): A parallelogram polyomino; (): A directed convex polyomino which is neither a parallelogram nor a stack one.

Figure 1 . 4 :

 14 Figure 1.4: A convex polyomino and the 4 sets of cells identiied by its intersection with the minimal bounding rectangle.

( c )

 c Parallelogram polyominoes (Figure 1.3 ()) are a particular family of convex polyominoes uniquely identiied by a pair of paths consisting only of north and east steps, such that the paths are disjoint except at their common ending points. The path beginning with a north (respectively east) step is called upper (respectively lower) path.

Figure 1 . 5 :

 15 Figure 1.5: (): A path between two cells of the polyomino ; (): A monotone path between two cells of the polyomino with four changes of direction.

Figure 1 . 6 :

 16 Figure 1.6: (a), (b) Two rectangles having a non-crossing intersection; (c) Two rectangles having crossing intersection.

Figure 1 . 7 :

 17 Figure 1.7: Two-lines representation of the permutation = 2314675 in () and in () the graphical representation of .

Figure 1 . 8 :

 18 Figure 1.8: () Set of right-to-left minima for = 21546837; () set of rightto-left maxima; () set of left-to-right minima; and () set of left-to-right maxima.

Deinition 12 .

 12 If B is an antichain, then B is unique and is called basis of the permutation class n (B). In this case, it also true that B = { / ∈ n (B) : ∀ S , ∈ n (B)} . Proposition 13. Let be C = n (B 1 ) = n (B 2 ). If B 1 and B 2 are two antichains then B 1 = B 2 .

Figure 1 . 9 :

 19 Figure 1.9: () Classical pattern 3 -1 -4 -2; () Generalised (or vincular) pattern 3 -1 -42: () Bivincular pattern (3142, {1}, {3}); and () Mesh pattern (3142, ).

Figure 1 .

 1 10 displays the diagram obtained with = 3.

Figure 1 . 10 :

 110 Figure 1.10: The Hasse diagram of 3 .

Figure 2 . 1 (

 21 ) shows an example of convex polyomino that is not parallelogram, while Figure2.1 () depicts a 4-parallelogram (non 3-parallelogram) polyomino.

Figure 2 . 1 :

 21 Figure 2.1: () A convex polyomino; () a monotone path between two cells of the polyomino with four direction changes; () a 4-parallelogram.

Figure 2 . 2 :

 22 Figure 2.2: An example of 4-parallelogram polyomino and the internal path

Figure 2 . 3 :

 23 Figure 2.3: The paths ℎ (solid line) and (dashed line) in a parallelogram polyomino, where the cell has been highlighted; () a polyomino in P 3 ; () a polyomino in P U 3 ; () a polyomino in P R 4 ; () a polyomino in P U 3 where coincides with .

Figure 2 .

 2 Figure 2.3 () depicts a polyomino in P k , while Figures 2.3 (), (), and () depict polyominoes in P U k and P R k . According to this deinition all rectangles having width and height greater than one belong to P 1 .

6 XFigure 2 . 4 :

 624 Figure 2.4: Decomposition of a polyomino of P U 4 .

Figure 2 . 7 :

 27 Figure 2.7: () A polyomino ∈ P U 1 and () a polyomino in P 1 .

0, 3 ,

 3 10, 25, 56, 119, 246, 501, 1012, • • • .

Figure 2 . 9 :

 29 Figure 2.9: The seven trees with 6 nodes and height 5.

Figure 2 . 10 :

 210 Figure 2.10: () A polyomino in P U 4 and in () its corresponding tree.

Figure 2 .

 2 11 depicts the decomposition of the tree of Figure 2.10 ().

Figure 2 . 11 :

 211 Figure 2.11: The pair ( 1 , 2 ) of trees corresponding to the tree depicted in Figure 2.10, in particular 1 in () and 2 in ().

Figure 2 . 12 :

 212 Figure 2.12: Case 1. () A pair of trees 1 and 2 and its corresponding tree = ( 1 , 2 ) in ().

). 4 .

 4 | 1 | ≤ + 2 and | 2 | ≤ + 1. Also here we take into consideration the borderline case, | 1 | = + 2, | 2 | = + 1, and | ( )| = |( 1 , 2 )| = + 3.

Figure 2 . 13 :

 213 Figure 2.13: Case 1. () The tree = ( 1 , 2 ) and in () its corresponding parallelogram polyomino ( ).

Figure 2 . 14 :

 214 Figure 2.14: Case 2. () A pair of trees 1 and 2 and its corresponding tree = ( 1 , 2 ) in ().

Figure 2 . 15 :

 215 Figure 2.15: Case 2. () The tree = ( 1 , 2 ) and in () its corresponding parallelogram polyomino ( ).

Figure 2 . 16 :

 216 Figure 2.16: Case 3. () A pair of trees 1 and 2 and its corresponding tree = ( 1 , 2 ) in ().

Figure 2 . 17 :

 217 Figure 2.17: Case 3. () The tree = ( 1 , 2 ) and in () its corresponding parallelogram polyomino ( ).

Figure 2 . 18 :

 218 Figure 2.18: Case 4. () A pair of trees 1 and 2 and its corresponding tree = ( 1 , 2 ) in ().

Figure 2 . 19 :

 219 Figure 2.19: Case 4. () The tree = ( 1 , 2 ) and in () its corresponding parallelogram polyomino ( ).

Figure 2 . 20 :

 220 Figure 2.20: () A polyomino ∈ 3 . () A polyomino ∈ 3 . () A polyomino ∈ 3 in which the uppermost cells of are on the left of 3 , and the rightmost cells of are above 3 . () A polyomino ∈ 3 in which the uppermost cells of are on the right of 3 , and the rightmost cells of are below 3 .

3. 1 . 1 Figure 3 . 1 :

 1131 Figure 3.1: () Graphical representation (or diagram) of the permutation = 521634. () The permutation matrix corresponding to .

Figure 3 . 2 :

 32 Figure 3.2: A polyomino and its representation as a binary matrix.

Figure 3 . 3 :

 33 Figure 3.3: () A polyomino with no holes; () A polyomino ′

Figure 3 . 4 :

 34 Figure 3.4: () a matrix 1 ;() a polyomino that contains 1 as a submatrix, hence does not belong to P ( 1 ); () a polyomino that does not contain 1 , i.e. that belongs to P ( 1 ).

  Proof. Working in the poset (M, ), Proposition 57 ensures that C + = M (M). And since C = C + ∩ S (resp. C = C + ∩ P), Remark 64 yields the conclusion. Example 68. For the (trivial) permutation class T = {1, 12, 21}, we have

Deinition 72 .

 72 Let C be a permutation (resp. polyominoe) class. Every antichain M of matrices such that C = S (M) (resp. P (M)) is called a matrix-basis (or -basis) of C. Examples 73 to 76 show several examples of -bases of permutation and polyomino classes which are diferent from the canonical -basis.

Figure 3 . 5 :

 35 Figure 3.5: The -basis and some -bases of I.

Example 80 .{ 1 }

 801 On our running examples, Proposition 79 ensures that both T and A each have two minimal -basis, and { 2 } respectively. The polyomino class V (resp. R) has however a unique minimal -basis:

Example 83 .

 83 Figures 3.6 and 3.7 give the -basis of the classes A and R of Examples 69 and 71, and illustrate its relation to their canonical -basis.

Figure 3 . 6 :

 36 Figure 3.6: The -basis and the canonical -basis of A = S (321, 231, 312).

Figure 3 . 7 :

 37 Figure 3.7: The -basis and the canonical -basis of the class R of polyominoes having rectangular shape.

Proposition 86 .

 86 The polyomino class C = P ( ) deined by the avoidance of has an ininite -basis.

Figure 3 . 8 :

 38 Figure 3.8: An ininite antichain of polyominoes belonging to the -basis of P ( ).

  A class is robust when all -bases contain the -basis.

Figure 3 . 9 :

 39 Figure 3.9: A non robust class.

Figure 3 .

 3 Figure 3.10: A graphical representation of the conditions of Proposition 92.

Example 93 .

 93 Let us consider the class C = P ( 1 , 2 ), where 1 and 2 are the polyominoes depicted in Figure 3.11.

Figure 3 .

 3 Figure 3.11: A robust class.

⎠⎠⎠

  denotes the set of all permutations such that in any occurrence of 231 the elements mapped by the 2 and the 3 are at adjacent positions; denotes the set of all permutations such that in any occurrence of 231 the elements mapped by the 2 and the 3 are at adjacent positions, and the elements mapped by the 1 and the 2 have consecutive values; denotes the set of all permutations such that in any occurrence of 231 the element mapped by the 3 is the maximum of the permutation.

Figure 3 .

 3 Figure3.12: A quasi-permutation matrix with no uncovered 0 entries and the corresponding marked-mesh pattern.

Figure 3 . 13 :

 313 Figure 3.13: () A convex polyomino; () A directed polyomino; () A directed-convex polyomino; () A parallelogram polyomino; () An -convex polyomino.

Figure 3 .

 3 Figure 3.13() shows a convex polyomino. The convexity constraint can be easily expressed in terms of excluded submatrices since its deinition already relies on some speciic conigurations that the cells of each row and column of a polyomino have to avoid: Proposition 98. Convex polyominoes can be represented by the avoidance of the two submatrices = [ 1 0 1 ] and =

Figure 3 . 14 :

 314 Figure 3.14: The -basis and canonical -basis of the class of convex polyominoes.

Proposition 99 .

 99 The family D of directed-convex polyominoes is characterised by the avoidance of the submatrices = [ us prove that D = P (, , ).

Proposition 100 .

 100 Parallelogram polyominoes are characterised by the avoidance of the submatrices:

Theorem 101 .

 101 A binary matrix is uniquely determined by its horizontal and vertical projections if and only if it does not contain 1 = that the set L of -convex polyominoes is a polyomino class.Proposition 102.

Figure 3 . 15 :

 315 Figure 3.15: () a 2-convex polyomino ; () a submatrix of that is not a 2-convex polyomino.

1

  Before providing the proof of Proposition 105 we need to recall some useful facts.

  patterns are just the rotations of the previous ones. If contains 1 then it has to contain a submatrix ′ of this type 0 * . . . . 1 * 1 . . . . 0 . . . . . . . . . . . . . . . . . . . . . 1 0 . . . . 0 ,

0

  . . . 0| * . . . 1 . . . . . . . . . . . . . . . . . . . . 0| . . . * 1 . . * * . . . 1 * . . . 0| . . . . . . . . . . . . . . . . . . . . 1 . . . * 0| . . . 0 ,

  .16 (); -one of the paths running from 1 to 2 does not exist, see Figure 3.16 (); -the two paths running from 1 to 2 coincide after the irst direction change, see Figure 3.16 ();-the two paths running from 1 to 2 coincide after the second direction change, see Figure3.16 ().

Figure 3 . 16 :

 316 Figure 3.16: The possible monotone paths connecting the cells 1 and 2 , those cells are the ones greyed. () the two paths are distinct; () one of the paths does not exist; () the two paths running from 1 to 2 coincide after the irst direction change;() the two paths running from 1 to 2 coincide after the second direction change.

  .

16

 16

  (), then have to contain a submatrix ′ of the following type 0 . . . 0 1 . . . 1 . . . . . . . . . . . . . . . . . . . . 0 . . . 1 1 . . . 1 1 . . . 1 1 . . . 0 . . . . . . . . . . . . . . . . . . . . 1 . . . 1 0 . . . 0 , where the horizontal and vertical lines, which indicate the adjacency constraints, have been placed to impose the direction changes.

Proposition 105 .

 105 The family of directed polyominoes can be represented as the class of polyominoes avoiding the following patterns can reach our goal using reasonings analogous to Proposition 105 based on the deinition of directed polyomino and recalling the proof of Proposition 99.

Figure 3

 3 Figure3.17: () a 2-convex polyomino ; () a pattern of that is not a 2-convex polyomino; () a generalised pattern, which is not contained in (), but is contained in the 3-convex polyomino (non 2-convex) ().

Figure 3 .

 3 Figure 3.18: () a -polyomino, where every pair of rows and columns are comparable; for instance, 1 2 ; () an example of a polyomino which is not an -polyomino, where the row 1 is not comparable both with rows 2 and 3 .

  The class P ( ′ , ′ ) with ′ =

Figure 3 .Figure 3 . 22 :

 3322 Figure 3.22: () a stack polyomino; (), (): hollow stacks.

Figure 3 .

 3 Figure 3.23: A rectangle with rectangular holes.

  .6.

	Proposition 9. A convex polyomino is -convex if and only if any two
	of its maximal rectangles have a nonempty crossing intersection.

  is, for all indexes and , ia < i b if and only if a < b ). In that case, i 1 i 2 • • • im is called an occurrence of in and we write S . In this context, is also called a pattern.If does not contain , we say that avoids , or that is -avoiding. For example, if = 231, then = 24531 contains 231, because the subsequence 2 3 5 = 451 has the same relative order as 231. However, = 51423 is 231-avoiding. We indicate with n () the set of -avoiding permutations in S n .

	Deinition 11. A permutation class is a set of permutations C that is down-
	ward closed for	S : for all ∈ C, if S , then ∈ C.

  Deinition 15. Two patterns are Wilf equivalent and belong to the same Wilf class if, for each , the same number of permutations of length avoids the same pattern.Wilf equivalence is a very important topic in the study of patterns. The smallest example of non-trivial Wilf equivalence is for the classical patterns of length 3; all six patterns 123, 321, 132, 213, 231, and 312 are Wilf equivalent; each pattern is avoided by n permutations of length , where n is the Catalan number1

	n+1	 2n n	 , see for example

  Deinition 20. A partial order = (; ≤) is called total order (or linear order) if for all , ∈ , either ≤ in or ≤ in . Deinition 21. Let , be two generic elements in . A partial order = (; ≤) is called lattice when there exist two elements, usually denoted by ∨ and by ∧ , such that: ❼ ∨ is the supremum of the set {, } in ❼ ∧ is the inimum of the set {, } in ,

i.e. for all in ≥ ∨ ⇐⇒ ≥ and ≥ ≤ ∧ ⇐⇒ ≤ and ≤ . Deinition 22. Given , in a poset , the interval [, ] is the poset { ∈ : ≤ ≤ } with the same order as .

  The Hasse diagram of + consists of the Hasse diagrams of and drawn together.2. Ordinal sum. ⊕ is the set ∪ , where ≤ P ⊕Q if and only if one of the following conditions holds:

∪, where ≤ P +Q if and only if one of the following conditions holds: ❼ , ∈ and ≤ P ❼ , ∈ and ≤ Q ❼ ≤ P +Q ❼ ∈ and ∈

  .3 ()) or with .Figure 2.3 depicts the various positions of into a parallelogram polyomino.From now on, unless otherwise speciied, we always assume that ≥ 1. Let us give a classiication of the polyominoes in P k , based on the position of the cell inside the polyomino. Deinition 37. A polyomino in P k is said to be 1. a lat -parallelogram polyomino if coincides with . The family of these polyominoes is denoted by P k ;2. an up (resp. right) -parallelogram polyomino, if is distinct from and ℎ and end with a step (resp. ). The family of up (resp. right)

-parallelogram polyominoes is denoted by P U k (resp. P R k ).

  Figure 2.8: () A polyomino in P 2 , () a polyomino in P U 2 in which 1 has at least two steps and () a polyomino in P U 2 in which 1 is equal to a step .

	x	x *	x	y	y(x+y) *	x	y(x+y) *	x
				y *	t *	x	t *
				y		yy +	x	y
				z *
						z *
								z *
							z +
	(a)					(b)	(c)

  Proposition 82. Let C be a permutation (resp. polyomino) class, and let M be an -basis of C. Then the -basis of C consists of all permutations (resp. polyominoes) that contain a submatrix in M, and that are minimal (w.r.t. ) for the property. The conclusion then follows by deinition of M being an -basis of C: permutations (resp. polyominoes) not belonging to C are exactly those that contain a submatrix in M.

	S resp.	P ) for this property.
	Proof. By Proposition 55 (resp. 59), the -basis of C is the set of minimal
	permutations (resp. polyominoes) that do not belong to C and are minimal
	w.r.t.

S (resp. P

Macsyma (Pro ject MAC's SYmbolic MAnipulator) is a computer algebra system that was originally developed from 1968 to 1982.

See www.wolfram.com/mathematica.

More in-depth information on the Catalan sequence A000108 is provided in[103]. The reader may also refer to the book by R. P. Stanley[START_REF] Stanley | Enumerative Combinatorics[END_REF], where over 100 diferent interpretations of Catalan numbers addressing various counting problems are provided.

This result was obtained by using Markov chain Monte Carlo methods to generate random 1324-avoiders.

where 3 is lat, 2 is empty and 1 is equal to a step .

Proposition 92. Let be 1 , 2 two polyominoes and let be C = P ( 1 , 2 ). If for every element in 1 ∧ 2 we have that:( 1 ) is a polyomino, or

Proposition 103. The family of 2-convex polyominoes can be described by the avoidance of the following generalised patterns:

The analogy essentially consists in exchanging 0 and 1 in the excluded submatrices

Propagating enumeration results and

Wilf-equivalences with submatrices

The similarities that we observed between the cases of the classes G, H, J and K are not a coincidence. Indeed, they can all be encapsulated in following proposition, which simply pushes the same idea forward to a general setting. Proposition 95. Let be a permutation. Let τ,top (resp. τ,bottom ) be the quasi-permutation matrix obtained by adding a row of 0 entries above (resp. below) the permutation matrix of . Similarly, let τ,right (resp. τ,lef t ) be the quasi-permutation matrix obtained by adding a column of 0 entries on the right (resp. left) of the permutation matrix of . The permutations of S ( τ,top ) (resp. S ( τ,bottom ), resp. S ( τ,right ), resp. S ( τ,lef t )) are exactly the permutations avoiding to which a maximal (resp. minimal, resp. last, resp. irst) element has been added.

Proof. We prove the case of τ,top only, the other cases being identical up to symmetry.

Consider a permutation ∈ S ( τ,top ), and denote by ′ the permutation obtained deleting the maximum of . Assuming that ′ contains , then would contain τ,top , which contradicts ∈ S ( τ,top ); hence ′ ∈ S ( ).

Conversely, consider a permutation ′ ∈ S ( ), and a permutation obtained by adding a maximal element to ′ . Assume that contains τ,top , and consider an occurrence of τ,top in . Regardless of whether or not this occurrence involves the maximum of , it yields an occurrence of in ′ , and hence a contradiction. Therefore, ∈ S ( τ,top ).

The permutation classes S (M 1 ) and S (M 2 ) are also Wilf-equivalent. The same holds replacing τ,top with τ,bottom , τ,right or τ,lef t .

By analogy 1 with the class of convex polyominoes (characterised by the avoidance of and ), we may consider the class C ′ of polyominoes avoiding the two submatrices ′ and ′ deined above. In some sense these objects can be considered as a dual class of convex polyominoes. Figure 3.19() shows a polyomino in C ′ . The avoidance of ′ and ′ also ensures that in a polyomino of C ′ every connected set of 0s has the shape of a convex polyomino, which we callby abuse of notation -a convex 0-polyomino (contained) in . Each of these convex 0-polyominoes has a minimal bounding rectangle, which deines an horizontal (resp. vertical) strip of cells in , where no other convex 0polyomino of can be found. Therefore every polyomino of C ′ can be uniquely decomposed in regions of two types: rectangles all made of 1s (of type ) or rectangles bounding a convex 0-polyomino (of type ). Then, we can map onto a quasi-permutation matrix as follows: each rectangle of type is mapped onto a 0, and each rectangle of type is mapped onto a 1. See an example in Figure 3.19().

Although this representation is non unique, we believe it may be used for the enumeration of C ′ . For a start, it provides a simple lower bound on the number of polyominoes in C ′ whose bounding rectangle is a square. Proposition 109. Let ′ n be the number of polyominoes in C ′ whose bounding rectangle is an × square. For ≥ 2, ′ n ≥ ⌊ n 2 ⌋ ! .

Proof. The statement directly follows from a mapping from permutations of size ≥ 1 to polyominoes in C ′ whose bounding rectangle is an 2 × 2 square, and deined as follows. From a permutation , we replace every entry of its permutation matrix by a 2 × 2 matrix according to the following rules. Every 0 entry is mapped onto a 2 × 2 matrix of type .

The 1 entry in the leftmost column is mapped onto

The 1 entry in the topmost row (if diferent) is mapped onto

Every other 1 entry is mapped onto

This mapping (illustrated in Figure 3.20) guarantees that the set of cells obtained is connected (hence is a polyomino), and avoids the submatrices ′ and ′ , concluding the proof. Let m,n be set of rectangles -binary pictures with all the entries equal to 1 -of dimension × (see Figure 3.21 ()). With = = 2 these objects (also called snake-like polyominoes) have a simple geometrical characterisation. Proposition 110. Every snake-like polyomino can be uniquely decomposed into three parts: a unimodal staircase polyomino oriented with respect to two axis-parallel directions 1 and 2 and two (possibly empty) -shaped polyominoes placed at the extremities of the staircase. These two -shaped polyominoes have to be oriented with respect to 1 , 2 .

We have studied the classes P ( m,n ), for other values of , , obtaining similar characterisations which here are omitted for brevity.

Snakes.

Let us consider the family of snake-shaped polyominoes (briely, snakes) -as that shown in Fig. 3 Let us recall that a stack polyomino is a convex polyomino containing two adjacent corners of its minimal bounding rectangle (see Fig. 3.23 ()). Stack polyominoes form a polyomino class, described by the avoidance of the patterns: