# On the enumeration of column-convex
permutominoes

Nicholas R. Beaton<fnref n="1" />, Filippo Disanto<fnref n="2" />, Anthony J. Guttmann<fnref n="1" /> and Simeon Rinaldi<fnref n="2" />

**Abstract.** We study the enumeration of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations. We provide a direct recursive construction for the column-convex permutominoes of a given size, based on the application of the ECO method and generating trees, which leads to a functional equation. Then we obtain some upper and lower bounds for the number of column-convex permutominoes, and conjecture its asymptotic behavior using numerical analysis.

**Résumé.** Nous étudions l’enumeration des permutominos verticalement convexes, c.à.d. les polyominos verticalement convexes définis par un couple de permutations. Nous donnons une construction recursive directe pour ces permutominos de taille fixée, basée sur une application de la méthode ECO et les arbres de génération, qui nous amène à une équat ion fonctionelle. Ensuite nous obtenons des bornes superieures et inférieures pour le nombre de ces permutominos convexes et nous conjecturons leur comportement asymptotique à l’aide d’analyses numériques.

**Keywords:** polyominoes, permutations, generating functions

## 1 Introduction

In the plane $Z \times Z$ a cell is a unit square, and a polyomino is a finite connected union of cells having no cut point. Polyominoes are defined up to translations. A column (row) of a polyomino is the intersection between the polyomino and an infinite strip of cells lying on a vertical (horizontal) line. A polyomino is said to be column-convex (row-convex) when its intersection with any vertical (horizontal) line of cells in the square lattice is connected, and convex when it is both column and row-convex. For the main definitions of these objects we refer to [6].

Let $P$ be a polyomino without “holes”, i.e. a polyomino whose boundary is a single loop, and having $n$ rows and $n$ columns, $n \ge 1$; we assume without loss of generality that the south-west corner of its minimal bounding rectangle is placed at (1, 1). We say that $P$ is a *permutomino* if for each abscissa (ordinate) between 1 and $n$ there is exactly one vertical (horizontal) bond in the boundary of $P$ with that coordinate, and $n$ is called the *size* of the permutomino. A permutomino can be equivalently defined by two permutations of length $n+1$, denoted $\pi_1$ and $\pi_2$, as depicted in Fig. 1. For more detailed definitions of permutations on permutominoes we refer to [4, 9, 11].

<footnote n="1">¹Department of Mathematics and Statistics, University of Melbourne, Victoria, Australia</footnote>

<footnote n="2">²Dipartimento di Scienze Matematiche e Informatiche, Università di Siena, Siena, Italy</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: A permutomino and the two associated permutations.</figcaption></figure>

Permutominoes were introduced in [15], and then considered by F. Incitti while studying the problem of determining the $\tilde{R}$-polynomials associated with a pair $(\pi_1, \pi_2)$ of permutations [13]. In recent years, a particular class of permutominoes, namely convex permutominoes and their associated permutations, have been widely studied [4, 9, 11]. The main enumerative results known about convex permutominoes are the following:

i. the number of parallelogram permutominoes of size $n$ is equal to the $n$-th Catalan number,

$$C_n = \frac{1}{n+1} \binom{2n}{n};$$

ii. the number of directed convex permutominoes of size $n$ is equal to $\binom{2n-1}{n}$;

iii. the number of convex permutominoes of size $n$ is:

$$2(n+3)4^{n-2} - \frac{n}{2}\binom{2n}{n} \quad n \ge 1. \qquad (1)$$

We point out that formula (1) was proved using analytical techniques independently in [5, 9], and a bijective proof of (1) was given in [8].

We also recall from [4] that permutations defining convex permutominoes are strictly related with the so-called *square permutations* (or *convex permutations*), recently considered by several authors [1, 10, 14].

Our aim is to deal with the enumeration of column-convex permutominoes. We determine a direct recursive construction for the column-convex permutominoes of a given size, based on the application of the ECO method [3] and generating trees [2], which leads to a functional equation. However we are not able to solve the equation so as to obtain the generating function of column-convex permutominoes. We are only able to obtain some upper and lower bounds for the number of column-convex permutominoes, and conjecture its asymptotic behavior using numerical analysis.
## 2 Generation of column-convex permutominoes

The ECO method [3] is a method for the enumeration and the recursive construction of classes of combinatorial objects. It is substantially based on an operator $\vartheta$, which constructs each object of a given size in a unique way, starting from those of immediately lower size. The recursive construction determined by $\vartheta$ can be suitably described by a *generating tree* [2], which then leads to a functional equation satisfied by the generating function of the class.

