# Enumeration of Symmetry Classes of Parallelogram PolyominoesWork partially supported by NSERC (Canada) and FCAR (Québec).

## 1 Introduction

Parallelogram polyominoes, sometimes called staircase polyominoes, form a subclass of (horizontally and vertically) convex polyominoes on the square lattice, characterized by the fact that they touch the bottom-left and the top-right corners of their minimal bounding rectangle. See Figure 1. A $`90^{}`$ rotation of these would give a distinct but equivalent class of parallelogram polyominoes. In the same way as for general convex polyominoes, the area of a parallelogram polyomino is defined as the number of cells that it contains and the half-perimeter is equal to the sum of its width and height. Considerable literature can be found on the enumeration of various classes of polyominoes having some convexity and directedness property, with motivation coming from combinatorics, statistical physics, computer science and recreational mathematics. See M. Bousquet-Mélou  for a recent survey. In particular, parallelogram polyominoes have been studied with respect to their perimeter and area first by Pólya, with further contributions yielding refined enumerations from Bender, Klarner, Rivest, Delest, Fédou, Viennot and others. Mireille Bousquet-Mélou, using the Temperley methodology (), has given a generating function with respect to height, width, area and height of first and last columns (, ).

Polyominoes are usually considered equivalent if they can be obtained from one another by a plane translation. They are sometimes called translation-type polyominoes to be more precise (see D. A. Klarner ). It is natural to consider also congruence-type polyominoes, that is, equivalence classes of polyominoes under rotations and reflections. They occur as pieces that can freely move in space, as in plane packing problems (see S. W. Golomb ). In , the enumeration of congruence-type polyominoes, according to area and perimeter, has been carried out in the case of convex polyominoes.

The problem is equivalent to the enumeration of orbits of the dihedral group $`𝔇_4`$, of symmetries of the square, acting on convex polyominoes. The group $`𝔇_4`$ contains eight elements, usually represented as $`1`$, $`r`$, $`r^2`$, $`r^3`$, $`h`$, $`v`$, $`d_1`$ and $`d_2`$, where $`1`$ denotes the identity element, $`r`$ denotes a rotation by a right angle, $`h`$ and $`v`$, reflections with respect to the horizontal and vertical axes respectively, and $`d_1`$ and $`d_2`$, reflections about the two diagonal axes of the square (we take the bissector of the first quadrant for $`d_2`$). The number of orbits $`|X/G|`$ of any finite group $`G`$ acting on a set $`X`$ is given by the Cauchy-Frobenius formula (alias Burnside’s Lemma):

$$|X/G|=\frac{1}{|G|}\underset{gG}{}|\mathrm{Fix}(g)|,$$
(1)   
where $`\mathrm{Fix}(g)`$ denotes the set of elements of X which are $`g`$-symmetric, that is, invariant under $`g`$. Hence the enumeration of congruence-type convex polyominoes involves determining the size of the symmetry classes of convex polyominoes for each group element $`g𝔇_4`$. Formula (1) is valid for infinite sets provided a weighted cardinality $`|X|_\omega `$ is taken, with respect to some $`G`$-invariant weight function $`\omega `$. For a class $`𝒫`$ of polyominoes this means using generating series $`𝒫(t,q)`$ with respect to half-perimeter and area (variables $`t`$ and $`q`$), for example.

The main goal of this paper is to carry out a similar procedure for the class $``$ of parallelogram polyominoes. We observe that a subgroup of $`𝔇_4`$ acts on parallelogram polyominoes, which we denote $`𝔇_2`$, namely $`𝔇_2=r^2,d_1=\{1,r^2,d_1,d_2\}`$, and that congruence types of parallelogram polyominoes coincide with orbits of $``$ under $`𝔇_2`$. In the following sections we therefore compute the generating series of the symmetry classes $`\mathrm{Fix}(g)`$ of parallelogram polyominoes for all $`g𝔇_2`$ except the identity. We then use (1) to obtain $`(/𝔇_2)(t,q)`$.

It is also possible to count asymmetric parallelogram polyominoes, that is polyominoes that are not $`g`$-invariant for any $`g`$ except the identity, using Möbius inversion in the lattice of subgroups of $`𝔇_2`$. This requires also the enumeration of the subclass $`\mathrm{Fix}(𝔇_2)`$ of $``$, of totally symmetric parallelogram polyominoes. We carry out this computation and show that asymmetric parallelogram polyominoes are asymptotically equivalent to all parallelogram polyominoes, as expected.

