A Combinatorial Interpretation of the Area of Schröder Paths

E. Pergola, R. Pinzani

Dipartimento di Sistemi e Informatica, Università di Firenze,
         Via Lombroso 6/17, 50134 Firenze, Italy,
    e-mail:  elisa@dsi.unifi.it, pinzani@dsi.unifi.it

Submitted: September 3, 1999; Accepted: October 14, 1999.

Abstract

An elevated Schröder path is a lattice path that uses the steps (1, 1), (1, −1), and (2, 0), that begins and ends on the x-axis, and that remains strictly above the x-axis otherwise. The total area of elevated Schröder paths of length 2n + 2 satisfies the recurrence f_{n+1} = 6f_{n} − f_{n−1}, n ≥ 2, with the initial conditions f_{0} = 1, f_{1} = 7. A combinatorial interpretation of this recurrence is given, by first introducing sets of unrestricted paths whose cardinality also satisfies the recurrence relation and then establishing a bijection between the set of these paths and the set of triangles constituting the total area of elevated Schröder paths.

1 Introduction

In the plane ZZ× ZZ, we will use lattice paths with three steps types: a rise step defined by (1, 1), a fall step defined by (1, −1), and a horizontal step defined by (2, 0). A Schröder path is a sequence of rise, fall and horizontal steps running from (0, 0) to (2n,0) and remaining weakly above the x–axis. These paths are counted by the large Schröder numbers, denoted by r_{n}. The first few entries of the sequence {r_{n}}_{n≥0} are: 1, 2, 6, 22, 90, 394, … (sequence M1659 in [14]) and their generating function is ∑_{n≥0} r_{n}t^{n} = \frac{1−t−\sqrt{1−6t+t^{2}}}{2t}. For other combinatorial objects counted by the Schröder numbers, see [2, 4, 5, 6, 10, 11, 12, 13].

An elevated Schröder path is the path obtained from a Schröder path by adding a rise step at its beginning and a fall step at its end. In the sequel, we denote S_{2n} the class of elevated Schröder paths of length 2n.

We wish to use the area under Schröder paths to consider the combinatorial significance of the recurrence:

f_{n+1} = 6f_{n} − f_{n−1}, n ≥ 2,  (1)

subject to the initial conditions f_{0} = 1, f_{1} = 7. This recurrence defines a sequence whose first terms are: 1, 7, 41, 239, 1393, … (sequence M4423 in [14]). These numbers are known as NSW numbers, and are related both to the order of simple groups [9] and to the solutions of the Diophantine equation: x^{2} + (x + 1)^{2} = y^{2} [8].

We will obtain a new bijective proof for this recurrence in terms of the area of Schröder paths. In 1976 Kreweras [7] proved that the sum of the areas of the regions lying under the elevated Schröder paths satisfies recurrence (1). Specifically,

Proposition 1.1 If A_{n} denotes the total area of the regions lying below the elevated Schröder paths of length 2n + 2 and the x-axis, then A_{n} satisfies the recurrence A_{n+1} = 6A_{n} − A_{n−1}, subject to the initial conditions A_{0} = 1, A_{1} = 7.

Bonin et al. [3] asked for the combinatorial interpretation of f_{n+1} = 6f_{n} − f_{n−1} with the phrase: “The recurrence f_{n+1} = 6f_{n} − f_{n−1} cries out for a combinatorial interpretation”. Barcucci et al. [1] gave the first answer using a regular language defined so that the number of words having length n is equal to f_{n+1}. Sulanke [15] gave a combinatorial interpretation of the recurrence in terms of total area of elevated Schröder paths.

In this paper, we present another combinatorial interpretation proving Proposition 1.1.

We remark that our analysis naturally applies to elevated Dyck paths of length 2n where the total area A_{n} satisfies A_{n} = 4A_{n−1}, and hence is 4^{n−1}.

2 An auxiliary path class

Let V_{n} denote the set of all unrestricted lattice paths that run from (0, 0) to the line x = 2n + 1 and that use the steps (1, 1), (1, −1) , and (2, 0) and that do not end with a rise step. The first stage of our proof of Proposition 1.1 will use

Proposition 2.1 The cardinality v_{n} of the set V_{n} satisfies the recurrence relation (1) subject to the given initial conditions.

Proof. The initial conditions are trivial to check. To prove that {v_{n}}_{n≥0} increases according to the recurrence (1), we apply 6 different operations to the paths in V_{n} and establish a construction for V_{n+1} if and only if some particular paths are removed.

