--- author: - 'Adrien Boussicault, Simone Rinaldi and Samanta Socci' nocite: '[@*]' title: 'The number of directed $k$-convex polyominoes' --- 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. Polyominoes are defined up to translations. Since they have been introduced by Golomb @golomb, polyominoes have become quite popular combinatorial objects and have shown relations with many mathematical problems, such as tilings @BN, or games @gardner among many others. Two of the most relevant combinatorial problems concern the enumeration of polyominoes according to their <span>*area*</span> (i.e., number of cells) or <span>*semi-perimeter*</span>. These two problems are both difficult to solve and still open. As a matter of fact, the number $a_n$ of polyominoes with $n$ cells is known up to $n = 56$ @jensen and asymptotically, these numbers satisfy the relation $\lim _n (a_n)^{1/n} = \mu, 3.96<\mu<4.64$, where the lower bound is a recent improvement of @BMRR. In order to probe further, several subclasses of polyominoes have been introduced on which to hone enumeration techniques. Some of these subclasses can be defined using the notions of connectivity and directedness: among them we recall the convex, directed, parallelogram polyominoes, which will be considered in this paper. Formal definitions of these classes will be given in the next section. In the literature, these objects have been widely studied using different techniques. Here, we just outline some results which will be useful for the reader of this paper: <span>(i)</span> The number $f_n$ of convex polyominoes with semi-perimeter $n \geq 2$ was obtained by Delest and Viennot in @DV, and it is: $$f_{n+2} = (2n + 11)4^n - 4(2n + 1)\binom{2n}{n}, \qquad n \geq 0; \qquad f_0 = 1, \qquad f_1 = 2.$$ <span>(ii)</span> The number of directed convex polyominoes with semi-perimeter $n+2$ is equal to ${{2n} \choose n}$ @BousquetMelou96amethod [@Bousquet1992; @LinChang88]. <span>(iii)</span> The number of parallelogram polyominoes with semi-perimeter $n+1$ is the $n$th <span>*Catalan number*</span> @DV. In this paper we present a new general approach for the enumeration of directed convex polyominoes, which let us easily control several statistics. This method relies on a bijection between directed convex polyominoes with semi-perimeter equal to $n+2$ and triplets $(F_e,F_s,\lambda)$, where $F_e$ and $F_s$ are forests of $m_e$ and $m_s$ trees, respectively, with a total number of nodes equal to $n$, and $\lambda$ is a lattice path made of $m_e+1$ east and $m_s+1$ south unit steps (see Proposition \[prop:directed\]). Basing on this bijection, we develop a new method for the enumeration of directed convex polyominoes, according to several different parameters, including the semi-perimeter, the degree of convexity, the width, the height, the size of the last row/column and the number of corners. We point out that most of these statistics have already been considered in the literature (see, for instance @BFR [@BousquetMelou96amethod; @LinChang88]), but what makes our method interesting, to our opinion, is that every statistic which can be read on the two forests $F_e$ and $F_s$, can be in principle computed. Basically, with $\cal C$ being a class of directed-convex polyominoes, our method consists of three steps: 1. provide a characterization of the two forests $F_e,F_s$ and of the path $\lambda$, for the polyominoes in $\cal C$; 2. determine the generating function – according to the considered statistics – of the forests $F_e,F_s$ and of the paths $\lambda$, for the polyominoes in $\cal C$; 3. obtain the generating function of $\cal C$ by means of the composition of the generating function of the paths $\lambda$ with the generating functions of the trees of $F_e,F_s$. Furthermore, the previously described bijection can be easily translated into a (new) bijection between directed convex polyominoes and Grand-Dyck paths (or bilateral Dyck paths). Other bijections between these two classes of objects can be found in the literature, see for instance, @BFR and @Bousquet1992. The most important and original result of the paper consists in applying our method to the enumeration of <span>*directed $k$-convex polyominoes*</span>, i.e. directed convex polyominoes which are also $k$-convex. Let us recall that in @Castiglione2003290 it was proposed a classification of convex polyominoes based on the number of changes of direction in the paths connecting any two cells of a polyomino. More precisely, a convex polyomino is <span>*$k$-convex*</span> if every pair of its cells can be connected by a monotone path with at most $k$ changes of direction. For $k=1$ we have the $L$-convex polyominoes, where any two cells can be connected by a path with at most one change of direction. In the recent literature $L$-convex polyominoes have been considered from several points of view: in @Castiglione2003290 it is shown that they are a well-ordering according to the sub-picture order; in @CFRR the authors have investigated some tomographical aspects, and have discovered that $L$-convex polyominoes are uniquely determined by their horizontal and vertical projections. Finally, in @lconv [@CFRR2] it is proved that the number $l_n$ of $L$-convex polyominoes having semi-perimeter equal to $n + 2$ satisfies the recurrence relation $$l_{n+2} = 4 l_{n+1} - 2 l_{n}, \qquad n\geq 1, \qquad l_0 = 1, \qquad l_1 = 2 \qquad l_2 = 7.$$ For $k=2$ we have $2$-convex (or $Z$-convex) polyominoes, such that each two cells can be connected by a path with at most two changes of direction. Unfortunately, $Z$-convex polyominoes do not inherit most of the combinatorial properties of $L$-convex polyominoes. In particular, their enumeration resisted standard enumeration techniques and it was obtained in @DRS by applying the so-called <span>*inflation method*</span>. The authors proved that the generating function of $Z$-convex polyominoes with respect to the semi-perimeter is: $$\frac{2z^4(1-2z)^2d(z)} {(1-4z)^2(1-3z)(1-z)}+\frac{z^2(1-6z+10z^2-2z^3-z^4)} {(1-4z)(1-3z)(1-z)},$$ where $ d(z)=\frac{1}{2} \left( 1-2z-\sqrt{1-4z} \right) $ is the generating function of Catalan numbers @DRS. Hence the number of Z-convex polyominoes having semi-perimeter $n+2$ grows asymptotically as $\frac{n}{24} 4^n$. However, the solution found for $2$-convex polyominoes seems to be not easily generalizable to a generic $k$, hence the problem of enumerating $k$-convex polyominoes for $k>2$ is still open and difficult to solve. Recently, some efforts in the study of the asymptotic behavior of $k$-convex polyominoes have been made by Micheli and Rossin in @MR. Thus, in order to simplify the problem of enumerating polyominoes satisfying the $k$-convexity constraint, the authors of @BatFedRinSoc 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. In this case, the authors prove that the generating function is rational for any $k\geq 0$, and it can be expressed as follows: $$\label{eq:kparal} 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* are defined by the following recurrence relation $$F_0 = 0, \hspace{.5cm} F_1 = 1 \hspace{.5cm} \mbox{ and } \hspace{.5cm} F_{k+2} = F_{k+1} - z F_{k} \hspace{.5cm} \text{ for } \hspace{.5cm} k\ge0.$$ At the end of @BatFedRinSoc the authors observe that in @BruKnuRic it is shown that the generating function of trees with height less than or equal to $k$ can be also expressed in terms of the Fibonacci polynomials, and it is precisely equal to $$\label{eq:parallelogram} \sum_{j\ge0} t_{j,\le k} z^j = \frac{z F_{k}}{F_{k+1}}.$$ Thus, considering (\[eq:parallelogram\]), it was proposed the problem of finding a bijection between $k$-parallelogram polyominoes and pairs of trees having height at most $k+2$, minus pairs of trees having both height exactly equal to $k+2$. As already mentioned, in this paper we succeed in solving this problem, as a specific sub-case of a more general framework: indeed we are able to provide a bijective proof for the number of directed $k$-convex polyominoes. In order to reach this goal, we rely on the observation that our bijection can be used to express the convexity degree of the polyomino in terms of the heights of the trees of the forests $F_e$ and $F_s$. Basing on this observation, the application of our method eventually let us determine the generating function of directed $k$-convex polyominoes, for any $k\geq 1$. This is a rational function, which be suitably expressed, again, in terms of the Fibonacci polynomials. More precisely, we prove that, for every $k\geq 1$, the generating function of directed $k$-convex polyominoes according to the semi-perimeter is equal to: $$\label{eq:kdirconv} z^2\, \left( \frac{F_{k+2}}{F_{2k+3}} \right)^2\, F_{2k+2}.$$ We point out that (\[eq:kdirconv\]) is the first result in the literature concerning the $k$-convexity constraint on directed-convex polyominoes. Due to the rationality of the generating function we can then apply standard techniques to provide the asymptotic behavior for the number of directed $k$-convex polyominoes. Moreover, if we restrict ourselves to the case of parallelogram polyominoes, we observe that our bijection reduces to a bijection between parallelogram polyominoes with semi-perimeter and pairs of trees, and this gives a simple tool to present a combinatorial proof for (\[eq:kparal\]). Notation and preliminaries ========================== In this section we recall some basic definitions about polyominoes, and other combinatorial objects, which will be used in the rest of the paper. First, we point out that, in the representaion of polyominoes, we use the convention that the south-west corner of the 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. Figure \[polyominoes\]$(b)$, $(c)$ show a column convex and a row convex polyomino, respectively. A polyomino is *convex* if it is both column and row convex (see Fig. \[polyominoes\]$(d)$). The *semi-perimeter* of a polyomino is naturally defined as half the perimeter, while the *area* is the number of its cells. 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. ![Examples of polyominoes. \[polyominoes\]](polyominoesq){width=".7\textwidth"} 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 is said to be *monotone* if it is comprised only of steps of two types. 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. We recall that a *<span><span>parallelogram polyomino</span></span>* 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. Figure \[parallelograms\] shows all directed convex polyominoes with semi-perimeter equal to $4$, where only the rightmost polyomino is not a parallelogram one. ![The six directed convex polyominoes with semi-perimeter $4$. \[parallelograms\]](parallelograms){width=".5\textwidth"} Now, we introduce another class of objects, which will be useful in this paper. An *ordered tree* is a rooted tree for which an ordering is specified for the children of each vertex. In this paper we shall say simply *tree* instead of *ordered tree*. The *size* of a tree is the number of nodes. The *height* $h(T)$ of a tree $T$ is the number of nodes on a maximal simple path starting at the root of $T$. $$\begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,0) -- (0, -1); \draw[color=black, line width={1}] (0,-1) -- (0, -2); \draw[color=black, line width={1}] (0,-2) -- (0, -3); \foreach \x/\y in { 0/0, 0/-1, 0/-2, 0/-3 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,0) -- (0, -1); \draw[color=black, line width={1}] (0,-1) -- (-0.5, -2); \draw[color=black, line width={1}] (0,-1) -- (0.5, -2); \foreach \x/\y in { 0/0, 0/-1, 0.5/-2, -0.5/-2 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (-0.5,-1) -- (-0.5, -2); \draw[color=black, line width={1}] (0,0) -- (-0.5, -1); \draw[color=black, line width={1}] (0,0) -- (0.5, -1); \foreach \x/\y in { 0/0, 0.5/-1, -0.5/-1, -0.5/-2 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0.5,-1) -- (0.5, -2); \draw[color=black, line width={1}] (0,0) -- (-0.5, -1); \draw[color=black, line width={1}] (0,0) -- (0.5, -1); \foreach \x/\y in { 0/0, 0.5/-1, -0.5/-1, 0.5/-2 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,0) -- (-1, -1); \draw[color=black, line width={1}] (0,0) -- (0, -1); \draw[color=black, line width={1}] (0,0) -- (1, -1); \foreach \x/\y in { 0/0, 1/-1, 0/-1, -1/-1 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array}$$ All trees with size equal to $4$ are shown in Fig. \[fig:ordered\_tree\_size\_3\], while Figure \[fig:ordered\_tree\_heigt\_4\] depicts some trees with height equal to $4$. $$\begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,0) -- (0, -1); \draw[color=black, line width={1}] (0,-1) -- (0, -2); \draw[color=black, line width={1}] (0,-2) -- (0, -3); \foreach \x/\y in { 0/0, 0/-1, 0/-2, 0/-3 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,1) -- (0, 0); \draw[color=black, line width={1}] (-0.5,-1) -- (-0.5, -2); \draw[color=black, line width={1}] (0,0) -- (-0.5, -1); \draw[color=black, line width={1}] (0,0) -- (0.5, -1); \foreach \x/\y in { 0/1, 0/0, 0.5/-1, -0.5/-1, -0.5/-2 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array} \begin{array}{c} \begin{tikzpicture}[scale=.5] \draw[color=black, line width={1}] (0,0) -- (-1, -1); \draw[color=black, line width={1}] (0,0) -- (0, -1); \draw[color=black, line width={1}] (0,0) -- (1, -1); \draw[color=black, line width={1}] (-1,-1) -- (-1, -2); \draw[color=black, line width={1}] (1,-1) -- (1, -2); \draw[color=black, line width={1}] (1,-2) -- (0.5, -3); \draw[color=black, line width={1}] (1,-2) -- (1.5, -3); \foreach \x/\y in { 0/0, -1/-1, 0/-1, 1/-1, -1/-1, -1/-2, 1/-2, .5/-3, 1.5/-3 }{ \filldraw[color=black] (\x, \y) circle ({.15*{1}}); } \end{tikzpicture} \end{array}$$ Now, let $t_{n,\le k}$ be the number of trees of size $n$ and height less than or equal to $k$. In @BruKnuRic the generating function $\mathcal{T}_{\le k}$ of trees with height less than or equal to $k$ is given by N.G. de Bruijn, D.E. Knuth and S.O. Rice: $$\mathcal{T}_{\le k} = \sum_{j\ge0} t_{j,\le k} z^j = \frac{z F_{k}}{F_{k+1}}$$ where $F_{k}$ are the Fibonacci polynomials. The *Fibonacci polynomials* are defined by the following recurrence relation: $$F_0 = 0, \hspace{.5cm} F_1 = 1 \hspace{.5cm} \mbox{ and } \hspace{.5cm} F_{k+2} = F_{k+1} - z F_{k} \hspace{.5cm} \text{ for } \hspace{.5cm} k\ge0.$$ This result can be simply explained by observing that a tree with height less than or equal to $k+1$ can be obtained by taking a root node and attaching zero or more subtrees each of which has height less than or equal to $k$. Hence, $$\mathcal{T}_{\leq k+1} = \sum_{j\ge 0} z ( \mathcal{T}_{\leq k} )^j = \frac{z}{1- \mathcal{T}_{\leq k}} .$$ Now, we can easily check that $\mathcal{T}_{\leq k} = \frac{z F_k}{F_{k+1}}$ is the correct solution. Since $F_k$ is a sequence of the first order, it is easy to obtain the formula: $$F_k \, = \, \frac{1}{\sqrt{1-4z}} \left( \left( \frac{ 1+\sqrt{1-4z} }{ 2 } \right)^k - \left( \frac{ 1-\sqrt{1-4z} }{ 2 } \right)^k \right).$$ We define by $\mathcal{T}_{=k}$ the generating function of trees with height equal to $k$. Easily we can obtain $\mathcal{T}_{=k}$ as the difference between the generating function $\mathcal{T}_{\leq k}$ of the class of trees with height less than or equal to $k$ and the generating function $\mathcal{T}_{\leq k-1}$ of the class of trees having height less than or equal to $k-1$; namely, $\mathcal{T}_{=k} = \mathcal{T}_{\leq k} - \mathcal{T}_{\leq k-1}$. It is possible to obtain $\mathcal{T}_{=k}$ in a different way: let $T$ be a tree having height equal to $k$, and denote by $e$ the rightmost node of $T$ having height $k$ with respect to the root of $T$. We consider the maximal chain starting at $e$ and ending at the root of $T$. Now each node of this chain (different from the node $e$) having height equal to $k-i+1$ (with $i=2,\ldots k$) can be considered the root of two trees having heights $i$ and $i-1$, respectively (see Figure \[fig:tree\_height\_k\]). This argument leads to a bijection between trees with height equal to $k$ and the sequence $(T_1,T_2,\ldots,T_{2(k-1)})$ of trees such that $T_{i}$ and $T_{i+1}$ are trees having height $i$ and $i-1$, respectively. Hence, $$\mathcal{T}_{=k} = z\prod_{i=2}^k \mathcal{T}_{\leq i} \mathcal{T}_{\leq i-1} z^{-1} = z\prod_{i=2}^{k} z \frac{\cancel{F_i}}{F_{i+1}} \frac{F_{i-1}}{\cancel{F_i}} = \frac{z^k}{F_{k}F_{k+1}}.$$ $ \begin{array}{c} \begin{tikzpicture}[scale=.5] \newcommand{\sizeGridTree}{.3} \draw[color=black, line width={1}] (-3*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree, 6*\sizeGridTree); \draw[color=black, line width={1}] (-1*\sizeGridTree,0*\sizeGridTree) -- (0*\sizeGridTree, 2*\sizeGridTree); \draw[color=black, line width={1}] (1*\sizeGridTree,0*\sizeGridTree) -- (0*\sizeGridTree,2*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,0*\sizeGridTree) -- (5*\sizeGridTree,2*\sizeGridTree); \draw[color=black, line width={1}] (0*\sizeGridTree,2*\sizeGridTree) -- (0*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,2*\sizeGridTree) -- (5*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (7*\sizeGridTree,2*\sizeGridTree) -- (5*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (9*\sizeGridTree,2*\sizeGridTree) -- (5*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (11*\sizeGridTree,2*\sizeGridTree) -- (12*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (13*\sizeGridTree,2*\sizeGridTree) -- (12*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (0*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (9*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (12*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \foreach \x/\y in { -1/0, 1/0, 3/0, 5/0, 3/2, 5/2, 7/2, 9/2, 11/2, 13/2, 0/4, 3/4, 5/4, 9/4, 12/4, 5/6, -3/4 }{ \filldraw[color=black] (\x*\sizeGridTree, \y*\sizeGridTree) circle ({.15*{1}}); } \draw[color=red, line width={1}] (5*\sizeGridTree,0*\sizeGridTree) -- (5*\sizeGridTree,2*\sizeGridTree); \draw[color=red, line width={1}] (5*\sizeGridTree,2*\sizeGridTree) -- (5*\sizeGridTree,4*\sizeGridTree); \draw[color=red, line width={1}] (5*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \foreach \x/\y in { 5/0, 5/2, 5/4, 5/6 }{ \filldraw[color=red] (\x*\sizeGridTree, \y*\sizeGridTree) circle ({.15*{1}}); } \node[color=red, below=1pt] at (5*\sizeGridTree,0*\sizeGridTree) {$e$}; \end{tikzpicture} \end{array} { \ext@arrow 9999{\longleftrightarrowfill@}{}{\hspace{.5cm}}}{} \begin{array}{c} \begin{tikzpicture}[scale=.5] \newcommand{\sizeGridTree}{.3} \draw[color=black, line width={1}] (-3*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree, 6*\sizeGridTree); \draw[color=black, line width={1}] (-1*\sizeGridTree,0*\sizeGridTree) -- (0*\sizeGridTree, 2*\sizeGridTree); \draw[color=black, line width={1}] (1*\sizeGridTree,0*\sizeGridTree) -- (0*\sizeGridTree,2*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,0*\sizeGridTree) -- (5*\sizeGridTree,2*\sizeGridTree); \draw[color=black, line width={1}] (0*\sizeGridTree,2*\sizeGridTree) -- (0*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,2*\sizeGridTree) -- (5*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (9*\sizeGridTree,2*\sizeGridTree) -- (7*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (11*\sizeGridTree,2*\sizeGridTree) -- (7*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (13*\sizeGridTree,2*\sizeGridTree) -- (14*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (15*\sizeGridTree,2*\sizeGridTree) -- (14*\sizeGridTree,4*\sizeGridTree); \draw[color=black, line width={1}] (0*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (3*\sizeGridTree,4*\sizeGridTree) -- (5*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (11*\sizeGridTree,4*\sizeGridTree) -- (7*\sizeGridTree,6*\sizeGridTree); \draw[color=black, line width={1}] (14*\sizeGridTree,4*\sizeGridTree) -- (7*\sizeGridTree,6*\sizeGridTree); \foreach \x/\y in { -1/0, 1/0, 3/0, 3/2, 5/2, 9/2, 11/2, 13/2, 15/2, 0/4, 3/4, 5/4, 11/4, 14/4, 5/6, -3/4 }{ \filldraw[color=black] (\x*\sizeGridTree, \y*\sizeGridTree) circle ({.15*{1}}); } \foreach \x/\y in { 5/2, 5/4, 5/6 }{ \filldraw[color=red] (\x*\sizeGridTree, \y*\sizeGridTree) circle ({.15*{1}}); } \foreach \x/\y in { 7/2, 7/4, 7/6 }{ \filldraw[color=red] (\x*\sizeGridTree, \y*\sizeGridTree) circle ({.15*{1}}); } \end{tikzpicture} \end{array} $ Now, using the previous argument, we provide a different proof for the result of Proposition \[prop:two\_way\_fk\] (already obtained in $\cite{BruKnuRic}$). \[prop:two\_way\_fk\] Let $F_k$ be the Fibonacci polynomials. We have: $$F_k^2 - F_{k+1}F_{k-1} = z^{k-1}.$$ From the previous result we know that $\mathcal{T}_{=k}=\mathcal{T}_{\leq k}-\mathcal{T}_{\leq k-1}=\frac{z^k}{F_{k}F{k+1}}$, whence $\frac{zF_{k}}{F_{k+1}} - \frac{zF_{k-1}}{F_{k}}=\frac{z^k}{F_{k}F_{k+1}}$. So we can conclude the statement. We recall that an *ordered forest* (briefly a *forest*) is a $t$-uple of ordered trees. The size of a forest is the sum of the sizes of its trees. It is known that the forests of size $n$ are in bijection with the trees of size $n+1$: to uniquely obtain a forest from a tree, we just need to remove the root of the tree. A bijective construction for directed convex polyominoes ======================================================== We start presenting a map $\Phi$, which builds a pair of forests from a given parallelogram polyomino. We point out that the mapping $\Phi$ is borrowed from @abbs14. In a parallelogram polyomino $P$, let $V_P$ be the set of dots defined as follows: - we enlighten $P$ from east to west and from north to south; - we put a dot in the enlightened cells of $P$ except for the rightmost cell (denoted by $E$) of the top row of $P$. We define the pair of forests $\Phi(P)=(F_e,F_s)$ using the following rules: - the set of nodes of $F_e$ and $F_s$ is $V_P$ and the roots of the trees of $F_e$ (resp. $F_s$) are the dots in the cells of the top row (resp. rightmost column) of $P$; - in a row (resp. column) of $P$, except for the top row and the rightmost column, the rightmost (resp. topmost) node is the father of each other node in the same row (resp. column), and these nodes are brothers ordered from east to west (resp. north to south); Figure \[phi\] shows an example of $\Phi$. Let the size of a pair $(F_e,F_s)$ of forests be given by the sum of the sizes of $F_e$ and $F_s$. \[prop:bijection\_pp\_pair\] The map $\Phi$ is a bijection between <span><span>parallelogram polyomino</span>es</span> with semi-perimeter $n$ and pairs of forests with size $n-2$. By definition of $\Phi$, for each node $x$ we have: - if $x$ is one of nodes of the top (resp. rightmost) row (resp. column) then $x$ is the root of a tree in $F_e$ (resp. $F_s$); - otherwise, by construction, $x$ has exactly one father, in fact: 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 nodes without fathers are the nodes of the top row and the rightmost column of $P$, $\Phi$ produces two ordered forests $F_e$ and $F_s$. The size of $(F_e,F_s)$ is equal to the number of dots enlightened in the <span><span>parallelogram polyomino</span></span> which is exactly equal to the semi-perimeter of the <span><span>parallelogram polyomino</span></span> minus two. Now we will prove that $\Phi$ is injective. Let $P_1$ and $P_2$ be two <span><span>parallelogram polyomino</span>es</span> 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 forests 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)$. Now we show surjectivity. Since forests of size $n$ are bijective to trees of size $n+1$, then pairs of forests of size $n$ are bijective to pairs of trees with size $n+2$. Now, pairs of trees with size $n+2$ are in bijection with trees of size $n+2$ (see Fig. \[phi2\]). Since it is known that <span><span>parallelogram polyomino</span>es</span> and ordered trees are equinumerous @Stanley, we can conclude that $\Phi$ is a bijection. $ \begin{array}{c} \includegraphics[width=.35\linewidth]{phiA} \end{array} { \ext@arrow 9999{\longleftrightarrowfill@}{}{\hspace{.2cm}}} \left( \begin{array}{r} F_e = \begin{array}{c} \includegraphics[width=.02\linewidth]{phiB} \end{array} , F_s = \begin{array}{c} \includegraphics[width=.25\linewidth]{phiC} \end{array} \end{array} \right) $ ![The bijection $\Psi$ between parallelogram polyominoes and pairs of forests. \[phi2\]](phi2){width=".75\textwidth"} 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. 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. \[fig:PD\]). For instance, for the parallelogram polyomino $P_D$ in Fig. \[fig:PD\] we have $\alpha(P_D)=5$ and $\beta(P_D)=4$. 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, with $D$ being the directed convex polyomino in Fig. \[fig:PD\], $\lambda_D=e^2se^2se^2s^3$. \[prop:directed\] 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$. A directed convex polyomino $D$ of semi-perimeter $n+2$ is uniquely determined by $P_D$ and $\lambda_D$. Now, using the bijection $\Phi$, the <span><span>parallelogram polyomino</span></span> $P_D$ is uniquely determined by a pair of forests $(F_e,F_s)$, with the property that the number of roots of $F_e$ (resp. $F_s$) is equal to $\alpha(P_D)$ (resp. $\beta(P_D)$). By construction of $\phi$, the sum of the sizes of $F_e$ and of $F_s$ is equal to $n$. Furthermore the cut has $\alpha(P_D) + 1$ east steps and $\beta(P_D) + 1$ south steps. Conversely, we consider a triplet $(F_e, F_s, \lambda)$ satisfying the conditions of Proposition \[prop:directed\], we can build the <span><span>parallelogram polyomino</span></span> $\Phi^{-1}(F_e,F_s)$. We have that $\alpha(P)=m_e$ and $\beta(P)=m_s$. We deduce that $\lambda$ is a cut of $P$ and we can determine an unique directed convex polyomino. We recall that a *bilateral Dyck path* is a directed path on $\mathbb{Z}\times \mathbb{Z}$ starting at $(0,0)$ in the $(x,y)$-plane and ending on the line $y=0$, which has unit steps in the $(1,1)$ (up step $u$) and $(1,-1)$ (down step $d$) directions. In the literature these objects are also referred to as free Dyck paths or Grand-Dyck paths. A *Dyck path* is a bilateral path which has no vertices with negative $y$-coordinates. The *semi-length* of a bilateral Dyck path is half the number of its steps. It is rather straightforward that the number of bilateral Dyck paths of semi-length $n$ is equal to ${2n} \choose {n}$. \[prop:bilateral\] The number of bilateral Dyck paths of semi-length $n$ is equal to the number of triplets $(F_e,F_s,\lambda)$ where $F_e$ and $F_s$ are forests, $\lambda$ is a monotone path, having $m_e$ east steps and $m_s$ south steps, and the integers $m_e$ and $m_s$ are respectively the number of trees in $F_e$ and $F_s$. The sum of the sizes of $F_e$ and of $F_s$ is equal to $n$. Let $\chi=(F_e,F_s,\lambda)$ be a triplet satisfying the hypotheses. We denote by $e_i$ (resp. $s_i$) the $i$-th east (resp. south) step of $\lambda$. We remark that the number of east (resp. south) steps of $\lambda$ is equal to the number of trees in $F_e$ (resp. $F_s$). We also recall that a tree $T$ can be represented by a Dyck path $D'(T)$, applying a standard mapping: we turn around the tree and we put an up step $u$ the first time we follow an edge of $T$ and a down step $d$ the second time. Then we build the elevated Dyck path $D(T)=uD'(T)d$. The semi-length of $D(T)$ is equal to the size of $T$. Now we associate to the $i$-th tree $T_i$ of $F_e$ the Dyck path $D(T_i)$, while to the $j$-th tree $T_j$ of $F_s$ the path $\overline{D}(T_j)$, obtained from $D(T_j)$ by exchanging $u$ steps with $d$ steps and viceversa. Now we define the bilateral Dyck path $B(\chi)$ as the concatenation of the paths $B_1\ldots B_{m_e + m_s}$, where: - $B_j=D(T_i)$ if the $j$-th step of $\lambda$ is $e_i$; - $B_j=\overline{D}(T_i)$ if the $j$-th step of $\lambda$ is $s_i$, where $j$ runs from $1$ to $m_e+m_s$. We can proceed in the inverse way to obtain the triplet $(F_e,F_s,\lambda)$ starting from a given bilateral Dyck path $B$. We can see an instance of this bijection in Fig. \[fig:bil\]. $$\left( \begin{array}{r} F_e = \begin{array}{c} \includegraphics[width=.15\linewidth]{Dir3} \end{array} , F_s = \begin{array}{c} \includegraphics[width=.075\linewidth]{Dir2} \end{array} , \lambda = e_1s_1e_2s_2e_3e_4e_5s_3 \end{array} \right)\\$$ $$\updownarrow$$ $$\begin{array}{r} \includegraphics[width=.8\linewidth]{bilateral} \end{array} $$ The number of bilateral Dyck paths of semi-length $n$ is equal to the number of directed convex polyominoes of semi-perimeter $n+2$. Given a bilateral Dyck path $B$, let $(F_e,F_s,\lambda)$ be the triplet corresponding to $B$ according to the bijection described in Proposition \[prop:bilateral\]. Now, let us define $\lambda'=e\,\lambda\,s$. Finally, according to Proposition \[prop:directed\] there is a unique directed convex polyomino $P$ corresponding to the triplet $(F_e,F_s,\lambda')$, then $P$ bijectively corresponds to $B$. Figure \[fig:bil\] shows the bilateral Dyck path bijectively associated with the directed convex polyomino in Figure \[fig:Dir\]. $ \begin{array}{c} \includegraphics[width=.25\linewidth]{Dir1} \end{array} { \ext@arrow 9999{\longleftrightarrowfill@}{}{\hspace{.2cm}}} \left( \begin{array}{r} F_e = \begin{array}{c} \includegraphics[width=.15\linewidth]{Dir3} \end{array} , F_s = \begin{array}{c} \includegraphics[width=.075\linewidth]{Dir2} \end{array} , \lambda = e^2sese^3s^2 \end{array} \right) $ As a consequence of Proposition \[prop:directed\] we have a refinement of Proposition \[prop:bijection\_pp\_pair\]. \[cor:parallelogram\] A parallelogram polyomino of semi-perimeter $n+2$ is uniquely determined by a pair $(F_e,F_s)$ of ordered forests, where $F_e$ (resp. $F_s$) has exactly $\alpha(P)$ (resp. $\beta(P)$) ordered trees and the sum of the sizes of $F_e$ and of $F_s$ is equal to $n$. We just need to observe that, a directed convex poly omino $D$ is a parallelogram polyomino if and only if $\lambda_D=e^{\alpha(P)+1}s^{\beta(P)+1}$. A general method for the enumeration of directed convex polyominoes =================================================================== In this section, we present a general method, based on Proposition \[prop:directed\], to enumerate several statistics on families of directed convex polyominoes. Let $\cal C$ be a class of directed convex polyominoes. Our method consists of 3 steps: 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 in $D$/$P_D$. Let us begin with a classical example. We will count directed convex polyominoes according to the semi-perimeter. The generating function of directed convex polyominoes with respect to the semi-perimeter is given by $$\frac{z^2}{\sqrt{1-4z}}.$$ Let us apply the 3 steps of our method: **Step 1:** According to Proposition \[prop:directed\], 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 generating function $\mathcal{T}$ for each ordered tree in $F_e$ and in $F_s$ is the following: $$\mathcal{T} = \frac{1-\sqrt{1-4z}}{2}.$$ The generating function for the cut is : $$\mathcal{G}(s,e,z_s,z_e) = \frac{z_s\,z_e}{1-(s+e)},$$ where $z_s$ (resp. $z_e$) represents the first (resp. last) south (resp. east) step of the cut. while $e$ and $s$ represent all the other east and south steps of the cut. **Step 3:** The generating function of directed convex polyominoes is $$\mathcal{G}(\mathcal{T},\mathcal{T},z,z) = \frac{z\,z}{1-2\mathcal{T}} = \frac{z^2}{\sqrt{1-4z}}.$$ The generating function of directed convex polyominoes according to the semiperimeter, the size of the top row and the size of the rightmost column of the associated parallelogram polyominoes is $$\frac{2xyz^2}{2-(x+y)(1-\sqrt{1-4.z})}.$$ Let $z$, $x$, $y$ take into account the semi-perimeter, the size of the top row and the size of the rightmost column of the associated parallelogram polyominoes, respectively. We just need to observe that the generating function for the cut is $\mathcal{G}(s, e, z_s, z_e ) = \frac{y\,z_s\, x\,z_e}{1-(y\,s+x\,e)}$. So we obtain the desired generating function $\mathcal{G}(\mathcal{T},\mathcal{T},z,z)$. The generating function of directed convex polyominoes according to the semiperimeter, the size of the top row and the size of the rightmost column of the polyominoes is $$xy \, \frac{(1-\mathcal{T})^2}{(1-x\,\mathcal{T})(1-y\,\mathcal{T})} \, \frac{z^2}{\sqrt{1-4z}},$$ where $\mathcal{T}=\frac{1-\sqrt{1-4z}}{2}$. Let $z$, $x$, $y$ take into account the semi-perimeter, the size of the top row and the size of the rightmost column of the polyominoes, respectively. All south (resp. east) steps of the cut are labelled $s$ (resp. $e$), but, since there are not trees in bijection with the first south step and the last east step of the cut, we need to multiply the final generating function by $\frac{z_e\,z_s}{s\,e}$. We need to take into account the first (resp. last) sequence of east (resp. south) steps of $\lambda$, which are labelled $x\,e$ (resp. $y\,s$), since they give the size of the top (resp. rightmost) row (resp. column) of the polyominoes. So the regular expression for the cut is the following: $x\,e(x\,e)^*\left( 1 + s(e+s)^*e \right) (y\,s)^*y\,s$. So the generating function is : $\mathcal{G}(s, e, z_s, z_e ) = \frac{z_e\,z_s}{e\,s} \left[ \frac{x\,e}{1-x\,e} \, \left( 1 + \frac{e\,s}{1-(e+s)} \right) \,\frac{y\,s}{1-y\,s} \right]$. So we obtain the desired generating function $\mathcal{G}(\mathcal{T},\mathcal{T},z,z)$. \[@LinChang88 [@Bousquet1992]\] 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 } } \, .$$ Let $z$, $x$, $y$ take into account the semi-perimeter, the width and the height of the polyominoes, respectively. Given a directed convex polyomino $D$, 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 $\mathcal{T}_e$ and $\mathcal{T}_s$ for the trees of $F_e$ and $F_s$, respectively. The nodes at odd (resp. even) height in $\mathcal{T}_e$ (resp. $\mathcal{T}_s$) are labelled by $x\,z$ and the nodes at even (resp. odd) height are labelled by $y\,z$. The two generating functions are obtained by solving the following system: $$\mathcal{T}_e = \frac{x z}{1 - \mathcal{T}_s}\quad \mbox{ and } \quad \mathcal{T}_s = \frac{y z}{1 - \mathcal{T}_e} \,$$ from which we have $$\mathcal{T}_e(x,y) = \frac{1+(x-y)z-\sqrt{\left( 1+(x-y)z \right)^2-4xz} }{2} \quad \mbox{ and } \quad \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{x z_e y z_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, respectively. So 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 } }.$$ Now we consider a further statistic, i.e. the number of <span>*inside/outside corners*</span> of a directed convex polyomino. Let us recall that, following the boundary of a directed convex polyomino clockwise, any turn to the right (reps. left) is called an outside (resp. inside) corner. Also the corner at $(0,0)$ is an outside corner. Let us recall that the number of outside and inside corners of any polyomino differ in the amount of $4$. For instance, the polyomino in Fig.\[fig:Dir\] has $11$ outside corners and $7$ inside corners. \[prop:corners\] The generating function of directed convex polyominoes according to the semi-perimeter and the number of outside corners is given by $$\frac{x^4 z^2}{1-2\mathcal{T}_c + (1-x)\mathcal{T}_c^2},$$ where $\mathcal{T}_c = \frac{1 + (1-x)z - \sqrt{ (1 + (1-x)z)^2 - 4z }}{2}$. The regular expression for the cut is $(ee^*xss^*)(ee^*xss^*)^*$ where $x$ counts the number of east-south corners in the cut. The generating function of the cut is equal to : $$\mathcal{G}(e,s,z_e,z_s) = \frac{z_e z_s}{es} \cdot \left[ \frac{esx}{(1-e)(1-s)} \cdot \frac{1}{1 - \frac{esx}{(1-e)(1-s)} } \right] = \frac{x z_e z_s}{1 - (e+s) + (1-x)es} .$$ Except for the topmost and leftmost (resp. rightmost and lowest) outside corners of the directed convex polyomino $D$, the outside corners of type north-east and south-east are bijective with the first son of each node of the forests. The generating function $T_c$ for the trees is obtained by solving the following equation: $$T_c = z( 1 + x( T_c+ T_c^2 + \dots ) ) = (1-x)z + \frac{zx}{1-T_c}.$$ We obtain the generating function $$T_c = \frac{1 + (1-x)z - \sqrt{(1 + (1-x)z)^2 - 4z } }{2}.$$ Now the desired generating function is: $$x^3 \mathcal{G}( T_c, T_c, z, z ).$$ In the formula above we have added the factor $x^3$, which takes into account the following three corners of the polyomino: the topmost and leftmost outside corner; the rightmost and lowest outside corner; and the lowest and leftmost outside corner. \[prop:insidecorners\] The generating function of directed convex polyominoes according to the semi-perimeter and the number of inside corners of polyominoes is given by $$\frac{z^2}{1-2\mathcal{T}_c + (1-x)\mathcal{T}_c^2},$$ where $\mathcal{T}_c = \frac{1 + (1-x)z - \sqrt{ (1 + (1-x)z)^2 - 4z }}{2}$. We have already observed that the number of outside corners of a polyomino is given by the number of inside corners plus $4$. So we obtain the desired generating function from the generating function for directed convex polyominoes with respect to the number of outside corners and semi-perimeter (obtained in Proposition \[prop:corners\]) and multiplying by the factor $x^{-4}$. We recall that the *site-perimeter* of a polyomino is the number of nearest-neighbour vacant cells. This parameter is of considerable interest to physicists and probabilists. In @DG the generating function for the parallelogram polyominoes with respect to the site-perimeter was computed and in @MBR the authors find the generating function with respect to the site-perimeter for the family of bargraphs polyominoes. The enumeration according to corners lets us freely obtain the enumeration of directed convex polyominoes according to the site-perimeter. The generating function of directed convex polyominoes according to the site-perimeter and the semi-perimeter is given by $$\frac{ (y^2z)^2 }{ 1-2\mathcal{T}_s + ( 1 - y^{-1} ) \mathcal{T}_s^2 },$$ where $\mathcal{T}_s = \mathcal{T}_c( y^{-1}, y^2z ) $ and $\mathcal{T}_c(x,z) = \frac{1 + (1-x)z - \sqrt{ (1 + (1-x)z)^2 - 4z }}{2}$. In a convex polyomino the site-perimeter is equal to the perimeter minus the number of inside corners. According to Corollary \[prop:insidecorners\], let ${\cal D}_c(x,z)$ be the generating function for directed convex polyominoes where $x$ (resp. $z$) takes into account the number of inside corners (resp. the semi-perimeter) of polyominoes. So, the generating function of directed convex polyominoes with respect to their site-perimeter and semi-perimeter is: $${\cal D}_c(y^{-1},y^2z)$$ where $y$ (resp. $z$) takes into account the site-perimeter (resp. the semi-perimeter). \[@Deutsch2003\] The generating function of the symmetric directed convex polyominoes according to the semi-perimeter is given by $$\frac{z^2}{\sqrt{1 - 4z^2}}.$$ Let $D$ be a symmetric directed convex polyomino and $\Phi(D) = (F_e, F_s, \lambda)$. By construction of $\Phi$, since $D$ is symmetric, $F_e = F_s$ and $\lambda$ is the concatenation of the half-cut $\lambda_{1/2}$ which is a path starting with an east step $e$, and the mirror of $\lambda_{1/2}$. To compute the generating function, we need to determine the generating function of the half-cut and plug a tree inside. Then we need to count each node twice. The generating function for $\lambda_{1/2}$ is $$\mathcal{G}(e,z_e) = \frac{z_e}{e} \left[ \frac{e}{1-(e+s)} \right].$$ The generating function for the trees is $\mathcal{T}$. The final result is $$\mathcal{G}( \mathcal{T}(z^2), z^2 ) = \frac{z^2}{\sqrt{1 - 4z^2}}.$$ Enumeration of directed $k$-convex polyominoes ============================================== In this section we apply the method described in the previous section in order to obtain the generating function of directed $k$-convex polyominoes. We start recalling some basic definitions and enumerative results about $k$-convex polyominoes. $k$-convexity constraint ------------------------ A *path connecting two cells*, $b$ and $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. \[paths\]$(a)$). Figure \[paths\]$(b)$ shows a monotone path connecting two cells of a polyomino. Let $p=p_1\dots 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. \[paths\]). In @Castiglione2003290 the authors prove that a polyomino is convex if and only if every pair of its cells can be joined by a monotone path. 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. 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. Fig. \[paths\]$(b)$ shows a convex-polyomino with degree of convexity $k=2$. ![$(a)$ a path connecting two cells of the polyomino with two changes of direction; $(b)$ a monotone path between two cells of the polyomino with two changes of direction. \[paths\]](paths){width=".4\textwidth"} 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). 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 (see Fig. \[u-v\]). Therefore, from now on, we will consider the case where $j'\geq 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. \[bouncepaths\]$(a)$). ![$(a)$ A directed convex polyomino $D$ and its associated parallelogram polyomino $P_D$.<span data-label="fig:PD"></span>](PD1){width=".4\textwidth"} We need to 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. Observe that 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}$. In what follows, we will prove some combinatorial properties concerning directed convex polyominoes, understanding that they hold for parallelogram polyominoes a fortiori. Let $D$ be a directed convex polyomino. Given $k\geq 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. ($\Rightarrow$) It follows from the definition of directed $k$-convex polyomino.\ ($\Leftarrow$) We suppose, by contradiction, that $D$ is not a directed $k$-convex polyomino, then there exist two cells $a=(i_1,j_1)$ and $b=(i_2,j_2)$ (with $a,b\neq S$) which have to be connected by means of a path with at least $k+1$ changes of direction. We can suppose that $j_2> j_1$ and $i_2>i_1$ (otherwise we can find a path connecting the two cells with at most one change of direction). We consider the bounce path $m_{S,b}$: by hypothesis it has at most $k$ changes of direction; so it is possible to find a monotone path connecting $a$ to $b$ with at most $k$ changes of direction. To find this path, we just have to consider $m_{S,b}$ and, when it passes through a cell $c$ in the same column or row of $a$, we join $c$ to $a$. This is contradiction, so we have the proof. ![Two cells $b=(i,j)$, $c=(i',j')$ of a directed convex polyomino where $j'<j$. \[u-v\]](u-v){width="32.00000%"} \[lem:bounce\] Let $D$ be a directed convex polyomino and let $b$ and $c$ be two cells of $D$. The number of changes of direction of the minimal bounce path joining $b$ to $c$ is less than or equal to the number of changes of direction of any path joining $b$ to $c$. Let $p$ be a path joining $b=(i,j)$ to $c=(i',j')$ and starting at the centre of $b$ with an east unit step. The other case, where the starting step is a north step, is completely analogous. We consider the change of direction of $p$ from east to north (similarly from north to east) occurring in the first cell $t$ such that there exists a cell $t'$ on the east (resp. north) of $t$. We remark that if such a cell $t'$ does not exist then, adding an unit east step to $p$ such that it starts at $(i -\frac{3}{2},j-\frac{1}{2})$ we obtain the bounce path $r_{b,c}$, hence the result follows. Starting from $p$, we can build a new path $p'$, which has a change of direction at $t'$ instead of at $t$ and joins $b$ to $c$ with a number of changes of direction which is less then or equal to the number of changes of direction of $p$. If we repeat this operation, and at the end we add an east step to the obtained path, such that it starts at $(i -\frac{3}{2},j-\frac{1}{2})$, we obtain the bounce path $r_{b,c}$ joining $b$ to $c$. We can conclude that the number of changes of direction of the bounce path $r_{b,c}$ (resp. $u_{b,c}$) is less than or equal to the number of changes of direction of any path joining $b$ to $c$, starting with an east (resp. north) unit step. So we have the result for the minimal bounce path joining $b$ to $c$. 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 <span><span>parallelogram polyomino</span></span> $P$, we denote by $E$ the 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 denote by $r(P)$ (resp. $u(P)$) the bounce path $r_{S,E}$ (resp. $u_{S,E}$)(see Fig. \[bouncepaths\]$(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$. ![$(a)$ The bounce paths joining two cells of a directed convex polyomino; $(b),(c)$ The bounce paths of a parallelogram polyomino. \[bouncepaths\]](bouncepathsT){width="100.00000%"} $k$-parallelogram polyominoes ----------------------------- Now, we restrict our investigation to the case of $k$-parallelogram polyominoes. We will show that the convexity degree of a parallelogram polyomino can be expressed in terms of the heights of the two forests associated with the polyomino, via the mapping $\Phi$. Let $b$ and $c$ be two cells of a given <span><span>parallelogram polyomino</span></span> $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}$. \[lem:difference\_u\_r\] Let $P$ be <span><span>parallelogram polyomino</span></span> and let $b$,$c$ be two cells of $P$. The number of changes of direction between $r_{b,c}$ and $u_{b,c}$ differ in the amount of $\pm 1$ if $J_{b,c} \neq c$ and by $0$ if $J_{b,c} = c$. In the subpath between $b$ and $J_{b,c}$, each time $r_{b,c}$ crosses $u_{b,c}$, the number of changes of direction of $r_{b,c}$ and of $u_{b,c}$ increases by $1$. If $J_{b,c}=c$ then the number of changes of direction of the two paths differ in the amount of $0$. If $J_{b,c}\neq c$ then the number of changes of direction of the two paths differ in the amount of $\pm 1$. Precisely, the difference is equal to $1$ if $r_{b,c}$ has a change of direction at $J_{b,c}$ and to $-1$ if $u_{b,c}$ has a change of direction at $J_{b,c}$. \[lem:max\_bounce\] Let $P$ be a <span><span>parallelogram polyomino</span></span> and let $b$ and $c$ be two cells of $P$. The number of changes of direction of the minimal bounce path $m$ is greater than or equal to the number of changes of direction of the minimal bounce path $m_{b,c}$ joining $b$ to $c$. Let $b$ and $c$ be two cells of a <span><span>parallelogram polyomino</span></span> $P$. Let $u_{b,c}$ be the bounce path joining $b$ to $c$ (the argument is similar if we consider the bounce path $r_{b,c}$). Now we consider the bounce path $u_{b,E}$ joining $b$ to $E$. We observe that $u_{b,E}$ coincides with $u_{b,c}$ in the subpath from $b$ to the last change of direction of $u_{b,c}$. We deduce that the number of changes of direction of $u_{b,E}$ is greater than or equal to the number of changes of direction of $u_{b,c}$. By a similar argument, the number of changes of direction of $r_{b,E}$ is greater than or equal to the number of changes of direction of $r_{b,c}$. We deduce that the number $h''$ of changes of direction of $m_{b,E}$ is greater than or equal to the number $h'$ of changes of direction of $m_{b,c}$. Now we suppose by contradiction that the number $h$ of changes of direction of the minimal bounce path $m$ of $P$ is less than $h'$ (namely, the number of changes of direction of $m_{b,c}$). Then we can find a path $p$ joining $b$ to $E$, (in fact we consider $m=m_{S,E}$ and when it pass through a cell $t$ in the same column or row of $b$, we join $t$ to $b$) with a number of changes of direction less than or equal to $h$, while we supposed by contradiction that $h<h'$. We also observed above that $h'\leq h''$, and this contradicts Lemma
{'source': 'arXiv_out/1501'}