Generalized Schröder Numbers and the Rotation Principle

Joachim Schröder Universiteit van die Vrystaat Departement van Wiskunde Posbus 339 Bloemfontein 9300 South Africa

              schroderjd@qwa.uovs.ac.za ^{∗}

Abstract

Given a point-lattice (m+1)×(n+1) ⊆ ℕ×ℕ and l ∈ ℕ, we determine the number of royal paths from (0, 0) to (m, n) with unit steps (1, 0), (0, 1) and (1, 1), which never go below the line y = lx, by means of the rotation principle. Compared to the method of “penetrating analysis”, this principle has here the advantage of greater clarity and enables us to find meaningful additive decompositions of Schröder numbers. It also enables us to establish a connection to coordination numbers and the crystal ball in the cubic lattice ℤ^{d}. As a by-product we derive a recursion for the number of North-East turns of rectangular lattice paths and construct a WZ-pair involving coordination numbers and Delannoy numbers.

1 Introduction

Given a m × n chess board we can ask ourselves in how many different ways a king can walk from the lower left corner (0, 0) to the upper right corner (m, n). The king may only take single steps to the north, east, and north-east; see Fig.1 for m = n = 2. Such paths are called royal. The (known) answer to this question is given by the Delannoy numbers

D(n, m) = ∑_{ν=0}^{m} (\begin{matrix}m \\ ν \end{matrix}) (\begin{matrix}n + ν \\ m \end{matrix}) = ∑_{ν=0}^{min\{m,n\}} 2^{ν} (\begin{matrix}m \\ ν \end{matrix}) (\begin{matrix}n \\ ν \end{matrix})  (1)

∗web page: http://www16.brinkster.com/jodis

[figure]

Figure 1: D(2, 2) = 13 and Schr(2, 2, 1) = 6

The sequence of central Delannoy numbers (D(n, n))_{n∈ℕ} is the Legendre transform of the constant sequence (1, 1, …) and the close relation to Legendre polynomials is often noticed: D(n, n) = P_{n}(3). Early references are Moser [20] and Lawden [18]. This relation is usually regarded as an isolated incident (see, e.g., Banderier and Schwer [3, p. 41], and Sulanke [34, p. 2]). Compare, however, the different opinion of Hetyei [14]. Sulanke alone lists 30 combinatorial structures counted by the Delannoy numbers in [34, 33]. Banderier & Schwer [3] give additional information about the origin and use of this number sequence.

A companion of the Delannoy sequence and of independent interest is the sequence of (large) Schröder-numbers (Schr(n, m))_{n,m∈ℕ}: The number of royal superdiagonal paths from (0, 0) to (m, n), i.e., the number of king walks which may touch but not go below the diagonal y = x. (see bold paths in Fig.1). The history of (small) Schröder numbers 1/2 × Schr(n, n), n ≥ 1, probably reaches tack as far as 200 B.C.E. [30]. Stanley [31, Exercise 6.39] gives 11 combinatorial objects counted by (Schr(n, n))_{n∈ℕ}.

Constrained lattice paths are closely related to the enumeration of trees, ballot sequences, pattern avoiding permutations, parallelogram polyominoes and polygon dissections [31].

There are general methods of deriving complicated formulae for restricted lattice paths [17, 5, 11]. However, one might be interested in an expression of closed form.

Goulden & Serrano [13], using the step set {(0, 1), (1, 0)}, noticed that André ’s reflection principle [2] can successfully be replaced by the rotation principle [16, 13], when the restricting line has an integer slope strictly larger than 1. We will apply their method to lattice paths with the step set {(0, 1), (1, 0), (1, 1)}, i.e., we will be dealing with generalized Schröder numbers. They have been investigated before by Rogers [24, 23], Rogers & Shapiro [25] and Sulanke [32] within the framework of general convolution arrays in Example 6A.

Our approach is geometrically appealing and establishes a connection to Delannoy and coordination numbers [ see Def. 2.2.5 ]. There are other methods suited for this type of enumeration problems, but the geometric meaning is less obvious. They are variously termed ‘penetrating analysis’ (aka ‘cycle lemma application’ [10], ‘conjugacy principle’ [22], ‘radiation scheme’ [32]), the elegant ‘two rowed arrays’ [15] and ‘balls into cells’ [12], [19, p. 20], if the slope of the restricting line equals 1. Note that Goulden & Serrano [13] forced a geometric bijection between two-rowed-arrays and paths with a fixed number of turns.

After presenting preliminary facts and results about NE- and EN-turns in section 2, we address the main purpose of this paper as indicated in the title in section 3 and derive two additive decompositions of Schröder numbers. Section 4 deals with miscellaneous aspects such as generating functions, Delannoy numbers and coordination numbers. Calculations were carried out with Maple^{\begin{matrix}c \\ ◯ \end{matrix}} 9.1.