In order to define the ECO construction for column-convex permutominoes, we classify the corners of their boundary, using *reentrant* and *salient points*. So let us briefly recall the definition of these objects.

Let $P$ be a polyomino. Starting from the lowest among the leftmost points of $P$, and moving in a clockwise direction, the boundary of $P$ can be encoded as a word of a four letter alphabet, {N, E, S, W}, where N (resp. E, S, W) represents a *north* (resp. *east, south, west*) unit step. Any occurrence of a sequence NE, ES, SW, or WN in the word encoding $P$ defines a *salient point* of $P$, while any occurrence of a sequence EN, SE, WS, or NW defines a *reentrant point* of $P$ (see for instance, Figure 2).

Reentrant and salient points were considered for instance in [7], and it was proved that in any polyomino the difference between the number of salient and reentrant points is equal to 4. Moreover, we observe that the set of reentrant points of a convex permutomino of size $n$ defines a permutation matrix of size $n-1$. This property it is not true for column-convex permutominoes. However it is easy to prove that in a column-convex permutomino of size $n$ we have exactly one reentrant point for each abscissa between 1 and $n-1$.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** In the picture, the coding of the boundary of the permutomino starts from the circled point, and the reentrant points are those denoted by squares.</figcaption></figure>

Let $C_n$ be the set of column-convex permutominoes of size $n$, and let $P \in C_n$; the number of cells in the rightmost column of $P$ is called the *degree* of $P$, and will be denoted by $d(P)$. Let the level of a cell in $P$ be the ordinate of its upper edge. Then we denote by $w(P)$ the level of the lowest cell of $P$ minus 1 and by $h(P)$ the level of the uppermost cell of $P$ (see Fig. 2); clearly $h(P) + d(P) + w(P) = n$. To a column-convex permutomino $P$ we assign the label $(h(P), d(P), w(P))$ ($(h, d, w)$, for brevity).

Now we define an ECO operator $\vartheta: C_n \to 2^{C_{n+1}}$ which defines a recursive construction of all the column-convex permutominoes of size $n+1$ in a unique way from those of size $n$. The operator $\vartheta$ acts on a column-convex permutomino performing some local expansions on the cells of its rightmost column.
The operator $\vartheta$ consists in four operations denoted by $\alpha, \beta, \gamma$, and $\delta$, and below we give a detailed description of each of them:

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Operation $\alpha$ performed on a column-convex permutomino, adding a new column of length $d+2$. The added cells have been highlighted.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 4:** Operation $\alpha$ performed on a column-convex permutomino, adding a new column of length $d+h+1$.</figcaption></figure>

(α) for each $i$ such that $d+1 \le i \le d+h+1$, operation $\alpha$ adds a column of length $i$ next to the rightmost column of the permutomino, starting from the bottom, and adds a cell to the top of each cell at level $w+i$, in order to maintain the property of being permutomino, as in Figure 3. When $i=d+h+1$, no other cell is added, according to Figure 4.

It is clear that the resulting polyomino is a column-convex permutomino of size $n+1$, and that the rightmost reentrant point in such a new permutomino is always of type EN.

(β) is performed on each cell of the rightmost column. So let $q_i$ be the $i$th cell of such a column, from
bottom to top, with $1 \le i \le d$. Operation $\beta$ adds a cell to the top of each cell of the row containing $q_i$, and a new column made of $i$ cells on the right of $q_i$, as illustrated in Figure 5.

It is clear that, for any $i$, the obtained polyomino is a column-convex permutomino of size $n+1$, and its rightmost reentrant point is of type SE.

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** Operation $\beta$ performed on the highlighted cell of a column-convex polyomino. The added cells have been highlighted.</figcaption></figure>

(γ) is performed on each cell of the rightmost column. So let $q_i$ be the $i$th cell of such column, numbered from bottom to top, with $1 \le i \le d$. Operation $\gamma$ adds a cell on the top of each cell of the row containing $q_i$, and a new column made of $d-i+1$ cells on the right of $q_i$, as illustrated in Figure 6.

It is clear that, for any $i$, the obtained polyomino is a column-convex permutomino of size $n+1$, and its rightmost reentrant point is of type WS.

