# The number of directed *k*-convex polyominoes

Adrien Boussicault, Simone Rinaldi, Samanta Socci

► To cite this version:

Adrien Boussicault, Simone Rinaldi, Samanta Socci. The number of directed *k*-convex polyominoes. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.511-522, 10.46298/dmtcs.2465 . hal-01337797

HAL Id: hal-01337797

https://hal.science/hal-01337797

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The number of directed $k$-convex polyominoes

Adrien Boussicault<fnref n="1" />, Simone Rinaldi<fnref n="2" /> and Samanta Socci<fnref n="2" />

**Abstract.** We present a new method to obtain the generating functions for directed convex polyominoes according to several different statistics including: width, height, size of last column/row and number of corners. This method can be used to study different families of directed convex polyominoes: symmetric polyominoes, parallelogram polyominoes. In this paper, we apply our method to determine the generating function for directed $k$-convex polyominoes. We show it is a rational function and we study its asymptotic behavior.

**Résumé.** Nous présentons une nouvelle méthode générique pour obtenir facilement et rapidement les fonctions génératrices des polyominos dirigés convexes avec différentes combinaisons de statistiques : hauteur, largeur, longueur de la dernière ligne/colonne et nombre de coins. La méthode peut être utilisée pour énumérer différentes familles de polyominos dirigés convexes: les polyominos symétriques, les polyominos parallélogrammes. De cette façon, nous calculons la fonction génératrice des polyominos dirigés $k$-convexes, nous montrons qu'elle est rationnelle et nous étudions son comportement asymptotique.

**Keywords:** Parallelogram polyomino, directed convex polyomino, degree of convexity, tree, path, generating function.

## 1 Introduction

In the plane $\mathbb{Z} \times \mathbb{Z}$ a cell is a unit square and a polyomino is a finite connected union of cells (see Fig. 1). Polyominoes are defined up to translations. We assume without loss of generality that the south-west corner of its minimal bounding rectangle is placed at (0, 0). A column (row) of a polyomino is the intersection of the polyomino and an infinite strip of cells whose centers lie on a vertical (horizontal) line. A polyomino is said to be column-convex (row-convex) when its intersection with any vertical (horizontal) line is connected. A polyomino is convex if it is both column- and row-convex (see Fig. 1(b)). The semi-perimeter of a polyomino is naturally defined as half the perimeter. As a matter of fact, the semi-perimeter of a convex polyomino is given by the sum of the number of its rows and its columns.

In [11] the authors propose a classification of convex polyominoes in terms of paths internal to polyominoes. A convex polyomino is said to be $k$-convex if every pair of its cells can be connected by a path, internal to the polyomino, with at most $k$ changes of direction. For $k=1$, we have $L$-convex polyominoes, which have been studied by several points of view [11, 12, 13]. In particular in [12] it is shown that the generating function of $L$-convex polyominoes according to the semi-perimeter is rational. For $k=2$

<footnote n="1">¹ LaBRI, Université de Bordeaux, 351 cours de la libération 33405 Talence, France</footnote>

<footnote n="2">² Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, via Roma 56, 53100 Siena, Italy</footnote>
we have the Z-convex polyominoes, which instead have an algebraic generating function [14]. The methods applied for the enumeration of L-convex and Z-convex polyominoes are not easily extendable to the general case, and, as a matter of fact, the enumeration of k-convex polyominoes is an open problem, for $k > 2$. Thus, in order to simplify the enumeration problem, the authors of [3] provide a general method to enumerate an important subclass of k-convex polyominoes, that of k-parallelogram polyominoes, i.e. k-convex polyominoes which are also parallelogram.

Let us recall some basic definitions: a polyomino is said to be *directed* when each of its cells can be reached from a distinguished cell, called the *root* (denoted by $S$), by a path which is contained in the polyomino and uses only north and east unit steps. A polyomino is *directed convex* if it is both directed and convex. The number of directed convex polyominoes with semi-perimeter $n+2$ is known to be equal to $\binom{2n}{n}$ [5, 6, 15]. We recall that a *parallelogram polyomino* is a polyomino whose boundary can be decomposed in two paths, the upper and the lower paths, which are comprised of north and east unit steps and meet only at their starting and final points. It is clear that parallelogram polyominoes are also directed convex polyominoes, while the converse does not hold. It is known that the number of parallelogram polyominoes with semi-perimeter $n+1$ is the $n$th *Catalan number* [17].

In this paper we present a new bijection between directed convex polyominoes and triplets $(F_e, F_s, \lambda)$, where $F_e$ and $F_s$ are forests of trees, and $\lambda$ is a lattice path made of two types of steps, satisfying special constraints. This bijection allows to express the convexity degree of the polyomino in terms of the heights of the trees of $F_e$ and $F_s$. Basing of this bijection, we develop a new method, for the enumeration of directed convex polyominoes, which allows us to control several statistics, including the semi-perimeter, the degree of convexity, the width, the height, the size of the last row/column and the number of corners. Our method eventually let us determine the generating function of directed k-convex polyominoes, for any $k \ge 1$. This is a rational function, and it can be suitably expressed using the *Fibonacci polynomials* [10]. Moreover, we provide the asymptotic behavior for the number of directed k-convex polyominoes.

