Lattice Paths between Diagonal Boundaries

Heinrich Niederhausen Department of Mathematical Sciences Florida Atlantic University, Boca Raton, FL 33431

Abstract

A bivariate symmetric backwards recursion is of the form d[m, n] = w_{0}(d[m− 1, n]+d[m, n−1])+ω_{1}(d[m−r_{1}, n−s_{1}]+d[m−s_{1}, n−r_{1}])+⋯+ω_{k}(d[m−r_{k}, n−s_{k}] + d[m − s_{k}, n − r_{k}]) where ω_{0}, … ω_{k} are weights, r_{1}, … r_{k} and s_{1}, … s_{k} are positive integers. We prove three theorems about solving symmetric backwards recursions restricted to the diagonal band x + u < y < x − l. With a solution we mean a formula that expresses d[m, n] as a sum of differences of recursions without the band restriction. Depending on the application, the boundary conditions can take different forms. The three theorems solve the following cases: d[x+u, x] = 0 for all x ≥ 0, and d[x−l, x] = 0 for all x ≥ l (applies to the exact distribution of the Kolmogorov-Smirnov two-sample statistic), d[x + u, x] = 0 for all x ≥ 0, and d[x − l + 1, x] = d[x − l + 1, x − 1] for x ≥ l (ordinary lattice paths with weighted left turns), and d[y, y − u + 1] = d[y − 1, y − u + 1] for all y ≥ u and d[x − l + 1, x] = d[x − l + 1, x − 1] for x ≥ l. The first theorem is a general form of what is commonly known as repeated application of the Reflection Principle. The second and third theorem are new; we apply them to lattice paths which in addition to the usual North and East steps also make two hook moves, East-North-North and North-East-East. Hook moves differ from knight moves (covered by the first theorem) by being blocked by any piece of the barrier they encounter along their three part move.

Submitted: September 9, 1997; Accepted: June 15, 1998 AMS Subject Classification: 0A15

1 Introduction

Finding the number of lattice paths inside a band can sometimes be achieved by solving a recursion with boundary conditions. The conditions do not only depend on the position of the band; it is also important how the paths interact with the boundaries. Suppose we want to count lattice paths which in addition to the unit steps upwards and to the right, → and ↑, can also make the two knight moves up-

right-right [figure]and right-up-up, [figure](vizier+knight moves). Formulas for the number of such symmetric moves restricted by boundaries parallel to the diagonal (diagonal boundaries) are elegantly derived by applying the Reflection Principle, if we assume that crossing a boundary means for a knight to start and end at different sides of a boundary. Reflection is more difficult if steps like the above knight moves cannot temporarily slide over the boundary during the move. We call such a move a hook;

the hooks [figure] and [figure] differ from the knight moves only when they encounter a barrier.

\begin{aligned}& ⊙ & & ■ \\ & & ■ \\ ⊗ & ■ \\ ■ \end{aligned}

no [figure] - move from ⊗ to ⊙

(1)

The recursion for calculating the number of paths is the same for both problems, but the initial values change. Instead of a diagonal line of zeroes along the boundary, we have to pick up values from the previous row – we call them recursive initial values (Section 2.5). Solving recursive initial value problems arising from a diagonal band is the main goal of this paper. However, I do not believe in pursuing a general method that will eventually cover all kinds of lattice path problems. Only one type of recursive initial values is considered in this paper; the approach can be modified to work with closely related problems.

1.1 Statement of Results

A board [d] = [d[m, n]]_{m,n≥0} is a matrix whose elements can be recursively calculated, except for certain initial values. We are primarily interested in d[m, n] for nonnegative integers m and n (the first quadrant, the board), but the recurrence relation may allow us to find entries for other quadrants. In that way we obtain an extended board [d[m, n]]_{m,n∈ℤ}, which we also call an extension array. The extended board follows the same recursion on ℤ^{2} as the original board on ℕ^{2}. A 0-left board can be calculated assuming that d[m, n] = 0 for negative n, and m ≥ 0.

In this paper we will use brackets for matrices; d[m, n] is the number of (restricted) paths from the origin to the lattice point (n, m). The indices are switched when we use n, m as Euclidean coordinates instead of row and column indices of a matrix.

Definition 1 Let r := {r_{k,1}, r_{k,2} | k = 1, …, ρ} be a finite set of ordered pairs with positive integer components. Together with a vector τ := (τ_{0}, τ_{1}, …, τ_{ρ}) of weights the set r defines a linear backwards recurrence relation (r, τ) on [d] via

d[m, n] = τ_{0}d[m − 1, n] + τ_{0}d[m, n − 1] + ∑_{k=1}^{ρ} τ_{k}d[m − r_{k,1}, n − r_{k,2}]

= (τ_{0}E_{1}^{−1} + τ_{0}E_{2}^{−1} + ∑_{k=1}^{ρ} τ_{k}E_{1}^{−r_{k,1}}E_{2}^{−r_{k,2}}) d[m, n]

for all d[m, n] which are not initial values. The recursion (r, τ) is symmetric, if for any k ∈ {1, …, ρ} either r_{k,1} = r_{k,2}, or there is a unique (r_{l,1}, r_{l,2}) such that r_{k,1} = r_{l,2} and r_{k,2} = r_{l,1} and τ_{k} = τ_{l}.

Note that the pairs (steps) (1, 0) and (0, 1) are special; they are the only steps that have a zero component. For the rest of this paper the word recursion will always mean backwards recursion, and all boards will be backwards recursive; we will not consider any others.

Definition 2 Let [d] be an extension array and a and integer. The translation operators E_{1}^{a} and E_{2}^{a} are defined by

E_{1}^{a}d[m, n] := d[m + a, n]
E_{2}^{a}d[m, n] := d[m, n + a]

for all integers m and n. The operators ∇_{1} := 1 − E_{1}^{−1} and ∇_{2} := 1 − E_{2}^{−1} are called backwards difference operators. If [d] is a 0-left board we write ∇_{2}^{−1} or \frac{1}{1−E_{2}^{−1}} for ∑_{j≥0} d[m, n − j] (see Section 2.5 for details).

For positive integers u and l, the lines y = x + u and y = x − l enclose a diagonal band of width u+l. The following three theorems show how to solve certain symmetric recursions, restricted to that band, under three different combinations of boundary conditions.

Theorem 3 (zeroes along both boundaries) Let u and l be positive integers, defining a diagonal band of width W = u + l. Suppose the 0-left board [v^{0}] follows a symmetric recursion, and has initial values

v^{0}[n − l, n] = 0 for n ≥ l.