As we will see, the enumeration of all the symmetry classes of parallelogram polyominoes, according to perimeter, involves in one way or the other either the Dyck paths (or Dyck words, see J. Labelle ), counted by the Catalan numbers $`c_n`$, or the left factors of Dyck paths, counted by the central binomial coefficients $`b_n`$ (see Cori and Viennot ), where

$$b_n=\left(\genfrac{}{}{0pt}{}{2n}{n}\right)\text{and}c_n=\frac{1}{n+1}\left(\genfrac{}{}{0pt}{}{2n}{n}\right).$$
(2)   
When the area is taken into account, $`q`$-analogues (some well-known and some novel) of these numbers appear naturally.

We would like to thank X. G. Viennot and M. Bousquet-Mélou for useful discussions.

## 2 Enumeration of parallelogram polyominoes

It has been known for a long time (Levine , Pólya ) that the number of parallelogram polyominoes of perimeter $`2n`$ is given by the Catalan number $`c_{n1}=\frac{1}{n}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)`$. One proof of this fact is provided by the following bijection, due to Delest and Viennot () between parallelogram polyominoes of perimeter $`2n+2`$ and Dyck paths of length $`2n`$: given a parallelogram polyomino $`P`$ of perimeter $`2n+2`$, let $`(a_1,a_2,\mathrm{},a_k)`$ be the sequence of column heights of $`P`$, and $`(b_1,b_2,\mathrm{},b_{k1})`$ be such that $`b_i`$ is the number of cells of contact between columns $`i`$ and $`i+1`$ of $`P`$. The associated Dyck path $`D`$ is the unique Dyck path with $`k`$ peaks and $`k1`$ valleys such that the peak heights are given in order by the sequence $`(a_1,a_2,\mathrm{},a_k)`$, and the valley heights by the sequence $`(b_11,b_21,\mathrm{},b_{k1}1)`$ (the horizontal axis is at level $`0`$). The height of $`P`$ is $`n+1k=n(k1)`$, which is also given by

$$a_1+(a_2b_1)+(a_3b_2)+\mathrm{}+(a_kb_{k1})=\underset{i=1}{\overset{k}{}}a_i\underset{j=1}{\overset{k1}{}}b_j.$$

On the other hand, the number of $``$ steps in $`D`$, that is the half-length of the path, is given by

$$\underset{i=1}{\overset{k}{}}a_i\underset{j=1}{\overset{k1}{}}(b_j1)=\underset{i=1}{\overset{k}{}}a_i\underset{j=1}{\overset{k1}{}}b_j+(k1),$$

which is seen to be $`n`$ by the previous equation. Hence $`D`$ is a Dyck path of length $`2n`$.

Also, note that the sum of the heights of the peaks, $`_{i=1}^ka_i`$ is simply the area of $`P`$. Figure 2 illustrates the bijection.

It follows that the generating series $`(t)`$ for parallelogram polyominoes according to half-perimeter is

$$(t)=\underset{n2}{}c_{n1}t^n=\frac{12t\sqrt{14t}}{2}.$$
(3)   
It has also been known for some time that when the area is taken into account, the generating series involves a quotient of $`q`$-analogues of Bessel functions (see Klarner and Rivest  and Bender ). Pólya ( and ) found a Laurent series relating the area and perimeter generating function to a specialization of itself, from which the terms of the series can be extracted easily. The width, height and area generating series can also be expressed as a continued fraction (see ). We will use the following recent more general form due to M. Bousquet-Mélou , giving the generating series $`(v,x,y,q)`$ of parallelogram polyominoes, where the variables $`v`$, $`x`$, $`y`$ and $`q`$ mark respectively the height of the rightmost column, the width, the overall height, and the area.

###### Proposition 1

() The generating function $`(v,x,y,q)`$ of parallelogram polyominoes is given by

$$(1,v,x,y,q)=vy\frac{J_1(v,x,y,q)}{J_0(x,y,q)},$$
(4)   
with

$$J_0(x,y,q)=\underset{n0}{}\frac{(1)^nx^nq^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}}{(q)_n(yq)_n}$$
(5)   
and

$$J_1(v,x,y,q)=\underset{n1}{}\frac{(1)^{n1}x^nq^{\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)}}{(q)_{n1}(yq)_{n1}(1vyq^n)}$$
(6)   
with the usual notation $`(a)_n=(a;q)_n=_{i=0}^{n1}(1aq^i)`$. $`\mathrm{}`$