While in the last years a growing interest was shown in the combinatorial properties of k-convex polyominoes, as certified by [8, 9, 16], the general enumeration problem remains open. Thus we believe that our approach can be used to develop a bijective method for the solution of the problem of enumerating k-convex polyominoes.

For brevity sake, some of the proofs will be omitted. We point out that the full version of the paper containing all the definitions and proofs, with several examples is on the ArXiv [7].

## 2 Notation and preliminaries

Let $P$ be a convex polyomino whose minimal bounding rectangle has dimension $l_1 \times l_2$. We number the $l_1$ columns and the $l_2$ rows from left to right and from bottom to top, respectively.

Thus, we consider the bottom (resp. top) row of $P$ as its first (resp. last) row, and the leftmost (resp. rightmost) column of $P$ as its first (resp. last) column. By convention, we will often write $(i, j)$ to denote the cell of $P$, whose north-west corner has coordinates equal to $(i, j)$. With that convention, the cell is at the intersection of the $i$-th column and the $j$-th row. A *path* is a self-avoiding sequence of unit steps of four types: north $n = (0, 1)$, south $s = (0, -1)$, east $e = (1, 0)$, and west $w = (-1, 0)$. A *path connecting two cells*, $b$ and

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** A path connecting two cells of the polyomino with two changes of direction; a monotone path between two cells of the polyomino with two changes of direction.</figcaption></figure>
c, of a convex polyomino P, is a path, entirely contained in P, which starts from the center of b, and ends at the center of c (see Fig. 1). A path is said to be *monotone* if it is comprised only of steps of two types (see Fig. 1). Let $p = p_1...p_j$ be a path, each pair of steps $p_i p_{i+1}$ such that $p_i \neq p_{i+1}$, $1 \le i < j$, is called a *change of direction* (see Fig. 1). Given $k \in \mathbb{N}$, a convex polyomino is said to be *k-convex* if every pair of its cells can be connected by a monotone path with at most k changes of direction [11]. For the sake of clarity, we point out that a *k-convex* polyomino is also *h-convex* for every $h > k$. We define the *degree of convexity* of a convex polyomino P as the smallest $k \in \mathbb{N}$ such that P is *k-convex*. Figure 1 shows a convex-polyomino with degree of convexity $k = 2$. In this paper we will deal with the class $\mathbb{D}_{\le k}$ (resp. $\mathbb{P}_{\le k}$) of directed *k-convex* polyominoes (resp. *k*-parallelogram polyominoes), i.e. the subclass of *k-convex* polyominoes which are also directed convex polyominoes (resp. parallelogram polyominoes). Given a directed convex polyomino D with a minimal bounding rectangle of size $l_1 \times l_2$, we define $P_D$ to be the parallelogram polyomino obtained from D, extending the side of D with ordinate equal to $l_2$ in the east direction to the point with coordinate $(l_1, l_2)$ and extending the side of D with abscissa equal to $l_1$ in north direction to the point with coordinate $(l_1, l_2)$ (see Fig. 2). Let $b = (i, j)$, $c = (i', j')$ be two cells of D. Without loss of generality, we can suppose that $i \le i'$. Now if $j' < j$, since D is a directed convex polyomino, we can always join b and c by means of a monotone path with at most one change of direction. Therefore, from now on, we will consider the case where $j' \ge j$. Let us define the *bounce paths joining b to c* as the two monotone paths internal to D starting at $(i - \frac{3}{2}, j - \frac{1}{2})$ (resp. at $(i - \frac{1}{2}, j - \frac{3}{2})$) with an east (resp. north) unit step and ending at the center of c, denoted by $r_{b,c}$ (resp. $u_{b,c}$), where every side has maximal length (see Fig. 3(a)).

We observe that the bounce paths joining two cells b and c are slightly different from the paths from b to c, due to the presence of the tails. This is just a precaution to ensure that the two bounce paths are always different, and it will not affect the computation of the degree of convexity. The *minimal bounce path joining b to c* (denoted by $m_{b,c}$) is the bounce path joining b to c with the minimal number of changes of direction. If the two bounce paths joining b to c have the same number of changes of direction, by convention we define the minimal bounce path joining b to c to be the bounce path $r_{b,c}$.

<figure><img src="image_3.png" /><figcaption>Fig. 2: A directed convex polyomino D and its associated parallelogram polyomino $P_D$.</figcaption></figure>

**Proposition 1** Let D be a directed convex polyomino. Given $k \ge 1$, then D is a directed *k*-convex polyomino if and only if S can be connected to each cell of D by means of a path having at most k changes of direction.

Therefore, it is worth defining the *degree of a cell b* of a directed convex polyomino as the number of changes of direction of the minimal bounce path joining S to b.