<figure><img src="image_6.png" /><figcaption>**Fig. 6:** Operation $\gamma$ performed on the highlighted cell of a column-convex polyomino. The added cells have been highlighted.</figcaption></figure>

(δ) for each $i$ such that $1 \le i \le w+1$, operation $\delta$ adds a column of length $d+i$ next to the rightmost column of the permutomino, starting from the top, and adds a cell to the bottom of each cell at level
$w - i + 1$. When $i = w + 1$, no other cell is added, see Figure 7.

It is clear that the resulting polyomino is a column-convex permutomino of size $n + 1$, and that the rightmost reentrant point in such new permutomino is always of type NW.

<figure><img src="image_7.png" /><figcaption>**Fig. 7:** The two column-convex permutominoes produced through the application of $\delta$ to the permutomino on the left.</figcaption></figure>

The proof of the following statement is then straightforward.

**Theorem 2.1** Any column-convex permutomino of size $n \ge 2$ is uniquely obtained through the application of the operator $\vartheta$ to a convex permutomino of size $n - 1$.

Formally, the application of $\vartheta$ to a column-convex permutomino with a generic label $(h, d, w)$, produces $2d + h + w + 2$ column-convex permutominoes according to the following succession rule:

$$ \begin{array}{lclcl} (h, d, w) & \stackrel{\alpha}{\rightsquigarrow} & (h-i+1, d+i, w) & 1 \le i \le h+1 & \\ & \stackrel{\beta}{\rightsquigarrow} & (d+h-i+1, i, w) & 1 \le i \le d & \\ & \stackrel{\gamma}{\rightsquigarrow} & (h, i, d+w-i+1) & 1 \le i \le d & \\ & \stackrel{\delta}{\rightsquigarrow} & (h, d+i, w-i+1) & 1 \le i \le w+1. & \end{array} $$

These have root $(0, 1, 0)$, which is the label of the one cell permutomino.

## 3 Enumeration of column-convex permutominoes

The previous succession rule can be suitably represented by means of a *generating tree*, which is a rooted tree where the objects at level $n$ are the labels of the column-convex permutominoes of size $n$. Thus, the root is $(0, 1, 0)$, and the sons of a generic label $(h, d, w)$ at level $n$ are given by the succession rule production. The number $f_n$ of column-convex permutominoes of size $n$ is then given by the number of objects at level $n$ of the generating tree.
Let $C$ denote the set of all column-convex permutominoes. Our aim is to determine the generating function:

$$ 
\begin{aligned}
F(x, y, z) &= \sum_{P \in C} x^{h(P)} y^{d(P)} z^{w(P)} \\
&= y + xy + yz + 2y^2 + 3x^2y + 2xyz + 3z^2y + 4xy^2 + 4zy^2 + 6y^3 + \dots
\end{aligned}
$$

where, in particular, $F(y, y, y)$ is the generating function of column-convex permutominoes according to size. Using the succession rule, and standard methods, we can write

$$ 
\begin{aligned}
F(x, y, z) &= y + \sum_{P \in C} x^h y^{d+1} z^w + \dots + x^0 y^{d+h+1} z^w + \sum_{P \in C} x^{d+h} y^1 z^w + \dots + x^{h+1} y^d z^w \\
&\quad + \sum_{P \in C} x^h y^z d^{w+1} + \dots + x^h y^d z^{w+1} + \sum_{P \in C} x^h y^{d+1} z^w + \dots + x^h y^{d+w+1} z^0,
\end{aligned}
$$

and then, after some calculation, we obtain the following functional equation

$$ F(x, y, z) = y + \frac{yz}{z-y} F(x, z, z) - \frac{y^2}{z-y} F(x, y, y) + \frac{xy}{x-y} F(x, x, z) - \frac{y^2}{x-y} F(y, y, z). \quad (2) $$

From this equation we are able to compute the first terms of sequence $f_n$:

1, 4, 22, 152, 1262, 12232, 135544, 1690080, 23417928, 356958816, 5936071344, 106944112320, 2074955738160, 43135041684288...

Indeed, we have obtained the first 200 coefficients, and report on their analysis in Section 3.3. We have not been able to solve the equation, or to find a closed formula for the number of column-convex permutominoes. In the following sections we add some combinatorial considerations, and give upper and lower bounds. We remark that from the ECO construction it easily follows that $F(x, y, z) = F(z, y, x)$; this fact does not help us, however, in solving (2).

## 3.1 Directed column-convex permutominoes