Let [d] be a board for the same symmetric recursion which agrees with [v_{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, and satisfies the two diagonal boundary conditions

d[m, m − u] = 0 for all m ≥ u, d[n − l, n] = 0 for all n ≥ l.

Then [d] can be written as a sum of shifted and transposed [v^{0}] boards,

d[m, n] = \frac{1}{1 − E_{1}^{W} E_{2}^{−W}} v^{0}[m, n] − \frac{E_{1}^{u}E_{2}^{−u}}{1 − E_{1}^{W} E_{2}^{−W}} v^{0}[n, m].

The Theorem is proved in Section 3.

Theorem 4 (recusrsive initial values at the bottom) Let u and l be positive integers, defining a band of width W = u + l. Suppose the 0-left board [v^{0}] follows a symmetric recursion, has polynomial columns v^{0}[m, n] of degree n if m ≥ n, and satisfies the recursive initial conditions

v^{0}[n − l + 1, n] = v^{0}[n − l + 1, n − 1] for all n ≥ l.

If the board d[m, n] follows the same symmetric recursion, satisfies the boundary conditions

d[m, m − u] = 0 for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l,

and coincides with [v^{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, then [d] can be expanded as

d[m, n] = \frac{1}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} (v^{0}[m, n] − v^{0}[n + u, m − u]).

The proof will be given in Section 4.

Theorem 5 (recursive initial values along both boundaries) Let u and l be positive integers, defining an exterior band of width W := u + l, and an interior band width w := W − 2. Suppose the 0-left board [v^{0}] follows a symmetric recursion, has polynomial columns d[m, n] of degree n if m ≥ n, and satisfies the recursive initial conditions

v^{0}[n − l + 1, n] = v^{0}[n − l + 1, n − 1] for all n ≥ l

If the board d[m, n] follows the same symmetric recursion, satisfies the boundary conditions

d[m, m − u + 1] = d[m − 1, m − u + 1] for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l,

and coincides with [v^{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, then [d] can be expanded as

d[m, n] = \frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (v^{0}[m, n] − ∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1]) .

See Section 5 for the proof.

The binomial coefficient \binom{n}{k} will frequently occur when the above Theorems are applied. It is usually obvious from the context when \binom{n}{k} has to be interpreted as 0 for negative n. In a few instances, however, we find it necessary to reinforce this convention by writing \binom{n}{k}_{+}.

1.2 Examples

In Section 2 we develop some very elementary algebraic operations on boards that mimic the Reflection Principle. Most examples which we will use later are introduced in that section. The following table is an index to formulas occurring in the examples.

Equation #  barrier
and symbol Steps Name lower upper
(10) \left[{ \atop P̂}\right] →, ↑  ordinary path, vizier zeroes
(21)  moves  zeroes  zeroes
(22)  – given initial values zeroes  zeroes
(5)  [N] [figure], [figure]  knight moves  unrestricted
(11) [N̂]  zeroes
(23)  zeroes  zeroes
(5)  [H] [figure], [figure]  hook moves  unrestricted
(12) [Ĥ]  zeroes
(24)  zeroes  zeroes
(3)  [S] →, ↑, ↗  king moves  unrestricted
(9)  [Ŝ]  Schröder path  zeroes
(13)  zeroes
(20)  zeroes  zeroes
(7)  →, ↑, → μ^{↑}  ordinary path  unrestricted
(14)  with μ-weighted  zeroes
(16)  left turns  recursive
(30)  recursive zeroes
(4)  →, ↑, [figure], [figure]  vizier+knight moves  unrestricted
(31)  →, ↑,[figure], [figure]  vizier+hook moves recursive recursive
or →, ↑, [figure], [figure]
(17)  →, ↑, [figure], [figure]  vizier+knight+hook recursive
(29)  or →, ↑, [figure], [figure]  recursive zeroes
(2)  [K] →, ↑, ↗, [figure], [figure] king+knight  unrestricted
(8)  [K̂]  moves  zeroes
(19)  zeroes  zeroes

1.3 Notes

There is no universally accepted catalog for naming lattice paths. Fairy Chess [2] is better regulated, and can serve as a reference for certain “unusual” moves. However, all step vectors in this paper have only nonnegative components, and therefore take only half of the possible moves of the corresponding fairy chess piece. Hence, a vizier (arabic wazir) moves → and ↑, a king moves →, ↑ and ↗, etc. Ordinary lattice paths that stay above the diagonal are often called ballot paths. A ballot path that ends on the diagonal is a Catalan path or (rotated) Dyck path [8]. A generalized ballot path with steps →, ↑ and ↗ (king moves) is also called a Schröder path [14], [16].

The number of ordinary paths (10) above (or below) a diagonal boundary is usually attributed to André [1]. Takács [17] gives an excellent review of the history of lattice path counting. André does not use the Reflection Principle in his paper. The principle appears to be much older, and is sometimes referred to as d’Alembert’s Reflection Principle in Physics. For example, it has been used by Marjan Smoluchowski^{1} [15, p. 419 - 421] in 1913 to find the distribution of Brownian motion between parallel reflecting walls, a continuous version equivalent to the asymptotic distribution of the Kolmogorov-Smirnov test. The exact number of ordinary paths between diagonal bounds, (21), appears much later in a paper by Koroljuk [5] in 1955 (centered band), and Fray and Roselle [3] in 1971 (general case). S. G. Mohanty’s book is a general reference to Lattice Path Counting and Applications [9]. C. Jordan’s book Calculus of Finite Differences [4] is a classical reference to the power of differencing.

A survey on the enumeration of lattice paths with weighted turns can be found in [6], which contains proofs based on two-row arrays for (14) and (16). For polynomial enumeration by turns of lattice paths above or below non-diagonal lines see [10].

I want to thank the referee for the careful reading of this paper, and the many insightful comments, which led to substantial improvements.

2 Recursive Boards

Recursive boards are very simple mathematical objects. Still we found it beneficial to get a better understanding of the role of initial values. In the next two subsections we provide some technical lemmas which are necessary for the following sections, but could be skipped on first reading.

2.1 Initial Values and Extensions

Definition 6 The row-depth d_{row} of the recursion r is the max {1, r_{1,1}, r_{2,1}, …, r_{ρ,1}}. The column depth d_{col} is analogously defined.

In an extended (r, τ)-board [d] every element d[m, n] is determined by the elements below and to the left. If we calculate the board column by column, we need a border of d_{col} initial left columns , and an initial value in all other columns to fill the table recursively.

Frequently it is assumed that d[m, n] = 0 for negative n (or m), cutting down on the number of initial values on the board. A 0-left board can be calculated assuming that d[m, n] = 0 for negative n, and m ≥ 0; in a 0-bottom board d[m, n] = 0 for negative m, and n ≥ 0.

1I am indebted to L. Takács for this reference.

3  0 0 0 * * * *
2  0 0 0 * * * *
1  0 0 0 * * * *
0  0 0 0 * * * *

-1

-2 ? ?

-3

{m↑ \atop n→} -3 -2 -1 0 1 2 3

A 0-left board

We call [b[m, n]]_{m,n∈ℤ} an extension array of the board [d] if both agree in the first quadrant. The board [d] and an extension array [b] follow the same recursion, but extensions are not unique.

Lemma 7 Suppose [a] and [b] are extended boards which follow the same recursion.

(Column version:) If [a] and [b] agree in d_{col} columns and in at least one entry in every column to the right, then they are identical everywhere to the right of the given d_{col} columns.

(Row version:) If [a] and [b] agree in d_{row} rows and in at least one entry in every row above, then they are identical everywhere above the given d_{row} rows.

Proof. Without loss of generality we can assume that the arrays agree in column 0, …, d_{col}−1, and that for some N ≥ d_{col} holds a[m, k] = b[m, k] for all k = 0, …, N − 1, and all integers m. If τ_{0} = 0 then column N is a sum of entries from previous columns, and the lemma is trivial. Suppose τ_{0} ≠ 0. We know that the array d[m, n] := a[m, n] − b[m, n] has a zero entry in every column. Suppose, d[M, N] = 0. From

d[M, N] = τ_{0}d[M − 1, N] + τ_{0}d[M, N − 1] + ∑_{j=1}^{ρ} τ_{j}d[M − r_{j,1}, N − r_{j,2}]
= τ_{0}d[M − 1, N]

follows by induction that d[m, N] = 0 for all m ≤ N. In the same way we find that d[M + 1, N] = τ_{0}d[M, N], and by induction d[m, N] = 0 for all m > N.

Note: It is essential for the above proof that r_{2,j} > 0 for all j.

0-left and 0-bottom boards will play a major role in the following. In general, there is more than one extension of a given board. However, there is a “canonical” extension for certain boards.

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 2, n − 1] + d[m − 2, n − 2]

\begin{matrix}2 & 0 & 0 & 0 & 0 & 1 & 4 & 9 & 15 & 22 \\ 1 & 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -2 & 0 & 0 & 0 & 1 & -1 & 1 & -1 & 1 & -1 \\ -3 & 0 & 0 & -1 & 2 & -3 & 4 & -5 & 6 & -7 \\ -4 & 0 & 1 & -2 & 3 & -5 & 8 & -12 & 17 & -23 \\ {m↑ \atop n→} & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{matrix}  0 0 0 0 1 4 9 15 0 0 0 0 1 2 3 4 0 0 0 0 1 1 1 1 1 -1 1 -1 1 -1 1 -1 -2 1 0 0 1 -2 3 -4 5 -3 1 0 0 -1 3 -6 -2 0 0 1 -3 5 -6 5 -4 -3 -2 -1 0 1 2 3

Canonical Extension  Noncanonical Extension

The canonical row extension produces the largest amount of leading zeroes, row by row. The following Theorem is peripheral to the topic of this paper, and we omit the proof.

Theorem 8 A 0-left board [d] can be extended with leading zeroes: In every row m there is an index k_{m} such that d[m, n] = 0 for all n < k_{m}.

Analogously, there exists a canonical column extension for 0-bottom boards.

Example 9 (King+Knight) The weighted number K[m, n] of moves of the

king+knight combination →, ↑, ↗, [figure], [figure]is given by the recurrence relation ({(1, 1), (1, 2), (2, 1)} , (τ_{0}, κ, ν, ν))

K[m, n] = τ_{0}K[m − 1, n] + τ_{0}K[m, n − 1] + κK[m − 1, n − 1]
+ ν(K[m − 1, n − 2] + K[m − 2, n − 1])

and the initial conditions K[0, n] = K[m, 0] = 1, K[−1, n] = K[m, −1] = 0 for nonnegative integers m and n. We have ρ = 3 and d_{row} = 2. The forward recursion is νK[m, n] = K[m + 2, n + 1] − τ_{0}K[m + 1, n + 1] − τ_{0}K[m + 2, n] − κK[m + 1, n] − νK[m + 1, n − 1].

K[m, n] = K[m − 1, n] + K[m, n − 1] + κK[m − 1, n − 1] +ν(K[m − 1, n − 2] + K[m − 2, n − 1])

3 … 0  0  0  1  4 + 3κ + 2ν 10 + ⋯ + 9ν
2 … 0  0  0  1  3 + 2κ + ν 6 + ⋯ + 4ν
1 … 0  0  0  1  2 + κ  3 + 2κ + ν
0 … 0  0  0  1  1  1
−1 … 0  0  0  0  0  0
−2 … 0  0  1/ν  0  0  0
−3 … 0  −ν^{−2}  −κν^{−2}  −ν^{−1}  0  0
−4 … ν^{−3} ν^{−2} + 2κν^{−3} κ^{2}ν^{−3} + ν^{−2} 2κν^{−2}  ν^{−1}  0
⋮ … ⋮  ⋮  ⋮  ⋮  ⋮  ⋮
{m↑ \atop n→} … −3  −2  −1  0  1  2

It follows from elementary counting arguments that there are

K[m, n] = ∑_{i,j,k≥0} τ_{0}^{m+n−2k−3i−3j}κ^{k}ν^{i+j}\binom{m + n − k − 2i − 2j}{k, i, j, m − k − 2i − j, n − k − i − 2j} (2)

possible moves to reach (n, m) from (0, 0). The summation runs over all indices that result in nonnegative arguments of the multinomial coefficients. If we let ν = 0 and τ_{0} = 1 we obtain the number S[m, n] of (directed) king moves,

S[m, n] = ∑_{k≥0} κ^{k}\binom{m + n − k}{k, m − k, n − k}.  (3)

Without the diagonal steps (κ = 0) the king+knight moves become vizier+knight moves. Their weighted count is

∑_{s≥0} τ_{0}^{m+n−3s}ν^{s} ∑_{i≥0} \binom{m + n − 2s}{i, s − i, m − s − i, n − 2s + i}

= ∑_{s≥0} τ_{0}^{m+n−3s}ν^{s}\binom{m + n − 2s}{m − s} ∑_{i≥0} \binom{m − s}{i}\binom{n − s}{s − i}

= ∑_{s≥0} τ_{0}^{m+n−3s}ν^{s}\binom{m + n − 2s}{m − s}\binom{m + n − 2s}{s}_{+}.  (4)

If there are no barriers, knight moves [figure], [figure], and hook moves [figure], [figure]are counted the same way. We get the number of such moves from (4) if τ_{0} = 0,

ν^{(m+n)/3}\binom{(m + n)/3}{(2n − m)/3}  (5)

for m ≤ 2n ≤ 4m and m + n divisible by 3.

d[m, n] = d[m − 1, n − 2] + d[m − 2, n − 1]
7  4  10
6  1  6  5
5  3  4
4  1  3  1
3  2  1
2  1  1
1  1
0 1
{m↑ \atop n→} 0 1 2 3 4 5 6 7 8 9

The knight board [N] and hook board [H] are isomorphic to the ordinary lattice paths board [P] (“Pascal’s triangle”) where P [i, j] = N[2i + j, 2j + i] = H[2i + j, 2j + i] = \binom{i+j}{i}.

Lemma 10 Let c be a nonnegative integer. If the 0-left board [t] has a constant first column above c, t[m, 0] constant for all m ≥ c, then the board [a] with entries

a[m, n] = t[m + c + 1, n + 1] − t[m + c, n + 1]
= ∇_{1}t[m + c + 1, n + 1]

is a 0-left board following the same recursion as [t].

A row version of the above Lemma follows from transposition of [t] and [a].

Proof. Because of linearity, [a] follows the same recursion as [t]. Let m ≥ 0. If n < −1 then t[m + c + 1, n + 1] and t[m + c, n + 1] are both zero, and so is a[m, n]. If n = −1 then

a[m, −1] = t[m + c + 1, 0] − t[m + c, 0] = 0.

Lemma 11 Suppose, [a] and [b] are (r, τ)-boards with initial conditions a[m_{n}, n] = α_{n} and b[m_{n+c}, n] = β_{n}, where c and m_{n} are non-negative integers, α_{n} and β_{n} are initial values, n = 0, 1, … (β_{n} = 0 for negative n). If [b] is a 0-left board then d[m, n] := a[m, n] + b[m, n − c] is an (r, τ)-board with initial conditions d[m_{n}, n] = α_{n} + β_{n−c} for all n ≥ 0, coinciding with a[m, n] for the first c columns.

Proof. The linearity of the recurrence implies that d[m, n] follows the same recurrence as [a] and [b]. Because of b[m, n − c] = 0 for m ≥ 0, n < c, we get d[m, n] = a[m, n] for those columns.

The “row version” of the above Lemma follows.

Lemma 12 Suppose, [a] and [b] are (r, τ)-boards with initial conditions a[m, n_{m}] = α_{m} and b[m, n_{m+c}] = β_{m}, where c and n_{m} are non-negative integers, α_{m} and β_{m} are initial values, m = 0, 1, … (β_{m} = 0 for negative m). If [b] is a 0-bottom board then d[m, n] := a[m, n] + b[m − c, n] is an (r, τ)-board with initial conditions d[m, n_{m}] = α_{m} + β_{m−c} for all m ≥ 0, coinciding with a[m, n] for the first c rows.

2.2 Eventually Polynomial Boards

Polynomials can be a great tool for handling certain two dimensional recursions under side conditions, because the calculus of polynomials is well developed. Unfortunately there are already very elementary problems which do not give rise to polynomials, as in the following example of vizier+knight moves. Both tables show the number of paths from (0, 0) to (n, m) for the same recursion, but under different initial conditions.

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 2, n − 1] + d[m − 1, n − 2]

\begin{matrix}5 & 1 & 10 & 49 & 170 & 474 & 1136 \\ 4 & 1 & 8 & 32 & 94 & 226 & 474 \\ 3 & 1 & 6 & 19 & 46 & 94 & 170 \\ 2 & 1 & 4 & 10 & 19 & 32 & 49 \\ 1 & 1 & 2 & 4 & 6 & 8 & 10 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {m↑ \atop n→} & 0 & 1 & 2 & 3 & 4 & 5 \end{matrix}  \begin{matrix}5 & 1 & 8 & 27 & 56 & 70 & 0 \\ 4 & 1 & 6 & 14 & 18 & 0 & −71 \\ 3 & 1 & 4 & 5 & 0 & −17 & −62 \\ 2 & 1 & 2 & 0 & −6 & −9 & −51 \\ 1 & 1 & 0 & −1 & −8 & 12 & … \\ 0 & 1 & −2 & 2 & −14 & … & … \\ {m↑ \atop n→} & 0 & 1 & 2 & 3 & 4 & 5 \end{matrix}

Neither row nor column polynomials Columns are polynomials of degree n

In both tables we start with d[m, 0] = 1, and d[m, −1] = 0 for m ≥ 0. In the first table we let d[1, n] = 1 and d[−1, n] = 0 for n ≥ 0, which gives us the “unrestricted” vizier+knight moves. The n-th column in that table is obviously not obtainable in the form d[m, n] = d_{n}(m), where d_{n} is a polynomial of degree n. This is the case for the table to the right, where we required the initial values d[n, n] = δ_{0,n}, counting the number of paths staying strictly above the diagonal after their start at the origin. In order for the column polynomials to appear we have to extend the initial conditions d[m, 0] = 1, and d[m, −1] = 0 to negative values of m.

A formula for the entries in the left table can be found by elementary combinatorial arguments. The polynomials in the right table are easily constructed by algebraic methods like the Umbral Calculus [11],

d[m, n] = d_{n}(m) = ∑_{l=0}^{n} \frac{m − n}{n − 2l + m}\binom{n − 2l + m}{l}\binom{n − 2l + m}{n − l}.

This paper is about non-polynomials tables. In the last two sections, however, we need the assumptions that the columns are (eventually) polynomial above the diagonal, as it is the case in the left table.

The backwards difference operator ∇ lowers the degree of any polynomial by 1. Therefore, the differencing of 0-left (0-bottom) boards in Lemma 10 can be repeated, if the columns (rows) d[m, n] are polynomials of degree n (m). A slightly stronger result can be shown.

Corollary 13 Let c be a nonnegative integer. Suppose that the columns t[m, n] of the 0-left board [t] are values of polynomials of degree n for m ≥ n + c, and that t[m, 0] ≠ 0 for m ≥ c. For all k ≥ 0, [∇_{1}^{k}t[m + k + c, n + k]]_{m,n≥0} is a 0-left board where the columns ∇_{1}^{k}t[m + k + c, n + k] are values of polynomials of degree n for all m ≥ n, with constant nonzero first column.

There is of course also a row version of this corollary, by transposition of the board [t].

Proof. The statement is true for k = 0. Suppose it holds for some k − 1 ≥ 0. Let a[m, n] := ∇_{1}^{k−1}t[m + k − 1 + c, n + k − 1]. By Lemma 10, ∇_{1}^{k}t[m + k + c, n + k] = ∇_{1}a[m + 1, n + 1] is a 0-left board. By induction, the columns a[m, n + 1] are polynomials of degree n + 1 for m ≥ n + 1. Hence, the columns of ∇_{1}a[m + 1, n + 1] are values of polynomials of degree n for m ≥ n + 1. The first column is a nonzero constant because it is the backwards difference of a polynomial of degree 1.

2.3 Symmetric Backwards Recursions

For symmetric backwards recursions (r, τ) holds

∑_{k=1}^{ρ} τ_{k}d[m − r_{k,1}, n − r_{k,2}] = ∑_{k=1}^{ρ} τ_{k}d[m − r_{k,2}, n − r_{k,1}]  (6)

(see Definition 1). Note that symmetry of the recursion does not imply symmetry of the board! The latter will depend on the choice of initial values.

Example 14 (weighted left turns) The recursion ((1, 1) , (1, γ)) occurs in the enumeration of lattice paths, d[m, n] = d[m − 1, n] + d[m, n − 1] + γd[m − 1, n − 1]. The paths take horizontal, vertical, and diagonal steps (a king). If we write γ = μ − 1, then this recurrence enumerates lattice paths with horizontal (East → direction) and

vertical (North ↑) unit steps, where the left turns → ∘^{↑} have weight μ.

↑
∘ → ∘ → ∘ → μ
↑
→ μ

Lattice Path with Weight μ^{2}

By elementary counting arguments one finds the total weight

d[m, n] = ∑_{d≥0} \binom{m}{d}\binom{n}{d}μ^{d}  (7)

of all paths reaching the point (n, m). This board has both polynomial columns and polynomial rows, and they are equal by symmetry.

2.4 Initial Zeroes along a Barrier

Suppose we want to count the number of some kind of paths from (0, 0) to (n, m) which stay strictly above the boundary y = x − c. For ordinary lattice paths this problem is usually solved by applying the Reflection Principle. In the language of recursions the ‘mirror’ is a boundary of initial values which are zero.

Lemma 15 Suppose, [a] is a 0-bottom board for a symmetric recursion, and c is some positive integer constant. Then

d[m, n] := a[m, n] − a[n − c, m + c]

is the board for the same recursion with boundary values d[n − c, n] = 0 for all n ≥ c.

Proof. It is straightforward to check that [d] has the required boundary values. Let (r, τ) denote the recursion. Because of symmetry, both a[m, n] and a[n, m] are (r, τ)-recursive. By linearity, [d] is also (r, τ)-recursive.

The above Lemma has to be applied with caution to enumeration problems. It must be carefully checked whether the condition d[n − c, n] = 0 really suffices to describe the effect of the lower boundary. For a counter example see Section 2.5.

Example 16 (asymmetric board) Lemma 15 does not require that the board [a] must be symmetric - only the recursion needs symmetry. Here is an example for an unsymmetrical 0-bottom board satisfying d[m, n] = d[m − 1, n] + d[m, n − 1] and the boundary condition d[n − 2, n] = 0.

d[m, n] = d[m − 1, n] + d[m, n − 1]

\begin{matrix}5 & ? & 11 & 29 & 68 − 1 & 143 − 9 & 275 − 45 & 492 − 396 \\ 4 & ? & 7 & 18 & 39 − 1 & 75 − 8 & 132 − 36 & 217 − 121 \\ 3 & ? & 5 & 11 & 21 − 1 & 36 − 7 & 57 − 28 & 85 − 85 \\ 2 & ? & 3 & 6 & 10 − 1 & 15 − 6 & 21 − 21 & 28 − 57 \\ 1 & ? & 2 & 3 & 4 − 1 & 5 − 5 & 6 − 15 & 7 − 36 \\ 0 & ? & 1 & 1 & 1 − 1 & 1 − 4 & 1 − 10 & 1 − 21 \\ −1 & ? & 0 & 0 & 0 − 1 & 0 − 3 & 0 − 6 & 0 − 11 \\ {m↑ \atop n→} & −1 & 0 & 1 & 2 & 3 & 4 & 5 \end{matrix}

Oridinary paths above y = x − 2 when column 0 lists all primes

The board [d] above is explicitly written in the form a[m, n]−a[n−2, m+2], displaying [a] as the nonnegative entries in the table. The board [a] is easy to find if we have a table of primes to determine a[i, 0], because

a[m, n] = ∑_{i=0}^{m} a[i, 0]\binom{m + n − i − 1}{m − i}

(by combinatorial arguments or calculus of differences [4]).

Example 17 (king+knight) In example 9 we investigated the king+knight moves

→, ↑, ↗, [figure], [figure]. The symmetric board [K] can be either extended to a 0-left or to a 0-bottom array. In the board K̂ we want to force all king+knight positions to stay above the line y = x − l, where l is a positive integer. For calculating K̂ we need more assumptions about the nature of the knight moves than what is expressed in the recursion. The knights can jump over the border as long as they start and end above the barrier. The initial values K̂[m, n] = K[m, n] for all integers m and n = l − 1, l, and K̂[n − l, n] = 0 for n ≥ l uniquely determine the solution (by Lemma 7).

\begin{matrix}3 & 1 & 4 + 3κ + 2ν & 9 + 12κ + 3κ^{2} + 2κν + 9ν & 14 + ⋯ + 2ν^{2} & … \\ 2 & 1 & 3 + 2κ + ν & 5 + 6κ + κ^{2} + 4ν & 5 + ⋯ + 6ν & 0 \\ 1 & 1 & 2 + κ & 2 + 2κ + ν & 0 & −4 ⋯ − 6ν \\ 0 & 1 & 1 & 0 & −2 − 2κ − ν & −5 ⋯ − 4ν \\ {m↑ \atop n→} & 0 & 1 & l = 2 & 3 & 4 \end{matrix}

The number of such moves (with τ_{0} = 1) to (n, m) is according to Lemma 15

K̂[m, n] = K[m, n] − K[n − l, m + l]  (8)

= ∑_{i,j,k≥0} κ^{k}ν^{i+j}\binom{m + n − k − 2i − 2j}{k, i, j, m + n − 2k − 3i − 3j} ×

(\binom{m + n − 2k − 3i − 3j}{m − k − 2i − j}_{+} − \binom{m + n − 2k − 3i − 3j}{m + l − k − 2i − j}_{+})

If we eliminate the knight moves (ν = 0) we obtain

Ŝ[m, n] = ∑_{k≥0} κ^{k}\binom{m + n − k}{k} (\binom{m + n − 2k}{m − k}_{+} − \binom{m + n − 2k}{m + l − k}_{+})  (9)

king moves (→, ↑, ↗) strictly above the line y = x − l. We obtain the classical Ballot numbers if we also set γ = 0;

P̂[m, n] − P̂[n − l, m + l] = \binom{m + n}{m} − \binom{m + n}{m + l}  (10)

is the number of →, ↑-paths strictly above y = x − l.

Example 18 (knights) The pure knight moves [figure], [figure]are similar to ordinary lattice paths (see (5)). Lemma 15 tells us that the number N̂[m, n] of knight moves to [m, n] staying above the boundary y = x − l is given by

N̂[m, n] = N[m, n] − N[n − l, m + l] = \binom{(m + n)/3}{(2n − m)/3} − \binom{(m + n)/3}{(2n − m − 3l)/3} (11)

for n − l < m ≤ 2n ≤ 4m and m + n divisible by 3.

N̂[m, n] = N̂[m − 1, n − 2] + N̂[m − 2, n − 1]
7  4  5 □
6  1  5  □
5  3  0
4  1  2 □
3  2  □
2  1  0
1  1 □
0 1  □
{m↑ \atop n→} 0 1 l = 2 3 4 5 6 7 8 9

Example 19 (hooks) Every time a hook move ( [figure], [figure]) lands on a cell adjacent to the boundary y = x − l it has no further place to go. We can therefore replace the contents of such cells (framed in the table below) by zeroes, and count the knight moves above y > x − l + 1 instead, using formula (11).

Ĥ[m, n] = Ĥ[m − 1, n − 2] + Ĥ[m − 2, n − 1]
8  1  9  5
7  4  5  ■
6  1  5  ■
5  3  2 ■
4  1  2  ■
3  2  ■
2  1  1 ■
1  1  ■
0 1  ■
{m↑ \atop n→} 0 1 2 l 4 5 6 7 8 9 10
Ĥ[m, n] = \binom{\frac{1}{3}(m + n)}{\frac{1}{3}(2n − m)} − \binom{\frac{1}{3}(m + n)}{\frac{1}{3}(2n − m) − l + 1}  (12)

for n − l + 1 < m ≤ 2n ≤ 4m and m + n divisible by 3.

There is also a “row version” of the lemma 15 for 0-left boards [a] with symmetric recursions, i.e., d[m, n] := a[m, n] − a[n + c, n − c] is the array for the same recursion with boundary values d[m, m − c] = 0 for all m ≥ 0.

Example 20 (kings and left turns below barrier) The number of king moves strictly below the line y = x + u can be obtained from K[m, n] − K[n + u, m − u] with ν = 0,

∑_{k≥0} κ^{k}\binom{m + n − k}{k} (\binom{m + n − 2k}{m − k}_{+} − \binom{m + n − 2k}{m − u − k}_{+}) .  (13)

We saw in Example 14 that replacing κ by μ − 1 counts the ordinary →, ↑-paths with weighted left turns

∑_{k≥0}(μ − 1)^{k}\binom{m + n − k}{k} (\binom{m + n − 2k}{m − k}_{+} − \binom{m + n − 2k}{m − u − k}_{+}) .

Instead of expanding (μ − 1)^{k} we can apply the row version of Lemma 15 directly to (7) and get

∑_{d≥0} μ^{d} (\binom{m}{d}\binom{n}{d} − \binom{m − u}{d}\binom{n + u}{d}) .  (14)

This result is well known (see for example [6]). It follows that ∑_{k≥0} \binom{m−u}{k}\binom{n+u}{k}μ^{k} is the total weight of the paths from the origin that reach (n, m) after reaching the line y = x + u. However, we cannot specialize the result (9) for the number of king moves above y = x − l to weighted left turns, because the initial values d[n − l, n] = 0 are not valid for weighted left turns. Instead, we need the recursive initial condition d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l.

2.5 Recursive Initial Values along a Barrier

There are many situations when a lower boundary y = x − l cannot be described by 0 values along the barrier. In Example 17 we assumed that a knight can temporarily cross a barrier during a jump that starts and ends above the barrier. If such a temporary crossing is forbidden, the initial values d[n − l, n] = 0 for all n ≥ l must be replaced by complicated recursive initial values. Instead of trying a general approach covering a wide range of possible recursions on initial values, we investigate only one

special situation arising from the hook moves [figure]and [figure]. It is left to the reader to check how the method applies to different problems. The same kind of recursive initial values occur already in the easier problem of →, ↑-paths with weighted left turns, where a left turn is a right-up move that cannot touch the barrier y = x − l. It follows, that the position [n − l + 1, n] (right above the barrier) can only be reached from the left, and therefore d[n − l + 1, n] = d[n − l + 1, n − 1].

If [a] is a 0-bottom board and [b] is a 0-left board then the expressions

∑_{i≥0} E_{1}^{−i}a[m, n] = ∑_{i≥0} a[m − i, n] and ∑_{j≥0} E_{2}^{−j}b[m, n] = ∑_{j≥0} b[m, n − j]

are finite, and we write

∇_{1}^{−1}a[m, n] = \frac{1}{1 − E_{1}^{−1}} a[m, n] = ∑_{i≥0} E_{1}^{−i}a[m, n]

∇_{2}^{−1}b[m, n] = \frac{1}{1 − E_{2}^{−1}} b[m, n] = ∑_{j≥0} E_{2}^{−j}b[m, n].

Note that

∇_{1}∇_{1}^{−1}a[m, n] = a[m, n],

supporting the choice of notation.

Lemma 21 Suppose, [t] is a 0-bottom board for a symmetric recursion, with constant first row, and l is some positive integer constant. The board [d] which equals [t] for n = 0, …, l − 1 and satisfies the same recursion and the recursive initial conditions

d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l

can be expanded in terms of [t],

d[m, n] = t[m, n] − ∇_{1}^{−1}∇_{2}t[n − l + 1, m − 1 + l]

for all m, n ≥ 0.

Proof. It is straightforward to check that d[n, m] follows the recursion and satisfies the required boundary conditions. However, we want to show how to construct the answer. We start with an ‘Ansatz’ of the form

d[m, n] = t[m, n] − q[n − l, m − 1]

and try to determine the 0-bottom (r, τ)-array [q[m, n]], guaranteeing that [d] and [t] agree in the first l columns (the symmetry of (r, τ) is necessary so the right hand side of the above equation will follow the correct recursion). We first determine the difference w[m, n] := ∇_{1}q[m, n] which must have initial values

w[n, n] = q[n, n] − q[n − 1, n]

= t[n + 1, n + l] − d[n + 1, n + l] − t[n + 1, n + l − 1] + d[n + 1, n + l − 1]

= t[n + 1, n + l] − t[n + 1, n + l − 1].  (15)

[∇_{2}t[m + 1, n + l]]_{m,n≥0} is a 0-bottom board by Lemma 10, and has the required initial values (15). Therefore w[m, n] := ∇_{2}t[m + 1, n + l] for all m, n ≥ 0, and

q[m, n] = ∇_{1}^{−1}w[m, n] = ∇_{1}^{−1}∇_{2}t[m + 1, n + l].

Example 22 (left turns) As we already have pointed out, the μ-weighted left turns

→ ∘^{↑} cannot slide along the barrier y = x − l where l is a positive integer. The left turn recursion

t[m, n] = t[m − 1, n] + t[m, n − 1] + (μ − 1)t[m − 1, n − 1]

can be written as

μt[m − 1, n − 1] = ∇_{1}∇_{2}t[m, n],

which simplifies the application of Lemma 21:

d[m, n] = t[m, n] − ∇_{1}^{−1}∇_{2}t[n − l + 1, m − 1 + l]
= t[m, n] − ∇_{1}^{−1}∇_{2}∇_{1}∇_{2}t[n − l + 2, m + l]/μ
= t[m, n] − ∇_{2}^{2}t[n − l + 2, m + l]/μ.

Substitute

t[m, n] = ∑_{d≥0} \binom{m}{d}\binom{n}{d}μ^{d}

(see (7)) and get

d[m, n] = ∑_{d≥0} μ^{d} (\binom{m}{d}\binom{n}{d} − \binom{m − 2 + l}{d − 1}\binom{n − l + 2}{d + 1}_{+}) .  (16)

Two other proofs of this result can be found in [7].

Example 23 (vizier+knight+hook) The symmetric recursion ({(1, 2), (2, 1)} , (1, ν, ν)) is another subcase of the king+knight moves. Suppose, the

step (1, 2) belongs to the knight move [figure], but (2, 1) belongs to the hook move [figure] , unable to even temporarily cross the barrier y = x − l. The bold entries in the left table below are the recursive initial values d[n − l + 1, n] which are obtained from d[n − l + 1, n − 1]. The right table shows the king+knight moves for comparison.

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 2, n − 1] + d[m − 1, n − 2]

\begin{matrix}5 & 1 & 10 & 49 & 168 & 447 & 953 & 1570 \\ 4 & 1 & 8 & 32 & 92 & 203 & 339 & 339 \\ 3 & 1 & 6 & 19 & 44 & 75 & 75 & ■ \\ 2 & 1 & 4 & 10 & 17 & 17 & ■ \\ 1 & 1 & 2 & 4 & 4 & ■ \\ 0 & 1 & 1 & 1 & ■ \\ {m↑ \atop n→} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \end{matrix}  1 10 49 169 458 1012 1785 1 8 32 93 212 379 461 1 6 19 45 82 100 0 1 4 10 18 22 0 1 2 4 5  0 1 1 1 0 0 1 2 3 4 5  6

[figure] cannot jump over the barrier  The knights [figure], [figure]pass by the barrier

The unrestricted counts (see (4))

t[m, n] = ∑_{s≥0} τ_{0}^{m+n−3s}ν^{s}\binom{m + n − 2s}{m − s}\binom{m + n − 2s}{s}_{+}

are the same for hooks and knights. From Lemma 21 we get the following formula for the number of this kind of vizier+knight+hook moves above y = x − l

d[m, n] = t[m, n] − ∇_{1}^{−1}∇_{2} ∑_{k≥0} τ_{0}^{m+n−3k}ν^{k}\binom{m + n − 2k}{n − l + 1 − k}\binom{m + n − 2k}{k}_{+} (17)

for m > n − l + 1.

Suppose, b[m, n] is the number of vizier+knight+hook moves with steps →, ↑, [figure], and [figure]from (0, 0) to (n, m) staying strictly above y = x − l. It is easy to verify that b[m, n] is also given by (17) for m > n − l + 1, and b[n − l + 1, n] = b[n − l + 1, n − 1] + b[n − l, n − 2].

3 Two Barriers of Zeroes

Frequently, the problem of finding the number of paths inside a diagonal band can be formulated as a boundary value problem with zeroes on both diagonal boundaries. D’Alembert’s Reflection Principle has been successfully applied to such pairs of boundaries; however in view of the next section we want to show how an ‘inclusionexclusion’ of boards can be used to prove Theorem 3 in Section 1.1. The Reflection Principle is implicitly still present, in the form of transposition of boards.

7  0  0
6  0  0
5  0  0
4  0  0
u 0  0
2  0
1  0
0  0
{m↑ \atop n→} 0 1 2 3 4 l 6 7 W 9 10 11 12

Boundaries represented by zeroes

For easier reference, we state Theorem 3 again, in an equivalent formulation.

Let u and l be positive integers, defining a diagonal band of width W = u + l. Suppose the 0-left board [v^{0}] follows a symmetric recursion, and has initial values

v^{0}[n − l, n] = 0 for n ≥ l.

Let [d] be a board for the same symmetric recursion which agrees with [v_{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, and satisfies the two diagonal boundary conditions

d[m, m − u] = 0 for all m ≥ u, d[n − l, n] = 0 for all n ≥ l.

Then [d] can be written as an alternating sum of shifted and transposed [v^{0}] boards,

d[m, n] = ∑_{i≥0} (v^{0}[m + iW, n − iW] − v^{0}[n + u + iW, m − u − iW])

Proof of Theorem 3. The following proof contains more details than absolute necessary, because it serves as a model for the proof of Theorem 4 and Theorem 5 where the technical details are less transparent. Let (r, τ) denote the symmetric recursion. The board [d] is obtained from an “inclusion – exclusion” of (r, τ)- boards, v^{0} − h^{0} + v^{1} − h^{1} + …, which is schematically presented in the picture below.

0

u + 3W 0 −h^{3}
16  0
15  0  v^{3}
14  0  0
13  0  0
u + 2W  0  −h^{2}  0
11  0  0
10  0  v^{2}  0
9  0  0
8  0  0
u + W  0  −h^{1}  0
6  0  0
5  0  v^{1}  0
4  0  0
3  0 −h^{0}  0
u  0  0
1  0
0 v^{0} 0
{m↑ \atop n→}  0 1 2 l 4 W 6 7 8 9 2W 11 12 13 14 3W 16

The partial sums of this series are a sequence of approximating boards

\left[{ \atop d̂^{0}}\right] , [d^{0}] , \left[{ \atop d̂^{1}}\right] , [d^{1}] , …

where \left[{ \atop d̂^{k}}\right] agrees with [d] inside the rectangle 0 ≤ m < u + kW, 0 ≤ n < (k + 1)W,

and satisfies the initial condition d̂^{k}[n − l, n] for all n ≥ l. Each [d^{k}] agrees with [d] inside the rectangle 0 ≤ m < u + (k + 1)W, 0 ≤ n < (k + 1)W, and satisfies the initial condition d^{k}[m, m − u] for all m ≥ u.

d̂^{0}[m, n] = v^{0}[m, n] for 0 ≤ m < u and 0 ≤ n < W
u ? ? ? ? ? ? ? ? 0
2  0 ?
1  v^{0}[m, m]  0  ?
0  0  ?
{m↑ \atop n→} 0 1 2 3 4 l 6 7 W  …

Starting the construction

We begin with the (r, τ)-board \left[{ \atop d̂^{0}}\right] := [v^{0}]. Inside the rectangle 0 ≤ m < u and

0 ≤ n < W we have d̂_{0}[m, n] = d[m, n], and for all n ≥ l holds d̂^{0}[n − l, n] = 0. Let h^{0}[m, n] := v^{0}[n + u, m]. The board [h^{0}] is 0-bottom extendable, because [v^{0}] is a 0-left board. The board with entries

d^{0}[m, n] := d̂_{0}[m, n] − h^{0}[m − u, n]

equals 0 on the boundary m = n + u for all m ≥ u,

d^{0}[m, m − u] = d̂_{0}[m, m − u] − h^{0}[m − u, m − u] = v^{0}[m, m − u] − v^{0}[m, m − u] = 0,

and is (r, τ)-recursive because of Lemma 12. Therefore, d[m, n] = d^{0}[m, n] inside the rectangle 0 ≤ m < u + W, 0 ≤ n < W.

d^{0}[m, n] = v^{0}[m, n] − h^{0}[m − u, n]
for 0 ≤ m < u + W, 0 ≤ n < W
u + W ? ? ? ? ? ? ? ? 0
10  0 ?
9  0  ?
8  0  ?
7  0  ?
6  0  ?
5  0  ?
4  0  −h^{0}[m − u, n] ?
u  0  ?
2  0 ?
1  v^{0}[n, m]  0  ?
0  0  ?
{m↑ \atop n→}  0 1 2 3 4 l 6 7 W

For n ≥ W the lower boundary values

d^{0}[n − l, n] = d̂_{0}[n − l, n] − h^{0}[n − l − u, n] = 0 − h^{0}(n − l − u, n)

are no longer 0 in general. We correct that in the next step. Let v^{1}[m, n] := h^{0}[n, m+ l]. The board [v^{1}] is 0-left extendable, because we have switched row and column indices again. h^{0}[m − u, n] − v^{1}[m, n − W] vanishes on the boundary x = y + l,

h^{0}[n − l − u, n] − v^{1}[n − l, n − W] = h^{0}[n − l − u, n] − h^{0}[n − l − u, n] = 0

for all n ≥ 0. This together with Lemma 11 shows that

d̂^{1}[m, n] := d^{0}[m, n] + v^{1}[m, n − W]

agrees with [d] in the rectangle 0 ≤ m < u + W, 0 ≤ n < 2W, and vanishes along the lower boundary.

d̂^{1}[m, n] = v^{0}[m, n] − h^{0}[m − u, n] + v^{1}[m, n − W]
for 0 ≤ m < u + W, 0 ≤ n < 2W
u + W ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0
10  0  0 ?
9  0  0  ?
8  0  +v^{1}[m, n − W]  0  ?
7  0  0  ?
6  0  0  ?
5  0  0  ?
4  0  −h^{0}[m − u, n]  0  ?
u  0  0  ?
2  0  ?
1  v^{0}[n, m]  0  ?
0  0  ?
{m↑ \atop n→}  0 1 2 3 4 l 6 7 W 9 10 11 12 13 14 15 2W

The entries in the top row will be determined in the next step We have enlarged both sides of the original rectangle 0 ≤ m < u + 0 · W, 0 ≤

n < 1 · W by W, to the new rectangle 0 ≤ m < u + 1 · W, 0 ≤ n < 2 · W. This construction can be repeated indefinitely: If we define h^{k}[m, n] := v^{k}[n + u, m] and v^{k}[m, n] := h^{k−1}[n, m + l] then

d^{k}[m, n] = d̂^{k}[m, n] − h^{k}[m − u, n]
= d^{k−1}[m, n] + v^{k}[m, n − w] − h^{k}[m − u, n]
= ∑_{i=0}^{k} (v^{i}[m, n − iW] − h^{i}[m − u − iW, n])  (18)

agrees with d[m, n] inside the rectangle 0 ≤ m < u + (k + 1)W, 0 ≤ n < (k + 1)W. The recursion

v^{k}[m, n − kW] = h^{k−1}[n − kW, m + l] = v^{k−1}[m + W, n − kW]
= ⋯ = v^{0}[m + kW, n − kW]

finishes the proof.

In the few cases where lattice paths between diagonal boundaries of zeroes have been counted in the literature, the summation in Theorem 3 is usually written as a sum over all integers. This is possible if d[m, n] is assumed to be zero for m < 0, 0 ≤ n < l, and 0 ≤ m < u, n < 0.

Corollary 24 Let u and l be positive integers, defining a band of width W := u + l. Suppose, [d] follows a symmetric recursion and satisfies the two diagonal boundary conditions

d[m, m − u] = 0 for all m ≥ u, d[n − l, n] = 0 for all n ≥ l.

Let [a] be a symmetric board for the same recursion that can be extended to a 0-left board. If d[m, n] = a[m, n] on the rectangle 0 ≤ m < u, 0 ≤ n < l then it can be expanded for 0 ≤ n − l ≤ m ≤ n + u as

d[m, n] = ∑_{s∈ℤ}(a[m + sW, n − sW]_{+} − a[m + sW + l, n − sW − l]_{+})

where a[j, i]_{+} = 0 for negative i or j.

Proof. Because [a] is a symmetric, it also has an extension to a 0-bottom board which we call [a′]; we denote the 0-left extension again by [a]. Both extensions agree in the first quadrant. A slight generalization of Lemma 15 shows that

v^{0}[m, n] := a[m, n] − a′[n − l, m + l]

can serve as the 0-left board in Theorem 3. On the first quadrant holds v^{0}[m, n] = (1 − E_{1}^{l}E_{2}^{−l})a[m, n] by symmetry. According to Theorem 3, d[m, n] equals

\frac{1 − E_{1}^{l}E_{2}^{−l}}{1 − E_{1}^{W} E_{2}^{−W}} a[m, n] − \frac{E_{1}^{u}E_{2}^{−u}(1 − E_{1}^{l}E_{2}^{−l})}{1 − E_{1}^{W} E_{2}^{−W}}a[n, m]

= \frac{1 − E_{1}^{l}E_{2}^{−l}}{1 − E_{1}^{W} E_{2}^{−W}} a[m, n] − \frac{E_{1}^{−u}E_{2}^{u}(1 − E_{1}^{−l}E_{2}^{l})}{1 − E_{1}^{−W} E_{2}^{W}}a[m, n]

= (\frac{1 − E_{1}^{l}E_{2}^{−l}}{1 − E_{1}^{W} E_{2}^{−W}} + \frac{1 − E_{1}^{l}E_{2}^{−l}}{1 − E_{1}^{−W} E_{2}^{W}} E_{1}^{−W} E_{2}^{W} ) a[m, n]

= (1 − E_{1}^{l}E_{2}^{−l}) (∑_{k≥0} E_{1}^{kW} E_{2}^{−kW} a[m, n] + ∑_{j≥1} E_{1}^{−jW} E_{2}^{jW} a[m, n])

for 0 ≤ n − l ≤ m ≤ n + u.

Example 25 (king+knight) We found in Example 9 the weighted count K[m, n] of king+knight moves. The board [K] has a 0-left extension; according to Corollary 24 the weighted count of such moves strictly inside the band x − l < y < x + u is given by

∑_{s∈ℤ}(K[m + sW, n − sW] − K[m + sW + l, n − sW − l])

= ∑_{i,j,k≥0} κ^{k}ν^{i+j}\binom{m + n − k − 2i − 2j}{k, i, j, m + n − 2k − 3i − 3j} ×

∑_{s∈ℤ}(\binom{m + n − 2k − 3i − 3j}{m + sW − k − 2i − j}_{+} − \binom{m + n − 2k − 3i − 3j}{m + sW + l − k − 2i − j}_{+})  (19)

Again, we allowed the knights to jump over the barriers as long as they start and land inside the band.

Special cases: Lattice paths with steps →, ↑, and κ-weighted diagonal steps ↗ (king moves) are obtained from the above by setting ν = 0. There are

∑_{k≥0} κ^{k}\binom{m + n − k}{k, m + n − 2k} ∑_{s∈ℤ}(\binom{m + n − 2k}{m + sW − k}_{+} − \binom{m + n − 2k}{m + sW + l − k}_{+}) (20)

such weighted paths strictly inside the band x − l < y < x + u (with width W = l + u).

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 1, n − 1]
4  0 30 116 306 663 1251 2039 2468 0
u 0 6 24 62 128 229 359 429 0
2 1 5 13 25 41 60 70  0
1 1 3 5 7 9 10 0
0 1 1 1 1 1 0
{m↑ \atop n→} 0 1 2 3 4 l 6 7 W 9

King moves inside a band

Without diagonal steps (κ = 0) this simplifies to the well known number of ordinary lattice paths inside a diagonal band,

∑_{s∈ℤ}(\binom{m + n}{m + sW} − \binom{m + n}{m + sW + l}) .  (21)

Example 26 (asymmetric starting values) The above example is based on a 0bottom and 0-left board [a] so that Corollary 24 can be applied. This example is about ordinary paths (vizier moves) on a 0-left board with given initial values d[0, n] = α_{n} for all n = 0, …, l−1, and α_{0} ≠ 0. Let [a] be a 0-left board for the same recursion and initial values as [d] (up to column l − 1), but without the restrictions imposed by the band. Because of the simple recursion, [a] has polynomial columns, a[m, n] = a_{n}(m) for some polynomial sequence {a_{n}(x)}_{n≥0}. It can be shown in many ways (e.g. [11, equation (2)]) that

a[m, n] = ∑_{j=0}^{n} α_{j}\binom{n − j − 1 + m}{n − j},

where α_{j} = a[0, j] for all j ≥ 0.

d[m, n] = d[m − 1, n] + d[m, n − 1]
4  0 62 306 1005 2432 4587 6742 6742 0
u 0 10 62 244 699 1427 2155 2155 0
2 1 10 52 182 455 728 728 0
1 1 9 42 130 273 273 0
0 1 8 33 88 143 0
{m↑ \atop n→} 0 1 2 3 4 l 6 7 W 9

Ordinary paths with given bottom inputs inside a band

In the above board α_{j} := \frac{10−2j}{10} \binom{j+9}{j} and therefore a[m, n] = a_{n}(m) = \frac{m+10−2n}{m+10} \binom{n+m+9}{n}. According to [11, equation (6)],

v^{0}[m, n] = ∑_{k=0}^{l−1} a_{k}(k − l)\frac{m − n + l}{m − k + l}\binom{n + m − 2k + l − 1}{n − k}.  (22)

In the sample board above, l = 5 and u = 3. By Theorem 3,

d[m, n] = ∑_{i≥0} ∑_{k=0}^{4} \frac{5 − k}{k + 5}\binom{2k + 4}{k}\frac{m − n + 5 + 16i}{m − k + 5 + 8i}\binom{n + m − 2k + 4}{n − k − 8i}

− ∑_{i≥0} ∑_{k=0}^{4} \frac{5 − k}{k + 5}\binom{2k + 4}{k}\frac{m − n + 11 + 16i}{n − k + 8 + 8i}\binom{n + m − 2k + 4}{m − k − 3 − 8i}

Example 27 (knights) For the knight moves [figure], [figure]inside a diagonal band there always exists an isomorphic board counting ordinary lattice paths inside a band with the same width. Alternatively, we can apply Corollary 24 to the unrestricted knight moves (5) and get the number of knight moves to (n, m) inside the band x − l < y < x + u as

∑_{s∈ℤ}(\binom{(m + n)/3}{\frac{1}{3}(2n − m) − sW} − \binom{(m + n)/3}{\frac{1}{3}(2m − n) + sW + l})  (23)

for n − l < m ≤ 2n ≤ 4m < 4(n + u) and m + n divisible by 3.

Example 28 (hooks) We saw already in Example 19 that the hook moves [figure]and [figure]reach dead ends adjacent to the lower boundary y = x − l. Similarly, they reach dead end position adjacent to the upper boundary. Replace the contents of those cells (framed in the board below) by zero, and obtain an equivalent problem for knight moves in the band x − l + 1 < y < x + u − 1.

d[m, n] = d[m − 1, n − 2] + d[m − 2, n − 1]
8  ■  4  4
7  ■ 2  4  ■
6  ■  4  ■
5  ■  2  2 ■
4  ■ 1  2  ■
u = 3 ■  2  ■
2  1  1 ■
1  1  ■
0  1  ■
{m↑ \atop n→} 0 1 2 l = 3 4 5 6 7 8 9 10
d[m, n] = ∑_{s∈ℤ}(\binom{(m + n)/3}{\frac{1}{3}(2n − m) − sw} − \binom{(m + n)/3}{\frac{1}{3}(2m − n) + sw + l − 1})  (24)

where w = u + l − 2 and n − l + 1 < m ≤ 2n ≤ 4m < 4n + 4u − 4, and m + n is divisible by 3.

4 Recursive Initial Values at the Bottom of the Band

For weighted left turns inside a band only the lower boundary requires recursive initial values; the upper boundary can be represented by zeroes.

5  0  ε ε ■
4  0  δ δ ■
u 0  γ γ ■
2  β β ■
1  α α ■
0  ■
{m↑ \atop n→} 0 1 2 3 4 l 6 7 W 9 10 11 12

Mixed types of initial values

Theorem 4 (Section 1.1) deals with this situation for symmetric backwards recursions in general:

Let u and l be positive integers, defining a band of width W = u + l. Suppose the 0-left board [v^{0}] follows a symmetric recursion, has polynomial columns v^{0}[m, n] of degree n if m ≥ n, and satisfies the recursive initial conditions

v^{0}[n − l + 1, n] = v^{0}[n − l + 1, n − 1] for all n ≥ l.

If the board d[m, n] follows the same symmetric recursion, satisfies the boundary conditions

d[m, m − u] = 0 for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l,

and coincides with [v^{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, then [d] can be expanded as

d[m, n] = \frac{1}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} (v^{0}[m, n] − v^{0}[n + u, m − u]).

We give two proofs for this theorem; the first is a verification of the recurrence and initial values. That can be done in a few lines, but gives little guidance to the solution of related enumeration problems. The second proof constructs the solution and can be adopted to other recursive initial values.

Proof of Theorem 4 by verification. Because of Corollary 13 and Lemma 15 the board [d] follows the same recursion as [v^{0}] and vanishes along the upper barrier y = x + u. It is also obvious that d[m, n] = v^{0}[m, n] for 0 ≤ m < u and 0 ≤ n < W. It remains to show that E_{1}^{1−l}∇_{2}d[m, n] = 0 when m = n ≥ l. From

E_{1}^{1−l}∇_{2}d[m, n] = \frac{1}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} (E_{1}^{1−l}∇_{2}v^{0}[m, n] − E_{1}^{u}E_{2}^{1−l−u}∇_{1}v^{0}[n, m])

= \frac{E_{1}^{1−l}∇_{2}}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} (v^{0}[m, n] − E_{1}^{W −1}E_{2}^{1−W} ∇_{1}∇_{2}^{−1}v^{0}[n, m])

follows E_{1}^{1−l}∇_{2}d[n, n] = E_{1}^{1−l}∇_{2}v^{0}[n, n] which is 0 for all n ≥ l.

Proof of Theorem 4 by construction. The proof of this theorem is a variation of the proof of Theorem 3, constructing a sequence [v^{0}] , [h^{0}] , [v^{0}] , [h^{1}] , … of boards whose alternating partial sums \left[{ \atop d̂^{0}}\right] , [d^{0}] , \left[{ \atop d̂^{1}}\right] , [d^{1}] , … are approximations of [d],

covering an increasing part of the lattice. We start again with the 0-left board \left[{ \atop d̂^{0}}\right] := [v^{0}], which agrees with [d] in the rectangle 0 ≤ m < u and 0 ≤ n < W, and has recursive initial values along the whole lower barrier. Let [d^{−1}] ≡ [0], and suppose [d^{k−1}] and

d̂^{k}[m, n] = d^{k−1}[m, n] + v^{k}[m, n − kW]

have already been constructed such that

• [d^{k−1}] = [d] in the rectangle 0 ≤ m < u + kW, 0 ≤ n < kW, and d^{k−1}[m, m − u] = 0 for all m ≥ u.

• \left[{ \atop d̂^{k}}\right] = [d] in the rectangle 0 ≤ m < u + kW, 0 ≤ n < (k + 1)W, and

E_{1}^{1−l}∇_{2}d̂^{k}[n, n] = 0 for all n ≥ l.

Let h^{k}[m, n] := v^{k}[n + u, m], and

d^{k}[m, n] = d̂^{k}[m, n] − h^{k}[m − u − kW, n]  (25)

as before. From

d^{k}[m, m − u] = d̂^{k}[m, m − u] − h^{k}[m − u − kW, m − u]
= d^{k−1}[m, m − u] = 0

for all m ≥ 0 follows that [d^{k}] = [d] inside the rectangle 0 ≤ m < u + (k + 1)W, 0 ≤ n < (k +1)W. However, for enlarging the rectangle to 0 ≤ m < u+(k +1)W, 0 ≤ n < (k + 2)W we must define v^{k+1}[m, n] such that v^{k+1}[m, n] = 0 for negative n (0-left board), and such that

d̂^{k+1}[m, n] := d^{k}[m, n] + v^{k+1}[m, n − (k + 1)W]

has the recursive initial values d̂^{k+1}[n−l+1, n] = d̂^{k+1}[n−l+1, n−1] for all n ≥ l. By induction \left[{ \atop d̂^{k}}\right] already satisfies this boundary condition. We only have to determine

[v^{k+1}] such that

v^{k+1}[n − l + 1, n − (k + 1)W] − h^{k}[n − (k + 1)W + 1, n]
= v^{k+1}[n − l + 1, n − 1 − (k + 1)W] − h^{k}[n − (k + 1)W + 1, n − 1],

i.e.,

∇_{2}v^{k+1}[n − l + 1, n − (k + 1)W] = ∇_{1}h^{k}[n − (k + 1)W + 1, n]
= ∇_{1}v^{k}[n + u, n − (k + 1)W + 1].

Hence

v^{k+1}[m, n] := ∇_{2}^{−1}∇_{1}v^{k}[m + W − 1, n + 1].  (26)

has the required recursive initial values for all n ≥ l. The construction of \left[{ \atop d̂^{k+1}}\right] from

\left[{ \atop d̂^{k}}\right] is finished.

We calculate [v^{k}] recursively,

v^{k}[m, n] = ∇_{2}^{−1}∇_{1}E_{1}^{W −1}E_{2}^{1}v^{k−1}[m, n] = ⋯ = ∇_{2}^{−k}∇_{1}^{k}E_{1}^{k(W −1)}E_{2}^{k}v^{0}[m, n]. (27)

By Corollary 13 [v^{k}] is a 0-left board. Substitute first for [h^{i}] then for [v^{i}] in equation (25) to get

d^{k}[m, n] = ∑_{i=0}^{k} (v^{i}[m, n − iW] − v^{i}[n + u, m − u − iW])

= ∑_{i=0}^{k} E_{2}^{−iW} (v^{i}[m, n] − v^{i}[n + u, m − u])

= ∑_{i=0}^{k} E_{2}^{−iW} ∇_{2}^{−i}∇_{1}^{i}E_{1}^{i(W −1)}E_{2}^{i} (v^{0}[m, n] − v^{0}[n + u, m − u]) . (28)

Similar to Corollary 24 we have the following result.

Corollary 29 Let u and l be positive integers, defining a band of width W := u + l. Suppose, [d] follows a symmetric recursion and satisfies the two diagonal boundary conditions

d[m, m − u] = 0 for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l.

Let [a] be a symmetric board for the same recursion that is 0-left extendable and has polynomial columns a[m, n] of degree n if m ≥ n. If d[m, n] = a[m, n] on the rectangle 0 ≤ m < u, 0 ≤ n < l then d[m, n] can be expanded as

∑_{k∈ℤ}(E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1})^{k} (a[m, n]_{+} − a[m − u, n + u]_{+})