Note that the half-perimeter and area generating function $`(t,q)`$ of parallelogram polyominoes is obtained by putting $`v=1`$, $`x=t`$, $`y=t`$ in (4).

## 3 Symmetry classes of parallelogram polyominoes

### 3.1 Rotational symmetry

Observe that if we apply the Delest-Viennot bijection to an $`r^2`$-symmetric parallelogram polyomino of perimeter $`2k+2`$, the Dyck path we obtain is vertically symmetric (or, equivalently, the Dyck word associated to it is a palindrome). Hence we need only consider half the path, which is simply a left factor, of length $`k`$, of a Dyck path.

###### Proposition 2

The number of $`r^2`$-symmetric parallelogram polyominoes of half-perimeter $`k+1`$ is equal to the number of left factors of Dyck paths, of length $`k`$. $`\mathrm{}`$

###### Corollary 3

The number of $`r^2`$-symmetric parallelogram polyominoes of half-perimeter $`k+1`$ is given by

$$r_{k+1}(1)=\{\begin{array}{cc}\left(\genfrac{}{}{0pt}{}{k}{k/2}\right)\hfill & \text{if }k\text{ is even},\hfill \\ \frac{1}{2}\left(\genfrac{}{}{0pt}{}{k+1}{(k+1)/2}\right)\hfill & \text{if }k\text{ is odd}.\hfill \end{array}$$
(7)   
It is known that the number of left factors of length $`2n`$ of Dyck words is equal to the number of words in the alphabet {0,1} with distribution $`0^n1^n`$, from which (7) follows easily. See  for a bijective proof. Here we prove (7) using generating functions. Dyck paths and left factors of Dyck paths are generated by the algebraic grammar

$`C\epsilon +xC\overline{x}C`$   
$`LC+CxL,`$   
over the alphabet $`\{x,\overline{x}\}`$. $`C`$ denotes the Dyck paths and $`L`$ the left factors, while $`x`$ and $`\overline{x}`$ respectively denote a $``$ step and a $``$ step. The first production rule gives $`C(x,\overline{x})=1+x\overline{x}C(x,\overline{x})^2`$, which we solve for

$$C(x,\overline{x})=\frac{1\sqrt{14x\overline{x}}}{2x\overline{x}}.$$

The second production rule gives $`L(x,\overline{x})=C(x,\overline{x})(1+xL(x,\overline{x}))`$, which we can solve, now that we have $`C(x,\overline{x})`$, for

$$L(x,\overline{x})=\frac{\sqrt{14x\overline{x}}1}{x(12\overline{x}\sqrt{14x\overline{x}})}.$$

Substituting $`xt,\overline{x}t`$ into $`L(x,\overline{x})`$ gives the generating series $`L(t)`$ of left factors of Dyck paths by their length:

$$L(t)=\frac{2t1+\sqrt{14t^2}}{2t(1t)},$$

from which (7) follows. $`\mathrm{}`$

In order to include the area, we could extend another bijection, due to Bousquet-Mélou and Viennot , involving heaps of segments, to left factors of Dyck paths. However, there is a more direct approach. Indeed, parallelogram polyominoes with rotational symmetry can be obtained from two copies of a same parallelogram polyomino glued together. The glueing process depends on whether we want the final object to be of even width or of odd width, as can be seen in Figure 3. If $`R_2(x,y,q)`$ is the generating function of $`r^2`$-symmetric parallelogram polyominoes, then

$$R_2(x,y,q)=R_2^{(e)}(x,y,q)+R_2^{(o)}(x,y,q)$$
(8)   
where $`R_2^{(e)}(x,y,q)`$ and $`R_2^{(o)}(x,y,q)`$ are respectively the generating series of even-width and odd-width $`r^2`$-symmetric parallelogram polyominoes.

###### Proposition 4

The generating function $`R_2^{(e)}(x,y,q)`$ of even-width parallelogram polyominoes is given by

$$R_2^{(e)}(x,y,q)=\frac{1}{1y}\left((\frac{1}{y},x^2,y^2,q^2)(1,x^2,y^2,q^2)\right).$$
(9)   
where $`(v,x,y,q)`$ is the generating function (4) of parallelogram polyominoes.

Let $`P`$ be an $`r^2`$-symmetric parallelogram of even width. We define the fundamental region of $`P`$ to be the left half of $`P`$. Call this polyomino $`Q`$ (see Figure 3(a)). We first remark that $`Q`$ is a parallelogram polyomino. To get $`P`$ from $`Q`$, we rotate a copy of $`Q`$ by $`180^{}`$ and glue the result $`\overline{Q}`$ to $`Q`$ along the rightmost column. If this column has length equal to $`k`$, there will be $`k`$ possible positions for $`\overline{Q}`$ relative to $`Q`$. The substitution $`v1/y`$, $`xx^2`$, $`yy^2`$ and $`qq^2`$ in the generating series $`P(1,v,x,y,q)`$ of directed convex polyominoes corresponds to the highest position of $`\overline{Q}`$, which minimizes the overall height of $`P`$. All the possible positions will be accounted for by multiplying by $`(1+y+\mathrm{}+y^{k1})`$. In other words, the substitution to make in $`(v,x^2,y^2,q^2)`$ is

$$v^k\frac{1+y+\mathrm{}+y^{k1}}{y^k}=\frac{1}{1y}\left(\frac{1}{y^k}1\right).$$
(10)   
Summing over all possible $`k`$’s, we find the proposed generating series (9) for $`r^2`$-symmetric parallelograms. $`\mathrm{}`$

###### Proposition 5

The generating function $`R_2^{(o)}(x,y,q)`$ of odd-width parallelogram polyominoes is given by

$$R_2^{(o)}(x,y,q)=\frac{1}{x}(\frac{1}{yq},x^2,y^2,q^2).$$
(11)   
where $`(v,x,y,q)`$ is the generating function of parallelogram polyominoes.

The proof is similar to the previous one. The main difference is that only one glueing position of $`\overline{Q}`$ to $`Q`$ is admissible and that furthermore the rightmost column of $`Q`$ and its rotated image in $`\overline{Q}`$ are superimposed to yield an odd width (see Figure 3(b)). Details are left to the reader. $`\mathrm{}`$

We would like to find the number of $`r^2`$-symmetric parallelograms of a given half-perimeter, without losing the area information, i.e. we want to express the generating series in the form

$$R_2(t,q)=R_2(t,t,q)=\underset{k0}{}r_k(q)t^k.$$
(12)   
The above expressions for the generating series of $`r^2`$-symmetric parallelogram polyominoes can be used to extract the polynomials $`r_k(q)`$ from it (i.e. develop it in powers of $`t`$ after substituting $`xt,yt`$ in it). Here are the first few of these polynomials:

$`r_2(q)`$ $`=`$ $`q`$   
$`r_3(q)`$ $`=`$ $`2q^2`$   
$`r_4(q)`$ $`=`$ $`q^4+2q^3`$   
$`r_5(q)`$ $`=`$ $`2q^6+2q^4`$   
$`r_6(q)`$ $`=`$ $`q^9+2q^8+q^7+2q^6+4q^5`$   
### 3.2 Reflective symmetries

We begin by introducing a subfamily of parallelogram polyominoes which we will call Dyck polyominoes as they correspond to Dyck paths drawn over and above the main diagonal. We will also consider truncated Dyck polyominoes, which we will call left factors of Dyck polyominoes (or $`LFD`$ polyominoes for short), again in analogy with the left factors of Dyck paths. Dyck and $`LFD`$ polyominoes are illustrated in Figure 4.

We introduce $`L_n(u)=L_n(u,y,q)`$ the generating function for $`LFD`$ polyominoes having a basis of width $`n`$, with variables $`u`$, $`y`$ and $`q`$ corresponding to the number of cells of the uppermost row, the height and the area respectively. $`L_n(u)`$ can be defined recursively by the following functional equation, illustrated in Figure 5:

$$L_n(u)=u^nyq^n+\frac{yu^2q^2}{1uq}(L_n(1)L_n(uq)).$$
(13)   
The generating function $`L(u)`$ of all $`LFD`$ polyominoes is simply the sum over all possible base widths,

$$L(u)=\underset{n1}{}L_n(u).$$
(14)   
Moreover, the Dyck polyominoes being the $`LFD`$ polyominoes with width one bases, their height and area generating series $`D(t,q)`$ is given by

$$D(y,q)=L_1(1,y,q).$$
(15)   
A straightforward application of Lemma 2.3 from  (M. Bousquet-Mélou) gives the solution to the functional equation (13). As we do not need the variable $`u`$ for our purpose, we set it equal to $`1`$, which simplifies the expression for the generating function.

###### Proposition 6

The area and height generating function $`L_n(1,y,q)`$ for $`LFD`$ polyominoes having a basis of width $`n`$ is given by

$$L_n(1,y,q)=\frac{{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^my^{m+1}q^{(m+n)(m+1)}}{(q)_m}}}{{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^my^mq^{m(m+1)}}{(q)_m}}}.$$
(16)   
$`\mathrm{}`$