A simple lower bound is given by the number of directed column-convex permutominoes. Let us define the ECO operator $\vartheta'$ as the operator which performs the operations $\alpha, \beta$, and $\gamma$ defined before, but not operation $\delta$. Starting from the one cell permutomino, the operator $\vartheta'$ generates all column-convex permutominoes which do not contain any WS reentrant point; that is to say, the column-convex permutominoes which are *north-west directed* (briefly, directed, see Fig. 8 (a)). Let $G(x, y, z)$ be the generating function of directed column-convex permutominoes. This time, using the operator $\vartheta'$, and the associated succession rule, we can obtain the following functional equation for $g(y) = G(y, y, y)$:

$$ g(y) = 2y g(y) + y^2 g'(y) + y, $$

and then we readily find that the number of directed column-convex permutominoes of size $n$ is $\frac{(n+1)!}{2}$. We also have a simple bijective proof of this fact.
<figure><img src="image_8.png" /><figcaption>Fig. 8: (a) A directed column-convex permutomino; (b) A column-convex permutominide.</figcaption></figure>

## 3.2 Column-convex permutominides

To provide an upper bound, we need to introduce another combinatorial object, the column-convex permutominide. Without going further into formal definitions, a column-convex permutominide of size $n$ is substantially a polyomino whose boundary is allowed to cross itself, while the columns remain connected, and with exactly one edge for every abscissa and exactly one edge for every ordinate between 1 and $n$, see Fig. 8 (a). These objects have been treated and enumerated, according to size, in [8].

To a column-convex permutominide $P$ of size $n$ we associate a side permutation $\pi(P)$ of length $n+1$, as follows: Among the two horizontal edges of $P$ starting from the left side of the minimal bounding square there is only one with length 1, and its ordinate is denoted $\pi(1)$. Now, removing this edge, there is one horizontal edge for each abscissa between 1 and $n$, so let $\pi(i+1)$ be the ordinate of the edge with abscissa $i$. For instance, the side permutation associated with the column-convex permutominide depicted in Fig. 9 (b) is (3, 7, 1, 9, 2, 4, 8, 5, 6). The reader can easily observe that the permutation $\pi(P)$ does not uniquely determine $P$; in fact, we have the following:

**Proposition 1** Given a permutation $\sigma$ of size $n+1$, there are $2^{n-2}$ column-convex permutominides of size $n$ having $\sigma$ as side permutation.

**Proof:** Let us fix a set $\Gamma \subseteq \{4, \dots, n+1\}$. We want to prove that $\sigma$ and $\Gamma$ uniquely determine a column-convex permutominide. Let us consider the points $(1, \sigma(1))$, and $(i, \sigma(i))$, for $i > 1$. We will write $\sigma(i)$ to mean the point $(i, \sigma(i))$. Now we join $\sigma(1)$ with $\sigma(3)$ and, from left to right, all the points $\sigma(i)$, with $i \in \Gamma$, until we reach the right side of the minimal bounding square, see Fig. 9 (a). Now the permutominide of size $n$ is uniquely determined, see Fig. 9 (b). $\square$

The following statement then readily follows:

**Proposition 2** The number of column-convex permutominides of size $n$ is $2^{n-2}(n+1)$!

This number is an upper bound on the number of column-convex permutominoes. Using combinatorial arguments, we may slightly refine this upper bound. For instance, if $P$ is a permutomino then $\pi(2)$ must not be between $\pi(1)$ and $\pi(3)$.
<figure><img src="image_9.png" /><figcaption>Fig. 9: (a) The path obtained connecting $\sigma(1)$ with the points belonging to the set $\Gamma = \{4, 7, 8\}$; (b) The column-convex permutominide determined from $\sigma$ and $\Gamma$.</figcaption></figure>

## 3.3 Final remarks

Our bounds allow us to write that for sufficiently large values of $n$ we have:

$$(n+1)! < f_n < (n+1)! 2^n.$$

The upper and lower bounds suggest that an exponential generating function is likely to be appropriate, and so we applied the simplest possible analysis. Using the first 200 terms of the sequence $\{f_n\}$, we simply calculated the sequence $\tilde{f}_n = f_n/(n+1)!$, and then calculated the ratio of successive terms of this new sequence, viz. $\tilde{f}_n/\tilde{f}_{n-1}$. We found this sequence converges very rapidly to a constant, which we find to be

$$h = 1.385933275998194253860621814882515...$$