for n − l < m ≤ n + u (a[j, i]_{+} = 0 for negative i or j).

Proof. As in Corollary 24 we call the extension of [a] to a 0-bottom board [a′], and denote the 0-left extension again by [a]. Both extensions agree in the first quadrant. A slight generalization of Lemma 21 shows that

v^{0}[m, n] = a[m, n] − ∇_{1}^{−1}∇_{2}a′[n − l + 1, m − 1 + l]

the electronic journal of combinatorics 5 (1998), #R30 29 can serve as the 0-left board [v^{0}] in Theorem 4. In the first quadrant holds v^{0}[m, n] = (1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[m, n]. Hence, d[m, n] equals

\frac{1}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} (v^{0}[m, n] − v^{0}[n + u, m − u])

= \frac{1}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} ((1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[m, n]

− E_{1}^{u}E_{2}^{−u} (1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[n, m])

= \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} a[m, n] − \frac{E_{2}^{u}E_{1}^{−u} (1 − ∇_{1}^{−1}∇_{2}E_{1}^{1−l}E_{2}^{l−1})}{1 − E_{2}^{W −1}E_{1}^{−W +1}∇_{2}∇_{1}^{−1}}a[m, n]

= \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1}} a[m, n] + \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{2}^{W −1}E_{1}^{−W +1}∇_{2}∇_{1}^{−1}} ∇_{1}^{−1}∇_{2}E_{1}^{1−W} E_{2}^{W −1}a[m, n]