For $`n=1`$, this gives

$$D(y,q)=\frac{{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^my^{m+1}q^{(m+1)^2}}{(q)_m}}}{{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^my^mq^{m(m+1)}}{(q)_m}}}$$
(17)   
for the height and area generating function for Dyck polyominoes. However, we can also express $`D(y,q)`$ using the classical $`q`$-analogue of Catalan numbers $`c_n(q)`$, satisfying the recurrence

$$c_n(q)=\underset{k=0}{\overset{n1}{}}q^kc_k(q)c_{n1k}(q),$$
(18)   
as it is well known that they area-enumerate Dyck paths of length $`2n`$. The area enumerated by $`c_n(q)`$ is the number of cells under the path and strictly above its supporting diagonal (i.e. the cells on the diagonal are not included in the area). To get a Dyck polyomino from a Dyck path, we have to add the area of the diagonal. If the length of the path is $`2n`$, then a factor of $`q^n`$ has to be added. A further diagonal of cells has to be added because the Dyck paths can touch the supporting diagonal, in which case they are not polyominoes. For the paths of length $`2n`$, $`n+1`$ cells thus have to be added, contributing a further $`q^{n+1}`$ factor to the area. This last diagonal also adds one unit of height to the polyominoes. Hence

$$D(y,q)=\underset{n1}{}y^nq^{2n1}c_{n1}(q).$$
(19)   
#### 3.2.1 Reflective symmetry along the first diagonal

