Counting parallelogram polyominoes with respect to wide rows 1
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.


\psfig{figure=show.ps,height=3.0in,width=4.5in}

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}}.$