This suggests that

$$f_n \sim k(n+1)!h^n, \qquad (3)$$

where we estimated the value of $k$ by the simple expedient of constructing the sequence $f_n/(n+1)!/h^n$. Again we obtain a rapidly convergent sequence, and estimate that

$$k = 0.34191113152179550788392501698973...$$

Detailed study of the rate of convergence suggests that it is exponential. Exponential convergence is one manifestation of a second singularity beyond the radius of convergence. We investigated this possibility by using differential approximants [12] to study the sequence $\{\tilde{f}_n\}$. This study shows a dominant singularity – a simple pole – at $1/h \approx 0.72153572588$, plus a second singularity at 1. The nature of the second singularity is less clear. It appears to be a confluent singularity. Its presence and nature indicates that the generating function, or indeed the exponential generating function, while having simple dominant asymptotics, has some subdominant terms that are more subtle.

We have attempted to study this sub-dominant singularity as follows: Given that we know the position of the dominant singularity, and its amplitude, very precisely, we can largely subtract it, and investigate the
remaining series. So we formed the sequence $d_n = \tilde{f}_n - k \times h^n$, using the values of $k$ and $h$ given above. Assuming that the sub-dominant singularity of the generating function for $\tilde{f}_n$ is precisely at 1, as our above analysis suggests, we then expect $d_n \sim e \times n^g$, where $e$ is a constant. If that is the case, it follows that we can construct a sequence of estimators for $g$ from the sequence $d_n/d_{n-1} = 1 + g/n + o(1/n)$, so the sequence $n(d_n/d_{n-1} - 1)$ should provide a sequence of estimators of $g$. In this way we find $g \approx -1.272$ where the last digit is in doubt. Indeed, we cannot really exclude that the correct value of this exponent is a simple rational fraction, such as $-5/4$, or it may be something bizarre, such as $-\log(\sqrt{2} - 1)/\log(2) = 1.2715...$. Then $e$ can be estimated by forming the sequence $d_n/n^g$, and in this way we estimate $e \approx 0.6625$. Putting together the pieces of our analysis, we conjecture that

$$ \tilde{f}_n \sim k \times h^n + e \times n^g. $$

It is natural to investigate the possibility that $h$ is an algebraic number. We have been unable to find a simple polynomial of degree less than 25 with $h$ as a root which suggests that it is not a simple algebraic number. Further investigation using interactive solvers that seek representations in terms of a variety of transcendental constants and their powers, as well as logarithms and Dirichlet functions has also been unsuccessful.

To solve equation (2) or to give a proof of (3) are open problems.

The form for $f_n$ given by (3) suggests that formulating the problem in terms of the exponential generating function may prove useful. If we write

$$ \begin{aligned} E(t, x, y, z) &= \sum_{P \in C} \frac{t^{h(P)+d(P)+w(P)} x^{h(P)} y^{d(P)} z^{w(P)}}{(h(P) + d(P) + w(P))!} \\ &= ty + \frac{t^2}{2}(xy + yz + 2y^2) + \frac{t^3}{6}(3x^2y + 2xyz + 3z^2y + 4xy^2 + 4zy^2 + 6y^3) + \dots \end{aligned} $$

then by the same method used for (2), we obtain

$$ \frac{\partial}{\partial t} E(t, x, y, z) = y + \frac{yz}{z-y} E(t, x, z, z) - \frac{y^2}{z-y} E(t, x, y, y) + \frac{xy}{x-y} E(t, x, x, z) - \frac{y^2}{x-y} E(t, y, y, z). \quad (4) $$

Unfortunately this equation seems no more tractable than (2).

It may be the case that there exists a different method for constructing column-convex permutominoes. One possibility involves adding the horizontal bonds, one column at a time, from left to right (column-convexity implies that there are precisely two horizontal bonds in each column). If the bonds in column $i$ are at heights $a_i$ and $b_i$, with $a_i > b_i$, for columns $i = 1...k$, then the bonds in column $k+1$ must satisfy either

* $a_{k+1} = a_k$ and $b_{k+1} \neq a_1, ..., a_k, b_1, ..., b_k$; or

* $b_{k+1} = b_k$ and $a_{k+1} \neq a_1, ..., a_k, b_1, ..., b_k$.