Given a parallelogram polyomino P, we denote by E rightmost cell of the top row of P. We define the *bounce paths* of P to be the two bounce paths joining S to E and we will denote by $r(P)$ (resp. $u(P)$) the bounce path $r_{S,E}$ (resp. $u_{S,E}$) (see Fig. 3(b), (c)). Henceforth, if no ambiguity occurs, we will write $u$ (resp. $r$) in place of $u(P)$ (resp. $r(P)$). The *minimal bounce path of P* (denoted by $m(P)$ or $m$) is the minimal bounce path joining S to E. The following lemma explains that the minimal bounce path retains all information about the degree of convexity of a parallelogram polyomino.
Figure 4 shows an example of $\Phi$. Let the size of a pair $(T_1, T_2)$ of trees be given by the sum of the sizes of $T_1$ and $T_2$.

**Proposition 3** *The map $\Phi$ is a bijection between parallelogram polyominoes with semi-perimeter $n$ and pairs of trees with size $n$.*

*Proof:* By definition of $\Phi$, each node $x \neq s_1, s_2$ has exactly one father, in fact:

* if $x$ is one of nodes of the top (resp. rightmost) row (resp. column) then its father is $s_2$ (resp. $s_1$);

* otherwise, by construction, there is exactly one topmost node in the same column of $x$ or one rightmost node in the same row of $x$, but not both at the same time.

Since a father always lies above or to the right of its sons, there is no cycle in the graph obtained by means of $\Phi$ and the only two nodes without fathers are $s_1$ and $s_2$ and hence, $\Phi$ produces two ordered trees $T_1$ and $T_2$. The size of $(T_1, T_2)$ is equal to the number of dots enlightened in the parallelogram polyomino plus two (the roots $s_1$ of $T_1$ and $s_2$ of $T_2$), which is exactly equal to the semi-perimeter of the parallelogram polyomino. Now we will prove that $\Phi$ is injective. Let $P_1$ and $P_2$ be two parallelogram polyominoes such that $P_1 \neq P_2$. Since $P_1$ is different from $P_2$ then there exists a first step of the lower path (or the upper path) of $P_1$ different to the corresponding step in $P_2$ and so in one of the two trees of $\Phi(P_1)$ (or of $\Phi(P_2)$) we can find a father with more sons that the corresponding father in the corresponding tree of $\Phi(P_2)$ (or of $\Phi(P_1)$). We deduce that $\Phi(P_1) \neq \Phi(P_2)$. To show surjectivity, we first prove that pairs of trees with size $n$ are bijective to trees with size $n$. In fact we can define a bijection $\Psi$ which builds, starting from a pair of trees $(T_1, T_2)$ a tree $T$, obtained from $T_1$ by adding $T_2$ as its subtree, with the rule that $s_2$ is the first son of $s_1$ (see Fig. 4). Since it is known that parallelogram polyominoes and ordered trees are equinumerous [17], we can conclude that $\Phi$ is a bijection. $\square$

<figure><img src="image_4.png" /><figcaption>Fig. 4: The bijections $\Phi$ and $\Psi$.</figcaption></figure>

Let $r$ and $u$ be the two bounce paths of a parallelogram polyomino $P$. At every change of direction the path $r$ (resp. $u$) individuates an enlightened cell. The sequence of these cells determines a path $d_r$ (resp. $d_u$) in $T_1$ or $T_2$ (see Figure 5). We observe that the last node of this path is $s_1$ or $s_2$ and that its length is not necessarily maximal. By $l(d_r)$ (resp. $l(d_u)$) we denote the length of $d_r$ (resp. $d_u$) and we note that $l(d_r) - 1$ (resp. $l(d_u) - 1$) is the number of changes of direction of $r$ (resp. $u$).

**Lemma 4** Let $P$ be a parallelogram polyomino and $\Phi(P) = (T_1, T_2)$. The following equivalences hold:

i. $h(T_1) = h(T_2) \Leftrightarrow d_r$ and $d_u$ are chains of different trees $\Leftrightarrow l(d_r) = l(d_u)$;

ii. $h(T_1) > h(T_2) \Leftrightarrow d_r$ and $d_u$ are chains of $T_1 \Leftrightarrow |l(d_r) - l(d_u)| = 1$ and $d_r, d_u \in T_1$;

iii. $h(T_2) > h(T_1) \Leftrightarrow d_r$ and $d_u$ are chains of $T_2 \Leftrightarrow |l(d_r) - l(d_u)| = 1$ and $d_r, d_u \in T_2$.

**Proposition 5** Let $P$ be a parallelogram polyomino, and $\Phi(P) = (T_1, T_2)$. The degree of convexity of $P$ is equal to $\max(h(T_1), h(T_2)) - \begin{cases} 1 & \text{if } h(T_1) = h(T_2); \\ 2 & \text{otherwise.} \end{cases}$
<figure><img src="image_5.png" /><figcaption>Fig. 5: The simple paths $d_r$ and $d_u$ associated with the bounce paths $r(P)$ and $u(P)$ respectively.</figcaption></figure>

We are now ready to calculate the generating function for $k$-parallelogram polyominoes, which was determined for the first time in [3], by using a purely analytic method. The following proposition provides a bijective proof of this enumerative result.

