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, s^k+1(x) = s^j(x) s^k-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

$${S}^{[j-1]} \times {S}^{[k-j]} \rightarrow {S}^{[k]}.$$

  

Figure 6: The first 3 steps of the algorithm.

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 P₁ into two parts: the polyomino lying under the top row, denoted by B₁ and the remaining one, denoted by A₁ (see fig. 6 (a));

2.

We construct the polyomino P₃^'''(which need not be "parallelogram") by attaching the polyomino P₂ to A₁ so the lower left cell of P₂ takes the previous position of the lower left cell of B₁. (see fig. 6 (b));

3.

We compose P₃^''' and B₁, obtaining P₃^'', by attaching the lower left cell of B₁ beside the rightmost top cell of P₃^''' (see fig. 6 (c));

4.

We attach a column of length one less than that of the first column of B₁above each column of P₂, contained in P₃^'', to obtain P₃^' (see fig. 6 (d)).

5.

Finally, we obtain the product $P_1 \times P_2=P_3$ from P₃^' by:

• appending a white cell to the right of the top row of P₃^' if the top row of P₂ is completely white (see fig. 7 (a));
• placing a new row at the top of P₃^' if the top row of P₂ is not completely white. It begins above the rightmost black column of P₂ and ends above the right column of B₁ (see fig. 7 (b));
• coloring the k rightmost columns of the resulting polyomino white, in either case. The remaining columns intersecting the top row of this polyomino take the same pattern of colors of the columns to the left of the (j-1) rightmost consecutive white columns of B₁.

  

Figure 7: The product of P₁ and P₂.

Given j and k, this construction can be easily reversed by first identifying the part belonging to B₁ and then using the following observation to identify the part belonging to A₁. If L_A, L_B, and L_min denote, respectively, the lengths of the right column of A₁, the left column of B₁, and minimum length of all the columns P'₃ that intersect P₂, then $L_A L_B \leq L_{min}$.

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