# Polyominoes determined by involutions

Filippo Disanto¹ and Simone Rinaldi¹

¹Università di Siena, Dipartimento di Scienze Matematiche e Informatiche, Pian dei Mantellini 44, 53100 Siena, Italy

**Abstract.** A permutomino of size $n$ is a polyomino determined by particular pairs $(\pi_1, \pi_2)$ of permutations of length $n$, such that $\pi_1(i) \neq \pi_2(i)$, for $1 \le i \le n$. In this paper we consider the class of convex permutominoes which are symmetric with respect to the diagonal $x = y$. We determine the number of these permutominoes according to the dimension and we characterize the class of permutations associated to these objects as particular involutions of length $n$.

**Résumé.** Les permutominos de taille $n$ sont des polyominos déterminés par certaines paires de permutations $(\pi_1, \pi_2)$ de taille $n$, telles que $\pi_1(i) \neq \pi_2(i)$, pour tout $1 \le i \le n$. Dans cet article nous considérons la classe des permutominos convexes qui sont symétriques par rapport à la diagonale $x = y$. Nous déterminons le nombre de ces permutominos en fonction de leur taille et nous caractérisons la classe des permutations associées à ces objets comme un certain ensemble d’involutions de taille $n$.

**Keywords:** Enumerative Combinatorics, Convex polyominoes, Permutations, Involutions.

## 1 Convex Permutominoes

In the plane $\mathbb{Z} \times \mathbb{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 (respectively row convex) if all of its columns (respectively row) are connected. A polyomino is said to be convex, if it is both row and column convex (see Fig. 1 (a)). The semi-perimeter of a polyomino is just half the number of edges of cells in its boundary; thus, for any convex polyomino the semi-perimeter is the sum of the numbers of its rows and columns. Moreover, any convex polyomino is contained in a rectangle in the square lattice which has the same semi-perimeter, called minimal bounding rectangle. For the main results concerning the enumeration and combinatorial properties of convex polyominoes we refer to [2, 3, 5, 6].

A polyomino is said to be *directed* when each of its cells can be reached from a distinguished cell, called the root, by a path which is contained in the polyomino and uses only north and east unitary steps. A polyomino is *directed convex* if it is both directed and convex (see Fig. 1 (b)). It is known [12] that the number of directed convex polyominoes of semi-perimeter $n+2$ is equal to the $n$th central binomial coefficient, i.e., $b_n = \binom{2n}{n}$, sequence A000984 in [11]. Finally, *parallelogram* polyominoes are a special subset of the directed convex ones, defined by two lattice paths that use north and east unit steps, and intersect only at their origin and extremity. These paths are called the *upper* and the *lower path* (see
<figure><img src="image_1.png" /></figure>

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

<figure><img src="image_3.png" /><figcaption>Fig. 1: (a) A convex polyomino; (b) a directed convex polyomino; (c) a parallelogram polyomino.</figcaption></figure>

Fig. 1 (c)). It is known [12] that the number of parallelogram polyominoes having semi-perimeter $n + 1$ is the $n$-th *Catalan number* (sequence A000108 in [11]), $c_n = \frac{1}{n+1} \binom{2n}{n}$.

**Permutominoes.** Let $P$ be a polyomino without holes, having $n$ rows and columns, $n \ge 1$; we assume without loss of generality that the south-west corner of its minimal bounding rectangle is placed in (1, 1). Let $\mathcal{A} = (A_1, \dots, A_{2(r+1)})$ be the list of its vertices (i.e., corners of its boundary) ordered in a clockwise sense starting from the lowest leftmost vertex. We say that $P$ is a *permutomino* if $\mathcal{P}_1 = (A_1, A_3, \dots, A_{2r+1})$ and $\mathcal{P}_2 = (A_2, A_4, \dots, A_{2r+2})$ represent two permutations of length $n$ (as usual $S_n$ denotes the symmetric group of size $n$). Obviously, if $P$ is a permutomino, then $r = n$. The two permutations defined by $\mathcal{P}_1$ and $\mathcal{P}_2$ are indicated by $\pi_1(P)$ and $\pi_2(P)$, respectively (see Fig. 2), and their length is $n+1$ – which is the size of the permutomino. The set of convex permutominoes of size $n$ is denoted $C_n$.

<figure><img src="image_4.png" /><figcaption>Fig. 2: A permutomino of size 7 and the two associated permutations.</figcaption></figure>

From definition any permutomino $P$ of size $n$ has the property that, for each abscissa (ordinate) between 1 and $n$ there is exactly one vertical (horizontal) side in the boundary of $P$ with that coordinate. It is simple to observe that this property is also a sufficient condition for a polyomino to be a permutomino.

Permutominoes were introduced by F. Incitti while studying the problem of determining the $\tilde{R}$-polynomials associated with a pair $(\pi_1, \pi_2)$ of permutations [9]. During the last years, a particular class of permutominoes, i.e. convex permutominoes, have been widely studied, and here we recall the main results: the number of *parallelogram permutominoes* of size $n$ is equal to $c_{n-1}$ and the number of *directed convex permutominoes* of size $n$ is equal to $\frac{1}{2} b_{n-1}$ [8]. Finally, the number of *convex permutominoes* of size $n+1$ is [7]:

$$2(n+3)4^{n-2} - \frac{n}{2} \binom{2n}{n} \quad n \ge 1, \qquad (1)$$
the first few terms being 1, 4, 18, 84, 394, 1836, 8468, ... (sequence A126020) in [11]).