= ∑_{k∈ℤ}(E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1})^{k} (1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[m, n]

for n − l < m ≤ n + u. Example 30 (vizier+knight+hook) Suppose, the moves are →, ↑, and [figure], [figure].

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 2, n − 1] + d[m − 1, n − 2]

\begin{matrix}5 & & & 0 & 98 & 352 & 829 & 1415 \\ 4 & & 0 & 22 & 80 & 189 & 323 & 323 \\ 3 & 0 & 5 & 18 & 43 & 74 & 74 & ■ \\ 2 & 1 & 4 & 10 & 17 & 17 & ■ \\ 1 & 1 & 2 & 4 & 4 & ■ \\ 0 & 1 & 1 & 1 & ■ \\ {m↑ \atop n→} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \end{matrix}  1 10 49 170 474 1136 2431 1 8 32 94 226 474 899 1 6 19 46 94 170 282 1 4 10 19 32 49 70 1 2 4 6 8 10 12 1 1 1 1 1 1  1 0 1 2 3 4 5  6
[figure] must stay away from lower barrier Unrestricted moves

become eventually polynomial

The unrestricted board [a] has been calculated in (4) as

a[m, n] = ∑_{k≥0} ν^{k}\binom{m + n − 2k}{m − k}\binom{m + n − 2k}{k}.

