Next: 3. Zebras, generating trees Up: Schröder Triangles, Paths, and Previous: 1. Introduction

  
2. Schröder arrays and lattice paths

The first array, $\{S(m,n)\}_{m \geq0, n\geq 0}$ (A011117), is defined by the recurrence, for (m,n) in Z²,

$$S(m,n) = S(m,n-1) + \sum_{j\geq 1} 2^{j-1} S(m-j, n-1)$$ (1)

subject to the conditions S(0,0) = 1, S(m,n) = 0 if m < 0 and S(m,n) = 0 if n < m.

The terms of the sequence $\{S(n,n)\}_{n\geq 0}$ are known as the small Schröder numbers (A001003). Plutarch [13,24] recorded the numbers 103,049 and 310,952 as being known to Hipparchus two centuries earlier as counting certain logical propositions. Recently, as reported in [24], David Hough identified the first number as the tenth Schröder number, namely s₉ = S(9,9). Habsieger, Kazarian, and Lando [11] have found that S(9,10) = 310,954 (in our notation), which differs only slightly from the recorded number of antiquity. In their explanation, in terms of bracketings counted by the Schröder numbers, agrees with the straight forward calculation of S(9,10) from (1). Subsequently, Sloane [22] has cataloged (as sequence A010683) the sequence ${S(n,n+1)}_{n\geq0} = 1,2,7,28,121 , ...$, which is the second diagonal of Table 1.a.

If s(x) denotes the generating function $\sum_{n \geq 0} S(n,n) x^n$, then, as one can derive from Lemma 6.1, s(x) is the combinatorially meaningful solution to

 

2 x s(x)² -(x+1)s(x) +1 = 0, (2)

which is s(x) = ( 1 + x - (1 - 6 x + x² )^1/2 ) /4x.

One can associate weighted lattices paths on specific step sets with the recurrence arrays we consider. The weight of a lattice path is the product of the weights of its steps, and the weight of a path set is the sum of the weights of its paths. Let S[m,n] denote the set of lattice paths from (0,0) to (m,n)that never pass below the line n=m and that use the infinite set of weighted steps { (0,1)₁, (1,1)₁, (2,1)₂, (3,1)₄, (4,1)₈, ... }. Here the subscripts indicate the step weights. One can show that S(m,n) is the weight of the paths in S[m,n]. One can rephrase path weights as path counts by allowing multiple steps. We remark that the recurrence $C(m,n) = C(m,n-1) + \sum_{j\geq 1} C(m-j, n-1)$, subject to C(0,0) = 1, C(m,n) = 0 if m < 0 and C(m,n) = 0 if n < m, yields a ``Catalan triangle.''

It is straight forward to show that the array {S(m,n)} also satisfies the recurrence

$$S(m,n) = S(m,n-1) + \sum_{j\geq 1} S(m-j, n)$$ (3)

subject to the same conditions as (1) is. Here the path model is the set of lattice paths from (0,0) to (m,n) that never pass below the line n=m and that use the infinite set of steps { (0,1), (1,0),(2,0), (3,0), (4,0), ... }.

The second triangle $\{ R(m,n)\}_{m \geq 0, n\geq 0}$ (A033877), is defined for $(m,n) \in {Z^2}$ by the recurrence

$$R(m,n) = R(m,n-1) + 2\sum_{j\geq 1} R(m-j, n-1)$$ (4)

subject to the conditions R(0,0) = 1, R(m,n) = 0 if m < 0 and R(m,n) = 0 if n < m.

This array is illustrated in Table 1b, with the sequence $\{R(n,n)\}_{n\geq 0}$ being the large Schröder numbers (A006318). If $r(x) = \sum_{n \geq 0} R(n,n) x^n$, then, as one can derive from Lemma 6.1, r(x) is the combinatorially meaningful solution to

x r(x)² +( x-1)r(x) +1 = 0, (5)

which is r(x) = ( 1 - x - (1 - 6 x + x²)^1/2/2x. In terms of lattice paths, R(m,n) counts the set of the paths from (0,0) to (m,n) that never pass below n=m and that use the infinite set of weighted steps $\{ (0,1)_1, (1,1)_2, (2,1)_2, (3,1)_2, (4,1)_2, \ldots \}$.

One can easily show that $\{ R(m,n)\}_{m \geq 0, n\geq 0}$also satisfies the recurrence

R(m,n) = R(m,n-1) + R(m-1, n-1) + R(m-1, n) (6)

subject to the same conditions as (4) is. Here the constrained lattice path model uses the step set { (0,1), (1,1), (1,0) }.

Next: 3. Zebras, generating trees Up: Schröder Triangles, Paths, and Previous: 1. Introduction