**Permutations defining convex permutominoes.** In [1] the authors considered the following subsets of $S_n$:

$$ \tilde{C}_n = \{ \pi_1(P) : P \in \mathcal{C}_n \}, \quad \tilde{C}'_n = \{ \pi_2(P) : P \in \mathcal{C}_n \}. $$

Easily we have that $|\tilde{C}_n| = |\tilde{C}'_n|$, and that $\pi \in \tilde{C}_n$ if and only if $\pi^R \in \tilde{C}'_n$ (where for any $\pi = (\pi_1, \dots, \pi_n)$, its reversal is $\pi^R = (\pi_n, \dots, \pi_1)$). It is then reasonable to study, without loss of generality, the class $\tilde{C}_n$. In particular, if a permutation $\pi \in \tilde{C}_n$ (i.e. there is at least a permutomino $P$ such that if $\pi = \pi_1(P)$) we say that $\pi$ is $\pi_1$-associated (briefly associated) with a convex permutomino.

Let $\pi$ be a permutation of $S_n$, we define $\mu(\pi)$ (briefly, $\mu$) as the maximal upper unimodal sublist of $\pi$, and $\sigma(\pi)$ (briefly, $\sigma$) as the sublist of $\pi$ beginning with $\pi(1)$, ending with $\pi(n)$, and containing the elements not in $\mu$ (by convention $\mu$ and $\sigma$ retain the indexing of $\pi$). For instance, for the convex permutomino in Fig. 2, we have $\pi_1 = (2, 5, 6, 1, 7, 3, 4)$, and the two subsequences $\mu$ and $\sigma$ are

<table><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><th>μ</th><td>2</td><td>5</td><td>6</td><td>-</td><td>7</td><td>-</td><td>4</td></tr><tr><th>σ</th><td>2</td><td>-</td><td>-</td><td>1</td><td>-</td><td>3</td><td>4</td></tr></tbody></table>

For the sake of brevity we will represent the two sequences omitting the empty spaces, as $\mu = (2, 5, 6, 7, 4)$, $\sigma = (2, 1, 3, 4)$. The following theorem [1] gives a characterization of the permutations of $\tilde{C}_n$.

**Theorem 1** Let $\pi \in S_n$ be a permutation. Then $\pi \in \tilde{C}_n$ if and only if:

1. $\sigma$ is lower unimodal, and

2. there are no two permutations, $\theta \in S_m$, and $\theta' \in S'_{m}$, such that $m + m' = n$, and $\pi = \theta \ominus \theta'$.