2 Prerequisites

Definition 2.1. 1. A nonempty subset S ⊆ ℕ × ℕ \ {(0, 0)} is called step set.

2. A path in (m + 1) × (n + 1) from (0, 0) to (m, n) is a finite sequence of points ((x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{k}, y_{k})) such that (x_{i}, y_{i}) ∈ S for all i, 1 ≤ i ≤ k and ∑ x_{i} = m, ∑ y_{i} = n.

3. A path is called l-path, l ∈ ℕ, if for all j, 1 ≤ j ≤ k we have ∑_{i=1}^{j} y_{i} ≥ l ∑_{i=1}^{j} x_{i}; i.e., an l-path may touch but may not go below the line y = lx.

4. The set of all l-paths from (0, 0) to (m, n) with the step set S is denoted by _{l}L_{S}(m, n).

5. Let L ∈_{l}L_{S}(m, n). An up-step (0, 1) of L immediately followed by a right-step (1, 0) is called North-East-turn (NE-turn for short) or up-right corner of L. A right-step (1, 0) of L immediately followed by an up-step (0, 1) is called EN-turn or right-up corner of L. The number of NE-turns (EN-turns) of L is denoted by NE(L) (EN(L)). We will use the coordinate of the corner to specify a turn.

6. |A| denotes the cardinality of a set A or the absolute value of a number A.

Definition 2.2. Let S = {(0, 1), (1, 0), (1, 1)}.

1. Define D(n, m) := | _{0}L_{S}(m, n)| (Delannoy numbers)

2. Define Schr(n, m, l) := | _{l}L_{S}(m, n)|, l ≥ 1 (Schröder numbers)

3. If f : D → ℤ, D ⊆ ℤ, is a function, then the (forward) difference operator Δ is defined by Δf(n) = f(n + 1) − f(n). For instance Δ\binom{n}{ν} = \binom{n+1}{ν} − \binom{n}{ν} = \binom{n}{ν−1}, where \binom{n}{ν} is the usual binomial coefficient.

4. Let x = (x_{1}, x_{2}, ..., x_{d}) ∈ ℤ^{d}, d ∈ ℕ. The L^{1}-norm |x|_{1} of x is defined by |x|_{1} := ∑ |x_{i}|.

5. S_{d}(n) := {x | x ∈ ℤ^{d} and |x|_{1} = n} is called d − 1-dimensional crystal sphere of radius n. We set S_{d}(n) := | S_{d}(n)|. The sequence (S_{d}(n))_{n∈ℕ} is called a coordination sequence (or coordination numbers). cf. \underline{A035597} pp. and \underline{A035607} in the Encyclopedia of Integer Sequences, EIS, [29]

The union ⋃_{ν=0}^{n} S_{d}(ν) =: G_{d}(n) is called d-dimensional crystal ball of radius n. We put | G_{d}(n)| =: G_{d}(n) = ∑_{ν=0}^{n} S_{d}(ν).

Remark 2.3. In the case of l = 0 or l = 1 or n = m beautiful intuitive methods are available to show why the specified enumeration problem has the specific solution. In the sequel we will need the fact that the solution to the classical ballot problem reads (cf. [19])

|_{l}L_{\{(0,1),(1,0)\}}(m, n)| = \frac{n − lm + 1}{n + 1}\binom{m + n}{n} = \binom{m + n}{n} − l\binom{m + n}{n + 1}  (2)

and the number of paths L ∈ _{l}L_{{(0,1),(1,0)}}(m, n) with c NE-turns is (cf. [15, 13]) NE\overleftarrow{(n,m,l)}(c) := |\{L|L ∈ _{l}L_{\{(0,1),(1,0)\}}(m, n) and NE(L) = c\}| =

\binom{m − 1}{c − 1}\binom{n + 1}{c} − l\binom{m}{c}\binom{n}{c − 1} = \frac{n − lm + 1}{n + 1}\binom{m − 1}{c − 1}\binom{n + 1}{c}  (3)

Whereas the corresponding formula for EN-turns reads (cf. [15, 13]) EN\overleftarrow{(n,m,l)}(c) := |\{L|L ∈ _{l}L_{\{(0,1),(1,0)\}}(m, n) and EN(L) = c\}| =

\binom{m}{c}\binom{n}{c} − l\binom{m + 1}{c + 1}\binom{n − 1}{c − 1}  (4)

We note in passing that a separate calculation (cf. [15, 13]) of the NE-turn- and EN-turn-statistics is not necessary, because there is a fixed relation between the number of NE-turns and the number of EN-turns: |NE(L) − EN(L)| ≤ 1, depending on the type of the first and the last step. For instance, if the first step is an up-step and the last step is a right step, we have NE(L) = EN(L) + 1. An appropriate classification of paths by the type of the last step before hitting the right edge (respectively upper edge) leads to

