Bijective Recurrences concerning Schröder Paths

Robert A. Sulanke Boise State University Boise, Idaho, USA

                      sulanke@math.idbsu.edu

Submitted: April 7, 1998; Accepted: October 30, 1998

Abstract

Consider lattice paths in Z^{2} with three step types: the up diagonal (1, 1), the down diagonal (1, −1), and the double horizontal (2, 0). For n ≥ 1, let S_{n} denote the set of such paths running from (0, 0) to (2n, 0) and remaining strictly above the x-axis except initially and terminally. It is well known that the cardinalities, r_{n} = |S_{n}|, are the large Schröder numbers. We use lattice paths to interpret bijectively the recurrence (n + 1)r_{n+1} = 3(2n − 1)r_{n} − (n − 2)r_{n−1}, for n ≥ 2, with r_{1} = 1 and r_{2} = 2.

We then use the bijective scheme to prove a result of Kreweras that the sum of the areas of the regions lying under the paths of S_{n} and above the x-axis, denoted by AS_{n}, satisfies AS_{n+1} = 6AS_{n} − AS_{n−1}, for n ≥ 2, with AS_{1} = 1, and AS_{2} = 7. Hence AS_{n} = 1, 7, 41, 239, 1393, . . .. The bijective scheme yields analogous recurrences for elevated Catalan paths.

Mathematical Reviews Subject Classification: 05A15

1 The paths and the recurrences

We will consider lattice paths in Z^{2} whose permitted step types are the up diagonal (1, 1) denoted by U, the down diagonal (1, −1) denoted by D, and the double horizontal (2, 0) denoted by H. We will focus on paths that run from (0, 0) to (2n, 0), for n ≥ 1, and that never touch or pass below the x-axis except initially and terminally. Let C_{n} denote the set of such paths when only U-steps and D-steps are allowed, and let S_{n} denote the set of such paths when all three types are allowed. It is well known that the cardinalities c_{n} = |C_{n}| and r_{n} = |S_{n}|, for n ≥ 1, are the Catalan numbers and the large Schröder numbers, respectively. (See Section 4, particularly Notes 2 and 4.) Hence, here one might view the elements of S_{n} as elevated Schröder paths. Let AC_{n} denote the sum of the areas of the regions lying under the paths of C_{n} and above the x-axis. Likewise, let AS_{n} denote the sum of the areas of the regions lying under the paths of S_{n} and above the x-axis.

Figure 1: The 6 elevated Schröder paths of S_{3} bound 41 triangles of unit area.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & … \\ c_{n} & 1 & 1 & 2 & 5 & 14 & … \\ r_{n} & 1 & 2 & 6 & 22 & 90 & … \\ AC_{n} & 1 & 4 & 16 & 64 & 256 & … \\ AS_{n} & 1 & 7 & 41 & 239 & 1393 & … \end{matrix}

The Catalan numbers and the Schröder numbers have been studied extensively; Section 4 references some studies related to lattice paths. In our notation their explicit formulas are, for n ≥ 1,

c_{n} = \frac{1}{n}\binom{2n − 2}{n − 1} and r_{n} = ∑_{k=1}^{n} \frac{1}{k}\binom{n − 2}{k − 1}\binom{n − 1}{k − 1}2^{k}.

It is known that these sequences satisfy the recurrences

(n + 1)c_{n+1} = 2(2n − 1)c_{n}  (1)
(n + 1)r_{n+1} = 3(2n − 1)r_{n} − (n − 2)r_{n−1}  (2)

for n ≥ 2, with initial conditions c_{1} = 1, c_{2} = 1, r_{1} = 1, and r_{2} = 2.

We will give a bijective proof for (1) and (2) when the sequences c_{n} and r_{n} are defined in terms of the sets of lattice paths. We will then employ this bijective construction to obtain a combinatorial interpretation that the sequences for the total areas satisfy

AC_{n+1} = 4AC_{n}  (3)
AS_{n+1} = 6AS_{n} − AS_{n−1}  (4)

for n ≥ 2 with initial conditions AC_{1} = 1, AC_{2} = 4, AS_{1} = 1, and AS_{2} = 7.