We pass from a path P ∈ V_{n} to a path P′ ∈ V_{n+1} by:

1. adding a pair of rise steps at the beginning of P (see Figure 1, (1)),

2. adding a rise step followed by a fall step at the beginning of P (see Figure 1, (2)),

3. adding a pair of fall steps at the beginning of P (see Figure 1, (3)),

4. adding a fall step followed by a rise step at the beginning of P (see Figure 1, (4)),

5. adding a horizontal step at the beginning of P (see Figure 1, (5)),

6. inserting a horizontal step after the first step of P (see Figure 1, (6)).

The paths obtained by performing the above described operations lie in V_{n+1}, and moreover, each P′ ∈ V_{n+1} is obtained from some P ∈ V_{n}. However, some paths in V_{n+1} are obtained twice. They are precisely those paths beginning with two consecutive horizontal steps obtained under operations 5 and 6. The proof is completed by seeing that the set of paths beginning in a horizontal step is immediately obtained by adding a first horizontal step to the paths in V_{n−1}, which has cardinality v_{n−1}.

Next we partition V_{n} into three sets. The paths in V_{n}^{(−1)} have final ordinate (−1) and end with a fall step, they are counted by the Delannoy numbers [4, p. 81]. Let V_{n}^{↑} denote the subset of paths that have positive final ordinate. Let V_{n}^{↓} denote the complement V_{n} − V_{n}^{(−1)} − V_{n}^{↑} .

Figure 1: The six different operations to pass from V_{n} to V_{n+1}.

Taking a path in V_{n}^{↑} into consideration, we remove its last step, take the reflection in the horizontal axis and reinsert the removed last step (see Figure 2).

Hence,

Lemma 2.2 There is a bijection between V_{n}^{↑} and V_{n}^{↓}.

3 A bijection between triangles and paths of V_{n}

Consider the region bounded by a path P and the x–axis. Let a(P) denote the area of that region. We will take as our measure unit a triangle whose vertex coordinates are either (x, y), (x + 1, y + 1), and (x + 2, y) or (x, y), (x − 1, y + 1), and (x + 1, y + 1). We call the first type an up triangle and the second type a down triangle. Figure 3 shows an elevated Schröder path of length 16 and area 25. Let A_{n} = ∑_{P ∈S_{2n}} a(P), i.e., A_{n} is the total area

of elevated Schröder paths having length 2n (see Figure 4).

Figure 2: The bijection between V_{n}^{↑} and V_{n}^{↓}.

We can partition the triangles decomposing the total region of the (2n + 2)–length elevated Schröder paths into three sets. The set T_{1}^{(n)} contains the up triangles that touch the path by their right side. The set T_{2}^{(n)} contains the up triangles that do not touch the path by their right side, and the set T_{3}^{(n)} contains the down triangles (see Figure 5). It is easily seen that each triangle in T_{2}^{(n)} has on its right a triangle in T_{3}^{(n)}, and that every triangle in T_{3}^{(n)} is so obtained.

Hence,

Lemma 3.1 There is a bijection between T_{2}^{(n)} and T_{3}^{(n)}.

We will now give constructions that establish: the electronic journal of combinatorics 6 (1999),#R40 6

Figure 3: An elevated Schröder path. Figure 4: The 6 elevated Schröder paths of S_{6} and A_{3} = 41.

Figure 5: The partition of the area of a (2n + 2)–length elevated Schröder path.

Lemma 3.2 There are bijections between the following pairs:

• T_{1}^{(n)} and V_{n}^{(−1)},

• T_{2}^{(n)} and V_{n}^{↑},

• T_{3}^{(n)} and V_{n}^{↓}.

Proof.

A bijection from the triangles in T_{1}^{(n)} to the path in V_{n}^{(−1)} Suppose that (x, y), (x + 1, y + 1), and (x + 2, y) are the vertices of a

triangle in T_{1}^{(n)} under an elevated Schröder path P ∈ S_{2n+2}. Let Q denote the point (x + 2, y). To obtain the corresponding path in V_{n}^{(−1)} first delete the initial rise step of P and then transpose the subpath of P that follows Q with the modified subpath that precedes Q. (see Figure 6).

Figure 6: A pointed triangle in T_{1}^{(n)} and the corresponding path in V_{n}^{(−1)}.

Figure 7: A path in V_{n}^{(−1)} and the corresponding pointed triangle in T_{1}^{(n)}.