We recall that, given two permutations $\theta = (\theta_1, \dots, \theta_m) \in S_m$ and $\theta' = (\theta'_1, \dots, \theta'_{m'}) \in S_{m'}$, $\theta \ominus \theta'$ is defined as $(\theta_1 + m', \dots, \theta_m + m', \theta'_1, \dots, \theta'_{m'})$. So, for instance $(2, 5, 6, 1, 7, 3, 4)$ satisfies conditions 1. and 2. and it defines at least one convex permutomino (as the one in Fig. 2). The reader can check that (i) there is no convex permutomino associated with $(2, 5, 3, 7, 4, 1, 6)$ since $\sigma = (2, 3, 4, 1, 6)$ is not lower unimodal; (ii) there is no convex permutomino associated with $\pi = (5, 9, 8, 7, 6, 3, 1, 2, 4)$ since $\pi = (1, 5, 4, 3, 2) \ominus (3, 2, 1, 4)$. In [1] it is also proved that the cardinality of $\tilde{C}_{n+1}$ is

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

defining the sequence 1, 3, 13, 62, 301, 1450, ..., recently added to [11] as A122122.

**Convex permutominoes associated with a permutation.** For any $\pi \in \tilde{C}_n$, let us consider $[\pi] = \{P \in \mathcal{C}_n : \pi_1(P) = \pi\}$, i.e., the set of convex permutominoes associated with $\pi$. We say that a fixed point $i$ of $\pi$, with $1 < i < n$, is a free fixed point if $\pi$ can be decomposed as the direct sum $\pi = \sigma_1 \oplus (1) \oplus \sigma_2$, where $\sigma_1 \in S_{i-1}$, and $\sigma_2 \in S_{n-i}$. Let $\mathcal{F}(\pi)$ (briefly $\mathcal{F}$) denote the set of free fixed points of $\pi$.

**Theorem 2** Let $\pi \in \tilde{C}_n$, and let $\mathcal{F}(\pi)$ be the set of free fixed points of $\pi$. Then we have $|[\pi]| = 2^{|\mathcal{F}(\pi)|}$.

For instance, let $\pi = (2, 1, 3, 4, 7, 6, 5)$ we have $\mu = (2, 3, 4, 7, 6, 5)$, $\sigma = (2, 1, 5)$, and $\mathcal{F}(\pi) = \{3, 4\}$. Then there are four convex permutominoes associated with $\pi$, as shown in Fig. 3.
<figure><img src="image_5.png" /><figcaption>**Fig. 3:** The four convex permutominoes associated with (2, 1, 3, 4, 7, 6, 5). The two free fixed points are encircled.</figcaption></figure>

## 2 Symmetric permutominoes

In this paper we study the convex permutominoes which are symmetric with respect to the diagonal $x = y$, we characterize the pairs of permutations $(\pi_1, \pi_2)$ defining such permutominoes, and we give the enumeration according to the size. Since we will always assume that the objects we treat satisfy the convexity constrain, by abuse of notation we will often speak of symmetric permutominoes in place of symmetric convex permutominoes. Let $Sym_n$ denote the class of symmetric permutominoes of size $n$, and let $\tilde{Sym}_n = \{ \pi_1(P) : P \in Sym_n \}$ (see Fig. 4). It is easy to prove the following fact.

**Proposition 1** Let $P$ be a convex permutomino; then $P \in Sym_n$ if and only if both $\pi_1(P)$ and $\pi_2(P)$ are involutions.

Figure 3 shows that if $\pi_1(P)$ is an involution, then $P$ is not necessarily symmetric.

**Proposition 2** If $P$ is a symmetric permutomino, then $\pi_1(P)$ has no free fixed point.

(Sketch of proof.) Assume that $i$ is a free fixed point of $\pi_1(P)$, then $\pi_1(P) = \theta \oplus (1) \oplus \theta'$. Since the boundary of $P$ must necessarily contain the point $I = (i, \pi_1(i))$, and $P$ is symmetric with respect to $x = y$, the boundary of $P$ intersects itself in $I$. Hence $P$ is not a permutomino. As a consequence $\pi_1(P)$ has at most two fixed points. $\square$

<figure><img src="image_6.png" /><figcaption>**Fig. 4:** A symmetric permutomino of size 15 and the two associated involutions $\pi_1 = (10, 9, 11, 7, 14, 6, 4, 15, 2, 1, 3, 13, 12, 5, 8)$, $\pi_2 = (11, 10, 14, 9, 15, 7, 6, 13, 4, 2, 1, 12, 8, 3, 5)$.</figcaption></figure>
In practice, according to Proposition 2 and Theorem 2, a symmetric permutomino is uniquely determined by one of the two defining permutations, i.e. there is a trivial bijection between $Sym_n$ and $\tilde{Sym}_n$. Thus, if $\pi \in \tilde{Sym}_n$, we can legitimately say that $\pi$ defines a symmetric permutomino. The following result is straightforward.

**Theorem 3** A permutation $\pi$ defines a symmetric permutomino if and only if $\pi \in \tilde{C}_n$ and it is an involution without free fixed points.

Summarizing, a permutation $\pi$ of length $n$ belongs to $\tilde{Sym}_n$ if and only if: (1) $\sigma(\pi)$ is lower unimodal; (2) $\pi \neq \theta_1 \ominus \theta_2$ for some $\theta_1, \theta_2$; (3) $\pi$ is an involution; (4) $\pi$ does not contain free fixed points.

For instance, if $\pi = (10, 9, 11, 7, 14, 6, 4, 15, 2, 1, 3, 13, 12, 5, 8)$, we have that $\mu = (10, 11, 14, 15, 13, 12, 8)$, $\sigma = (10, 9, 7, 6, 2, 1, 3, 5, 8)$. Moreover $\pi$ is an involution, and the unique fixed point is 6 (not a free fixed point), therefore $\pi$ defines a symmetric permutomino, precisely the one depicted in Fig. 4. For $n = 2, \dots, 4$:

$$ \tilde{Sym}_2 = \{12\}, \quad \tilde{Sym}_3 = \{132, 213\}, \quad \tilde{Sym}_4 = \{1324, 1432, 2143, 3214\}. $$

## 2.1 Symmetric permutominides: a larger class of objects

Our aim in this section is to consider a larger class of objects, containing the class of symmetric permutominoes and preserving its main features. In practice, the idea is to enlarge this class including a more general class of diagrams having the basic properties of symmetric permutominoes, see Proposition 3, except for the fact that the boundary is now allowed to cross itself. These objects have nice combinatorial properties and will help us in the enumeration of symmetric permutominoes.

A set of cells is said to be convex if each of its rows and columns is non empty and connected (see Fig. 5 (a)). A convex set of cells $P$ naturally defines a boundary, and the vertices of $P$ are the points at the extremities of each side of maximal length in the boundary of $P$. To the set $P$ we associate a closed path $p(P)$ following the boundary of $P$ and connecting all its vertices. Such a path uses north $N = (0, 1)$, south $S = (0, -1)$, east $E = (1, 0)$ and west $W = (-1, 0)$ steps. It starts with a north step from the lowest leftmost vertex of $P$, and connects a generic vertex $X$ to the unique vertex, never visited before, which can be reached from $X$ following a horizontal or a vertical side of the boundary of $P$. This path naturally defines an order on the vertices of $P$ (see Fig. 5 (b)).

So let $A = (A_1, \dots, A_{2(r+1)})$ be the list of vertices of $P$. Similarly to the definition of a permutomino, we say that $P$ is a symmetric permutominide if $P_1 = (A_1, A_3, \dots, A_{2r+1})$ and $P_2 = (A_2, A_4, \dots, A_{2r+2})$ represent two involutions of $S_{r+1}$, indicated as usual by $\pi_1(P)$ and $\pi_2(P)$, respectively. We say that $n+1$ is the size of the permutominide.

For instance, Figure 5 (c) presents a permutominide and the two involutions defining it. Let $P_n$ be the class of symmetric permutominides of size $n$. Clearly, concerning polyominoes, the definitions of permutominide and of symmetric permutomino coincide, whence $Sym_n$ is strictly included in $P_n$. Indeed permutominides retain some properties of symmetric permutominoes.

**Proposition 3** If $P \in P_n$ then

1. $P$ is symmetric with respect to the diagonal $x = y$.

2. There is exactly one horizontal (vertical) side of $P$ for each ordinate (abscissa) between 1 and $n$.
<figure><img src="image_7.png" /><figcaption>**Fig. 5:** (a) a convex set of cells $P$; (b) the path $p(P)$, starting from $O$; (c) a permutominide of size 5, and its two defining involutions.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 6:** (a),(b) Two permutominides, and the associated paths and involution; (c) a convex set of cells symmetric with respect to the x-axis but not a permutominide.</figcaption></figure>

In Figure 6 (c) we see that conditions 1. and 2. are not sufficient for a polygon $P$ to be a permutominide. In contrast to what happened for symmetric permutominoes, a permutominide $P$ is not uniquely determined by simply $\pi_1(P)$. For instance, Figure 6 (a) and (b) show two distinct permutominides $P_1$ and $P_2$ such that $\pi_1(P_1) = \pi_1(P_2)$. Actually the class $\mathcal{P}_n$ can easily be partitioned into three disjoint classes:

1. the symmetric permutominoes $\text{Sym}_n$,

2. the permutominides of size $n$, which are not permutominoes and such that $\pi_1(1) < \pi_1(n)$; these objects are called, for obvious graphical reasons, *north-east oriented* permutominides (briefly *ne-permutominides*), and belong to $\mathcal{NE}_n$ (see Fig. 5 (c));

3. the permutominides $P$ of size $n$, which are not permutominoes and such that $\pi_1(1) > \pi_1(n)$; these are called *south-east oriented* permutominides (briefly *se-permutominides*), as the one in Fig. 7), and belong to $\mathcal{SE}_n$.

The *ne*-permutominides and the *se*-permutominides have a simple and rather predictable characterization, which relates the problem of their enumeration to the problem of the enumeration of some special
subclasses of symmetric permutominoes.

**Proposition 4** Let $P$ be a permutominide of size $n$. We have:

i) $P$ is a *ne-permutominide* if and only if $P$ can be uniquely decomposed into a sequence $V_1, \dots, V_h$ of symmetric permutominoes concatenated along the diagonal $x = y$, with $h \ge 2$, and where

1. $V_1$ is the reflection of a directed convex permutomino with respect to $x + y = 0$,

2. $V_2, \dots, V_{h-1}$ are parallelogram permutominoes,

3. $V_h$ is a directed convex permutomino (see for instance Fig. 5 (c)).

ii) $P$ is a *se-permutominide* if and only if $P$ can be uniquely decomposed into a sequence of $2h + 1$ permutominoes $V_1, \dots, V_h, W, V'_h, \dots, V'_1$, with $h \ge 1$, concatenated along the diagonal $x + y = n + 1$, where,