While we have not been able to obtain an enumeration via this method, we note that the corresponding version for column-convex permutominoes uses the slightly relaxed rules
• $a_{k+1} = a_k$ or $b_k$ and $b_{k+1} \neq a_1, \dots, a_k, b_1, \dots, b_k$; or

• $b_{k+1} = a_k$ or $b_k$ and $a_{k+1} \neq a_1, \dots, a_k, b_1, \dots, b_k$.

In this case an enumeration readily follows, and agrees with the result of Proposition 2.

From another perspective, we remark that column-convex permutominoes are an interesting class of
permutominoes, since they show some features that make them different from the other classes of permu-
tominoes previously studied.

In fact, we have seen that the generating functions of the classes of previously considered permu-
tominoes are of the same nature (i.e. rational or algebraic) as the corresponding class of polyominoes
(enumerated according to the semi-perimeter). So, for instance, the classes of convex, directed-convex,
parallelogram permutominoes have algebraic generating functions, while the classes of stack, centered
permutominoes have rational generating functions. Using the previously stated result, we are led to think
that, while the class of column-convex polyominoes is an algebraic class [6], the class of column-convex
permutominoes has a transcendental generating function. The reason for this distinction probably arises
from the fact that, in passing to column-convex permutominoes the relation:

$$
\text{size of the permutomino } P = 2 \text{ semi-perimeter of the permutomino } P,
$$

holding for convex permutominoes, now fails. Thus, it would also be interesting to enumerate column-
convex permutominoes according to the semi-perimeter, but in this case the ECO construction we have
given is not helpful.

References

[1] Albert, M., Linton, S., Ruskuc, N., Waton, S., On convex permutations, online available at http://www.math.ufl.edu/~vatter/.

[2] Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions for generating trees, *Disc. Math.* 246 (2002) 29-55.

[3] Barcucci, E., Del Lungo, A., Pergola, E., Pinzani, R.: ECO: a methodology for the Enumeration of Combinatorial Objects., *J. Diff. Eq. and App.* 5 (1999) 435-490.

[4] Bernini, A., Disanto, F., Pinzani, R., Rinaldi, S., Permutations defining convex permutominoes, *J. Int. Seq.*, 10 (2007) Article 07.9.7.

[5] Boldi, P., Lonati, V., Radicioni, R., Santini, M.: The number of convex permutominoes., *Information and Computation* 206, Issues 9-10, (2008) 1074–1083.

[6] Bousquet-Mélou, M., A method for the enumeration of various classes of column convex polygons, *Disc. Math.*, 154 (1996) 1–25.

[7] Brlek, S., Labelle, G., Lacasse, A., Properties of the countour path of discrete sets, *Int. J. Found. Comp. Sci.*, 17 (2006) 543–556.

[8] Disanto, F., Duchi, E., Pinzani, R., Rinaldi, S., Polyominoes determined by permutations: enumeration via bijectiuons, *Annals of Cominatorics*, to appear.
[9] Disanto, F., Frosini, A., Pinzani, R., Rinaldi, S., A closed formula for the number of convex permutominoes, *El. J. Combinatorics*, 14 (2007) Article R57.

[10] Duchi, E., Poulalhon, D., On square permutations, *Fifth Colloquium on Mathematics and Computer Science, Proceedings of Discrete Mathematics and Theoretical Computer Science*, AI (2008) 207-222.

[11] Fanti, I., Frosini, A., Grazzini, E., Pinzani, R., Rinaldi, S., Characterization and enumeration of some classes of permutominoes, *Pure Math. Applications*, Vol. 18 No. 3-4 265-290 (2007).

[12] Guttmann, A. J. *Asymptotic analysis of power series expansions* in Phase Transitions and Critical Phenomena, **13**, (1989), 3-234, eds. C. Domb and J. L. Lebowitz, Academic Press, N.Y.

[13] Incitti, F., Permutation diagrams, fixed points and Kazdhan-Lusztig $R$-polynomials, *Ann. Comb.*, 10 (2006) 369-387.

[14] Mansour, T., Severini, S., Grid polygons from permutations and their enumeration by the kernel method, *19-th International Conference on Formal Power Series and Algebraic Combinatorics*, Tianjin, China, July 2-6, 2007.

[15] Kassel, C., Lascoux, A., Reutenauer, C., The singular locus of a Schubert variety, *J. Algebra* 269 (2003) 74–108.

[16] Sloane, N.J.A., *The On-Line Encyclopedia of Integer Sequences*, available on line at http://www.research.att.com/~njas/sequences/