**Proposition 6 ([3])** The generating function of $k$-parallelogram polyominoes with respect to the semi-perimeter is given by $P_{\le k} = z^2 \left( \frac{F_{k+2}}{F_{k+3}} \right)^2 - z^2 \left( \frac{F_{k+2}}{F_{k+3}} - \frac{F_{k+1}}{F_{k+2}} \right)^2$, where $F_k$ are the Fibonacci polynomials.

**Proof:** As already mentioned, the function $f = z^2 \left( \frac{F_{k+2}}{F_{k+3}} \right)^2$ is the generating function of pairs of trees with height less than or equal to $k+2$ with respect to their size. According to Proposition 5, to obtain $P_{\le k}$ we need to remove from $f$ the generating function $z^2 \left( \frac{F_{k+2}}{F_{k+3}} - \frac{F_{k+1}}{F_{k+2}} \right)^2$ of pairs $(T_1, T_2)$ of trees with height exactly equal to $k+2$ with respect to their size. $\square$

# 4 Directed $k$-convex polyominoes

Given a parallelogram polyomino $P$, we denote by $\alpha(P)$ (resp. $\beta(P)$) the number of cells in the top row (resp. rightmost column) of $P$ minus one. A monotone path starting with an east step and ending with a south step is said to be a *cut of $P$* if the number of east steps is equal to $\alpha(P) + 1$ and the number of south steps is equal to $\beta(P) + 1$. We can easily check that in a directed convex polyomino $D$, the path $\lambda_D$ starting from the leftmost corner of the top row (with an east step) and following clockwise the boundary of $D$ until it reaches the lowest corner of the rightmost column (with a south step) is a cut of $P_D$. For instance, $D$ being the directed convex polyomino in Fig. 2, $\lambda_D = e^2se^2se^2s^3$.

**Proposition 7** The directed convex polyominoes of semi-perimeter $n+2$ are in bijection with triplets $(F_e, F_s, \lambda)$ such that $F_e$ and $F_s$ are forests and $\lambda$ is a monotone path, starting with an east step and ending with a south step, and having $m_e + 1$ east steps and $m_s + 1$ south steps. The integers $m_e$ and $m_s$ are respectively the numbers of trees in $F_e$ and $F_s$. The sum of the sizes of $F_e$ and of $F_s$ is equal to $n$.
**Proof:** (sketch) A directed convex polyomino $D$ is uniquely determined by $P_D$ and $\lambda_D$, whereas $F_e$ and $F_s$ are obtained from $\Phi(P_D) = (T_1, T_2)$ by removing the roots of $T_1$ and $T_2$ (see Fig.6). $\square$

<figure><img src="image_6.png" /><figcaption>**Fig. 6:** A directed convex polyomino with the corresponding triplet $(F_e, F_s, \lambda)$.</figcaption></figure>

## 4.1 k-convexity constraint

Let $b$ and $c$ be two cells of a given parallelogram polyomino $P$. There may exist a cell starting from which the two paths $r_{b,c}$ and $u_{b,c}$ are superimposed. In this case, we denote such a cell by $J_{b,c}$ ($J$ is for “joining”). Clearly $J_{b,c}$ may even coincide with $b$ and if such cell does not exist, we assume that $J_{b,c}$ coincides with $c$. We denote by $J$ or $J(P)$ the cell $J_{S,E}$.

Let $D$ be a directed convex polyomino; a sequence of cells of $P_D$ is naturally determined by the points where the bounce paths $r(P_D)$ and $u(P_D)$ cross each other. The sequence of these cells (denoted by $L_h = (i_h, j_h)$) starts from $S$ and ends with $J$. Let $M$ be the index such that $L_M = J$. We extend $(L_h)_h$ to a new sequence $(I_h)_h$ by defining $I_{h \le M} = L_h$, and $I_{h > M}$ by the cells where the two superimposed bounce paths change direction. Each cell $I_h$ will be labelled

by $h$. From now on, we will refer to the set of directed convex polyominoes such that $J(P_D) = E$, as flat directed convex polyominoes.

<figure><img src="image_7.png" /><figcaption>**Fig. 7:** The degrees of the cells in a flat and a non flat parallelogram polyomino.</figcaption></figure>

**Corollary 8** Let $D$ be a directed convex polyomino such that the degree of convexity of $P_D$ is $k$. The sequence $(I_h)_h$ has length $k$. If $D$ is flat then $I_k = E$; otherwise $I_k \neq E$ and $I_k$ is the cell where the minimal bounce path $m$ of $P_D$ has the last change of direction.

**Proposition 9** Let $D$ be a directed convex polyomino. Let us consider the cells $I_{h-1} = (i_{h-1}, j_{h-1})$ and $I_h = (i_h, j_h)$. Then we have:

1) each cell $(i, j)$ of $P_D$ (resp. $D$) with $i_{h-1} < i \le i_h$ and $j_{h-1} < j$ has degree $h$;

2) each cell $(i, j)$ of $P_D$ (resp. $D$) with $j_{h-1} < j \le j_h$ and $i_h < i$ has degree $h$;

3) each cell $(i, j)$ of $P_D$ (resp. $D$) with $i_h < i$ and $j_h < j$ has degree greater than $h$.
The content of Proposition 9 is illustrated by Figure 7. Now, given a parallelogram polyomino $P$ with degree of convexity equal to $k$, we define $R_P$ as the set of cells $c = (i, j)$ of $P$ such that $i_{k-1} < i$ and $j_{k-1} < j$.