1. $V_1$ is the reflection of a directed convex permutomino with respect to the $y$-axis,

2. $V_2, \dots, V_h$ are the reflection of parallelogram permutominoes with respect to the $y$-axis,

3. $W$ is symmetric with respect to $x = y$ and is the reflection with respect to the $y$-axis of a parallelogram permutomino,

4. each $V'_i$ is the reflection of $V_i$ with respect to $x = y$ (the decomposition of a south-east oriented permutominide is shown in Fig. 7).

<figure><img src="image_9.png" /><figcaption>**Fig. 7:** A south-east oriented permutominide and its reentrant points. The path determined by its boundary, starting from $O$, has been put in evidence by means of arrows.</figcaption></figure>

For any $P \in \mathcal{P}_n$ we consider the path $p(P)$, represented by a word in the alphabet $\{N, E, S, W\}$. Using the terminology of [4], we say that an occurrence of one of the sequences $EN, SE, WS$, or $NW$ defines a *reentrant point* of $p(P)$. For brevity, we say that these are the reentrant points of $P$ (see Fig. 7). A permutominide of size $n \ge 2$ has exactly $n-2$ reentrant points, precisely one reentrant point for any abscissa and ordinate between 2 and $n-1$. Thus we have the next proposition.
**Proposition 5** The positions of the reentrant points of a permutominide of size $n$ represent a permutation matrix of dimension $n-2$, $n \ge 2$.