Theorem 2.4.

NE\overleftarrow{(n,m,l)}(c) = ∑_{v=lm}^{n} EN\overleftarrow{(v,m−1,l)}(c − 1)  (5)

EN\overleftarrow{(n,m,l)}(c) = ∑_{μ=1}^{m} NE\overleftarrow{(n−1,μ,l)}(c)  (6)

Proof: Every path above y = lx, l ≥ 1, commences with an up step. A path L with first step up and last step right has one NE-turn more than EN-turns. Every path has to reach the line segment joining (m, lm) and (m, n) and does so with a right step, see Fig. 2(a). A path L′ from (0, 0) to (m − 1, ν), lm ≤ ν ≤ n with c − 1 EN-turns corresponds to a path L from (0, 0) to (m, n) with c NE-turns and a right step at (m − 1, ν). Summing over ν shows Equation 5. To show Equation 6 we apply a similar argument and observe that a path L′ from (0, 0) to (μ, n), 1 ≤ μ ≤ n^{†}, with last step up has equal numbers of NE- and EN-turns, see Fig. 2(b). □

†The case μ = 0 does not contribute to the number of EN-turns.

[figure: (m,n); y=lm; (a); ⋮; …; (m,n); y=lm; (b); ⋮; ⋮]

Figure 2: Classification of paths by right edge (a) and by upper edge (b), see the proof of Theorem 2.4.

Corollary 2.5.

\frac{n − lm + 1}{n + 1}\binom{m − 1}{c − 1}\binom{n + 1}{c} = ∑_{v=lm}^{n} [\binom{m − 1}{c − 1}\binom{v}{c − 1} − l\binom{m}{c}\binom{v − 1}{c − 2}]  (7)
\binom{m}{c}\binom{n}{c} − l\binom{m + 1}{c + 1}\binom{n − 1}{c − 1} = ∑_{μ=1}^{m} \frac{n − lμ}{n}\binom{μ − 1}{c − 1}\binom{n}{c}  (8)

Proof: Substitute Equations (3), (4) into Equations (6), (5) of Theorem 2.4. □ Corollary 2.6.

NE\overleftarrow{(n,m,l)}(c) = ∑_{v=lm}^{n} ∑_{μ=1}^{m−1} NE\overleftarrow{(v−1,μ,l)}(c − 1)  (9)
EN\overleftarrow{(n,m,l)}(c) = ∑_{μ=1}^{m} ∑_{v=lμ}^{n−1} EN\overleftarrow{(v,μ−1,l)}(c − 1)  (10)

Proof: Substitution of Equation (6) in (5) and of Equation (5) in (6). □ Corollary 2.7.

\frac{n − lm + 1}{n + 1}\binom{m − 1}{c − 1}\binom{n + 1}{c} = ∑_{v=lm}^{n} ∑_{μ=1}^{m−1} \frac{v − lμ}{v}\binom{μ − 1}{c − 2}\binom{v}{c − 1}  (11)

\binom{m}{c}\binom{n}{c} − l\binom{m + 1}{c + 1}\binom{n − 1}{c − 1} = ∑_{μ=1}^{m} ∑_{v=lμ}^{n−1} [\binom{μ − 1}{c − 1}\binom{v}{c − 1} − l\binom{μ}{c}\binom{v − 1}{c − 2}] (12)

Proof: Easy substitution of Equations 3 and 4 in Corollary 2.6. □

These formulae, but in general not their interpretation as number of turns, are also correct for l ≤ 0.

In the following we will repeatedly make use of

Lemma 2.8. Let m, n ∈ ℕ, p ∈ ℤ. Then

∑_{ν=p}^{m} 2^{ν}\binom{m}{ν}\binom{n}{ν − p} = ∑_{ν=0}^{m} \binom{m}{ν}\binom{n + ν}{m − p}

Proof: We know from Equ.1 that ∑_{ν=0}^{min\{m,n\}} 2^{ν}\binom{m}{ν}\binom{n}{ν} = ∑_{ν=0}^{m} \binom{m}{ν}\binom{n+ν}{m}. The (forward) difference operator Δ applied p times yields

∑ 2^{ν}\binom{m}{ν}\binom{n}{ν−p} = Δ^{p} ∑ 2^{ν}\binom{m}{ν}\binom{n}{ν} = Δ^{p} ∑ \binom{m}{ν}\binom{n+ν}{m} = ∑ \binom{m}{ν}\binom{n+ν}{m−p}. □

Our purpose is to extend the reach of the rotation principle beyond Goulden & Serrano [13] and to use it to find a meaningful additive decomposition of Schröder numbers. First, here is what we can get without geometric principles and penetrating analysis:

Theorem 2.9. The number of superdiagonal royal paths from (0, 0) to (m, n), n ≥ lm > 0, l ≥ 1, on a m × n grid is

Schr(n, m, l) = \frac{n − lm + 1}{n + 1} ∑_{ν=1}^{m} 2^{ν} (\begin{matrix}m − 1 \\ ν − 1 \end{matrix}) (\begin{matrix}n + 1 \\ ν \end{matrix}) = \frac{n − lm + 1}{m} ∑_{ν=1}^{m} 2^{ν} (\begin{matrix}m \\ ν \end{matrix}) (\begin{matrix}n \\ ν − 1 \end{matrix})

= \frac{n − lm + 1}{m} ∑_{ν=0}^{m} (\begin{matrix}m \\ ν \end{matrix}) (\begin{matrix}n + ν \\ m − 1 \end{matrix}) = \frac{n − lm + 1}{n + 1} ∑_{ν=0}^{n+1} (\begin{matrix}n + 1 \\ ν \end{matrix}) (\begin{matrix}m − 1 + ν \\ n \end{matrix})

= \frac{n − lm + 1}{n + 1} ∑_{v=0}^{m} \binom{n + 1}{m − v}\binom{n + v}{v}

Proof: (compare with the proof in Sulanke [32]) We know from Equ. 3 that there are \frac{n−lm+1}{n+1} \binom{m−1}{v−1}\binom{n+1}{v} paths weakly above y = lx with v NE-turns. NE-turns may be changed independently into diagonal steps or left as they are without interfering with the line y = lx. We can do this in 2^{v} different ways. Summing the term \frac{n−lm+1}{n+1}2^{v}\binom{m−1}{v−1}\binom{n+1}{v} over v proves the first equation. The remaining equations follow by easy term manipulations and by means of Lemma 2.8. □

Table 1 displays Schr(n, m, l) for small-sized input. Whereas some sequences contained in this Table can be found in Sloane’s EIS [29] (e.g., the diagonals \underline{A006318}, \underline{A006319}, ... and concatenated rows \underline{A106579}, \underline{A033877}), columns Schr(∗, m, l) and diagonals for l > 2 are not contained in the database [29].

l = 1  2  3  4
n\m 0 1 2  3 0 1 2  3 0 1 2 3 0 1 2 3
0  1  1  1  1
1  1 2  1  1  1
2  1 4 6  1 2  1  1
3  1 6 16 22 1 4  1 2  1
4  1 8 30 68 1 6 10  1 4  1 2
5  1 10 48 146 1 8 24  1 6  1 4
6  1 12 70 264 1 10 42 66 1 8 14  1 6
7  1 14 96 430 1 12 64 172 1 10 32  1 8
8  1 16 126 652 1 14 90 326 1 12 54  1 10 18
9  1 18 160 938 1 16 120 536 1 14 80 134 1 12 40
10 1 20 198 1296 1 18 154 810 1 16 110 324 1 14 66
11 1 22 240 1734 1 20 192 1156 1 18 144 578 1 16 96
12 1 24 286 2260 1 22 234 1582 1 20 182 904 1 18 130 226

Table 1: Schr(n, m, l) for small n, m, l.

3 Two Decompositions of Schröder Numbers

Theorem 3.1. Let l, m, n ∈ ℕ, l > 0, n ≥ lm. Then the number of royal paths on the m × n grid above the line y = lx from (0, 0) to (m, n) is

Schr(n, m, l) = D(n, m) − lD(n + 1, m − 1) − (l − 1)D(n, m − 1)

Proof: If a path crosses the line y = lx, there will be a first segment C whose right end-point is below y = lx. This end-point has to lie on one of the lines y = lx − s, 1 ≤ s ≤ l. As usual, we will subtract the number of bad paths (i.e., paths, which cross the line) from the number of all paths, which is given by the Delannoy numbers. There are two possibilities: The crucial segment C is a right step (I, see Fig.3 Case I), or it is a diagonal step (II, see Fig.3 Case II).

Case I) We can follow the approach of Goulden & Serrano [13]. The right end-point of C = [(α − 1, β), (α, β)] has a horizontal distance to y = lx of p/l for some p ∈ {1, 2, …, l}. Rotating the portion of the path from (0, 0) to (α − 1, β) by 180^{o}, shifting the resulting path down and right by one step each and filling the empty gap between the points (α, β − 1) and (α, β) by adding a vertical step, establishes a bijection for every p ∈ {1, 2, …, l} between all paths from (1, −1) to (m, n) and bad paths with horizontal C from (0, 0) to (m, n). Instead of repeating details from [13], we turn to Case II) Now C is a diagonal step: C = [(α − 1, β − 1), (α, β)] and C is part of a straight line y = x + k, 0 ≤ k ≤ n − 1. (α, β) lies on one of the lines y = lx − s, 1 ≤ s ≤ l. The case s = l (and only that one) can be refuted, using β = lα − s and β − 1 ≥ l(α − 1). Hence there are β − 1 ≥ lα − l, β − 1 ≥ β + s − l, s ≤ l − 1. On the other hand, if β − 1 = l(α − 1),