There is a nice area-preserving bijection between $`d_1`$-symmetric parallelograms of a given half-perimeter and $`r^2`$-symmetric parallelograms with same half-perimeter. Since the minimal rectangle of a $`d_1`$-symmetric parallelogram is necessarily a square, the perimeter is a multiple of $`4`$, and thus the half-perimeter is even. Hence we have

$$D_1(x,y,q)=\underset{k0}{}r_{2k}(q)t^{2k},$$
(20)   
where $`D_1(x,y,q)`$ is the generating series of $`d_1`$-symmetric parallelogram polyominoes and the $`r_{2k}(q)`$ are defined by (12). The bijection is shown on an example in Figure 6, and goes as follows: a $`r^2`$-symmetric parallelogram has a center of rotation. If it has even half-perimeter, this center will either fall in the center of a cell (if both the height and the width are odd) or be the common corner of four cells forming a square (if both the height and the width are even). In both cases, we consider the first diagonal (parallel to the bissector of the second quadrant) passing through the center of rotation and the region of the parallelogram below the second diagonal (see Figure 6). This region is not a polyomino, but the parallelogram is obtained by glueing the region and a copy of it rotated by $`180^{}`$ in the unique way such that there are no “half-cells” left. Suppose that instead of rotating the copy of the region, we reflect it along the second diagonal and glue it so that there are no half-cells left, then we clearly obtain a $`d_1`$-symmetric parallelogram which, further, has the exact same perimeter and area as the initial $`r^2`$-symmetric parallelogram. We can similarly reverse the process to start with an arbitrary $`d_1`$-symmetric parallelogram and end with a $`r^2`$-symmetric parallelogram.

#### 3.2.2 Reflective symmetry along the second diagonal

We next consider $`d_2`$-symmetric parallelogram polyominoes, i.e. parallelograms which are left invariant by a symmetry along the second diagonal. Figure 7 gives an example of such a parallelogram. We observe first that the minimal rectangle of such a parallelogram will always be a square with side length equal to the quarter-perimeter of the inscribed parallelogram.

We note that $`d_2`$-symmetric parallelogram polyominoes can be constructed from two copies of a same Dyck polyomino, whose diagonals we glue together (dark cells on Figure 7). The area of the final object will be twice the area of the Dyck polyomino minus the area of diagonal, which was counted twice. There are as many cells on the diagonal as the height of the Dyck polyomino, and the width of the final object will also be the height of the Dyck polyomino. Hence we get

###### Proposition 7

The generating series $`D_2(x,y,q)`$ of $`d_2`$-symmetric parallelogram polyominoes is given by

$$D_2(x,y,q)=D(\frac{xy}{q},q^2).$$
(21)   
$`\mathrm{}`$

#### 3.2.3 Reflective symmetry along both diagonals