Moreover it is simple to check that any permutominide is uniquely determined by the set of its reentrant points.

## 2.2 A path representation for permutominides

Our aim in this section is to enumerate permutominides, and in particular symmetric permutominoes, according to their size. To do this we will encode permutominides in terms of paths in the plane.

Let us consider paths in the plane using *up* steps $U = (1, 1)$, *down* steps $D = (1, -1)$, and two types of *horizontal* steps, $(1, 0)$, namely *solid* and *dotted* horizontal steps, denoted respectively by $\alpha$ and $\beta$. Let $M_n$ be the set of these paths running from $(0, 0)$ to $(n, 0)$, remaining weakly above the $x$-axis and with the further requirements that:

- an $\alpha$ (solid) step can never occur after the first occurrence of a down step;

- a $\beta$ (dotted) step can never occur before the last occurrence of an up step.

Examples of paths of this class are given in Fig. 9, 10, 11.

<figure><img src="image_10.png" /><figcaption>**Fig. 8:** (a) The four types of reentrant points of a permutominide; (b) the coding of each reentrant point through the mapping $\varphi$.</figcaption></figure>

Now we define the mapping $\varphi : \text{Sym}_n \cup \text{SE}_n \rightarrow M_{n-2}$. Let $P$ be a permutominide in $\text{Sym}_n \cup \text{SE}_n$. The function $\varphi$ maps each type of reentrant point of $P$ into a different type of step (as sketched in Fig. 8):

- a reentrant point $EN$ is mapped to an up step $U$;

- a reentrant point $SE$ is mapped to a horizontal dotted step $\beta$;

- a reentrant point $WS$ is mapped to a down step $D$;

- a reentrant point $NW$ is mapped to an up a horizontal solid step $\alpha$.

The path $\varphi(P)$ is obtained as the concatenation of the steps encoding the reentrant points of $P$ from left to right. For instance, the permutomino in Fig. 4 is mapped to the path in Fig. 9 (a), while the south-east oriented crossing permutomino in Fig. 7 is mapped to the path in Fig. 9 (b).

**Proposition 6** For any $n \ge 2$, the function $\varphi$ is a bijection between the sets $\text{Sym}_n \cup \text{SE}_n$ and $M_{n-2}$.
<figure><img src="image_11.png" /><figcaption>Fig. 9: The image, through $\varphi$, of the permutominoes of Fig. 4 (a), and Fig. 7 (b).</figcaption></figure>

