Next: 7. An algorithm for Up: Schröder Triangles, Paths, and Previous: 5. A bijection between

   
6. Generating function considerations

6.1 A brief review of results for recurrence arrays

For orientation and reference we review some known techniques for dealing with arbitrary recurrence arrays. For any real sequence $c_0, c_1, c_2, \ldots$, with $c_0 \neq 0$, consider the two arrays, $\{C_{0}(m,n)\}_{m \geq 0, n\geq 0}$ and $\{C_{1}(m,n)\}_{m \geq 0, n\geq 0}$ that, for $\mu \in \{0,1\}$, satisfy the recurrence

$$C_{\mu}(m,n) = \sum_{i\geq0} c_iC_{\mu}(m-i,n-1)$$

subject to $C_{\mu}(m, m\mu-1) =0$ for m >0, $C_{\mu}(0,-1) = 1$, and $C_{\mu}(m,n) =0$ for m <0. ${\mu}$ is slope of the constraint. Put $f(x) = \sum_{j\geq 0} c_jx^j$ and $c(t)= \sum_{j\geq 0} C_1(j,j)x^j$. The following lemma collects some well-known basic formulas (see [25]). The first three follow from various convolutions. The fourth is a direct consequence of the Lagrange inversion formula applied to the third formula. Here $[x^i]\sum_k b_k x^k$ denotes b_i.

Lemma 6.1   The arrays $\{C_{0}(m,n)\}$ and $\{C_{1}(m,n)\}$, for $m \geq 0$ and $n \geq 0$ satisfy

1.

C₀(m,n) = [x^m] f(x)ⁿ⁺¹.

2.

C₁(m,n+m-1) = [x^m]c(x)ⁿ.

3.

c(x) = f(x c(x) ).

4.

C₁(m,n) = (n-m+1)/(n+1) C₀(m,n).

In this study $f(x) = 1 + \sum_{j\geq 1} 2^{j-1}x^{j}$ with c(x) = s(x) in the case of (1), and $f(x) = 1 + \sum_{j\geq 1} 2x^{j}$ with c(x) = r(x) in the case of (4).

As an example, one can obtain, for $0 \leq m \leq n$,

$$R(m,n) = \frac{n-m+1}{n+1} \sum_{0\leq k \leq m}{{n+1}\choose{m-k}} {{n+k}\choose{k}}$$

.

  

Figure 4: A modified construction for zebras related to CONSTRA.

6.2 Enumerating Z_n by the number rightmost top white cells

In this section we again consider the cardinalities ${z}_{n,j} =\vert \{ P \in Z :\ \ n(P)=n, \ \ ur(P)=j \} \vert$, where $n \geq 1$ and $j \geq 0$. We first compute the generating function $S^{(j)}(x)= \sum_{n \geq 1} {z}_{n,j} x^n$ for $j \geq 0$. We then determine the coefficients in Corollary 6.3. It seems interesting how CONSTRA is used in modified form in the following proof.

Proposition 6.2   The generating function S^(j)(x) satisfies, for $j \geq 0$,

 

S^(j)(x)= x^j+1s^j+1(x), (7)

where s(x) is the generating function for the small Schröder numbers.

Proof. For $j \geq 1$, let $\{ W^{\underline{j}} \}$ denote the zebra consisting of a single row of white cells of length j and let ${A}^{(j)} = \{P \in Z: \ \ ur(P)=j \} \ \setminus \{ W^{\underline{j}} \}$. Modify the construction CONSTRA by reversing its ``direction'' from up-and-to-the-right to proceed down-and-to-the-left and by starting the construction with the zebra $W^{\underline{j}}$. Now we construct the zebras inductively either by adding left justified rows to the bottom of the zebras where each new cell is colored as the above column or by adding a new cell of either color to the left of the lowest row (see Figure 4). For $P \in Z_n$ such that ur(P) = j, let T(P)denote the set of the children of P in Z_n+1 under the modified construction. We can recursively decompose A^(j) into a union of disjoint sets. This decomposition illustrated is in Figure 5 for the case j=3 and an arbitrary zebra P in A^(j).

$${A}^{(j)} = T(W^{\underline{j}}) \setminus \{W^{\underline{j+1}} \} \bigcup \bigcup_{P \in {A}^{(j)} } T(P)$$ (8)

  

Figure 5: Decomposition of A^(j) into a union of disjoint sets.

Let $${ a^{(j)}(x,y)= \sum \limits_{P \in {A}^{(j)}} x^{n(P)} y^{f(P)} }$$where f(P)= the length of the lowest row of P. The decomposition of (8) translates to the following equation.

 

$$x^{j+2}(y^{j+1}+...+y)+ x \sum_{P \in {A}^{(j)}} \left(x^{n(P)}y^{f(P)+1} + \sum_{k=1}^{f(P)+1} x^{n(P)} y^{k} \right)$$ a^(j)(x,y) =