It has polynomials columns for m ≥ m. From Corollary 29 follows that

d[m, n] = ∑_{k∈ℤ}(E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1})^{k} (a[m, n]_{+} − a[m − u, n + u]_{+})  (29)

for n − l < m ≤ n + u. Example 31 (weighted left turns inside band) We saw in (7) that

a[m, n] = ∑_{d≥0} μ^{d}\binom{m}{d}\binom{n}{d}

unrestricted →, ↑-paths with μ-weighted left turns → ∘^{↑} reach the point (n, m). The paths with weighted left turns follow a very special recursion,

∇_{1}∇_{2}a[m, n] = μE_{1}^{−1}E_{2}^{−1}a[m, n],

which tremendously simplifies the formula in Theorem 4, because it follows that

∇_{2}^{−i}a[m, n] = μ^{−i}E_{1}^{i}E_{2}^{i}∇_{1}^{i}a[m, n]

for 0 ≤ i ≤ min(m, n). We substitute this into (28) and obtain the total weight d[m, n] of all paths strictly between x + u < y < x − l,

∑_{k∈ℤ}(E_{1}^{W −1}E_{2}^{−W +1}∇_{1}∇_{2}^{−1})^{k} (a[m, n] − a[m − u, n + u])

= ∑_{k∈ℤ}(E_{1}^{W −1}E_{2}^{−W +1}∇_{1})^{k} μ^{−k}E_{1}^{k}E_{2}^{k}∇_{1}^{k} (a[m, n] − a[m − u, n + u])