(Sketch of proof.) Let $P \in \text{Sym}_n \cup \text{SE}_n$. It is clear that $\varphi(P)$ is a path made of $n-2$ steps. The proof consists of two steps:

(a) $\varphi(P) \in M_{n-2}$. Since the permutominide $P$ is not north-east oriented, the path $\varphi(P)$ cannot pass below the x-axis; moreover, it is clear that, from left to right, the reentrant points of type EN must all come before the first reentrant point of type SE, and similarly, the reentrant points of type NW must all come before the first reentrant point of type WS. Therefore an $\alpha$ step in $\varphi(P)$ can never occur after the leftmost occurrence of a down step, and a $\beta$ step in $\varphi(P)$ can never occur before the rightmost occurrence of an up step.

(b) $\varphi(P)$ is a bijection. To see this we define a function $\xi : M_{n-2} \to \text{Sym}_n \cup \text{SE}_n$ such that, for all $P \in \text{Sym}_n \cup \text{SE}_n$, we have $\xi(\varphi(P)) = P$. Let $w = w_1 \dots w_{n-2} \in M_{n-2}$, and let $r$ (respectively $s$) be the number of the horizontal solid $\alpha$ steps (respectively horizontal dotted steps $\beta$) in $w$. The first step to build $\xi(P)$ is to place its reentrant points, according to the following rule:

* if $w_i$ is the $j$th up step of $w$, then we place a reentrant point of type EN in the point $(i+1, l+1)$ where $l$ is the index such that $w_l$ is the $j$th down step.

* if $w_i$ is the $j$th down step of $w$, then we place a reentrant point of type WS in the point $(i+1, l+1)$ where $l$ is the index such that $w_l$ is the $j$th up step.

* if $w_i$ is the $j$th horizontal $\alpha$ step of $w$, then we place a reentrant point of type NW in the point $(i+1, l+1)$ where $l$ is the index such that $w_l$ is the $(r-j+1)$th horizontal $\alpha$ step.

* if $w_i$ is the $j$th horizontal $\beta$ step of $w$, then we place a reentrant point of type SE in the point $(i+1, l+1)$ where $l$ is the index such that $w_l$ is the $(s-j+1)$th horizontal $\beta$ step.

Once the $n-2$ reentrant points have been placed, by connecting them we can easily build the unique permutominide of size $n$ having these points as reentrant points. It is also simple to prove that $\xi = \varphi^{-1}$. □

Figure 10 (a) depicts a path $w$ in $M_{13}$, where the number $i$ above an up (resp. down, $\alpha, \beta$) step means that this is the $i$th up (resp. down, $\alpha, \beta$) step in $w$. Let us place the reentrant points of $\varphi^{-1}(w)$. In $w$ we have $r=6$, $s=2$. The first step of $w$, i.e. $w_1$, is an $\alpha$ horizontal step; the step corresponding to it is the 6th $\alpha$ step, which is $w_9$. Then we place a reentrant point of type NW in position (2, 10). In a symmetric manner, applying the same rule to the step $w_9$, we must place a reentrant point of type NW in position (10, 2). Then we go on with $w_2$, which is the first up step, and we place a EN reentrant point in position (3, 11), since $w_{10}$ is the first down step in $w$. We have also to place a WS reentrant point in position (11, 3). Similarly we can place all the other reentrant points of $\xi(w)$, and then build the permutominide.
<figure><img src="image_12.png" /><figcaption>**Fig. 10:** (a) A path $w$ in $M_{13}$; (b) the set of the reentrant points of $\varphi^{-1}(w)$; joining these points in the natural way we obtain the permutomino of size 15 depicted in Fig. 7.</figcaption></figure>

Proposition 6 ensures that

$$|Sym_n| + |SE_n| = |Sym_n \cup SE_n| = |M_{n-2}|. \qquad (3)$$

## 2.3 Enumeration of various classes of symmetric permutominoes

Here we consider some subclasses of symmetric permutominoes and enumerate them using the bijection $\varphi$.

**Proposition 7** Let $P \in Sym_n$. Then:

1. $P$ is directed convex if and only if $\varphi(P)$ does not contain $\alpha$ steps (see Fig. 11 (a));

2. $P$ is parallelogram if and only if $\varphi(P)$ does not contain $\alpha$ or $\beta$ steps, i.e. it is a Dyck path (see Fig. 11 (b)).
The enumeration of these two classes is then straightforward, using standard combinatorial techniques. The generating function of directed convex symmetric permutominoes is

$$Dir(x) = \frac{x(1 - 2x - \sqrt{1 - 4x^2})}{2(2x - 1)}. \qquad (4)$$