[figure: Case I; y=2x−1; y=2x−2; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; (m,n); (1,−1); Case II; y=2x−1; y=2x−2; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; (m,n); (1,0)]

Figure 3: Two bad paths with their rotated portion, one for each case. See the proof of Theorem 3.1.

then β = lα − (l − 1). Hence there are only l − 1 different types of diagonal C to consider, compared to l types of horizontal C in the previous case I. For each of these l − 1 types we will construct a bijection to the set of all royal path from (1, 0) to (m, n). Let y = lx − s for fixed s ∈ {1, 2, …, l − 1} and let P′ be a (unrestricted) royal path from (1, 0) to (m, n). Since n ≥ lm there is a smallest α, α ≥ 1, where P′ hits the line y = lx − s at (α, lα − s) = (α, β). (α, β) has to be the end-point of an up step U = [(α, β − 1), (α, β)] of P′. We take the portion of P′ from (1, 0) to (α, β − 1), rotate it by 180^{o} about the centre of the line from (1, 0) to (α, β − 1) and shift it one unit to the left, which yields a path from (0, 0) to (α − 1, β − 1). Then (α − 1, β − 1) is joined to (α, β) by a diagonal step and (α, β) is joined to (m, n) using the remainder of P′. On the other hand, given a bad path P from (0, 0) to (m, n) with crossing segment C = [(α − 1, β − 1), (α, β)], β = lα − s, we rotate the portion of P from (0, 0) to (α − 1, β − 1) about the mid-point of the line segment [(0, 0), (α − 1, β − 1)]. The resulting partial path is shifted one step to the right, the gap between (α, β − 1) and (α, β) is filled with an up-step. The remainder of P from (α, β) to (m, n) completes the construction. □

Theorem 3.2. Let l, m, n ∈ ℕ, l > 0, n ≥ lm. Then

Schr(n, m, l) = S_{n+1}(m) − lS_{m}(n + 1),

i.e., Schr(n, m, l) equals the coordination number of distance m in the (n+1)-dimensional cubic lattice ℤ^{n+1} minus l times the coordination number of distance n+1 in the m-dimensional cubic lattice ℤ^{m}

Proof: By Theorem 3.1, the number of point-lattice paths above y = lx is Schr(n, m, l) = D(n, m) − lD(n + 1, m − 1) − (l − 1)D(n, m − 1) =

∑_{ν=0}^{m} 2^{ν} (\begin{matrix}m \\ ν \end{matrix}) (\begin{matrix}n \\ ν \end{matrix}) − l ∑_{ν=0}^{m−1} 2^{ν} (\begin{matrix}m − 1 \\ ν \end{matrix}) (\begin{matrix}n + 1 \\ ν \end{matrix}) − (l − 1) ∑_{ν=0}^{m−1} 2^{ν} (\begin{matrix}m − 1 \\ ν \end{matrix}) (\begin{matrix}n \\ ν \end{matrix}) =

∑_{ν=0}^{m} 2^{ν} (\begin{matrix}n \\ ν \end{matrix}) [(\begin{matrix}m \\ ν \end{matrix}) + (\begin{matrix}m − 1 \\ ν \end{matrix})] − l ∑_{ν=0}^{m−1} 2^{ν} (\begin{matrix}m − 1 \\ ν \end{matrix}) [(\begin{matrix}n + 1 \\ ν \end{matrix}) + (\begin{matrix}n \\ ν \end{matrix})] =

= S_{n+1}(m) − lS_{m}(n + 1).  (13)

Indeed, Conway & Sloane show in [7], p. 9, Equ. (16), that

S_{d}(n) = ∑_{k=0}^{d} \binom{d}{k}\binom{n + d − k − 1}{d − 1} (= ∑_{k=0}^{d} \binom{d}{k}\binom{n + k − 1}{d − 1})

is the coordination number of distance n in ℤ^{d}. To establish equality in Equ. 13 we only need Lemma 3.3.

S_{a+1}(b) = ∑_{ν≥0} (\begin{matrix}a + 1 \\ ν \end{matrix}) (\begin{matrix}b − 1 + ν \\ a \end{matrix}) = ∑_{ν≥1} 2^{ν} (\begin{matrix}a + 1 \\ ν \end{matrix}) (\begin{matrix}b − 1 \\ ν − 1 \end{matrix})