**Corollary 10** Let $D$ be a directed convex polyomino such that $P_D$ has degree of convexity $k$. Then the cells of $R_{P_D}$ (resp. $R_{P_D} \cap D$) are the only cells with degree $k$ in $P_D$ (resp. $D$).

**Lemma 11** If $D$ is a flat directed convex polyomino, then $R_{P_D}$ is a non empty rectangle.

Let $P$ be a flat parallelogram polyomino with degree of convexity $k$. Let $a$ and $b$ be the width and the height of $R_P$, respectively. We denote by $\lambda_{R_P}$ the cut $ee^{\alpha(P)-a}s^b e^a s^{\beta(P)-b}s$ of $P$, which is precisely the cut of the directed convex polyomino obtained removing $R_P$ from $P$.

## 4.2 Enumeration of directed $k$-convex polyominoes

Now we present a general method, based on Proposition 7, to enumerate several statistics on families of directed convex polyominoes. This method contains 3 steps:

**Step 1:** Determine a combinatorial characterization of the cut $\lambda$ and the two forests $F_e$ and $F_s$ associated with the considered class $C$ of directed convex polyominoes;

**Step 2:** Determine the generating functions with respect to the studied statistics for all the cuts $\lambda$, and for all the trees of $F_e$ and $F_s$ associated with the class $C$;

**Step 3:** The generating function of the class $C$ is then obtained by performing the composition of the generating function of the cuts with all the generating functions of the trees of $F_e$ and $F_s$.

This method is generic and very simple, and it allows us to obtain generating functions for several subclasses of directed convex polyominoes according to several different parameters, such as: the semi-perimeter, the degree of convexity, the width, the height, the size of the last row/column and the number of corners in $D/P_D$. Let us begin with a classical example. We will count directed convex polyominoes according to semi-perimeter, width and height. We point out that these results were first discovered by K. Y. Lin and S. J. Chang in [15] and then by M. Bousquet-Mélou in [6].

**Proposition 12 ([15, 6])** The generating function of directed convex polyominoes according to the semi-perimeter, the width and the height of the polyominoes is
$$ \frac{xyz^2}{\sqrt{(1-(x+y)z)^2-4xyz^2}}. $$

**Proof:** Let $z, x, y$ take into account the semi-perimeter, the width and the height of the polyominoes, respectively. Let us apply the 3 steps of our method:

**Step 1:** According to Proposition 7, directed convex polyominoes are in bijection with triplets $(F_e, F_s, \lambda)$ where: to each east step of $\lambda$ is bijectively associated a tree of $F_e$, except for the last east step of $\lambda$, and to each south step of $\lambda$ is associated a trees of $F_s$, except for the first south step. There is no constraint on the trees of $F_e$ and $F_s$.

**Step 2:** The width (resp. height) of $D$ is given by the number of cells of $P_D$ which are enlightened from north to south (resp. from east to west). By construction of $\Phi$, the cells contributing to the width (resp. height) of $D$ are associated with the nodes having an odd (resp. even) height in $F_e$ (resp. $F_s$) and with the nodes having an even (resp. odd) height in $F_s$ (resp. $F_e$). So we need the two generating functions $T_e$ and $T_s$ for the trees of $F_e$ and $F_s$, respectively. The nodes at odd (resp. even) height in $T_e$ (resp. $T_s$) are labelled by $xz$ and the nodes at even (resp. odd) height are labelled by $yz$. The two generating functions are obtained by solving the following system: $T_e = \frac{xz}{1-T_s}$ and $T_s = \frac{yz}{1-T_e}$, from
which $\mathcal{T}_e(x, y) = \frac{1+(x-y)z-\sqrt{(1+(x-y)z)^2-4xz}}{2}$ and $\mathcal{T}_s(x, y) = \mathcal{T}_e(y, x)$. The generating function for the cut is $\mathcal{G}(e, s, z_e, z_s) = \frac{xz_e yz_s}{1-(e+s)}$, where $z_s$ and $z_e$ represent the first south step and the last east step of the cut, while $e$ and $s$ represent all the other east and south steps of the cut.

**Step 3:** The final generating function is: $\mathcal{G}(\mathcal{T}_e, \mathcal{T}_s, z, z) = \frac{xyz^2}{\sqrt{(1-(x+y)z)^2-4xyz^2}}$. $\square$

The following statement gives a characterization of the class $\mathbb{D}_{\le k}$, which will lead us to the desired generating function.

**Proposition 13** Every directed k-convex polyomino D is uniquely determined by one of the two (mutually exclusive) situations:

1) a k-parallelogram polyomino P and a cut $\lambda$, which is a cut of P, or;

2) a flat $k+1$-parallelogram polyomino P, with degree of convexity $k+1$, and a cut $\lambda$, which is a cut of P such that $\lambda \subseteq \lambda_{R_P}$, where the notation $\lambda \subseteq \lambda_{R_P}$ is used to mean that the path $\lambda_{R_P}$ is weakly above $\lambda$.