= ∑_{k∈ℤ}E_{1}^{kW} E_{2}^{−kw}∇_{1}^{2k}μ^{−k}(a[m, n] − a[m − u, n + u])

where w := u + l − 2, the interior band width. Note that ∇^{2k}\binom{x}{j} = \binom{x−2k}{j−2k}. Hence d[m, n] =

∑_{k≥0} ∑_{j≥2k} μ^{j−k}[\binom{m + kw}{j − 2k}_{+}\binom{n − kw}{j}_{+} − \binom{m + kw − u}{j − 2k}_{+}\binom{n − kw + u}{j}_{+}

= ∑_{k∈ℤ} ∑_{j≥k} μ^{j} (\binom{m + kw}{j − k}_{+}\binom{n − kw}{j + k}_{+} − \binom{m + kw − u}{j − k}_{+}\binom{n − kw + u}{j + k}_{+}) .(30)

This result is equivalent to Theorem 3.4.4 in [6], where lattice paths with weighted right turns are counted. More references on earlier work on this problem are also given in [6].

It is easy to check that disregarding the count of left turns (μ = 1) gives formula (21). Replacing μ by κ − 1 transforms the left-turn recursion into the King recursion (Example 9). Because of the recursive initial values, no diagonal steps are allowed alongside the barrier.

\begin{aligned}& ⊙ & ■ \\ ⊗ & ■ \\ ■ \end{aligned}

No ↗- move from ⊗ to ⊙

There is an interesting special case when the sum over k in (30) simplifies. The following proposition is equivalent to the identities

∑_{k∈ℤ}(\binom{n + 2 + 2k}{j − k}_{+}\binom{n − 2k}{j + k}_{+} − \binom{n + 3 + 2k}{j − k}_{+}\binom{n − 1 − 2k}{j + k}_{+}) = \binom{n + 1}{2j − n}

∑_{k∈ℤ}(\binom{n + 1 + 2k}{j − k}_{+}\binom{n − 2k}{j + k}_{+} − \binom{n + 3 + 2k}{j − k}_{+}\binom{n − 2 − 2k}{j + k}_{+}) = \binom{n + 1}{2j − n + 1}

for all integers j, n ≥ 0.

Proposition 32 If u = 3 and l = 1 in Theorem 30, then

d[n + 1, n] = ∑_{j≥0} \binom{n + 1}{n + 1 − 2j}μ^{n−j} and d[n + 2, n] = ∑_{j≥0} \binom{n + 1}{n − 2j}μ^{n−j}

for all n ≥ 0.

Proof. True for n = 0. Suppose true for n − 1.

d[n + 1, n] = d[n, n] + d[n + 1, n] + (μ − 1)d[n, n − 1]

= d[n + 1, n − 1] + μd[n, n − 1]

= ∑_{j≥0} \binom{n}{n − 1 − 2j}μ^{n−1−j} + ∑_{j≥0} \binom{n}{n − 2j}μ^{n−j}

= ∑_{j≥0} \binom{n + 1}{n + 1 − 2j}μ^{n−j}

d[n + 2, n] = d[n + 1, n] + d[n + 2, n − 1] + (μ − 1)d[n + 1, n − 1]

= d[n + 1, n] + (μ − 1)d[n + 1, n − 1]

= ∑_{j≥0} \binom{n + 1}{n + 1 − 2j}μ^{n−j} + (μ − 1) ∑_{j≥0} \binom{n}{n − 1 − 2j}μ^{n−1−j}

= ∑_{j≥0} [\binom{n + 1}{n + 1 − 2j} + \binom{n}{n − 1 − 2j} − \binom{n}{n + 1 − 2j}] μ^{n−j}

= ∑_{j≥0} [\binom{n}{n − 2j} + \binom{n}{n − 1 − 2j}] μ^{n−j} = ∑_{j≥0} \binom{n + 1}{n − 2j}μ^{n−j}

5 Recursive Initial Values Along Both Barriers

Finally, we consider the case of recursive initial values at both boundaries of the band. The example below shows how such a situation arises from vizier+hook moves between barriers.

d[m, n] = d[m − 1, n] + d[m, n − 1] + d[m − 2, n − 1] + d[m − 1, n − 2]

\begin{matrix}5 & & & ■ & 73 & 312 & 770 & 1335 \\ 4 & & ■ & 17 & 73 & 180 & 312 & 312 \\ u & ■ & 4 & 17 & 42 & 73 & 73 & ■ \\ 2 & 1 & 4 & 10 & 17 & 17 & ■ \\ 1 & 1 & 2 & 4 & 4 & ■ \\ 0 & 1 & 1 & 1 & ■ \\ {m↑ \atop n→} & 0 & 1 & 2 & l & 4 & 5 & 6 \end{matrix}  \begin{aligned}& & ■ & 90 & 312 & 770 & 1335 \\ & ■ & 21 & 73 & 180 & 312 & 385 \\ ■ & 5 & 17 & 42 & 73 & 90 & ■ \\ 1 & 4 & 10 & 17 & 21 & ■ \\ 1 & 2 & 4 & 5 & ■ \\ 1 & 1 & 1 & ■ \\ 0 & 1 & 2 & l & 4 & 5 & 6 \end{aligned}

Steps: →, ↑,[figure], and [figure]  Steps: →, ↑, [figure], and [figure]

We will continue the example at the end of this section, after we have proved Theorem 5 from Section 1.1:

Let u and l be positive integers, defining an exterior band of width W := u+l, and an interior band width w := W − 2. Suppose the 0-left board [v^{0}] follows a symmetric recursion, has polynomial columns d[m, n] of degree n if m ≥ n, and satisfies the recursive initial conditions

v^{0}[n − l + 1, n] = v^{0}[n − l + 1, n − 1] for all n ≥ l

If the board d[m, n] follows the same symmetric recursion, satisfies the boundary conditions

d[m, m − u + 1] = d[m − 1, m − u + 1] for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l,

and coincides with [v^{0}] in the rectangle 0 ≤ m < u, 0 ≤ n < W, then [d] can be expanded as

d[m, n] = \frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (v^{0}[m, n] − ∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1]) .