= ∑_{ν≥0} (\begin{matrix}a \\ ν \end{matrix}) [(\begin{matrix}b + ν \\ a \end{matrix}) + (\begin{matrix}b + ν − 1 \\ a \end{matrix})] = ∑_{ν≥0} 2^{ν} (\begin{matrix}a \\ ν \end{matrix}) [(\begin{matrix}b \\ ν \end{matrix}) + (\begin{matrix}b − 1 \\ ν \end{matrix})]

Proof: It is

∑_{ν≥0} (\begin{matrix}a \\ ν \end{matrix}) (\begin{matrix}b + ν \\ a \end{matrix}) = ∑_{ν≥1} (\begin{matrix}a \\ ν − 1 \end{matrix}) (\begin{matrix}b + ν − 1 \\ a \end{matrix}) = ∑_{ν≥0} (\begin{matrix}b + ν − 1 \\ a \end{matrix}) [(\begin{matrix}a + 1 \\ ν \end{matrix}) − (\begin{matrix}a \\ ν \end{matrix})] ,

thus

∑_{ν≥0} (\begin{matrix}a \\ ν \end{matrix}) [(\begin{matrix}b + ν \\ a \end{matrix}) + (\begin{matrix}b + ν − 1 \\ a \end{matrix})] = ∑_{ν≥0} (\begin{matrix}a + 1 \\ ν \end{matrix}) (\begin{matrix}b − 1 + ν \\ a \end{matrix}) = S_{a+1}(b) □

The remaining identities follow from the preparatory Lemma 2.8. □ Corollary 3.4.

S_{a+1}(b) = D(a, b) + D(a, b − 1)

Compare Corollary 4.4.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; k = 2 \{; l = 3 \{; \} l = 3; 4 = m; 14=lm+k=n; (l + 1)m + k = 18; 2; 6; 10; 14; 18; 1; 2; 3; 4 = m; F_{1} =6; F_{2} = 8; F_{3} = 18; F_{4} = 32; \frac{F_{1}}{4}; \frac{F_{2}}{4}; \frac{F_{3}}{4}; \frac{F_{4}}{4}; 12; F_{i} ↦ \frac{F_{i}}{l+1}]

Figure 4: The case n = 14, m = 4, l = 3.

Proof: This is trivially true because of Lemma 3.3 and Equation 1. □

It is an interesting detail that a contribution to the investigation of Schr(2m, m, 2) was made, though unknowingly, in the problem section of the American Mathematical Monthly [9, 6] by D. Callan and the proposer E. Deutsch, when they submitted their (different) solutions to problem 10658; see also sequence \underline{A027307} in the EIS [29]. In fact, as the subsequent Theorem 3.5 shows, they gave a first quadrant representation of Schr(2m, m, 2) in the following way: Let a_{m} denote the number of lattice paths in ℤ × ℤ which stay in the first quadrant, commence at (0, 0) and terminate at (3m, 0) with unit steps (1, 2), (2, 1) and (1, −1). Then

Theorem 3.5.  a_{m} = Schr(2m, m, 2), m ∈ ℕ  □

Instead of proving this Theorem we show the more general

Theorem 3.6. Let Q(k, m, l) denote the number of point-lattice paths in ℤ×ℤ which stay in the first quadrant, start at (0, k), end at ((l + 1)m + k, 0) and with unit steps (1, l), (2, l − 1), (1, −1). Then Q(k, m, l) = Schr(n, m, l), where k = n − ml, n, m, l ∈ ℕ, n ≥ ml.

Proof: The similarity between the reversed path in the first quadrant and the superdiagonal royal path in Fig. 4 is apparent and suggests finding an affine map between the two, but a bijective proof is preferable. The bijection is established by means of certain areas defined above a lattice path in the first quadrant and above a Schröder path in the m × n grid. The factor of proportionality between these areas is 1/(l + 1). Instead of tedious details, Fig. 4 might suffice as a proof. □

4 GF, Delannoy and Coordination Numbers

Remark 4.1. In the last section of this article we address miscellaneous results surrounding Schröder numbers such as their generating function (GF) and a recursion involving the slope l. A general result as regards GFs of convolution arrays was discovered by Sulanke [32, 1.8, 1.9]. We also establish a connection between Delannoy numbers and crystal spheres and construct a WZ-pair.

The special case Schr(2m, m, 2) was treated in Deutsch et al. [6]. Our GF is two-variate (see Theorem 4.7) and accomplished by combining two results from Sulanke [32]. We will need the GF of Delannoy numbers D(n, m) (cf. [31]):

GF((D(n, m))_{n,m≥0}) = ∑_{n,m≥0} D(n, m)x^{n}y^{m} = \frac{1}{1 − x − y − xy}

In essence the first result describes the GF of the coordination sequence of the cubic lattice ℤ^{d}. It is the GF version of Corollary 3.4.