Using binary trees, Rémy [10] gave a combinatorial proof of recurrence (1). Recently, Foata and Zeilberger [3] showed bijectively, using well-weighted binary plane trees, that the small Schröder numbers satisfy (2) with initial conditions r_{1} = 1 and r_{2} = 1. (See Section 4 for “well-weighted” and “small”.) Kreweras [4], using lattice paths equivalent to those of S_{n} showed AS_{n} = ∑_{0≤k<n} 2^{k}\binom{2n−1}{2k} and derived recurrence (4). Following his results, Bonin, Shapiro, and Simion [2] proved (4) using generating functions and then wrote that “This recurrence cries out for a combinatorial interpretation.” Section 3 comes to the rescue.

2 The proof of recurrences (1) and (2)

We will focus on recurrence (2) rearranged as 3(2n−1)r_{n} = (n+1)r_{n+1} +(n−2)r_{n−1}. In S_{n} replicate each path, defined as a sequence of steps, 3(2n − 1) times as follows: First repeatedly tag each path P by appending the symbol a, b, or c. Next, for each tagged path P, consecutively index its steps, as positioned in P, with the integers 1 through 2n−1 so that each U-step and each non final D-step receives one integer and each H-step receives two consecutive integers. Then mark each path P by selecting an integer from {1, …, 2n − 1} and marking the corresponding step on P

– by the superscript x if the step is U or if the step is H with odd index, and

– by the superscript y if the step is D or if the step is H with even index.

We write the set of such replications as {a, b, c} × {1, …, 2n − 1} × S_{n} = {a, b, c} × [2n − 1] × S_{n}, where, in general, [n] denotes {1, …, n}. For instance, for S_{2} = {UUDD, UHD},

{a, b, c} × [3] × S_{2} =

{U^{x}UDDa, UU^{x}DDa, UUD^{y}Da, U^{x}HDa, UH^{y}Da, UH^{x}Da,
U^{x}UDDb, UU^{x}DDb, UUD^{y}Db, U^{x}HDb, UH^{y}Db, UH^{x}Db,
U^{x}UDDc, UU^{x}DDc, UUD^{y}Dc, U^{x}HDc, UH^{y}Dc, UH^{x}Dc}.

Next in S_{n+1} replicate each path n + 1 times by sequentially marking one of its U-steps or H-steps by the symbol z. This replicated set is denoted as [n + 1] × S_{n+1}. Similarly, in S_{n−1} replicate each path n − 2 times by sequentially marking one of its H-steps or non final D-steps by the symbol z. This replicated set is denoted as [n − 2] × S_{n−1}.

For n ≥ 2, we now define the desired bijection,

f : {a, b, c} × [2n − 1] × S_{n} → [n + 1] × S_{n+1} ⋃ [n − 2] × S_{n−1}.  (5)

Suppose

P = p_{1} ⋯ p_{i} ⋯ p_{j} ⋯ p_{k} ⋯ p_{m}.  (6)

denotes a typical replicated path in [2n − 1] × S_{n} for which the following four items hold.

– The positions i, j, and k satisfy 1 ≤ i ≤ j < k ≤ m.

– The step p_{j} is the step that is marked by x or y.

– The step p_{i} is the last U-step preceding p_{j+1} for which lev(p_{i}) = lev(p_{j}). Here the level of arbitrary step p_{ℓ}, denoted lev(p_{ℓ}), is the ordinate of its final point. When p_{j} = U^{x}, i = j.

– The step p_{k} is the first D-step after p_{j} for which lev(p_{k}) = lev(p_{j}) − 1.

Case 1a: If p_{j} = U^{x}, H^{x}, or D^{y}, f(P a) = p_{1} ⋯ p_{i} ⋯ p_{j}U^{z}Dp_{j+1} ⋯ p_{k} ⋯ p_{m}.

(Here, f(P a) is obtained by inserting the pair U^{z}D immediately after p_{j}. The tags x, y, and a are erased here; the tags b and c are erased in the following cases. If P appears in Fig. 2, f(P a) appears in Fig. 3. In the figures the dots pertain to an illustration for the proof of the next section.)

Case 1b: If p_{j} = U^{x}, H^{x}, or D^{y}, f(P b) = p_{1} ⋯ p_{i}^{z} ⋯ p_{j}URDp_{k} ⋯ p_{m}, where R = p_{j+1} ⋯ p_{k−1}.