The number of symmetric directed convex permutominoes of size $n$ is therefore $\binom{n-2}{\lfloor \frac{n-2}{2} \rfloor}$. Similarly, the generating function of parallelogram symmetric permutominoes is

$$Par(x) = \frac{1 - \sqrt{1 - 4x^2}}{2}, \qquad (5)$$

and the number of parallelogram symmetric permutominoes of size $2n$ is equal to the Catalan number $c_{n-2}$.

<figure><img src="image_13.png" /><figcaption>**Fig. 11:** (a) a symmetric directed convex permutomino; (b) A symmetric parallelogram permutomino; (c) a symmetric reflected parallelogram permutomino, and their encoding path.</figcaption></figure>

In this section we are also interested in the class of symmetric permutominoes which are the reflection of a parallelogram permutomino with respect to the $x$-axis, which we will call reflected parallelogram symmetric permutominoes. Clearly, such permutominoes can only have reentrant points of type SE or NW, and $\phi$ maps them into paths without up or down steps (see Fig. 11 (c)).

**Proposition 8** The number of reflected parallelogram symmetric permutominoes having size $n$ is equal to $\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$.

(Sketch of proof.) A reflected parallelogram symmetric permutomino of size $n$ is uniquely determined by the sub-path $p$ of its boundary running from $(1, n)$ to the diagonal $x = y$, and remaining weakly above the diagonal $x + y = n + 1$, as shown in Fig. 12. Such a path $p$ is (up to a rotation) a prefix of a Dyck path of length $n-1$. Since the number of prefixes of Dyck paths of length $n-1$ is equal to $\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$ [12], we obtain the thesis. □
<figure><img src="image_14.png" /><figcaption>Fig. 12: (a) The path p; (b) the symmetric of p with respect to the diagonal x = y; (c) the unique permutomino obtained from p.</figcaption></figure>

## 2.4 Enumeration of symmetric and permutominides

In order to complete the enumeration of symmetric permutominoes, according to the identity (3), we need to count the sets $SE_n$ and $M_n$. Using the decomposition given in Proposition 4, and the generating functions of the various classes involved in such a decomposition – determined in the previous section – it is a simple exercise to compute the generating function of $SE_n$. We also need to recall from [8] that the generating functions of directed convex permutominoes and of parallelogram permutominoes are, respectively,

$$D(x) = \frac{x - \sqrt{1 - 4x}}{2\sqrt{1 - 4x}} \qquad P(x) = \frac{1 - 2x - \sqrt{1 - 4x}}{2}.$$

**Proposition 9** The generating function of south-east oriented permutominides according to the size is

$$SE(x) = \frac{\mathrm{Ref}(x) D(x^2)}{x^2 - P(x^2)} = \frac{x^2}{2(1 - 2x)\sqrt{1 - 4x^2}} - \frac{x^2}{2(1 - 2x)}, \qquad (6)$$

where Ref(x) is the generating function of reflected parallelogram symmetric permutominoes.

(Sketch of proof.) By the decomposition in Proposition 4, an se-permutominide P of size n can be uniquely decomposed into a sequence of $2h + 1$ permutominoes concatenated along the diagonal $x + y = n + 1$. We observe that the size of P is given by the sum of the sizes of the components minus $2h$. Hence the generating function is given by

$$\mathrm{Ref}(x) \frac{D(x^2)}{x^2} \left( 1 + \frac{P(x^2)}{x^2} + \frac{P(x^2)^2}{x^4} + \dots + \frac{P(x^2)^k}{x^{2k}} + \dots \right),$$

from which the assertion of the proposition follows. □

Consequently, the number of south east oriented permutominides of size n is:

$$|SE_n| = \frac{n-1}{2} \binom{n-2}{\lfloor \frac{n-2}{2} \rfloor} - 2^{n-3}.$$

We remark that the “smallest” permutomino of this class has size 4. Using standard combinatorial techniques it is easy to determine the generating function of the class $M_n$.
**Proposition 10** The generating function of the class $M_n$ is

$$M(x) = \frac{x(3 - 4x - \sqrt{1 - 4x^2})}{2(2x - 1)^2}. \qquad (7)$$

Now we have all ingredients to determine the number of symmetric permutominoes.

**Theorem 4** The generating function of the class $Sym_n$ is

$$Sym(x) = \frac{x(1-x)^2}{(1-2x)^2} - \frac{x^2(1+x)}{(1-2x)\sqrt{1-4x^2}} - x, \qquad (8)$$

and therefore the number of symmetric permutominoes of size $n$ is equal to:

