Counting parallelogram polyominoes with respect to wide rows ¹
R. A. Sulanke

A parallelogram polyomino is an array of unit squares bounded by two lattice paths that intersect only initially and terminally. (Paths have positively directed vertical and horizontal steps.) A row of a polyomino is wide when it contains more than one square.

Let ${\cal P}{\cal P}_{n,r}$ denote the set of parallelogram polyominoes having perimeter 2n+2 and r rows. Let ${\cal P}{\cal P}_{n,r,i,j}$ denote the subset of those in ${\cal P}{\cal P}_{n,r}$ having i left notches and j right notches. Let ${\cal P}{\cal P }{\cal W}_{n,w}$ denote the set of parallelogram polyominoes having perimeter 2n+2 and w wide rows. Let ${\cal P}{\cal P}{\cal W}_{n,w,i,j}$ denote the subset of those in ${\cal P}{\cal P }{\cal W}_{n,w}$ having i left notches and j right notches.

In this figure a polyomino in ${\cal P}{\cal P}{\cal W}_{23,7, 4,5}$ is mapped to one in ${\cal P}{\cal P}_{23,8, 4,5}$. The exchange of the initial and final sequences of squares serves to preserve the number of notches on each side when one of these sequences is empty. The figure indicates a bijection proving

$$\begin{eqnarray*}\vert{\cal P}{\cal P}{\cal W}_{n,k}\vert & = \vert{\cal P}{\cal... ...al W}_{n,k,i,j}\vert & = \vert{\cal P}{\cal P}_{n,k+1,i,j}\vert. \end{eqnarray*}$$

These results were motivated by a recent one of Emeric Deutsch that the number of Catalan paths (Dyck words) of length 2n with k high peaks (i.e., peaks which exceed the constraint by more than one step) equals the number of Catalan paths of length 2n with k+1 peaks. It is well known that the latter is counted by the Narayana number, ${n \choose k} {n \choose k}- {{n+1}\choose{k+1}}{{n-1}\choose{k-1}}.$

Since the right-hand sides of (1) and (2) have been counted previously [1], we have that $\vert{\cal P}{\cal P}{\cal W}_{n,k}\vert$ is a Narayana number and $\vert{\cal P}{\cal P}{\cal W}_{n,k,i,j}\vert$ has the symmetric Kreweras-Poupard distribution, namely, ${{n-k}\choose{i}} {{k}\choose{i}} {{n-k}\choose{j}} {{k}\choose{j}}- {{n-k+1}\choose{i+1}} {{k-1}\choose{i-1}} {{n-k-1}\choose{j-1}} {{k+1}\choose{j+1}}.$