This construction can be inverted as follows. For any path in V_{n}^{(−1)} (see Figure 7 (a)), the leftmost point in the path having least ordinate, say Q′, determines two paths, the one on its left and the one on its right. We place the desired triangle to lie just below the last step of the path as showed in Figure 7 (b). The two paths are transposed, together with the desired triangle, and a rise step is added at the beginning (see Figure 7 (c)).

A bijection from the triangles in T_{2}^{(n)} to the paths in V_{n}^{↑} Suppose that (x, y), (x + 1, y + 1), and (x + 2, y) define a triangle in T_{2}^{(n)}

under an elevated Schröder path P ∈ S_{2n+2}. We draw a line of slope 1 from the point (x + 2, y). This line meets the path P for the first time at a point on P, labeled Q. Next we draw y + 1 horizontal rays to the right from the center of the chosen triangle and from the center of each triangle beneath it. Each of these rays meets, for the first time, a fall step in P which we change into a rise step. We then delete the initial rise step and transpose the modified subpath following Q with the modified subpath preceding Q to obtain a path in V_{n}^{↑}. (see Figure 8).

Figure 8: A pointed triangle in T_{2}^{(n)} and the corresponding path in V_{n}^{↑}.

To see the inversion of this construction consider a path in V_{n}^{↑} with final ordinate 2y + 1, y ≥ 0, (see Figure 9 (a)). Let q be the ordinate of the rightmost point in the path having least ordinate. From each of the points in the set {(2n + 2, q + i − 0.5)|1 ≤ i ≤ y + 1} draw a horizontal ray to the left. These rays hit the path for a first time at y + 1 rise steps as shown in Figure 9 (b). The final end point of the (y + 1)–th rise step, say Q′, determines two paths: one on its left and one on its right (see Figure 9 (b)). We place the desired up triangle with its rightmost vertex determined by the intersection of the horizontal line of ordinate q + 2y and the line of slope 1 passing from the final point of the original path (see Figure 9 (b)). This triangle is rigidly attached to the path on the right of Q′. In the particular case of y = 0 the rise step which must be changed into fall step is the left side of the triangle, and the rise step that has to be added at the beginning of the path covers the left side of the triangle. Once the y + 1 rise steps that were hit have been changed into fall steps, the two resulting subpaths are transposed, along with the desired triangle, as showed in Figure 9 (c) and a rise step is added at the beginning. Simple geometric considerations show that the resulting path is an elevated Schröder path.

The third part of the lemma follows from the previous parts and Lemmas 2.2, 3.1.

Figure 10 shows the bijection between the triangles constituing the total area of 2– and 4–length Schröder paths and the paths in V_{0} and V_{1}, respectively.

Proposition 1.1 is now a consequence of Proposition 2.1 and the above lemma.

Figure 9: A path in V_{n}^{↑} and the corresponding pointed triangle in T_{2}^{(n)}.

Figure 10: The bijection between triangles and paths in V_{n}, n = 0, 1.

Acknowledgements

The authors wish to thank R. A. Sulanke for carefully reading the manuscript and giving them many useful suggestions and the anonymous referee for his valuable remarks.

References

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

[2] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, Some Combinatorial Interpretations of q–Analogs of Schröder Numbers, Annals of Combinatorics, 3 (1999) 173–192.

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

[4] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht (1974). Mathematical &

[5] D. Gouyou–Beauchamps, B. Vauquelin, Deux propriétés combinatoires des nombres de Schröder, Theoretical Informatics and Applications, 22 (1988) 361–388.

[6] D. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (second edition), Addison Wesley, Reading, MA (1973).

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

[8] M. A. Gruber et al., Problem 47, American Mathematical Monthly, 4 (1897) 24–28.

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

[10] E. Pergola, R. A. Sulanke, Schröder triangles, paths, and parallelogram polyominoes, Journal of Integer Sequences, Vol. 1 (1998)

[11] D. G. Rogers, L. Shapiro, Some correspondences involving the Schröder numbers and relations, Lecture Notes in Mathematics, Vol. 686, Springer–Verlag, New–York Heidelberg Berlin (1978) 267–274.

[12] D. G. Rogers, L. Shapiro, Deques, trees and lattice paths, Lecture Notes in Mathematics, Vol. 884, Springer–Verlag, New–York Heidelberg Berlin (1981) 293–303.

[13] L. Shapiro, A. B. Stevens, Bootstrap percolation, the Schröder numbers, and the n–kings problem, SIAM Journal on Discrete Mathematics, 4 (1991) 275–280.

[14] N. J. A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New–York (1995).

[15] R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electronic Journal of Combinatorics 5 (1998), # R47.