Next: 5. A bijection between Up: Schröder Triangles, Paths, and Previous: 3. Zebras, generating trees

   
4. New constructions for zebras

Using the background of the previous sections we introduce two new zebra constructions. We then consider the enumeration of certain subsets of zebras by the recurrence relations (1) and (4). Comparing Table 4 with Table 1 indicates the relationships of these constructions to (1) and to (4).


4.1 The construction CONSTRC

We describe an inductive construction for zebras that essentially adds rows with color change (see Figure 2).

  
Figure 2: The construction of zebras related to CONSTRC.
\begin{figure}
\begin{center}
\mbox{\psfig{file=FIGSWEB/fig2.ps,width=14cm} }\end{center}\end{figure}

This construction begins with Z1 = {|}. Assuming that Zn, $n \geq 1$, has been constructed, we construct all possible zebras of semiperimeter n+1, obtaining each from some zebra P in Zn, either

Proposition 4.1   The construction CONSTRC produces all zebras uniquely and satisfies the succession rules given in the upper-right cell of Table 3.

Denote the number of rightmost consecutive white cells on the top row of a zebra P by ur(P). Define Zn,k to be the subset of zebras, P, for which n(P) = nand ur(P) = k.

Proof of Prop. 4.1. For $n \geq 1$ it is straight forward to check that each zebra in Zn+1 has a unique parent in Zn and thus by induction each zebra will be constructed exactly once. Establishing the rules requires some attention. Given the construction, we observe that

1.
For $0 \leq j \leq k$, each P in Zn,k is the parent of 2k-j zebras in Zn+1, j. We prove this in three cases:
(a)
For 0 = j = k, P' in Zn+1, j results when a B is appended to the right of the top row of P.
(b)
For 0 = j < k, a P' in Zn+1, j results either when a B is appended to the right of the top row of P or when an arbitrary row of length i, for $1 \leq i \leq k$, ending in B forms the new top row. There are $1 + \sum_{1 \leq i \leq k} 2^{i-1} = 2^{k-j}$ ways to do so.
(c)
If $ 0  j \leq k $, then P' in Zn+1, j results either when a string of j W's forms the new top row or when a row of length i , for $j+1 \leq i \leq k$, ending in B followed by j W's forms the new top row. There are $1 + \sum_{j+1 \leq i \leq k } 2^{i-j-1} = 2^{k-j}$ choices.
2.
For $0 \leq k  j$, each P in Zn,k has only one child in P' in Zn+1, k+1 and none in Zn+1, j for j>k+1. The sole child results from appending a W to the right of the top row of P.
3.
For $k \geq 0$, each P in Zn, k is the parent of 2k+1 zebras is Zn+1, and conversely. The first clause is obtained by summing the results of 1. and 2. The converse follows the matching of k with 2k+1.
Using these three observations we establish the rules. If P has 2kchildren, then P belongs to Zn,k+1. For $ 0 \leq j \leq k-1$, P is the parent of 2k-j-1 zebras in Zn+1,j. Each of these is the parent of 2 j + 1 zebras in Zn+2. Finally, each P in Zn, k-1 has one child in Zn+1,k, which in turn has 2k+1 children. \fbox{}

The following proposition shows that |Zn,k| appears on the kth diagonal above the principal diagonal in the Schröder triangle of Table 1a. In Section 5 we prove this proposition in a bijective manner consistent with the above construction. In Section 6.2 we prove it while linking CONSTRA to CONSTRC.

Proposition 4.2   When S(m,n) denotes |Zn+1, n-m|, S(m,n) satisfies the recurrence (1).


 
Table 4: The frequencies of the labels for two generating trees of Section 4.

\begin{displaymath}\begin{array}{cc}
\begin{array}{c}
\begin{tabular}{l\vert ccc...
...ular}\\
\ \\
\textsc{constr}\textrm{D}
\end{array}\end{array}\end{displaymath}

 


4.2 The construction CONSTRD

Next we describe a construction for zebras that essentially adds columns with color change. This construction agrees with the recurrence (4). While it is absent in [2], the corresponding succession rule does appear in of Lemma 4.3 of [2].

This inductive construction begins with Z1 = {|}. Assuming that Zn, $n \geq 1$, has been constructed, we construct all possible zebras of semiperimeter n+1, obtaining each from some zebra P in Zn, either


Let Zn,c|k be the set of zebras in Zn, each having exactly k cells of color c in its rightmost column. Let Zn,d|j,c|k be the set of zebras in Zn,c|k, each having at least two cells on its top row and having exactly j cells of color d in the next to the rightmost column. When we restrict our attention to those zebras having a white right column, then the CONSTRD corresponds to the triangle for R(m,n); hence, with appropriate indexing |Zn,W|k|, for k>0, appears in the Schröder triangle of Table 1b. More precisely, we have

Proposition 4.3   For $ 0 \leq m \leq n$, suppose R(m,n) denotes |Zn+2,W|n+1-m|, the number of zebras in Zn+2, each having n+1-m white cells in its rightmost column. R(m,n) satisfies the recurrence (4).

Proof. For k>0,

\begin{displaymath}\begin{array}{ccl}
\vert Z_{n+1,W\vert k} \vert
& = & \vert\...
...ert + 2 \sum_{j\geq k} \vert Z_{n,W\vert j} \vert.
\end{array}\end{displaymath}

Thus

\begin{displaymath}\vert Z_{n+1,W\vert n-(n-k)} \vert=
\vert Z_{n,W\vert n-1-(n-...
... + 2 \sum_{n-j \leq n-k}
\vert{
Z}_{n,W\vert n-1-(n-j)}\vert,
\end{displaymath}

and the result follows after an appropriate change of indices. \fbox{}

We remark that this proof can be modified into a bijective proof involving lattice paths similar to the result in Section 5. In a manner comparable to the proof of Proposition 4.1, one can show

Proposition 4.4   The construction CONSTRD produces all zebras and satisfies the succession rules given in the lower-right cell of Table 3.

Notably zebras afford us bijective proofs that relate the row sums of each Schröder triangle to the diagonal entries of the other, as is now seen.

Proposition 4.5   For $n \geq 0$,

\begin{displaymath}\sum_{0 \leq m \leq n} S(m,n) =R(n,n)
\mbox{\quad and \quad}
\sum_{0 \leq m \leq n} R(m,n) =S(n+1,n+1).\end{displaymath}

Proof. Observe that $\sum_{0 \leq m \leq n} S(m,n) =
\sum_{0 \leq k \leq n} \vert Z_{n+1,k}\vert =
\vert Z_{n+1}\vert = \vert Z_{n+2, W\vert 1}\vert =
R(n,n)$. To prove the second identity, observe that $\sum_{0 \leq m \leq n} R(m,n) =$ $ \sum_{1\leq k \leq n+1} \vert Z_{n+2,
W\vert k}\vert =$ $
\vert\{ P \in Z_{n+2}: \mbox{ rightmost column of $P$\space is $W$\space } \}\vert =$ $
\vert\{ P \in Z_{n+2}: \mbox{ rightmost column of $P$\space is $B$\space } \}\vert =$ | Zn+2,0| = S(n+1,n+1). \fbox{}



Next: 5. A bijection between Up: Schröder Triangles, Paths, and Previous: 3. Zebras, generating trees