Proof of Theorem 5 by verification. Verification of recursion and initial values of [d] follows the same line as in the first proof of Theorem 4. We verify only the recursive initial values along the lower boundary. From

E_{1}^{1−l}∇_{2}d[m, n] =

\frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (E_{1}^{1−l}∇_{2}v^{0}[m, n] − E_{2}^{1−l}∇_{1}∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1])

= \frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (E_{1}^{1−l}∇_{2}v^{0}[m, n] − E_{1}^{u−1}E_{2}^{−w}∇_{2}^{−1}∇_{1}^{2}v^{0}[n, m])

= E_{1}^{1−l}∇_{2} \frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (v^{0}[m, n] − E_{1}^{w}E_{2}^{−w}∇_{2}^{−2}∇_{1}^{2}v^{0}[n, m])

follows E_{1}^{1−l}∇_{2}d[n, n] = E_{1}^{1−l}∇_{2}v^{0}[n, n] = 0 for all n ≥ l.

Proof of Theorem 5 by construction. This proof is another variation of the construction introduced to prove Lemma 3. Let [d^{−1}] ≡ [0], and \left[{ \atop d̂^{0}}\right] := [v^{0}], which agrees with [d] in the rectangle 0 ≤ m < u and 0 ≤ n < W, and has the right recursive initial values along the whole lower boundary. Suppose [d^{k−1}] and

d̂^{k}[m, n] = d^{k−1}[m, n] + v^{k}[m, n − kW]

have already been constructed such that

• [d^{k−1}] = [d] in the rectangle 0 ≤ m < u + kW, 0 ≤ n < kW, and E_{2}^{1−u}∇_{1}d^{k−1}[m, m] = 0 for all m ≥ u, the electronic journal of combinatorics 5 (1998), #R30 33