(Observation 1: In the path Q = q_{1}q_{2} ⋯ q_{m+2} = f(P b) a D-step immediately precedes the D-step q_{k+2}, which is the translation of the step p_{k}. The step q_{k+2} is the first step after q_{i}^{z} = p_{i}^{z} for which lev(q_{k+2}) = lev(q_{i}) − 1; q_{j} = p_{j} is now the last step before q_{k+2} such that lev(q_{j}) = lev(q_{k+2}) − 1. The path R may be empty.)

If P  UUUDH^{x}HUDDD  UHUH^{y}UHDDD  UUUDH^{y}HUDDD

then

f(P a) UUUDH\underline{U^{z}D}HUDDD UHU\underline{U^{z}}H\underline{D}UHDDD UUUD\underline{U^{z}}H\underline{D}UDDD
f(P b) UU^{z}UDH\underline{U}HUD\underline{D}DD UHU^{z}HUHD\underline{H}DD UU^{z}UD\underline{U}HUD\underline{D}UDDD
f(P c) UUUDH\underline{H^{z}}HUDDD UHU^{z}UHDH\underline{H}DD UUUD^{z}HUDDD

Table 1: This table spells out the examples of the Figures 1 to 9 and 11 to 14. Underlining identifies inserted steps.

Case 1c: If p_{j} = U^{x}, H^{x}, or D^{y}, f(P c) = p_{1} ⋯ p_{i} ⋯ p_{j}H^{z}p_{j+1} ⋯ p_{k} ⋯ p_{m}.

Case 2a: If p_{j} = H^{y}, f(P a) = p_{1} ⋯ p_{j−1}U^{z}HDp_{j+1} ⋯ p_{m}.

Case 2b: If p_{j} = H^{y}, f(P b) = p_{1} ⋯ p_{i}^{z} ⋯ p_{j−1}URDHp_{k} ⋯ p_{m}, where R is the subpath p_{j+1} ⋯ p_{k−1}.

(Here a U-step and a D-step are inserted and the step p_{j} = H is moved. Observation 2: In the path Q = f(P b) exactly one H-step immediately precedes q_{k+2}, the translation of p_{k}. The step q_{j−1} = p_{j−1} is now the last step before q_{k}q_{k+1}q_{k+2} = DHp_{k} such that lev(q_{j−1}) = lev(q_{k+2}) + 1. R may be empty.)

Case 2c: If p_{j−1}p_{j} = UH^{y}, f(P c) = p_{1} ⋯ p_{i}^{z} ⋯ p_{j−1}RHHp_{k} ⋯ p_{m}, where R is the subpath p_{j+1} ⋯ p_{k−1}.

(Observation 3: In the path Q = f(P c), at least two H-steps immediately precede the D-step q_{k+1}, the translation of p_{k}.)

Case 3: If p_{j−1}p_{j} = HH^{y} or DH^{y}, f(P c) = p_{1} ⋯ p_{j−1}^{z}p_{j+1} ⋯ p_{m}.

(Here f(P c) ∈ [n − 2] × S_{n−1} with the marked H-step being deleted.)

Table 1 and Figures 1 to 9 and 11 to 14 illustrate the map f. By giving special attention to the three Observations in the preceding, it is straight forward to check the necessary cases to show that f is a bijection. Assigning cardinalities to the sets in the bijection given in (5) yields the recurrence (2). To prove recurrence (1), simply remove all reference to the H-steps and to the tag c in the proof.

3 The proof of recurrences (3) and (4)

Retaining the previous notions, consider the recurrence (4). One can partition the region under a path and above the x-axis by copies of two isosceles right triangles whose hypotenuses have length 2 and are parallel to the x-axis. Figure 1 illustrates how these triangles of unit area uniquely partition the regions under the paths. A triangle is called an up triangle if its right angle is above its hypotenuse; otherwise, it is called a down triangle.

An up-triangle-strip (down-triangle-strip, respectively) under a path of S_{n} is a maximal array of up (down, respectively) triangles having the centers of their hypotenuses on a single line of slope −1 (slope 1, respectively). It is easily seen that each path in S_{n} has n up-triangle-strips and n − 1 down-triangle-strips. The marked triangles in Figure 2 illustrate an up-triangle-strip; those in Figure 6 illustrate a down-triangle-strip. Each marked path P ∈ [2n − 1] × S_{n} determines a unique strip under P as follows: If the step p_{j} is marked by x, then the corresponding strip is the up-triangle-strip whose line of centers of its triangles intersects the step p_{j}. If p_{j} is marked by y, then the corresponding strip is the down-triangle-strip whose line of centers of its triangles intersects the step p_{j}. In either case we designate by 6T_{P} six copies of the strip corresponding to the step p_{j}.