Our aim is to use the three steps of our method to obtain the generating function of directed k-convex polyominoes. However, since the characterization of the cut turns out to be quite complex, it will be easier to obtain the desired generating function by difference.

Let $\mathbb{D}_{\le k}^-$ be the class of directed convex polyominoes which are bijective to triplets $(F_e, F_s, \lambda)$ where $\lambda$ is a generic cut, and $F_e$ and $F_s$ are forests with heights less than or equal to $k$, according to the mapping described in Proposition 7. Proposition 13 and the bound on the height of the forests ensure that $\mathbb{D}_{\le k}^-$ is included in $\mathbb{D}_{\le k}$. Now $\mathbb{F}\mathbb{D}_{=k}$ is the set of the flat directed convex polyominoes with degree of convexity $k$. The following result can be proved using Proposition 13 and the bijection $\Phi$.

**Proposition 14** For any integer $k \ge 1$, we have $\mathbb{D}_{\le k+1}^- = \mathbb{D}_{\le k} \sqcup \mathbb{F}\mathbb{D}_{=k+1}$ where $\sqcup$ is the disjoint union.

We just need to determine the generating functions for $\mathbb{D}_{\le k+1}^-$ and $\mathbb{F}\mathbb{D}_{=k+1}$.

**Proposition 15** For any integer $k \ge 1$, the generating function for $\mathbb{D}_{\le k}^-$ is $z^2 \frac{F_{k+1}}{F_{k+2}-zF_k}$ where $z$ takes into account the semi-perimeter.

**Proof:** The g.f. for the cut is $\mathcal{G}(e, s) = \frac{z^2}{1-(s+e)}$. Then, the desired result is $\mathcal{G}(\mathcal{T}_{\le k}, \mathcal{T}_{\le k})$. $\square$

**Proposition 16** For any $k \ge 1$, the generating function for $\mathbb{F}\mathbb{D}_{=k+1}$ according to the semi-perimeter is

$$z^2 \cdot \left( \frac{z^{k+1}}{F_{2k+3}} \right)^2 \cdot \frac{F_{k+2}}{(F_{k+3} - zF_{k+1})}.$$

**Proof:** We will detail the 3 steps of our method:

**Step 1:** Let D be a flat directed polyomino with degree of convexity equal to $k$. Let us describe the trees of $F_e$ and $F_s$ of $P_D$. From Lemma 11 we know that $R_{P_D}$ is a non empty rectangle and $I_k = E$. Let R (resp. C) be the row (resp. column) containing the cell $I_{k-1}$. By construction of $\Phi$, the roots of $F_e$ (resp. $F_s$) are associated with the cells of the topmost (resp. rightmost) row (resp. column) of $P_D$. Hence, the height of the trees depends on the position of their roots:

* if the root is on the left (resp. above) of C (resp. R) the height of the tree is less than or equal to $k$;
* if the root belongs to $C$ (resp. $R$), the height is exactly equal to $k+1$ (the two bounce paths have $k+1$ changes of direction and are the image through $\phi^{-1}$ of chains $d_r$ and $d_u$ of $F_e$ and $F_s$);

* if the root is on the right (resp. left) of $C$ (resp. $R$), the height is less than equal to $k+1$.

Let us now give a characterization of the cuts. In the cuts, we will label the east steps by $e_1$ (resp. $e_2$) if they are mapped onto trees with height less than or equal to $k$ (resp. $k+1$). Similarly, we will label the south steps by $s_1$ (resp. $s_2$) if they are mapped onto trees with height less than or equal to $k$ (resp. $k+1$). Moreover, the first south (resp. last east) step of the cut is labelled $s_2$ (resp. $e_2$). Since these two steps are not mapped onto a tree, at the end of the process, we will obtain a bad generating function $G'$ for the cut. The correct generating function is then obtained by multiplying $G'$ by $\frac{z_e z_s}{e_2 s_2}$. We can use this trick because all the cuts have at least one south step and one east step. Since $D$ is flat, the cut contains two special steps $u_e$ and $u_s$ in the columns $C$ and $R$, respectively. As $D$ is exactly $k+1$-convex, from Corollary 10 we have that $R_{P_D} \cap D$ is non empty. We also observe that in the cut $u_e$ precedes $u_s$. Let $p_l, \tau$ and $p_r$ be 3 paths such that $p_l \cdot u_e \cdot \tau \cdot u_s \cdot p_r$ is the cut $\lambda$.

The path $p_l$ can be empty or it starts with an east step followed by any sequence of east/south steps. East steps are mapped onto trees having height less then or equal to $k$, so they are labelled by $e_1$. South steps are mapped onto trees having height less then or equal to $k+1$, so they are labelled by $s_2$. So, an unambiguous regular expression describing $p_l$ is $1 + e_1(e_1 + s_2)^*$. For

<figure><img src="image_8.png" /><figcaption>**Fig. 8:** A directed convex polyomino $D$ where the paths $p_l, \tau$ and $p_r$ of $\lambda_D$ are highlighted.</figcaption></figure>

