Next: Bibliography Up: Schröder Triangles, Paths, and Previous: 6. Generating function considerations

  
7. An algorithm for a product of zebras

We conclude with an algorithm for forming a product of two zebras, which provides a combinatorial interpretation of the convolution related to

S(k)(x) = S(j-1)(x)S(k-j)(x),

or equivalently, sk+1(x) = sj(x) sk-j+1(x), for $1 \leq j \leq k$ ( S(j)(x) is defined in Subsection 6.2). With S[k] denoting $\{ P \in Z : ur(P) = k \}$, our interpretation will involve defining a bijection

\begin{displaymath}{S}^{[j-1]} \times {S}^{[k-j]} \rightarrow
{S}^{[k]}.
\end{displaymath}


  
Figure 6: The first 3 steps of the algorithm.
\begin{figure}
\begin{center}
\mbox{\psfig{file=FIGSWEB/fig8.ps,width=9cm} }\end{center}\end{figure}

For fixed j and k, $1 \leq j \leq k$, the following algorithm, which we will see is invertible, produces a zebra $P_3 \in {
S}^{[k]}$ for each $ ( P_1, P_2 ) \in {S}^{[j-1]} \times {
S}^{[k-j]}$:

1.
We decompose P1 into two parts: the polyomino lying under the top row, denoted by B1 and the remaining one, denoted by A1 (see fig. 6 (a));
2.
We construct the polyomino P3'''(which need not be "parallelogram") by attaching the polyomino P2 to A1 so the lower left cell of P2 takes the previous position of the lower left cell of B1. (see fig. 6 (b));
3.
We compose P3''' and B1, obtaining P3'', by attaching the lower left cell of B1 beside the rightmost top cell of P3''' (see fig. 6 (c));
4.
We attach a column of length one less than that of the first column of B1above each column of P2, contained in P3'', to obtain P3' (see fig. 6 (d)).
5.
Finally, we obtain the product $P_1 \times P_2=P_3$ from P3' by:


  
Figure 7: The product of P1 and P2.
\begin{figure}
\begin{center}
\mbox{\psfig{file=FIGSWEB/fig9.ps,width=12cm} }\end{center}\end{figure}

Given j and k, this construction can be easily reversed by first identifying the part belonging to B1 and then using the following observation to identify the part belonging to A1. If LA, LB, and Lmin denote, respectively, the lengths of the right column of A1, the left column of B1, and minimum length of all the columns P'3 that intersect P2, then $L_A < L_B \leq L_{min} $.



Next: Bibliography Up: Schröder Triangles, Paths, and Previous: 6. Generating function considerations