The final (non-cyclic) subgroup whose set of fixed elements we study is the whole group itself. This group is generated by any two nontrivial elements, but it is convenient to consider the symmetries along the two diagonals as the generators. This allows us to characterize the fundamental region of a $`𝔇_2`$-symmetric parallelogram, as can be seen in Figure 8.

We note first that the minimal rectangle of a $`𝔇_2`$-symmetric parallelogram $`P`$ is a square. We remark also that the exterior path going from $`𝐀`$ to $`𝐂`$ is a Dyck path that has the additional property that it is symmetric with respect to the second diagonal passing through the center of $`P`$ (i.e. the Dyck word in $`x`$ and $`\overline{x}`$ associated to the Dyck path is a palindrome). Hence $`P`$ is completely determined by “half” a Dyck path (the path going from $`𝐀`$ to $`𝐁`$). If $`P`$ has half-perimeter $`2k`$ (its half-perimeter is necessarily even since the minimal rectangle is a square), then the path $`𝐀𝐂`$ is a symmetrical Dyck path of length $`2k2`$, and the path $`𝐀𝐁`$ is simply a left factor of length $`k1`$ of a Dyck path. Thus we have the following result:

###### Proposition 8

The number of $`𝔇_2`$-symmetric parallelogram polyominoes of half-perimeter $`2k+2`$ is given by

$$d_{2k+2}^{(1,2)}(1)=\{\begin{array}{cc}\left(\genfrac{}{}{0pt}{}{k}{k/2}\right)\hfill & \text{if }k\text{ is even},\hfill \\ \frac{1}{2}\left(\genfrac{}{}{0pt}{}{k+1}{(k+1)/2}\right)\hfill & \text{if }k\text{ is odd}.\hfill \end{array}$$
(22)   
See Corollary 7. $`\mathrm{}`$

We obtain the area and half-perimeter generating function for the $`𝔇_2`$-symmetric parallelogram polyominoes by constructing these from 4 copies of a $`LFD`$ polyomino, as illustrated in Figure 9. Some cells are superposed (the dark ones) and others have to be added (square of white cells in the center), and that has to be taken into account when computing the area of the final object. If the $`LFD`$ polyomino has area $`A`$, height (number of cells on the diagonal) $`d`$ and base $`n`$, then we have that the area of the $`𝔇_2`$-symmetric parallelogram polyomino is $`4A2d+(n2)^22`$, while its half-perimeter will be given by $`2n+4(d1)`$. Hence we have the following proposition:

###### Proposition 9

The half-perimeter and area generating function $`D_{1,2}(t,q)`$ for $`𝔇_2`$-symmetric parallelogram polyominoes is given by

$$D_{1,2}(t,q)=t^2q+\underset{n2}{}t^{2n4}q^{n^24n+2}L_n(1,\frac{t^4}{q^2},q^4)$$
(23)   
where $`L_n(u,x,q)`$ is the generating series for $`LFD`$ polyominoes with a base of width $`n`$. $`\mathrm{}`$

###### Corollary 10

$$D_{1,2}(t,q)=t^2q+\frac{{\displaystyle \underset{n2}{}}{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^mt^{4m+2n}q^{4m^2+2m+4mn+n^2}}{(q^4)_m}}}{1t^4q^6{\displaystyle \underset{m0}{}}{\displaystyle \frac{(1)^mt^{4m}q^{4m^2+10m}}{(q^4)_{m+1}}}}.$$
(24)   
This follows from equation (16). $`\mathrm{}`$

Here are the first few terms of $`D_{1,2}(t,q)`$:

$$D_{1,2}(t,q)=t^2q+t^4q^4+t^6q^9+t^8q^{10}+t^8q^{14}+t^8q^{16}+t^{10}q^{15}+t^{10}q^{19}+t^{10}q^{23}+t^{10}q^{25}+\mathrm{}$$

### 3.3 Congruence-type parallelogram polyominoes

We are now in a position to enumerate congruence-type parallelogram polyominoes, i.e. parallelograms up to rotation and reflection using formula (1) with $`G=𝔇_2`$ and $`𝒫=`$, the class of all parallelogram polyominoes:

$$|/𝔇_2|_w=\frac{1}{4}\underset{g𝔇_2}{}|\mathrm{Fix}(g)|_w,$$
(25)   
where $`|\mathrm{Fix}(g)|_w`$ is the half-perimeter and area generating series of the convex $`g`$-symmetric polyominoes. Therefore,

###### Proposition 11

The half-perimeter and area generating series $`(/𝔇_2)(t,q)`$ of congruence-type parallelograms is given by