similar argument, a regular expression for $p_r$ is $1 + s_1(s_1 + e_2)^*$. Consider now $\tau$: all south and east steps are mapped onto trees with height less then or equal to $k+1$, so $\tau$ is a word in $e_2$ and $s_2$. Previously we have seen that there is at least one cell in $R_{P_D} \cap D$, so $\tau$ should contain at least an occurrence of $e_2$ and $s_2$. An unambiguous regular expression for $\tau$ is $s_2^*e_2(e_2 + s_2)^*s_2e_2^*$. Now we just have to remark that the steps $u_e$ and $u_s$ are mapped onto trees having an height exactly equal to $k+1$.

**Step 2:** The generating function $G(e_1, s_1, e_2, s_2, u_e, u_s, z_e, z_s)$ for the cut $p_l \cdot u_e \cdot \tau \cdot u_s \cdot p_r$ is

$$ \frac{z_e z_s}{e_2 s_2} \cdot \left[ \left( 1 + \frac{e_1}{1 - e_1 - s_2} \right) \cdot u_e \cdot \frac{e_2 s_2}{(1 - e_2) \cdot (1 - e_2 - s_2) \cdot (1 - s_2)} \cdot u_s \cdot \left( 1 + \frac{s_1}{1 - s_1 - e_2} \right) \right], $$

which is equal to $\frac{1}{1-e_1-s_2} \cdot \frac{z_e z_s u_e u_s}{1-e_2-s_2} \cdot \frac{1}{1-s_1-e_2}$. The generating function for the trees associated with $s_1$ and $e_1$ (resp. $s_2$ and $e_2$) is $T_{\le k}$ (resp. $T_{\le k+1}$), and the generating function for the trees associated with $u_e$ and $u_s$ is $T_{=k+1}$.

**Step 3:** The final generating function is $G(T_{\le k}, T_{\le k}, T_{\le k+1}, T_{\le k+1}, T_{=k+1}, T_{=k+1}, z, z)$ and is equal to

$$ \left( \frac{T_{=k+1}}{1-T_{\le k}-T_{\le k+1}} \right)^2 \cdot \frac{z^2}{1-2T_{\le k+1}} = z^2 \cdot \left( \frac{z^{k+1}}{F_{2k+3}} \right)^2 \cdot \frac{F_{k+2}}{(F_{k+3}-zF_{k+1})}. \quad \square $$

<figure><img src="image_9.png" /></figure>

As a consequence of Propositions 14, 15 and 16 we have

**Proposition 17** For $k=0$ the generating function for directed $k$-convex polyominoes is equal to $\frac{z^2 \cdot (1+z)}{1-z}$, while for any $k \ge 1$, the generating function for directed $k$-convex polyominoes according to the semi-perimeter is equal to $z^2 \cdot \left( \frac{F_{k+2}}{F_{2k+3}} \right)^2 \cdot F_{2k+2}$.
**Proof:** We just observe that directed 0-convex polyominoes are precisely vertical and horizontal bars. For $k \ge 1$, the result can be obtained as the difference of the generating functions of $\mathcal{D}_{\le k+1}$ and $\mathcal{FD}_{=k+1}$. $\square$

# 5 Asymptotic behavior

It is now interesting to study some facts about the asymptotic behavior of the sequence $(d_{n, \le k})_{n, k}$ of directed $k$-convex polyominoes with semi-perimeter $n$.

**Proposition 18** *The number $d_{n, \le k}$ of directed $k$-convex polyominoes with semi-perimeter $n$ grows like $C_k \cdot (4 \cos^2(\pi/2k + 3))^n \cdot n$, where $C_k$ is a $k$-dependent constant.*

**Proof:** Since $\mathcal{D}_{\le k}(z) = z^2 \frac{(F_{k+2})^2 (F_{2k+2})}{(F_{2k+3})^2}$ is a rational function, it is known that the asymptotic form of the coefficients is $d_{n, \le k} = [z^n]\mathcal{D}_{\le k}(z) \sim C_k \cdot \mu(k)^n \cdot n$ where $C_k$ is a $k$-dependent constant, $\mu(k)$ is given by $1/d_{2k+3}$, where $d_{2k+3}$ is the smallest real root of $F_{2k+3}$. The fact that there is a double pole in $\mathcal{D}_{\le k}$ is responsible for the factor $n$. In [10] the authors observe that the roots of $F_k(z) = 0$ are $(4 \cos^2(j\pi/k))^{-1}$, for $1 \le j < k/2$. In particular the reciprocals of the roots of $F_{2k+3}(z) = 0$ are $(4 \cos^2(j\pi/2k + 3))$, for $1 \le j \le k+1$. With basic calculus one can easily prove that the biggest reciprocal occurs for $j=1$, and so $\mu(k) = 4 \cos^2(\pi/2k + 3)$. $\square$

**Proposition 19** *Let $\mathcal{D}_{\le k}$ and $\mathcal{D}$ be the generating functions of directed $k$-convex polyominoes and of directed convex polyominoes with respect to the semi-perimeter, respectively. Then, $\lim_{k \to +\infty} \mathcal{D}_{\le k} = \mathcal{D}$.*