In the region under any path in S_{n+1} a contiguous-strip is a maximal array of up and down triangles having the centers of their hypotenuses on a single line of slope −1. Each marked path P ∈ [n+1]×S_{n+1} determines a unique strip under P, namely that contiguous-strip whose line of hypotenuse centers intersects the marked step of P. We designate this strip by T C_{P}. The marked triangles of Figure 3 indicate a contiguous-strip. the electronic journal of combinatorics 47 (1998) #R47 6

Figures 2 through 14.

In the region under any path in S_{n−1} each down triangle can always be paired with the contiguous up triangle on its right, but not visa-versa. A diamond-strip is a maximal array of such pairs of triangles whose common sides lie on a line of slope 1. The marked step of each path P ∈ [n − 2] × S_{n−1} determines a unique diamond-strip under P, namely the diamond-strip whose line of common sides intersects the final point of the z-marked step of P. We designate this diamond-strip by T D_{P}. The marked triangles of Figure 14 indicate a diamond-strip.

Under a path P ∈ [n − 2] × S_{n−1}, any up triangle that is not contiguous along its left side with a down triangle is viewed as an isolated-triangle. Figure 10 illustrates an isolated-triangle. Since the left side of each isolated-triangle is a U-step of P and conversely, each U-step, say p_{h}, uniquely matches an isolated-triangle that we designate by T I_{P,h}. The disjoint collection of strips and isolated-triangles

(  ⋃_{P ∈[n−2]×S_{n−1}}{T D_{P} }) ⋃ ( ⋃_{P ∈S_{n−1}} ⋃_{h∈u(P)}{T I_{P,h}})

partitions the total region under the paths in S_{n−1}, where u(P) is the set of the positions of the U-steps on P.

To construct a function that yields a combinatorial proof of recurrence (4), consider defining

g : ⋃_{P ∈[2n−1]×S_{n}}{6T_{P} } → T ⋃ Q

where the elements of T and Q will be ordered triples and ordered quadruples, respectively, of mutually non overlapping strips partitioning the total region lying under the paths of S_{n+1} and S_{n−1}.

With P being an arbitrary path as in (6), the bijection f induces a function g so that Case i: if p_{j} = U^{x}, H^{x}, or D^{y}, define

g(6T_{P}) = (T C_{f(P a)}, T C_{f(P b)}, T C_{f(P c)}).

Case ii: if p_{j−1}p_{j} = p_{i}p_{j} = UH^{y}, define

g(6T_{P}) = (T C_{f(P a)}, T C_{f(P b)}, T C_{f(P c)}, T I_{R,i}),

where R = p_{1} ⋯ p_{i}p_{i+2} ⋯ p_{m}. Case iii: if p_{j−1}p_{j} = HH^{y} or DH^{y}, define

g(6T_{P}) = (T C_{f(P a)}, T C_{f(P b)}, T D_{f(P c)}).

The mapping of six copies of the strip of Figure 2 to those of Figures 3 to 5 illustrates Case i. Likewise Figure 6 with Figures 7 to 10 illustrates Case ii, and Figure 11 with Figures 12 to 14 illustrates Case iii. Notice that each column of the array of figures shows the 6-fold transfer of area.

The function f being bijective implies g is bijective. The following three items can be routinely checked to show that g transfers area as claimed. Here A(T) denotes the area of an arbitrary strip T. For Case i, (A(T C_{f(P a)}), A(T C_{f(P b)}), A(T C_{f(P c)})) = (2A(T_{P}) + 1, 2A(T_{P}) − 1, 2A(T_{P})); Case ii, (A(T C_{f(P a)}), A(T C_{f(P b)}), A(T C_{f(P c)}), A(T I_{R,j})) = (2A(T_{P}) + 1, 2A(T_{P}) − 1, 2A(T_{P}) − 1, 1); Case iii, (A(T C_{f(P a)}), A(T C_{f(P b)}), A(T D_{f(P c)})) = (2A(T_{P})+1, 2A(T_{P})−1, 2A(T_{P}));

Finally to prove recurrence (3) we remove all reference to H-steps and the tag c in this proof.