$$(/𝔇_2)(t,q)=|/𝔇_2|_w=\frac{1}{4}\left((1,t,t,q)+R_2(t,t,q)+D_1(t,t,q)+D_2(t,t,q)\right).$$
(26)   
$`\mathrm{}`$

Here are the first few terms of $`(/𝔇_2)(t,q)=_{k0}\stackrel{~}{p}_k(q)t^k`$:

$`\stackrel{~}{p}_2(q)`$ $`=`$ $`q`$   
$`\stackrel{~}{p}_3(q)`$ $`=`$ $`q^2`$   
$`\stackrel{~}{p}_4(q)`$ $`=`$ $`q^4+2q^3`$   
$`\stackrel{~}{p}_5(q)`$ $`=`$ $`q^6+q^5+3q^4`$   
$`\stackrel{~}{p}_6(q)`$ $`=`$ $`q^9+2q^8+3q^7+4q^6+6q^5`$   
### 3.4 Asymmetric parallelogram polyominoes

We can also enumerate asymmetric parallelogram polyominoes, i.e. parallelograms having no symmetry at all, using Möbius inversion in the lattice of subgroups of $`𝔇_2`$.

The reader is refered to  for a general discussion of Möbius inversion, and to  to see it applied to the enumeration of the symmetry classes of convex polyominoes. We simply give here in Figure 10 the lattice of the subgroups of $`𝔇_2`$ and the value of the Möbius function on the points of the lattice. For subgroups $`H`$ of $`𝔇_2`$, we denote by $`F_H`$ (resp. $`F_{=H}`$) the half-perimeter and area generating series for the set of parallelogram polyominoes having at least (resp. exactly) the symmetries of $`H`$.

###### Proposition 12

The half-perimeter and area generating series $`\overline{}(t,q)=F_{=0}`$ of asymmetric parallelogram polyominoes is given by

$`\overline{}(t,q)`$ $`=`$ $`F_0F_{r^2}F_{d_1}F_{d_2}+2F_{d_1,d_2}`$ (27)   
$`=`$ $`(1,t,t,q)R_2(t,t,q)D_1(t,t,q)D_2(t,t,q)+2D_{1,2}(t,t,q).`$   
where $`D_{1,2}(x,y,q)`$ is the generating series of $`𝔇_2`$-symmetric polyominoes. $`\mathrm{}`$

Here are the first few terms of $`\overline{}(t,q)=_{k0}\overline{p}_k(q)t^k`$:

$`\overline{p}_2(q)=\overline{p}_3(q)=\overline{p}_4(q)`$ $`=`$ $`0`$   
$`\overline{p}_5(q)`$ $`=`$ $`4q^5+4q^4`$   
$`\overline{p}_6(q)`$ $`=`$ $`8q^7+8q^6+8q^5`$   
$`\overline{p}_7(q)`$ $`=`$ $`4q^{11}+8q^{10}+20q^9+24q^8+32q^7+24q^6`$   
Note that the same method would allow us to enumerate the convex polyominoes having exactly the symmetries of any given subgroup of $`𝔇_2`$.

### 3.5 Asymptotic results

Here we show the asymptotic result that for large area or large perimeter, almost all parallelogram polyominoes are asymmetric. In other words, the probability for a parallelogram polyomino to have at least one symmetry goes to zero as the area or the perimeter goes to infinity.

We know from the work of Pólya () that the number of parallelogram polyominoes of half-perimeter $`n`$ is given by

$$p_n^{(t)}=c_{n1}\frac{4^n}{\sqrt{\pi }n^{3/2}}.$$
(28)   
For the area, we have the result from Bender:

###### Proposition 13

(Bender ) Let $`p_n^{(q)}`$ be the number of parallelogram polyominoes with area $`n`$. Then

$$p_n^{(q)}k\mu ^n,$$
(29)   
with

$$k=0.29745\mathrm{}\mu =2.30913859330\mathrm{}$$

$`\mathrm{}`$

###### Proposition 14

Let $`H`$ be any non-trivial subgroup of $`𝔇_2`$ and denote by $`P_H^{(q)}(n)`$ (resp. $`P_H^{(t)}(n)`$) the number of $`H`$-symmetric parallelogram polyominoes with area (resp. half-perimeter) $`n`$. Then,