Theorem 4.2.

GF((S_{a+1}(b))_{a,b≥0}) = ∑_{a,b≥0} S_{a+1}(b)x^{a}y^{b} = \frac{1 + y}{1 − x − y − xy}

Proof: We will use Lemma 3.3 and a result of Conway & Sloane [7], p 9, stating that for fixed d = a + 1

GF((∑_{ν=0}^{a+1} \binom{a + 1}{ν}\binom{b + ν − 1}{a})_{b≥0}) = (\frac{1 + y}{1 − y} )^{a+1}

and then

∑_{a,b≥0} S_{a+1}(b)x^{a}y^{b} = ∑_{a,b≥0} ∑_{ν=0}^{a+1} \binom{a + 1}{ν}\binom{b + ν − 1}{a}y^{b}x^{a} = ∑_{a≥0} (\frac{1 + y}{1 − y} )^{a+1} x^{a} =

\frac{1 + y}{1 − y} \frac{1}{1 − \frac{1+y}{1−y}x} = \frac{1 + y}{1 − y − x − xy}

□

Theorem 4.3.

D(a, b) = ∑_{μ=0}^{b} S_{a}(μ) = G_{a}(b)

see Fig. 5

Proof: We have

\frac{1}{1 − x − y − xy} = \frac{1}{1 − y} \frac{1}{1 − x\frac{1+y}{1−y}} = \frac{1}{1 − y} ∑_{a≥0} (\frac{1 + y}{1 − y} )^{a} x^{a} =

• • • • • • • • • • • • •

Figure 5: Thirteen points witnessing G_{2}(2) = 13 in agreement with thirteen lattice paths in Fig. 1.

\frac{1}{1 − y} ∑_{a,b≥0} S_{a}(b)y^{b}x^{a} = ∑_{a,b≥0} ∑_{μ=0}^{b} S_{a}(μ)y^{b}x^{a} = ∑_{a,b≥0} G_{a}(b)y^{b}x^{a},

see Definition 2.2.5. □

Corollary 4.4.

D(a, b) − D(a, b − 1) = S_{a}(b)

D(a, b) = \frac{S_{a+1}(b) + S_{a}(b)}{2}

D(a, b − 1) = \frac{S_{a+1}(b) − S_{a}(b)}{2}

Proof: Note G_{a}(b) − G_{a}(b − 1) = S_{a}(b) and Corollary 3.4 □

Remark 4.5. 1. Thus there is a strong relation between Delannoy numbers and coordination numbers S in ℤ^{a+1}. If we put E(n, b) := ΔD(n, b) = D(n + 1, b) − D(n, b), then (S, E) is a WZ pair, as defined in the HDCM [26], p 209.

2. Theorem 4.3 confirms in a new way the opinion of Mohanty [19], p 54, “... that paths with diagonal steps might ... be related to higher dimensional paths without diagonal steps”. Note that we may swap dimension d and distance n, because G_{d}(n) = G_{n}(d).

3. The author learned from Sulanke [34], that Theorem 4.3 is also contained in the paper of Vassilev&Atanassov [35]. Our proof is considerably shorter.

Lemma 4.6. Let m, l ∈ ℕ, l ≥ 1, n ≥ ml. Then

Schr(n, m, l) − S_{m}(n + 1) = Schr(n, m, l + 1),  (14)

as long as the left side of Equ.14 is not negative.

Proof: by easy calculation with Theorem 3.2. □

Theorem 4.7. Let A_{l}(z) = GF ((Schr(lm, m, l))_{m∈ℕ}). Then

GF ((Schr(n, m, l))_{n,m∈ℕ}) = ∑_{n,m≥0} Schr(n, m, l)w^{n}z^{m} = \frac{A_{l}(w^{l}z)}{1 − wA_{l}(w^{l}z)}

Proof: We know that GF ((Schr(lm + k, m, l))_{m≥0}) = A_{l}^{k+1}(z) (cf. [32]), consequently

GF ((Schr(lm + k, m, l))_{k,m∈ℕ}) = ∑_{k≥0} A_{l}^{k+1}(z)w^{k} = A_{l}(z)\frac{1}{1 − wA_{l}(z)}

The index shift k → lm + k is achieved by the replacement z → w^{l}z. □

References

[1] M. Aigner, Diskrete Mathematik, Vieweg, Braunschweig, 1993.

[2] D. André, Calcul des probabilités. Solution directe du problème résolu par M. Bertrand, C. R. Math. Acad. Sci. Paris, 105 (1887), 436.

[3] C. Banderier and S. R. Schwer, Why Delannoy numbers? J. Statist. Plann. Inference 135 (2005), 40–54. Electronic version available at

http://arxiv.org/abs/math/0411128.

