Next: 2. Schröder arrays and Up: Schröder Triangles, Paths, and Previous: Schröder Triangles, Paths, and

1. Introduction

Our intention is to consider the Schröder numbers, not as isolated sequences, but as belonging to larger arrays in which they form the main diagonals as in Table 1. We define the Schröder numbers, s_n = 1, 1, 3, 11, 45, 197, ... and r_n = 1, 2, 6, 22, 90, 394, ... , for n = 0, 1, 2, ..., by (1) and (4). As Stanley noted in his recent survey [24] regarding these numbers, apparently some of them were known to Hipparchus during the second century B.C. In 1870, Ernst Schröder [20] formulated them while enumerating unrestricted bracketings of words. These numbers have appeared in other contexts: they count dissections of a convex polygon [6,7], certain polyominoes [2,27], various lattice paths [2,15,18,23], plane trees [4,8,15,19], ukasiewicz words [12,14], and permutations avoiding given patterns [1,9,10,19,28]. Three recent combinatorial treatments of these numbers as isolated sequences, not as part of triangular arrays, are [8,26,27]. (They are sequences A001003 and A006318 in the Encyclopedia of Integer Sequences [22].)

We will define two recurrence arrays or essentially, ``renewal arrays'' as in [17] or ``Riordan arrays'' as in [21]. We will obtain combinatorial interpretations of these arrays in terms of lattice paths and bi-colored parallelogram polyominoes. While there are other arrays that contain the Schröder numbers (for instance, Table 2), these two seem very natural. They have been studied by Rogers[16,18], by Rogers and Shapiro [15,19], and by others [3,25]. Since each entry for (m,n), in either array, counts constrained lattice paths for a given step set to the lattice point (m,n) in Z², it is convenient to index the arrays as lying in the coordinate plane instead of the arrays as matrices.

 

Table 1: The arrays for S(m,n) and R(m,n).

$$\begin{array}{ccc} \begin{tabular}{r\vert ccccc} $n=4$ & 1& 4... ... \hline $m=$\space &$0$ & 1& 2& 3& 4 \end{tabular} \end{array}$$

 

Next: 2. Schröder arrays and Up: Schröder Triangles, Paths, and Previous: Schröder Triangles, Paths, and