• \left[{ \atop d̂^{k}}\right] = [d] in the rectangle 0 ≤ m < u + kW, 0 ≤ n < (k + 1)W, and E_{1}^{1−l}∇_{2}d̂^{k}[n, n] = 0 for all n ≥ l.

We must find a board [h^{k}] such that

d^{k}[m, n] := d̂^{k}[m, n] − h^{k}[m − u − kW, n]

satisfies the condition

E_{2}^{1−u}∇_{1}d^{k}[m, m] = 0 for all m ≥ u.

This will be the case iff

E_{2}^{1−u}∇_{1}d^{k}[m, m] = E_{2}^{1−u}∇_{1} (d^{k−1}[m, m] + v^{k}[m, m − kW] − h^{k}[m − u − kW, m]) equals 0 when n = m ≥ u. By induction E_{2}^{1−u}∇_{1}d^{k−1}[m, m] = 0; the above equation has the trivial solution

h^{k}[m − u − kW, n] = v^{k}[m, n − kW]

which gives [d^{k}] = [d^{k−1}], without improving the approximation, and the nontrivial solution where

E_{2}^{1−u}∇_{1}v^{k}[n, m − kW] = E_{2}^{1−u}∇_{1}h^{k}[m − u − kW, n],

i.e.,

h^{k}[m, n] = E_{1}^{u−1}∇_{2}^{−1}E_{2}^{1−u}∇_{1}v^{k}[n, m + u] = ∇_{2}^{−1}∇_{1}v^{k}[n + u − 1, m + 1].

With this choice of [h^{k}] we have d^{k}[m, n] = d[m, n] for all 0 ≤ m < u + (k + 1)W, 0 ≤ n < (k + 1)W. Next we must find a board [v^{k+1}] such that

d̂^{k+1}[m, n] := d^{k}[m, n] + v^{k+1}[m, n − (k + 1)W]

satisfies the condition

E_{1}^{1−l}∇_{2}d̂^{k+1}[n, n] = 0 for all m ≥ u.

The equation

E_{1}^{1−l}∇_{2}d̂^{k+1}[n, n] = E_{1}^{1−l}∇_{2} (d̂^{k}[n, n] − h^{k}[n − u − kW, n] + v^{k+1}[n, n − (k + 1)W])

= 0

gives the nontrivial solution E_{1}^{1−l}∇_{2}v^{k+1}[m, n − W] = E_{1}^{1−l}∇_{2}h^{k}[n − u, m].

Hence

v^{k+1}[m, n − W] = E_{2}^{l−1}∇_{1}^{−1}E_{1}^{1−l}∇_{2}h^{k}[n − u, m].

The board \left[{ \atop d̂^{k+1}}\right] equals [d] inside the rectangle 0 ≤ m < u + (k + 1)W, 0 ≤ n < l + (k + 2)W, and from here on the construction repeats itself.

Recursively we find

v^{k}[m, n] = ∇_{1}^{−1}∇_{2}h^{k−1}[n + 1, m + l − 1]
= E_{1}^{u−1}∇_{2}^{−2}E_{2}^{1−u}∇_{1}^{2}v^{k−1}[m + l − 1, n + u + 1]
= ∇_{2}^{−2}∇_{1}^{2}v^{k−1}[m + W − 2, n + 2]
= ∇_{2}^{−2k}∇_{1}^{2k}v^{0}[m + kW − 2k, n + 2k]
= E_{1}^{kw}E_{2}^{2k}∇_{2}^{−2k}∇_{1}^{2k}v^{0}[m, n]

which is indeed a 0-left board with constant first column by Corollary 13 (here we need the assumption that w ≥ 2). Similarly,

h^{k}[m, n] = ∇_{2}^{−1}∇_{1}v^{k}[n + u − 1, m + 1]
= E_{1}^{kw}E_{2}^{2k}∇_{2}^{−2k−1}∇_{1}^{2k+1}v^{0}[n + u − 1, m + 1]

can be verified as a 0-bottom board with constant first row by the row version of Corollary 13. Hence

d[m, n] = ∑_{i≥0} (v^{i}[m, n − iW] − h^{i}[m − u − iW, n])

= ∑_{i≥0} E_{1}^{iw}E_{2}^{2i}∇_{2}^{−2i}∇_{1}^{2i}(v^{0}[m, n − iw] − ∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1 − iW])

= ∑_{i≥0} (E_{2}^{−w}∇_{2}^{−2}E_{1}^{w}∇_{1}^{2})^{i} (v^{0}[m, n] − ∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1])

= \frac{1}{1 − E_{2}^{−w}∇_{2}^{−2}E_{1}^{w}∇_{1}^{2}} (v^{0}[m, n] − ∇_{2}^{−1}∇_{1}v^{0}[n + u − 1, m − u + 1]) .

In the same way as for the previous two theorems we get the following corollary.

Corollary 33 Let u and l be positive integers, defining a band of width W := u + l. Suppose, [d] follows a symmetric recursion and satisfies the two diagonal boundary conditions

d[m, m − u + 1] = d[m − 1, m − u + 1] for all m ≥ u,
d[n − l + 1, n] = d[n − l + 1, n − 1] for all n ≥ l.

Let [a] be a symmetric board for the same recursion that is 0-left extendable and has polynomial columns a[m, n] of degree n if m ≥ n. If d[m, n] = a[m, n] on the rectangle 0 ≤ m < u, 0 ≤ n < l then d[m, n] can be expanded as

∑_{j∈ℤ}(−1)^{j}E_{1}^{(jw)|2}E_{2}^{−(jw)|2}∇_{1}^{j}∇_{2}^{−j}a[m, n]

for n−l < m < n+u, where (jw)|2 equals jw/2 if j is even, and equals ⌊j/2⌋ w+l−1 if j is odd.

Note that for symmetric bands (u = l) the expression (jw)|2 can be replaced by jw/2.

Proof. We saw in the proof of Corollary 29 that v^{0}[m, n] = (1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[m, n] inside the first quadrant. Hence, d[m, n] equals

\frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} (v^{0}[m, n] − ∇_{2}^{−1}∇_{1}^{1}v^{0}[n + u − 1, m − u + 1])

= \frac{1}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} ((1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[m, n]

− E_{1}^{u−1}E_{2}^{−u+1}∇_{2}^{−1}∇_{1} (1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}) a[n, m])

= \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} a[m, n] − \frac{E_{2}^{u−1}E_{1}^{−u+1}∇_{1}^{−1}∇_{2} (1 − ∇_{1}^{−1}∇_{2}E_{1}^{1−l}E_{2}^{l−1})}{1 − E_{1}^{−w}E_{2}^{w}∇_{1}^{−2}∇_{2}^{2}}a[m, n]

= \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2}} a[m, n] + \frac{1 − ∇_{2}^{−1}∇_{1}E_{2}^{1−l}E_{1}^{l−1}}{1 − E_{1}^{−w}E_{2}^{w}∇_{1}^{−2}∇_{2}^{2}} ∇_{1}^{−2}∇_{1}^{2}E_{1}^{−w}E_{2}^{w}a[m, n]

= ∑_{k∈ℤ}(E_{1}^{w}E_{2}^{−w}∇_{2}^{−2}∇_{1}^{2})^{k} (1 − E_{1}^{l−1}E_{2}^{1−l}∇_{1}∇_{2}^{−1}) a[m, n]

= ∑_{k∈ℤ}(E_{1}^{w}E_{2}^{−w}∇_{1}^{2}∇_{2}^{−2})^{k} a[m, n] − ∑_{k∈ℤ}E_{2}^{−(kw+l−1)}∇_{2}^{−2k−1}E_{1}^{kw+l−1}∇_{1}^{2k+1}a[m, n]

for n − l < m < n + u.

Example 34 (vizier+hook between barriers ) Continuing the vizier+knight example from the beginning of this section we see that we must replace a[m, n] by (4) in

∑_{j∈ℤ}(−1)^{j}E_{1}^{(jw)|2}E_{2}^{−(jw)|2}∇_{1}^{j}∇_{2}^{−j}a[m, n]  (31)

to get the number of vizier+hook walks with steps →, ↑,[figure], and [figure]between the barriers x−l < y < x+u from the origin to the point (n, m) where n−l < m < n+u. Except at the positions (n − l + 1, n) and (m, m − u − 1) the vizier+hook walks with

steps →, ↑, [figure], and [figure]have the same number of choices. Formula (31) holds for them whenever n − l + 1 < m < n + u − 1.

References

[1] André, D. (1887). Solution directe du problème résolu par M. Bertrand, Comptes Rendues Hebdomadaires des Séances de l’Académie des Sciences (Paris), 105, 436-437.

[2] Dickens, A. (1969). A Guide to Fairy Chess. Dover Publ. Inc., New York, 1971.

[3] Fray, R.D., and Roselle, D.P. (1971). Weighted lattice paths. Pacific J. Math. 37, 85-96.

[4] Jordan, C. (1939). Calculus of Finite Differences. Chelsea Publ. Co., New York, 3rd edition 1979.

[5] Koroljuk,V.S. (1955). On the discrepancy of empiric distributions for the case of two independent samples. Izv. Akad. Nauk SSSR Ser. Mat. 19, 81-96 (IMS&AMS Sel. transl. Math. Statist. Prob. 4 (1963) 105-122).

[6] Krattenthaler, C. (1997) The enumeration of lattice paths with respect to their number of turns, Advances in Combinatorial Methods and Applications to Probability and Statistics (Ed.: N. Balakrishnan), 19-58, Boston, Birkhäuser.

[7] Krattenthaler, C. and Niederhausen, H. (1997) Lattice paths with weighted left turns above a parallel to the diagonal. To appear in Congressus Numeratium.

[8] Labelle, J., and Yeh, Y.-N. (1990). Generalized Dyck paths, Discrete Math. 82, 1-6.

[9] Mohanty, S.G. (1979). Lattice Path Counting and Applications. Academic Press, New York.

[10] Niederhausen, H. (1997) Recursive initial values. To appear in Discrete Math.

[11] Niederhausen, H. (1997) Lattice path enumeration and Umbral Calculus, Advances in Combinatorial Methods and Applications to Probability and Statistics (Ed.: N. Balakrishnan), 15-27, Boston, Birkhäuser.

[12] Niederhausen, H. (1996) Symmetric Sheffer sequences and their applications to lattice path counting, J. Statist. Planning and Inference 54, 87-100.

[13] Rota, G.-C., Kahaner, D. and Odlyzko, A. (1973). On the foundations of combinatorial theory, VIII. Finite operator calculus, J. Math. Anal. Appl. 42, 684-760.

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

[15] Smoluchowski, M. (1913) Einige Beispiele Brown’scher Molekularbewegung unter Einfluß äußerer Kräfte, Extrait du Bulletin de L’Académie des Sc. de Cracovie, Série A, 1913, pp.418

[16] Sulanke, R.A. (1989) A recurrence restricted by a diagonal condition, Fibonacci Q. 27, 33-46

[17] Takács, L. (1997) On the ballot theorems. Advances in Combinatorial Methods and Applications to Probability and Statistics (Ed.: N. Balakrishnan), 98-114, Boston, Birkhäuser. the electronic journal of combinatorics 5 (1998), #R30 37

Niederhausen@math.fau.edu