[4] J. Bertrand, Calcul des probabilités. Solution d’un problème, C. R. Math. Acad. Sci. Paris, 105 (1887), 369.

[5] M. T. L. Bizley, Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuaries 80 (1954), 55–62.

[6] D. Callan, Solution to Problem 10658, Amer. Math. Monthly 107 (2000), 368–371.

[7] J. H. Conway and N. J. A. Sloane, Low Dimensional Lattices VII: Coordination Sequences, Proc. Roy. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 453 (1997), 2369–2389. Electronic version available at

http://citeseer.ist.psu.edu/article/conway96lowdimensional.html.

[8] H. Delannoy, Emploi de l’échiquier pour la résolution de certains problèmes de probabilités, Association Francaise pour l’Avancement des Sciences, Bordeaux 24 (1895), 70–90.

[9] E. Deutsch, Problem 10658, Amer. Math. Monthly 105 (1998), 366.

[10] A. Dvoretzky and T. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305–313.

[11] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58 (1985), 300–321.

[12] E. Goodman and T. V. Narayana, Lattice paths with diagonal steps, Canad. Math. Bull. 12 (1969), 847–855.

[13] I. P. Goulden and L. G. Serrano, Maintaining the spirit of the reflection principle when the boundary has arbitrary integer slope, J. Combin. Theory Ser. A 104 (2003), 317– 326.

[14] G. Hetyei, Central Delannoy numbers and balanced Cohen-Macaulay complexes, Ann. Comb. 10 (2006), 443–462.

[15] C. Krattenthaler, The enumeration of lattice paths with respect to their number of turns, in N. Balakrishnan, ed., Advances in Combinatorial Methods and Applications to Probability and Statistics Birkhäuser, 1997, pp. 29–58.

[16] C. Krattenthaler and R. A. Sulanke, Counting pairs of non-intersecting lattice paths with respect to weighted turns, Discrete Math. 153 (1996), 189–198.

[17] G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions de entiers, Thesis, Université Paris, 1965

[18] D. F. Lawden, On the solution of linear difference equations, Math. Gaz. 36 (1952) 193–196.

[19] S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.

[20] L. Moser, King paths on a chessboard, Math. Gaz. 39 (1955), 54.

[21] E. Pergola and R. A. Sulanke, Schröder triangles, paths, and parallelogram polyominoes, J. Integer Seq. 1 (1998), Article 98.1.7.

[22] G. N. Raney, Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451.

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

[24] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

[25] D. G. Rogers and L. W. Shapiro, Some correspondences involving the Schröder numbers and relations, in Comb. Math., Proc. of the Intern. Conf., Canberra 1977, Lecture Notes in Mathematics 686, Springer-Verlag, 1978, pp. 267–276.

[26] K. H. Rosen et al., eds., Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.

[27] E. Schröder, Vier combinatorische Probleme, Z. Math. Phys. 15 (1870), 361–376.

[28] J. Schröder, Filling boxes densely and disjointly, Comment. Math. Univ. Carolin. 44 (2003), 187–196.

[29] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/∼njas/sequences/.

[30] R. P. Stanley, Hipparchus, Plutarch, Schröder and Hough, Amer. Math. Monthly 104 (1997), 344–350.

[31] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

[32] R. A. Sulanke, A recurrence restricted by a diagonal condition: generalized Catalan arrays, Fibonacci Quart. 27 (1989), 33–46.

[33] R. A. Sulanke, Problem 10894, Amer. Math. Monthly 108 (2001), 770.

[34] R. A. Sulanke, Objects counted by the central Delannoy Numbers, J. Integer Seq. 6 (2003), Article 03.1.5.

[35] M. Vassilev and K. Atanassov, On Delanoy [!] numbers, Annuaire Univ. Sofia Fac. Math. Inform. 81 (1987), 153–162.

[36] H. S. Wilf, Generatingfunctionology, Academic Press, 1994.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 05A15, 05A19. Keywords: Delannoy numbers, Schröder numbers, royal path, king path, point lattice, integer slope, coordination sequence, crystal sphere, generating function, recursion, rotation principle, WZ-pair, NE-turn, up-right corner.

(Concerned with sequences \underline{A006318}, \underline{A006319}, \underline{A006320}, \underline{A006321}, \underline{A027307}, \underline{A032349}, \underline{A033296}, \underline{A033877}, \underline{A035597}, \underline{A035598}, \underline{A035599}, \underline{A035600}, \underline{A035601}, \underline{A035602}, \underline{A035603}, \underline{A035604}, \underline{A035605}, \underline{A035606}, \underline{A035607}, and \underline{A106579}.)

Received January 8 2007; revised version received May 8 2007; July 25 2007. Published in Journal of Integer Sequences, July 25 2007.

Return to Journal of Integer Sequences home page.