4 Notes

1. The following corollary of the construction of the function f originated as a fortuitous observation resulting in the definition for the crucial Case 3:

For n ≥ 2, there are (n − 2)r_{n−1} step pairs of the form DH or HH on the totality of paths of S_{n}.

2. One of the more interesting of the many references to the Catalan numbers is Stanley’s [15] collection of 66 combinatorial interpretations of these numbers. His book [15] lists other primary references in the vast literature for these numbers.

3. In lieu of the three step types employed in this paper, the step types (0, 1), (1, 0), and (1, 1) are the usual step types defining Schröder paths. For the latter three types, clearly the Schröder number r_{n} counts the paths running from (0, 0) to (n−1, n−1) and never passing below the line y = x. In an early paper on paths with such step types Moser and Zayachkowski [7], realizing that the number of unrestricted paths from (0, 0) to (n, n) is a Legendre polynomial evaluated at 3, used a recurrence for these polynomials to derive essentially recurrence (2).

4. We use “r_{n}” for the large (or double as in [4]) Schröder numbers since s_{n} = r_{n}/2 for n ≥ 2 with s_{1} = 1 is reserved for the so-called small Schröder numbers: 1, 1, 3, 11, 45, . . .. Ernst Schröder formulated these numbers in the second problem of his 1870 paper [14]: In how many ways can one or more pairs of brackets be legally placed in z_{1}, z_{2} ⋯ z_{n}? For instance, when n = 3, there are the three bracketings, (z_{1}z_{2}z_{3}), ((z_{1}z_{2})z_{3}), and (z_{1}(z_{2}z_{3})). The problem of enumerating bracketings is equivalent both to the problem of enumerating dissections of convex polygons and to the problem of enumerating Schröder trees with a fixed number of leaves. (A Schröder tree is a plane trees whose internal nodes have at least two children.)

As noted in [16], David Hough discovered that the small Schröder numbers were apparently known to Hipparchus in the second century B.C. as counting certain logical propositions. The papers [2, 9, 12, 11, 13, 16, 17] form a selection of the studies concerning the Schröder numbers. Of particular interest is the result of Rogers and Shapiro, appearing implicitly in [12, 13], and later the result of Bonin, Shapiro, and Simion [2], that give combinatorial maps relating the enumeration of bracketings to the enumeration of lattice paths of S_{n}.

5. A well-weighted binary plane tree is a binary tree where each node having a right internal child is labeled with a 1 or a 2. Foata and Zeilberger [3], after giving a rather simple bijection between Schröder trees and well-weighted binary plane trees, showed bijectively that the small Schröder numbers satisfy (n + 1)s_{n+1} = 3(2n − 1)s_{n} − (n − 2)s_{n−1} with the conditions s_{1} = 1, and s_{2} = 1. Their proof is not isomorphic to our proof of (2); this is not surprising since the bijections mentioned at the end of Note 3 between bracketings and S_{n} do not seem to be trivial.

6. In this and the next note define sequence AS_{n} purely as the one satisfying the formal recurrence (4), not specifically in terms of lattice paths. Barcucci, Brunetti, Del Lungo, and Del Rietoro [1] recently gave a combinatorial interpretation of formal recurrence (4) in terms of a regular language. In [5] the sequence AS_{n} is related to solutions of the diophantine equation, x^{2} + (x + 1)^{2} = y^{2}, with x = (AS_{n} − 1)/2. Newman, Shanks, and Williams [8] found that the numbers AS_{n} correspond to the orders of certain simple groups.

7. The author [18] has considered the formal recurrences (1) to (4) bijectively in terms of parallelogram polyominoes. For n ≥ 2, let p_{α,n}(w) = ∑_{k} p_{α,n,k}w^{k}, where p_{0,n,k} denotes the number of parallelogram polyominoes with perimeter 2n and width k, and where (n − 1)p_{1,n,k} denotes the total area of such polyominoes. The paper [18] shows that the sequences p_{0,n}(w) and p_{1,n}(w) satisfy the recurrences

(n + 1 − α)p_{α,n+1}(w) = (2n − 1 − α)(1 + w)p_{α,n}(w) − (n − 2)(1 − w)^{2}p_{α,n−1}(w),

with initial conditions p_{α,2}(w) = w, p_{α,3}(w) = w + w^{2}. The proof for the case α = 0 in [18] is isomorphic to the proof in [3], but not to the proof of Section 2.