# 6 Conclusions and further work

In this paper we present a general method to calculate generating functions for different families of directed convex polyominoes with respect to several statistics, including the degree of convexity. This allows to solve the problem of enumerating directed $k$-convex polyominoes, which was presented in [3] as an open problem.

Our idea is that, for any statistic on directed convex polyominoes that can be read on the associated trees or on the cut, then our method can suitably be applied to obtain a generating function according to these parameters. We believe that our method can be applied in several different enumeration problems related with directed convex polyominoes, mainly because in Proposition 7 the sets of trees and the cut are not constrained. Moreover, Proposition 7 can be used to write out efficient algorithms to generate directed convex polyominoes with different combinations of fixed constraints. As a matter of fact, we used our method to implement a code (i) in the open-source software Sage [18, 19] for the enumeration of directed convex polyominoes. The code will be soon available in a future Sage release.

Moreover, we would like to point out that the main bijection and the general approach can be expressed using the formalism of the theory of Species [4]. For example, by using our bijection, we can define the species of directed convex polyominoes by $X^2 \cdot \sum_{k \ge 0} (A_L + A_L)^k$ where $X$, and $A_L$ are respectively the species of singletons and trees.

There are several guidelines for further research. One is to study the probability distributions of the convexity degree for directed convex polyominoes with a fixed semi-perimeter. Moreover, directed convex polyominoes can be seen as special kind of tree-like tableaux and the cut represents the states of the PASEP

<footnote>(i) An implementation of $k$-directed polyominoes in Sage: http://trac.sagemath.org/ticket/17178.</footnote>
(cf. [2] for tree-like tableaux context and definitions). So, our aim is to generalize Proposition 7 for tree-
like tableaux. In tree-like tableaux $T$ associated with directed convex polyominoes, the area counts the
number of some patterns in the permutation associated with $T$. We can try to obtain some generating
function counting the area statistic.

Acknowledgements

The authors are grateful to Tony Guttmann and Mireille Bousquet-Mélou for their help in the writing
process of this article.

References

[1] Aval, J. C. and Boussicault, A. and Bouvel, M. and Silimbani, M., Combinatorics of non-ambiguous trees, *Adv. in Appl. Math.* 56, 78–108 (2014).

[2] Aval, J. C. and Boussicault, A. and Nadeau, P., Tree-like tableaux, *Electron. J. Combin.* 20, (2013).

[3] Battaglino, D. and Fedou, J. M. and Rinaldi, S. and Socci, S., The number of k-parallelogram polyominoes, *DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics* (2013).

[4] F. Bergeron, G. Labelle, P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press Encyclopedia of Mathematics and its Applications (1998)

[5] Bousquet-Mélou, M., A Method for the Enumeration of Various Classes of Column-Convex Polygons, *Discrete Math.* 154 1-25 (1996).

[6] Bousquet-Mélou, M., Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères, *RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications*, 3, 26 205-219 (1992).

[7] Boussicault, A. and Rinaldi, S. and Socci S., The number of directed k-convex polyominoes, arXiv:1501.00872 [math.CO].

[8] S. Brocchi, G. Castiglione, P. Massazza, On computing the degree of convexity of polyominoes, *Electronic Journal of Combinatorics* 22(1) (2015), P1.7.

[9] S. Brocchi, G. Castiglione, P. Massazza, On the Exhaustive Generation of k-Convex Polyominoes, Proceedings of GASCom 2014, June 23-25 2014, Bertinoro (Italy).

[10] de Bruijn, N. G. and Knuth, D. E. and Rice, S. O., The average height of planted plane trees, *Graph Theory and Computing*, Academic Press, Inc, New York and London 15-22 (1972).

[11] Castiglione, G. and Restivo, A., Reconstruction of L-convex Polyominoes, *Electronic Notes in Discrete Mathematics* 12 290–301 (2003), 9th International Workshop on Combinatorial Image Analysis, ISSN 1571-0653.

[12] Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S., Combinatorial aspects of L-convex polyominoes, *European J. Combin.*, vol. 28, (2007), 1724-1741.

[13] Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S., Enumeration of L-convex polyominoes by rows and columns, *Theor. Comput. Sci.*, vol. 347, (2005), 336-352.

[14] Duchi, E., Rinaldi, S., Schaeffer, G., The number of Z-convex polyominoes, *Adv. Appl. Math.* 4 (2008) 54-72.

[15] Lin, K. Y. and Chang, S. J., Rigorous results for the number of convex polygons on the square and honeycomb lattices, *Journal of Physics A: Mathematical and General*, 11, 21 2635 (1988).

[16] A. Micheli, D. Rossin, Counting k-convex polyominoes, *Electronic Journal of Combinatorics*, 20(2) (2013), P56.

[17] Stanley, R. P., *Enumerative Combinatorics*, Vol. 2, Cambridge University Press, Cambridge (1999).

[18] The Sage-Combinat community, *Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics*, http://combinat.sagemath.org, 2014.

[19] W. A. Stein et al., *Sage Mathematics Software (Version 6.4-beta6)*, The Sage Development Team, 2014, http://www.sagemath.org.