$$|Sym_n| = (n + 2)2^{n-3} - (n - 1)\left(\left\lfloor\frac{n-2}{2}\right\rfloor\right) - (n - 2)\left(\left\lfloor\frac{n-3}{2}\right\rfloor\right) \quad n \ge 2. \qquad (9)$$

The sequence begins with 1, 2, 4, 10, 22, 54, 120, 284, ... and it is not in [11]. Due to the decomposition given in Proposition 4, the generating function of north-east oriented permutominides is given by $\frac{Dir^2(x)}{x-Par(x)}$, hence it is equal to

$$NE(x) = \frac{x^2(2x - 1 + \sqrt{1 - 4x^2})}{2(1 - 2x)^2}.$$

Finally, recalling that $|P_n| = |Sym_n| + |SE_n| + |NE_n| = |M_n| + |NE_n|$, we have

**Theorem 5** The generating function of the class $P_n$ is

$$P(x) = \frac{x^2(1-x)}{(1-2x)^2}, \qquad (10)$$

and therefore the number of permutominides of size $n$ is $n 2^{n-3}$.

The result in Theorem 5 is quite surprising, since it states that the permutominides are a rational class of objects, while all its subclasses we have previously studied are algebraic ones. It is also possible to prove equation (10) in a bijective way, but such a proof is omitted here for the sake of brevity. The table below lists the first terms of the main sequences treated in the paper, and their identifying number in the Sloane database [11]. We point out that diagonally symmetric polyominoes were first studied in [10], where the sequence $Ref_n$ was also determined.

<table><thead><tr><th>n</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>...</th><th>Sequence in [11]</th></tr></thead><tbody><tr><td>P<sub>n</sub></td><td>1</td><td>3</td><td>8</td><td>20</td><td>48</td><td>112</td><td>256</td><td>576</td><td>1280</td><td>...</td><td>A001792</td></tr><tr><td>M<sub>n</sub></td><td>1</td><td>2</td><td>5</td><td>12</td><td>29</td><td>68</td><td>158</td><td>360</td><td>813</td><td>...</td><td>---</td></tr><tr><td>Sym<sub>n</sub></td><td>1</td><td>2</td><td>4</td><td>10</td><td>22</td><td>54</td><td>120</td><td>284</td><td>626</td><td>...</td><td>---</td></tr><tr><td>SE<sub>n</sub></td><td>0</td><td>0</td><td>1</td><td>2</td><td>7</td><td>14</td><td>38</td><td>76</td><td>187</td><td>...</td><td>A107373</td></tr><tr><td>NE<sub>n</sub></td><td>0</td><td>1</td><td>3</td><td>8</td><td>19</td><td>44</td><td>98</td><td>216</td><td>467</td><td>...</td><td>---</td></tr><tr><td>Dir<sub>n</sub></td><td>1</td><td>1</td><td>2</td><td>3</td><td>6</td><td>10</td><td>20</td><td>35</td><td>70</td><td>...</td><td>A001405</td></tr><tr><td>Par<sub>n</sub></td><td>1</td><td>0</td><td>1</td><td>0</td><td>2</td><td>0</td><td>5</td><td>0</td><td>14</td><td>...</td><td>A000108</td></tr><tr><td>Ref<sub>n</sub></td><td>1</td><td>2</td><td>3</td><td>6</td><td>10</td><td>20</td><td>35</td><td>70</td><td>126</td><td>...</td><td>A001405</td></tr></tbody></table>
References

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

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

[3] Bousquet-Mèlou, M., Guttmann, A. J., Enumeration of three dimensional convex polygons, *Ann. of Comb.*, 1 (1997) 27–53.

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

[5] Chang, S.J., Lin, K.Y., Rigorous results for the number of convex polygons on the square and honeycomb lattices, *J. Phys. A: Math. Gen.*, 21 (1988) 2635–2642.

[6] Delest, M., Viennot, X.G., Algebraic languages and polyominoes enumeration, *Theor. Comp. Sci.*, 34 (1984) 169–206.

[7] Disanto, F., Frosini, A., Pinzani, R., Rinaldi, S., A closed formula for the number of convex permutominoes, *El. J. Combinatorics*, 14 (2007) #R57.

[8] Fanti, I., Frosini, A., Grazzini, E., Pinzani, R., Rinaldi, S., Polyominoes determined by permutations, (*submitted*).

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

[10] Leroux, P., Rassart, E., Robitaille, A., Enumeration of Symmetry Classes of Convex Polyominoes in the Square Lattice, *Adv. Appl. Math.*, 21 (1998) 343–380.

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

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