More specifically, the total area (n − 1)p_{1,n}(1) is 4^{n−2}; this result was recently derived by interesting generating-function argument by Woan, Shapiro, and Rogers [19]. The product (n − 1)p_{1,n}(2), corresponding to the sum of the areas of polyominoes having bi-colored columns, satisfies the recurrence np_{1,n+1}(2) = 6(n−1)p_{1,n}(2)− (n − 2)p_{1,n−1}(2) with early values (n − 1)p_{1,n}(2) = 1, 6, 35, 204, 1189, …, for n = 2, 3, 4, 5, 6 . . .. These polynomial sequences, p_{α,n}(w), generalize other well-known sequences: e.g., {p_{0,n}(1)}_{n≥2} are the Catalan numbers, {p_{0,n}(2)}_{n≥2} are the large Schröder numbers, {((n − 1)p_{1,n}(2)/2)^{2}}_{n≥2} are the square-triangular numbers, and {p_{2,n}(1)} are the central binomial coefficients.

8. Recently, Merlini, Sprugnoli, and Verri [6] used generating function methods in determining the sum of the areas bounded by constrained lattice paths belonging to sets that essentially generalize C_{n} and S_{n}. The paper [6] also contains additional relevant references to the literature.

References

[1] E. Barcucci, S. Brunetti, A. Del Lungo, and F. Del Rietoro, A combinatorial interpretation of the recurrence f_{n+1} = 6f_{n} − f_{n−1}, Discrete Math., 190 (1998) 235-240.

[2] J. Bonin, L. Shapiro, and R. Simion, Some q-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statistical Planning and Inference 34 (1993) 35-55.

[3] D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb. Theor., Ser. A., 80 (1997), 380-384. Available at http://www.math.temple.edu/˜ zeilberg/papers1.html.

[4] G. Kreweras, Aires des chemins surdiagonaux a étapes obliques permises. Cahier du B.U.R.O. 24 (1976) 9-18.

[5] A. Martin, Diophantine analysis (Solutions of Problems), Am. Math. Monthly, 4 (1897) 24-25.

[6] D. Merlini, R. Sprugnoli, and M. C. Verri, The area determined by underdiagonal lattice paths, Discrete Math., to appear.

[7] L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1963) 223-229.

[8] M. Newman, D. Shanks and H. C. Williams, Simple groups of square order and an interesting sequence of primes, Acta Aritmetica XXXVIII (1980) 129-140.

[9] E. Pergola and R. A. Sulanke, Schröder triangles, paths, and parallelogram polyominoes, Journal of Integer Sequences, Vol. 1 (1998), Available at http://www.research.att.com/˜ njas/sequences/JIS/

[10] J-L Rémy, Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatpoire, RAIRO Inform. Théor., vol 19 (1985) 179 - 195.

[11] D. G. Rogers, A Schröder triangle, Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference. Lecture Notes in Mathematics, vol 622, Springer-Verlag, Berlin (1977) 175-196.

[12] D. G. Rogers, The enumeration of a family of ladder graphs part II: Schröder and superconnective relations, Quart. J. Math. Oxford (2) 31 (1980) 491-506.

[13] D. G. Rogers and L. Shapiro, Some correspondences involving the Schröder numbers, Combinatorial Mathematics: Proceedings of International Conference, Canberra, 1977. Lecture Notes in Math. 686, Springer-Verlag (1978) 267-276.

[14] E. Schröder, Vier kombinatorische probleme, Z. Math. Phys. 15 (1870) 361 - 376.

[15] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999 (tentative)

[16] R. P. Stanley, Hipparchus, Plutarch, Schröder, Hough, Am. Math. Monthly, 104 (1997) 344 - 350.

[17] R. A. Sulanke, A recurrence restricted by a diagonal condition: generalized Catalan array, Fibonacci Q., 27 (1989) 33 - 46.

[18] R. A. Sulanke, Three recurrences for parallelogram polyominoes, J. of Difference Eq. and its Appl., (1998 tentative) Available at http://diamond.idbsu.edu/˜ sulanke/recentpapindex.html

[19] W-J Woan, L. Shapiro, and D. G. Rogers, The Catalan numbers, the Lebesgue integral and 4^{n−2}, Am. Math. Monthly, 104 (1997) 926 - 931.