$$\underset{n\mathrm{}}{lim}\frac{P_H^{(q)}(n)}{p_n^{(q)}}=0\text{and}\underset{n\mathrm{}}{lim}\frac{P_H^{(t)}(n)}{p_n^{(t)}}=0.$$
(30)   
The proof for the perimeter part of the Proposition is immediate as we have closed forms for all the coefficients, and thus the limit can be verified to be zero explicitly.

For the area, we need only consider $`r^2`$\- and $`d_2`$-symmetric parallelogram polyominoes, as the $`d_1`$-symmetric parallelograms are in bijection with a subclass of $`r^2`$-symmetric ones, and the $`𝔇_2`$-symmetric parallelograms are a subclass of all the other classes of symmetry. A same basic argument works for $`r^2`$\- and $`d_2`$-symmetric parallelogram polyominoes, using the fact that they are constructed from two congruent subpolyominoes. A supplementary column sometimes has to be added in the $`r^2`$ case, according to whether the height or the width of the initial parallelogram is odd or even. These subpolyominoes are parallelograms in every case, and they have at most half the area of the initial object.

* $`r^2`$-symmetric parallelogram polyominoes : An $`r^2`$-symmetric parallelogram polyomino with even width and area $`n`$ is constructed from two congruent subparallelograms with exactly half the area, which can be glued together in at most $`n/2`$ ways (the maximal height of the columns that get glued together). So $`P_{r^2}^{(q),even}(n)\frac{1}{2}np_{n/2}^{(q)}`$. Hence

$$\underset{n\mathrm{}}{lim}\frac{P_{r^2}^{(q),even}(n)}{p_n^{(q)}}\underset{n\mathrm{}}{lim}\frac{\frac{1}{2}nk\mu ^{n/2}}{k\mu ^n}=0.$$

Next consider an $`r^2`$-symmetric parallelogram polyomino with odd width and area $`n`$. This polyomino is constructed from a central column ($`n`$ choices of height) and two congruent subparallelograms of area at most $`n/2`$. Then there are at most $`n`$ possible positions where to glue the subparallelograms to the central column (they are glued symmetrically). Thus $`P_{r^2}^{(q),odd}(n)n^2(1+p_1^{(q)}+p_2^{(q)}+\mathrm{}+p_{n/2}^{(q)})<n^3p_{n/2}^{(q)}`$ and the result follows as above. Hence the result holds for the subgroup $`r^2`$ of $`𝔇_2`$;
* $`d_2`$-symmetric convex polyominoes : Let $`P`$ be a $`d_2`$-symmetric parallelogram polyomino and $`Q`$ its fundamental region. Suppose that $`P`$ has $`b`$ cells on the diagonal symmetry axis. Then the minimum area $`P`$ can have is $`b+2(b1)`$. This gives a minimum area of $`b+(b1)`$ for $`Q`$. Hence

$$\frac{\text{Area of }Q_{min}}{\text{Area of }P_{min}}=\frac{2b1}{3b2}.$$

Then if we add to $`Q`$ a cell not on the diagonal symmetry axis, two cells get added to $`P`$, and thus we conclude that the ratio can only decrease as we make $`P`$ into a larger $`d_2`$-symmetric parallelogram polyomino with the same number of cells on the diagonal axis. For $`b2`$, the ratio will be smaller than or equal to $`3/4`$. As a loose approximation, we can take $`Q`$ to be any parallelogram polyomino. This gives $`P_{d_2}(n)p_{3n/4}^{(q)}+1`$. The $`+1`$ term corresponds to the unique $`d_2`$-symmetric parallelogram polyominoes having only one cell on the diagonal axis. Hence the result will also hold for the subgroup $`d_2`$.

$`\mathrm{}`$

###### Proposition 15

If we denote by $`\overline{p}_n^{(q)}`$ (resp. $`\overline{p}_n^{(t)}`$) the number of asymmetric parallelogram polyominoes of area (resp. half-perimeter) $`n`$, then

$`\overline{p}_n^{(q)}`$ $``$ $`p_n^{(q)},`$ (31)   
$`\overline{p}_n^{(t)}`$ $``$ $`p_n^{(t)}.`$ (32)   
We get the result from equation (27) and from the previous Proposition. $`\mathrm{}`$

Two tables can be found in appendix that present the numbers of parallelogram polyominoes according to their symmetry types and their perimeter or area. The columns indexed by subgroups of $`𝔇_2`$ give the numbers of parallelogram polyominoes of a given perimeter or area that are left fixed by the symmetries of the subgroup. The columns \# Orbits and Asym give respectively the number of congruence-type and asymmetric parallelogram polyominoes of the given size.

Appendix