$$x^{j+2} (y^{j+2}-y)/(y-1)+ xy a^{(j)}(x,y) + {xy} \left( ya^{(j)}(x,y)- a^{(j)}(x,1) \right)/(y-1).$$ = (9)

To obtain the above one can easily check that the telescoping sum $(y-1)\sum \limits_{P \in {A}^{(j)}} \sum \limits_{k=1}^{f(P)+1} x^{n(P)}y^{k}$ is equal to y²a^(j)(x,y)-ya^(j)(x,1). Equation (9) implies

xy a^(j)(x,1) - x^j+2(y^j+2-y) - (2xy² - (x + 1) y+1)a^(j)(x,y) = 0.

Setting the indeterminate y equal to s(x), which is a solution to 2xy² - (x + 1) y+1 = 0, yields

a^(j)(x,1) = x^j+1 s^j+1(x) - x^j+1.

Once we recall the definition of A^(j), the proof is complete for $j \geq 1$. One can easily develop a proof for the case j=0 by modifying the above argument.

Corollary 6.3   The number Z_n,j satisfies z_n,n-1=1 and satisfies, for $0 \leq j \leq n$,

$${z}_{n,j}= \frac {j+1} {n} \sum_{i=0} ^{n-j-2}{ {n} \choose {i+1}} { {n-j-2} \choose {i}}2^{n-j-i-2}.$$

Proof. Equation (7) implies

$$\left[ x^{n}\right] S^{(j)}(x)= \left[ x^{n-j-1} \right] s^{j+1}(x)= \left[x^{n-j-1} \right] (t(x)+1)^{j+1},$$

where t(x)=s(x)-1satisfies t(x)=x(t(x)+1) (2t(x)+1). The Lagrange inversion formula yields

$$\left[ x^{n-j-1} \right] (t(x)+1)^{j+1}= \frac {j+1} {n-j-1} \left[ t^{n-j-2} \right] (t+1)^{n-1} (2t+1)^{n-j-1}.$$

The result then follows from binomial expansions.

The bijection between paths and zebras and this corollary yield, for $1 \leq m \leq n$,

$$S(m,n)= \frac {n-m+1} {n+1} \sum \limits_{i=0} ^{m-1} { {n+1} \choose {i+1}} { {m-1} \choose {i}} 2^{m-i-1}.$$

6.3 Enumerating Z_n by the length of the rightmost column

Here we consider again the numbers $z_{ n,W\vert j} =\vert \{ P \in Z_n : rc(P) = j \} \vert$, where rc(P) denotes the number of white cells in the right column of P. Since this section is similar to the previous section, the treatment is brief.

Proposition 6.4   For $j \geq 1,$ the generating function $R^{\vert j}(x)= \sum_{n \geq 2} z_{n,W\vert n} x^n$ is given by

R^|j(x) = x^j+2 r^j(x)

where r(x) is the generating function for the large Schröder numbers.

Proof. It will be interesting how CONSTRB is used. Let ${B}^{\vert j} = \{P \in { Z}: \ \ rc(P)=j \} \ \setminus \{ W^{\vert j} \}$ where W^|j is a white column of length j. We modify CONSTRB by reversing its ``direction'' from up-and-to-the-right to proceed down-and-to-the-left. Starting from the zebra W^|j, we then construct inductively all zebras in B^|j by adding bottom justified columns of either color on the left or by adding a new cell to the bottom of the leftmost column so that the cell retains the color of the column above. For $P \in Z_n$ such that rc(P) = j, let T'(P) denote the set of the children of P in Z_n+1. We can recursively decompose B^|j into a union of disjoint sets as follows:

$${B}^{\vert j} = T'(W^{\vert j}) \setminus \{W^{\vert{j+1}} \} \bigcup \bigcup_{P \in {B}^{\vert j} } T'(P)$$ (10)

With

$$b^{\vert j}(x,y)= \sum \limits_{P \in {B}^{\vert j}} x^{n(P)} y^{L(P)}$$

where L(P)= the length of the left column of P. The decomposition (10) translates to

 

$$2 x^{j+2}(y^{j}+...+y)+\sum_{P \in {B}^{\vert j}} (x^{n(P)+1}y^{L(P)+1} + 2\sum_{k=1}^{L(P)} x^{n(P)+1} y^{k} )$$ b^|j(x,y) =

= 2 x^j+2 (y^j+1-y)/(y-1)+xy b^|j(x,y) + 2xy( b^|j(x,y)- b^|j(x,1) )/(y-1), (11)

which implies

2xy b^|j(x,1) - x^j+2(y^j+1-y) - (xy² +(x - 1) y+1)b^|j(x,y) = 0.

When we set y equal to r(x), a solution to xy² + (x - 1) y+1 = 0, we find

b^|j(x,1) = x^j+1 r^j(x) - x^j+1.

The proof is completed upon recalling the definition of B^|j.

Next: 7. An algorithm for Up: Schröder Triangles, Paths, and Previous: 5. A bijection between