Lattice Path Enumeration and Toeplitz Matrices

Stefan Felsner and Daniel Heldt Institut für Mathematik Technische Universität Berlin Straße des 17. Juni 136 D-10623 Berlin Germany

               felsner@math.tu-berlin.de
               dheldt@math.tu-berlin.de

Abstract

This paper is about counting lattice paths. Examples are the paths counted by Catalan, Motzkin or Schröder numbers. We identify lattice paths with walks on some path-like graph. The entries of the nth power of the adjacency matrix are the number of paths of length n with prescribed start and end position. The adjacency matrices turn out to be Toeplitz matrices. Explicit expressions for eigenvalues and eigenvectors of these matrices are known. This yields expressions for the numbers of paths in the form of trigonometric sums. We give many examples of known sequences that have such expressions.

We also deal with cases where no explicit expressions for eigenvalues and eigenvectors of the relevant matrices are known. In some of these cases it is possible to use the characteristic polynomial to get linear recurrence relations for the numbers in question.

1 Introduction

Let P_{n}(α) be the path of n + 1 vertices with a loop of weight α at each vertex and pathedges of weight 1, see Figure 1. We label the vertices from one end to the other, starting with vertex 0 and ending with vertex n. A walk in a graph is a list x_{0}, e_{1}, x_{1}, …, e_{m}, x_{m} of vertices x_{i} and edges e_{j}, such that edge e_{i} has endpoints x_{i−1} and x_{i}. A walk is oriented; it starts with x_{0} and ends with x_{m}. We say that the walk is from x_{0} to x_{m}. The length of a path is the number of edges traversed, and it is m in the example. For a walk in an edge-weighted graph we define its weight as the product of the weights of its edges. Example: 1 → 2 → 3 → 3 → 2 is a walk from 1 to 2 in P_{5}(α). Its length is 4 and its weight is α.

α  1 α 1 α  α 1 α

Figure 1: The path P_{n}(α) with n + 1 vertices and loops of weight α.

Counting walks on P_{n}(α) enables us to count Motzkin paths in a strip: Motzkin paths of length n are lattice paths with steps of three types (x, y) → (x+1, y +1), (x, y) → (x+1, y), and (x, y) → (x + 1, y − 1) that start in (0, 0) end in (n, 0) and stay above the x-axis, i.e, y ≥ 0. A Motzkin path is in the strip [0, k] iff its y-coordinate never exceeds k.

Figure 2: The 9 Motzkin paths of length 4; the first eight are in the strip [0, 1].

Other types of lattice walks in a strip (for example Dyck paths or Schröder paths) can also be interpreted as walks on paths, see Section 3. We use the weighted adjacency matrix of P_{n}(α) as a tool to enumerate classes of such lattice paths. In principle, this is nothing but a variant of the traditional transfer-matrix method. Results similar to ours but tailored towards an audience of physicists and with a focus on random walks have been obtained by by Cicuta et al. [4].

The enumeration of classes of lattice paths is a classical topic originating from Bertrand’s ballot problem. They are investigated in probability theory in the context of the gambler’s ruin problem [7, Chapter XIV], but also in their own right. The monograph by Mohanty [12] gives a valuable overview. An survey on more recent aspects of lattice path enumeration was given by Humphrey [10].

2 The counting approach

Let us start with two simple facts about the enumeration of walks in graphs.

Fact 1. Let G be a graph with weights on the edges and let A be its weighted adjacency matrix. The sum of the weights of walks of length m from vertex i to vertex j is

e_{i}^{T} · A^{m} · e_{j}.

From now on we focus on the graph P_{n} = P_{n}(1) and its weighted version P_{n}(α) respectively. With A_{(n,α)} we denote the weighted adjacency matrix of P_{n}(α); clearly A_{(n,α)} ∈ ℝ^{(n+1)×(n+1)}.

Definition 2.

Z_{i,j}^{n}(m, ℓ) := #(walks from i to j of length m, using ℓ loops in P_{n}).

The following is obtained from Fact 1 and simple combinatorial reasoning.

Fact 3.

Z_{i,j}^{n}(m, ℓ) = \binom{m}{ℓ} · Z_{i,j}^{n}(m − ℓ, 0)  (1)
∑_{ℓ=0}^{m} Z_{i,j}^{n}(m, ℓ) α^{ℓ} = e_{i}^{T} · A_{(n,α)}^{m} · e_{j}  (2)

From these fact we can deduce explicit expressions for Z_{i,j}^{n}(m, ℓ) as trigonometric sums.

Theorem 4.

Z_{i,j}^{n}(m − ℓ, 0) = \frac{2}{n + 2} ∑_{k=1}^{n+1} (2 cos (\frac{k · π}{n + 2}))^{m−ℓ} sin (i\frac{k · π}{n + 2}) sin (j \frac{k · π}{n + 2})  (3)

e_{i}^{T} · A_{(n,α)}^{m} · e_{j} = \frac{2}{n + 2} ∑_{k=1}^{n+1} (α + 2 cos (\frac{k · π}{n + 2}))^{m} sin (i\frac{k · π}{n + 2}) sin (j \frac{k · π}{n + 2}) (4)

To prove the two formulas given in the theorem we begin with simple linear algebra. The first proposition is well known:

Proposition 5. Let A ∈ ℝ^{(n+1)×(n+1)} be a matrix and assume that A admits an orthonormal basis (v_{1}, …, v_{n+1}) of eigenvectors. Also let λ_{i} ∈ ℂ be the eigenvalue corresponding to v_{i} = (v_{1,i}, …, v_{n+1,i}). Then

e_{i}^{T} · A^{m} · e_{j} = ∑_{k=1}^{n+1} λ_{k}^{m}v_{i,k}v_{j,k}.

Proof. Consider the matrix S = [v_{1}, …, v_{n+1}], i.e., S · e_{i} = v_{i} for all i. From orthogonality we obtain S^{T} = S^{−1}. This implies e_{i} = S^{T} · v_{i} and S^{T} · A · S = diag(λ_{1}, …, λ_{n+1}) =: D. Now A^{m} = (S · D · S^{−1})^{m} = S · D^{m} · S^{−1} = S · D^{m} · S^{T} and hence, e_{i}^{T} · A^{m} · e_{j} = e_{i}^{T} S · D^{m} · S^{T} e_{j} = (S^{T} e_{i})^{T} · D^{m} · (S^{T} e_{j}) = (v_{i,1}, …, v_{i,n+1})^{T} · D^{m} · (v_{j,1}, …, v_{j,n+1}) = ∑_{k=1}^{n+1} λ_{k}^{m}v_{i,k}v_{j,k}.

Since A_{(n,α)} is a real symmetric matrix it has a real orthonormal basis (v_{1}, …, v_{n+1}) ∈ ℝ^{n+1} of eigenvectors. The next lemma relates eigenvalues and eigenvectors of A_{(n,α)} and of A_{(n,0)}.

Lemma 6. Let λ_{1}, …, λ_{n+1} be the eigenvalues of A_{(n,0)} and (v_{1} …, v_{n+1}) a corresponding orthonormal basis of eigenvectors. Then all eigenvalues of A_{(n,α)} are of the form λ_{i} + α and (v_{1}, …, v_{n+1}) is an orthonormal basis of eigenvectors of A_{(n,α)}.

Proof. Let v be an eigenvector of A_{(n,0)} with respect to λ, then A_{(n,α)}·v = (A_{(n,0)}+α·I_{n})·v = A_{(n,0)}·v+α·v = (λ+α)·v. Hence, v is an eigenvector of A_{(n,α)} w.r.t. the eigenvalue λ+α.

Our next aim is to determine the orthonormal basis of eigenvectors of A_{(n,0)}. The structure of this matrix is captured by the next definition.

Definition 7. (Toeplitz matrix)

A matrix A = (a_{ij}) ∈ ℝ^{(n+1)×(n+1)} is called a Toeplitz matrix if there exist

c_{−n}, c_{−(n−1)}, …, c_{0}, … c_{n} ∈ ℝ

such that

a_{ij} = c_{i−j} for all i, j = 1, 2, …, n + 1

i.e., A is constant on all diagonals. We will denote A as toep(c_{−n}, …, c_{n}) to have a short notation for A. If c_{−k} = c_{k} the matrix A is a symmetric Toeplitz matrix.

Fact 8. A_{(n,α)} = toep(0, … 0, 1, α, 1, 0, … 0) is the adjacency matrix of P_{n}(α).

Proposition 9. The eigenvalues λ_{k} and (right) eigenvectors v_{k} of A_{(n,0)} are

λ_{k} := 2 · cos (\frac{k · π}{n + 2})

and

v_{k} := (sin (1 · \frac{k · π}{n + 2}) , sin (2 · \frac{k · π}{n + 2}) , …, sin ((n + 1) · \frac{k · π}{n + 2}))

for k = 1, …, n + 1. Moreover, ∥v_{k}∥_{2}^{2} = \frac{n+2}{2} for all k.

Proof. Since A_{(n,0)} is a tridiagonal Toeplitz matrix with diagonals 1, 0, and 1, the eigenvectors and eigenvalues are known, see e.g. [2]. Replacing (a, b, c) in the given formula on page 35 of that book by (1, 0, 1) yields the result.

Now it is easy to complete the proof of formulas (3) and (4):

Proof. (Theorem 4) For (3) first replace Z_{i,j}^{n}(0, m − ℓ) by e_{i}^{T} · A_{(n,0)}^{m−ℓ} · e_{j}, a consequence of (2). The proof of the formulas now follows from a combination of Proposition 5, Lemma 6 and Proposition 9.

The eigenvalues in Proposition 9 are closely related to the roots of Chebyshev polynomials of the second kind. Connections between these polynomials and the counting of Motzkin paths have surfaced before. The work of Chow and West [3] contains relations between the Chebyshev polynomials, their roots, and 123-avoiding permutations, which are closely linked to Motzkin paths. Starting out from continued fractions expressions à la Flajolet, Elizalde and Mansour [6] have uncovered more explicit connections.

Besides the exact enumeration in terms of trigonometric sums, the numbers Z_{i,j}^{n}(m, ℓ) can also be related to linear recurrences and generating functions. An approach to obtaining the generating function can be found in [14, Chapter 4, Theorem 4.2.7]. A linear recurrence can be derived from the characteristic polynomial of the weighted adjacency matrix or any other polynomial, which has the weighted adjacency matrix as a root:

Fact 10. Let A ∈ ℝ^{(n+1)×(n+1)} be a matrix and χ_{A}(x) be the characteristic polynomial of A. The Cayley-Hamilton Theorem states that χ_{A}(A) = 0. The polynomial χ_{A_{(n,α)}}(x) = x^{n+1} + ∑_{k=0}^{n} a_{k}x^{k} leads to the linear recurrence:

(A_{(n,α)})^{n+1} = − ∑_{k=0}^{n} a_{k}(A_{(n,α)})^{k}.

With Fact 3(2) we obtain

Z_{i,j}^{n}(m, ℓ) = − ∑_{k=0}^{n} a_{k}Z_{i,j}^{n}(m − n + j, ℓ).

The characteristic polynomial of A_{(n,α)} is known to be determined by the n+1-th Chebyshev polynomial of second kind U_{n+1}(x) as

χ_{A_{(n,α)}}(x) = U_{n+1}(\frac{x−α}{2}).

From this the explicit expressions for the coefficients a_{k} can be obtained. This then leads to an explicit linear recurrence for Z_{i,j}^{n}(m, ℓ).

3 Interesting special cases

In this section we show that the numbers Z_{i,j}^{n}(m, ℓ) are quite universal. Special combinations of their parameters lead to a multitude of well known and not so well known sequences. In many cases we refer to a sequence by using its number from the The On-Line Encyclopedia of Integer Sequences (OEIS).

Example 11. (Binomial Coefficients)

Z_{k,n−k}^{n}(n, 0) = \binom{n}{k}

Proof. The start and end for the walks on P_{n} are such that any sequence of k steps down and n − k steps up stays on P_{n}.

The choice of the parameters is not unique. Indeed for all k′ ≥ k and n′ ≥ k′ + n − k we have

Z_{k′,k′+n−2k}^{n′}(n, 0) = Z_{k,n−k}^{n−k}(n, 0) = \binom{n}{k}.

Example 12. (Bounded Binomial Coefficients) Let C(n, k, b) be the number of {0, 1}-strings of length n with k times 1 such that for each initial segment of the string the number of 0’s and the number of 1’s differ at most by b. It is easy to verify that

C(n, k, b) = Z_{b,2k+b−n}^{2b}(n, 0).

For b = 1, we have Z_{1,1}^{2}(2n, 0) = 2^{n} = Z_{1,2}^{2}(2n+1, 0) and for b = 2 we have Z_{2,2}^{4}(2n, 0) = 2·3^{n}. Since the sequence a_{n} := Z_{3,3}^{6}(2n, 0) fulfills the recursion a_{n} = 4a_{n−1} − 2a_{n−2} and has the same initial values it is \underline{A006012}. The sequence b_{n} = Z_{4,4}^{8}(2n, 0) seems to be \underline{A147748}.

Example 13. (Catalan numbers)

Z_{0,0}^{n}(2n, 0) = \frac{1}{n + 1}\binom{2n}{n} = C_{n}

Proof. Catalan numbers count Dyck paths from (0, 0) to (0, 2n), i.e., lattice paths with steps i → i + 1 and i → i − 1 from (0, 0) to (0, 2n), which stay above the x-axis. Dyck paths correspond to walks on P_{n} without loops, starting at vertex 0 and returning to 0 after 2n steps.

Again, this can be generalized to all n′ ≥ n since Z_{0,0}^{n′}(2n, 0) = Z_{0,0}^{n}(2n, 0). Also Dyck paths can be restricted in height.

Example 14. (Bounded Catalan numbers) Bounded Catalan numbers in our sense count the number of Dyck paths, which do not exceed a given level k. When k = 2 we obtain Z_{1,1}^{2}(2(m − 1), 0) = Z_{0,0}^{2}(2m, 0) = 2^{m−1}. For bigger k some of the sequences are also well known, as the corresponding entries from the OEIS show:

Z_{0,0}^{3}(2m, 0) → \underline{A001519} Z_{0,0}^{5}(2m, 0) → \underline{A080937} Z_{0,0}^{m−2}(2m, 0) → not listed
Z_{0,0}^{4}(2m, 0) → \underline{A124302} Z_{0,0}^{6}(2m, 0) → \underline{A024175} Z_{0,0}^{m−1}(2m, 0) → not listed

Bounded Dyck paths have also been counted by Owczarek and Prellberg [13]. They derive a closed formula for a q-analog, where q is taking the area under the path into account.

Example 15. (Fibonacci Numbers)

Z_{0,gcd(m,2)}^{2}(m, 0) = F_{m}

Proof. F_{n} = number of Catalan paths from (0, 0) to (n, gcd(n, 2)) that stay between the lines y = 0 and y = 3. In the On-Line Encyclopedia of Integer Sequences this is attributed to Kimberling.

Example 16. (Motzkin numbers)

∑_{ℓ=1}^{n} Z_{0,0}^{⌊n/2⌋}(n, ℓ) = M_{n}

Proof. Motzkin numbers count Motzkin paths, i.e., lattice paths from (0, 0) to (0, n), using only steps up-left, horizontal or down-left, see Figure 2. These paths can be counted as walks with loops on P_{n}(1).

The refined counting for Motzkin numbers allows us to control the maximal height of the corresponding path as well as the number of horizontal steps allowed (or at least used).

Example 17. (Bounded Motzkin numbers) Bounded Motzkin numbers are defined similarly to bounded Catalan numbers but on the basis of Motzkin paths instead of Dyck paths.

∑_{ℓ} Z_{0,0}^{1}(m, ℓ) → 2^{m−1} ∑_{ℓ} Z_{0,0}^{5}(m, ℓ) → \underline{A094287}  ⋮  → ⋮
∑_{ℓ} Z_{0,0}^{2}(m, ℓ) → \underline{A024537} ∑_{ℓ} Z_{0,0}^{6}(m, ℓ) → \underline{A094288} ∑_{ℓ} Z_{0,0}^{⌊ \frac{m}{2} ⌋−1}(m, ℓ) → n.l.
∑_{ℓ} Z_{0,0}^{3}(m, ℓ) → \underline{A005207} ∑_{ℓ} Z_{0,0}^{7}(m, ℓ) → not listed ∑_{ℓ} Z_{0,0}^{⌊ \frac{m}{2} ⌋−2}(m, ℓ) → n.l.
∑_{ℓ} Z_{0,0}^{4}(m, ℓ) → \underline{A094286}  ⋮  →  ⋮  →

Example 18. (Delannoy numbers)

∑_{ℓ=0}^{a} Z_{a,b−a}^{b+a}(a + b − ℓ, ℓ) = ∑_{ℓ=0}^{a} \binom{a}{ℓ}\binom{b + ℓ}{b} = D(a, b)

Proof. Delannoy numbers describe the number of lattice paths from (0, 0) to (a, b) which use steps up, right and diagonal (i.e., steps with the effect of up+right). We do a refined counting (by counting the paths with a fixed number of diagonal steps and therefore a fixed number of total steps). The Delannoy paths from (0, 0) to (a, b) with ℓ ≤ a diagonal steps have length a + b − ℓ, they use b − ℓ up-steps and a − ℓ right-steps. Modeling right-steps as decreasing-steps in the path, diagonals as loops and up-steps as increasing-steps, we see that the number of these paths is Z_{a,b−a}^{b+a}(a + b − ℓ, ℓ).

Example 19. (Schröder numbers)

∑_{ℓ=0}^{n} Z_{0,0}^{n}(2n − 2ℓ, ℓ) = S(n)

Proof. Schröder numbers count lattice paths from (0, 0) to (n, n) with steps up, right and diagonal, which do not exceed the diagonal. Again, a counting, refined by fixing the number of diagonal steps (to fix the number of steps in the path) yields the result. All we have to change is the start and endpoint of our walks to ensure, that the path does not exceed the diagonal.

Example 20. (Pell numbers) Another example are Pell numbers (\underline{A000129}), which can be computed using b_{n} = ∑_{ℓ=0}^{n} Z_{0,2}^{2}(n, ℓ), since the b_{n} then satisfy the recursion b_{n} = 2b_{n−1} + b_{n−2}.

4 Refined Counting

In this section we derive linear recursions for a refined version of the ballot problem. A turn is a change of direction from up to down or vice versa (the up step and the down step need not be consecutive, they may enclose some loops, respectively horizontal steps). Figure 3 shows an example.

Figure 3: A lattice walk of length 12 with 4 turns (red double-arrows) and 2 straight steps (green) in P⃗_{3}(α) from u_{0} to u_{2}.

Refined counting is going to keep track of the number of turns of the paths. As in Section 2 we identify lattice walks with walks on some graph. The relevant graph P⃗_{n}^{+}(α) is obtained from the graph P⃗_{n}(α) shown in Figure 4 by adding the vertices u_{0} and d_{n} with their loops and the edges u_{0} → u_{1} and d_{n} → d_{n−1}.

The graph P⃗_{n}(α) consists of two directed paths of length n − 1 with loops which are connected by bidirectional edges in such a way, that the i-th vertex of the first path is linked to the (n − i)-th vertex of the second one. The weight of the loops is α. The weight of the bidirectional edges is β and the weight of the directed edges on the two paths is 1. Note that the vertices u_{0} and d_{n} are omitted, they have no incoming edges and do not play a role in the counting of lattice walks unless one of them represents the starting vertex.

Now, let

Z⃗_{v,w}^{n}(m, ℓ, t) := #( walks on P⃗_{n}(α) from v to w of length m

with ℓ loops and t turns),

Z⃗_{v,w}^{n}(m) := ∑_{ℓ,t} Z⃗_{v,w}^{n}(m, ℓ, t)α^{ℓ}β^{t}.

…  … α  β α  α  α α  β β β  β α α  αα  α u_{n} u_{2} u_{1} d_{0}  d_{1}  d_{n−1} u_{3}  u_{n−1} d_{2}  d_{n−2}

Figure 4: The directed path P⃗_{n}(α) with 2n vertices and loops of weight α and turning-edges of weight β

Krattenthaler counted some instances of these lattice paths. See [11], especially Theorem 3.4.4 for details. However, his work does not cover straight steps (or loops in our language).

Theorem 21. (Characteristic polynomial of P⃗_{n}(α) ) Let χ_{P⃗_{n}(α)}(x) be the characteristic polynomial of the adjacency matrix of the graph P⃗_{n}(α). Then:

∑_{n=0}^{∞} χ_{P⃗_{n}(α)}(x)λ^{n} = \frac{(α − x)^{2}(λ − 1) − β^{2}}{1 + (β^{2} − 1 + (α − x)^{2}(λ − 1))λ}

and

Z⃗_{v,w}^{n}(m) = \frac{−1}{c_{2n}^{n}} · ∑_{k=1}^{2n} c_{2n−k}^{n} · Z⃗_{v,w}^{n}(m − k),

where

c_{k}^{n} = (−1)^{k} ∑_{j=0}^{n} ∑_{l=0}^{n−j} ∑_{i=0}^{j} \binom{n − l − j − 1}{j − 1}\binom{l + j}{j}\binom{j}{i}\binom{2i}{k}(−β^{2})^{l+j−i}α^{2i−k}

are the coefficients of the characteristic polynomials χ_{P⃗_{n}(α)}(x) of the graphs P⃗_{n}(α).

To prove this theorem, we use a well known connection between cycle covers and determinants of the adjacency matrix of the covered (di-)graphs.

Definition 22. Let G⃗ be a directed graph with weighted edges. A cycle cover C of G⃗ consists of |V (G⃗)| edges, such that every vertex has one incoming and one outgoing edge. In other words it is a set of simply directed cycles which contains every vertex exactly once.

Further, the weight ω(C) of the cycle cover C is the product of all edge-weights of C multiplied with (−1)^{# even cycles}. Finally C(G⃗) is the set of all cycle covers of G⃗.

Lemma 23. (Cycle covers and determinants) Let G⃗ be a digraph with edge weights and adjacency matrix A = (a_{ij}). We have

det(A) = ∑_{σ∈S_{n}} (sgn(σ) · ∏_{i=1}^{n} a_{i,σ(i)}) = ∑_{C∈C(G⃗)} ω(C) = ω(C(G⃗)).

Proof. A permutation σ ∈ S_{n} can be seen as a subset of n directed edges C = {(i, σ(i)) | i = 1 …, n}, which form a cycle cover. This cycle cover has weight sgn(σ) · ∏_{i=1}^{n} a_{i,σ(i)}. If one of the edges is not present in G⃗, the weight is 0, since the corresponding entry of A is 0. The sign of σ is the product of the signs of individual cycles. Even cycles contribute a factor of −1, odd cycles a factor +1.

Proposition 24. (Theorem 4.7.2 of [14] or Proposition V.9 of [8]) Let A be the adjacency matrix of a graph G. Further, let N_{i,j}(k) be the number of walks from i to j of length k and w_{ij} = ∑_{k=0}^{∞} N_{i,j}(k) · t^{k}. Then W = (w_{ij}) = (I − t · A)^{−1}, where I is the identity matrix of the right size.

With this we are ready for the proof of the theorem:

Proof. (Theorem 21) To find the generating function for the characteristic polynomials χ_{P⃗_{n}(α)} of the adjacency matrix of the graph P⃗_{n}(α), we count weighted cycle covers of the graph P⃗_{n}(α−x). According to Lemma 23 the sum of their weights is the polynomial we are looking for. Now, we partition the set of all cycle covers, according to the edges they use, to cover the vertices d_{n−1} and u_{n}. Let A_{n} be the set of all cycle covers of P⃗_{n}(α − x), such that the vertices u_{n} and d_{n−1} are both covered by loops and let B_{n} be the set of all remaining cycle covers. Cycle covers in B_{n} contain the edge (u_{n}, d_{n−1}), since apart from the loop this is the only outgoing edge of u_{n}. Further, let a_{n} := ω(A_{n}) = ∑_{C∈A_{n}} ω(C) and b_{n} := ω(B_{n}). This implies ω(C(P⃗_{n}(α − x))) = ∑_{C∈C(P⃗_{n}(α−x))} ω(C) = a_{n} + b_{n}. Now, every cycle cover of P⃗_{n−1}(α) can be extended with two loops of weight (α − x)^{2} or a two-cycle of weight −β^{2}. Further for every cycle cover in B_{n−1}, we can replace the edge u_{n−1}, d_{n−2} by the path u_{n−1}, u_{n}, d_{n−1}, d_{n−2}. This leads to a cycle cover in B_{n} with the same weight. Conversely, from a cycle cover in A_{n} we can delete the two loops at u_{n} and d_{n−1} to obtain a cover of P⃗_{n−1}. In a cycle cover in B_{n} the two vertices u_{n} and d_{n−1} are either covered by a two cycle which can be deleted or they belong to a longer cycle from which they can be removed. This implies the linear recursions a_{n+1} = (α − x)^{2}(a_{n} + b_{n}) and b_{n+1} = −β^{2}a_{n} + (−β^{2} + 1)b_{n}. The initial conditions

are a_{0} = (α − x)^{2} and b_{0} = −β^{2}. With A = ( \begin{matrix}(α − x)^{2} & (α − x)^{2} \\ −β^{2} & −β^{2} + 1 \end{matrix} ), we obtain:

χ_{P⃗_{n}(α)}(x) = ω(C(P⃗_{n}(α − x))) = a_{n} + b_{n} = (1, 1) · (\begin{matrix}a_{n} \\ b_{n} \end{matrix})
= (1, 1) · A · (\begin{matrix}a_{n−1} \\ b_{n−1} \end{matrix}) = (1, 1) · A^{n} · (\begin{matrix}a_{0} \\ b_{0} \end{matrix}) .

Hence,

∑_{n=1}^{∞} χ_{P⃗_{n}(α)}(x)λ^{n} = ∑_{n=1}^{∞} ((1, 1) · A^{n} · (\begin{matrix}a_{0} \\ b_{0} \end{matrix})) · λ^{n}

and Proposition 24 can be applied. For this we need the inverse of (I_{2} − λA) which is

\frac{1}{1 + (β^{2} − 1)λ + (α − x)^{2}(λ^{2} − λ)} ( \begin{matrix}1 − (−β^{2} + 1)λ & (α − x)^{2}λ \\ −β^{2}λ & 1 − (α − x)^{2}λ \end{matrix} ) .

Hence, the generating function for the characteristic polynomials of P⃗_{n}(α) is

∑_{n=0}^{∞} χ_{P⃗_{n}(α)}(x) · λ^{n} = (1, 1) · (I_{2} − λA)^{−1} · (\begin{matrix}(α − x)^{2} \\ −β^{2} \end{matrix})

= \frac{(α − x)^{2}(λ − 1) − β^{2}}{1 + (β^{2} − 1 + (α − x)^{2}(λ − 1))λ}.

This proves the first part of the theorem.

To deduce the theorem’s second claim, one could establish an explicit representation of the characteristic polynomial χ_{P⃗_{n}(α)}(x) via a partial fraction decomposition of the generating function above. However, there is a more direct and elegant approach using Lemma 23: A cycle cover of P⃗_{n}(α−x) decomposes the upper path of P⃗_{n}(α−x) into segments of consecutive vertices, each segment belonging to one cycle. Conversely every such decomposition induces some cycle covers, each segment has to be closed to a cycle. For sections, which have length ≥ 1, the cycle is unique, while for singleton vertices, there is either a loop on both sides or a two cycle.

There are \binom{n−1}{p−1} decompositions of the upper part of P⃗_{n} into p parts. They induce different numbers of cycle decompositions of weights. We count these decompositions with respect to l, the number of sections of length 1, and j, the number of sections of length ≥ 2. There are \binom{n−l−j−1}{j−1} decompositions of n − l elements into j sections of length ≥ 2. For given (l, j) we therefore have \binom{n−l−j−1}{j−1}\binom{l+j}{j} decompositions. For each of them, the sum of the weights of the corresponding cycle covers is (−β^{2})^{l}((α − x)^{2} − β^{2})^{j}. This yields

χ_{P⃗_{n}(α)}(x) = ∑_{j=0}^{n} ∑_{l=0}^{n−j} \binom{n − l − j − 1}{j − 1}\binom{l + j}{j}(−β^{2})^{l}((α − x)^{2} − β^{2})^{j}

and with simple algebra this equals

∑_{k=0}^{2n} x^{k} \overbrace{((−1)^{k} ∑_{j=0}^{n} ∑_{l=0}^{n−j} ∑_{i=0}^{j} \binom{n − l − j − 1}{j − 1}\binom{l + j}{j}\binom{j}{i}\binom{2i}{k}(−β^{2})^{l+j−i}α^{2i−k})}^{=c_{k}^{n}} .

Now, Fact 10 yields the second claim of our theorem since Z⃗_{v,w}^{n}(m) is the entry of the m-th power of the adjacency matrix of P⃗_{n}(α), associated to v and w.

5 Further Results

5.1 Tri-diagonal Toeplitz matrices

In the literature you commonly find variants of the formulas in Theorem 4 with an additional parameter. This parameter represents different weights for the step i → i + 1 and the step i → i − 1. These different weights still yield a tridiagonal Toeplitz matrix. The spectrum and an orthonormal basis of eigenvectors are known for tridiagonal Toeplitz matrices, see [2]. Therfore, our theorem can easily be adapted to cover the more general case.

5.2 The symmetric case

For the case of symmetric lattice walks, i.e., walks on graphs, having an adjacency matrix, which is a symmetric Toeplitz matrix, we can apply Theorem 4 for the enumeration of the walks.

Let A ∈ ℝ^{(n+1)×(n+1)} be a symmetric Toeplitz matrix and let c_{0}, c_{1}, … c_{n} ∈ ℝ be its first row; A is completely determined by these values. The powers A_{(n,0)}^{k}, k = 0, …, n of the adjacency matrix of P_{n}(0) form a basis for symmetric Toeplitz matrices, in fact if a_{0}^{k}, a_{1}^{k}, … a_{n}^{k} is the first row of A_{(n,0)}^{k}, then a_{k}^{k} = 1 and a_{j}^{k} = 0 for all j > k.

Hence we can write

A = ∑_{k=0}^{n} c̃_{k} · A_{(n,0)}^{k}

and the coefficients c̃_{k} can be recursively computed as c̃_{n} = c_{n} and c̃_{k} = c_{k} − ∑_{j=k+1}^{n} c̃_{j}a_{k}^{j}.

Therefore, the orthonormal basis of eigenvectors of A_{(n,0)} is an orthonormal basis of eigenvectors of A. Furthermore the eigenvalues of A are

λ̂_{i} := ∑_{k=0}^{n−1} c̃_{k}λ_{i}^{k},

where λ_{i} are the eigenvalues of A_{(n,0)}. Since we have an orthonormal basis of eigenvectors and the corresponding eigenvalues, we can write down formulas for A that correspond to the formulas (3) and (4) for A_{(n,0)}.

5.3 Lattice walks with arbitrary positive steps

For some cases of asymmetric lattice walks, we find linear recursions. If we only allow steps i → i + j with j ∈ {−1, 0, 1, …, k} with weights c_{j} ∈ ℝ, then the adjacency matrices are of the form toep(0, …, 0, c_{−1}, c_{0}, …, c_{k}, 0, …, 0). For these, we can give linear recursions for the characteristic polynomials. With Fact 10 we obtain linear recursions for the number of corresponding lattice paths if we get a handle on the characteristic polynomial χ_{n}(x) of the n × n matrix toep(0, …, 0, c_{−1}, c_{0}, …, c_{k}, 0, …, 0).

A recursion for the characteristic polynomial can be obtained via Lemma 23. In a cycle decomposition the last vertex v_{n} belongs to a cycle v_{n} →^{−1} v_{n−1} →^{−1} … →^{−1} v_{n−j}, →^{j} v_{n} for some j. This yields the recursion

χ_{n+1}(x) = (c_{0} − x)χ_{n}(x) + ∑_{j=1}^{k} c_{−1}^{j}c_{j}χ_{n−j}(x).

For small k we can solve the linear recursion above and get an explicit representation of the characteristic polynomial. This yields an explicit linear recursion for the numbers of lattice walks.

5.4 Cylindrical lattice walks

As a last instance we now consider walks, which allow arbitrary step length (and arbitrary weights) on a cycle. Taking an edge for each allowed step we obtain a circulant graph. The “time expansion” yields a cylinder as analog to the lattice strips.

Figure 5: A circulant graph with 8 vertices and steps +1 (black) and −2 (blue).

The adjacency matrices of circulant graphs are circulant matrices. For this class of matrices eigenvalues and eigenvectors are known. According to Gray [9] they are as follows:

Theorem 25. ( Eigenvalues and -vectors of circulants, Theorem 3.1 of [9]) Let C ∈ ℝ^{n×n} a circulant matrix with first row (c_{0}, c_{1}, …, c_{n−1}) ∈ ℝ^{n}. Then the eigenvalues ψ_{m} and corresponding eigenvectors y_{m} of C for m = 0, 1, …, n − 1 are as follows:

ψ_{m} =: ∑_{k=0}^{n−1} c_{k}e^{\frac{−2πimk}{n}} , y_{m} =: \frac{1}{\sqrt{n}}(1, e^{\frac{−2πim}{n}} , e^{\frac{−2πim2}{n}} , …, e^{\frac{−2πim(n−1)}{n}}).

Note, that the eigenvectors of circulant matrices do not depend on the matrix, but only on the dimension n. Therefore, they are the same for all circulant matrices of the same size (which implies these matrices commute). Now, we can count walks on circulant graphs with the techniques from Section 2. This leads to explicit formulas as well as to linear recursions.

6 Conclusion and future work

Trigonometric sums of the form given in Theorem 4 can be handled quite well by computer algebra systems, e.g. Maple. Our impression is that indeed the formulas lead to the most effective way of evaluating the number of paths of a certain type in not too narrow and rather long strips. For narrow strips a generating function approach may be practical and superior. For short strips it can be reasonable to explicitly use the recursion (dynamic programming).

In the examples section (Section 3) we have listed some cases of integer sequences that could be obtained by counting (weighted) walks in P_{n}(α). The basic approach, however, is not limited to this case. The crucial requirement is that we are able find an explicit expression for the entries of powers of the adjacency matrix. Cases where this is possible include situations where Toeplitz matrices are substituted for the entries of a Toeplitz matrix. Investigating this and related cases should allow to count families of lattice surfaces, e.g., fillings of the cells of an n × m grid with numbers between 0 and h such that the numbers of adjacent cells differ by at most one.

Some problems remain. For example in Section 4, we found a linear recursion, but the explicit generating functions remain unknown. In Section 5.1 we quote results for band matrices with (at most) five nonzero diagonals. Improvements in this work can be directly translated back into lattice path enumeration. Section 5.3 contains linear recursions for linear recursions, can this be simplified?

Another direction might be to try to solve special families of instances that are not covered by our work. For example walks with steps i → i + k for k ∈ {−3, −1, 0, +1, +5}. Banderier and Nicodeme [1] considered some related instances. They were able to enumerate the corresponding number of lattice walks.

In general the inverses of Toeplitz matrices are interesting. If they are given we can apply Proposition 24, similar to what we did in the proof of Theorem 21. There is a lot of work in this direction, see [5] and references therein.

7 Acknowledgments

A preliminary version of this work was presented at the 7th International Conference on Lattice Path Combinatorics and Applications in Siena. There we got interesting feedback, hints to relevant literature, remarks and further ideas, which partly were included here. In particular, we thank Cyril Banderier, Christian Krattenthaler, and Helmut Prodinger for helpful remarks.

References

[1] Cyril Banderier and Pierre Nicodeme, Bounded discrete walks, In Proc. AofA’ 10, Discrete Math. Theor. Comput. Sci., 2010, pp. 35–48.

[2] Albrecht Böttcher and Sergei M. Grudsky, Spectral Properties of Banded Toeplitz Matrices, SIAM, 2005.

[3] Timothy Chow and Julian West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999), 119–128.

[4] Giovanni M. Cicuta, Marco Contedini, and Luca G. Molinari, Enumeration of simple random walks and tridiagonal matrices, J. Phys. A 35 (2002), 1125–1146.

[5] Murray Dow, Explicit inverses of Toeplitz and associated matrices, ANZIAM J. 44 (2003), 185–215.

[6] Sergi Elizalde and Toufik Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials, Discrete Math. 305 (2005), 170–189.

[7] William Feller, An Introduction to Probability Theory and its Applications, Vol. 1, John Wiley & Sons, 1968.

[8] Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009.

[9] Robert M. Gray, Toeplitz and circulant matrices: A review, Commun. Inf. Theory 2 (2005), 155–239.

[10] Katherine Humphreys, A history and a survey of lattice path enumeration, J. Statist. Plann. Inference 140 (2010), 2237–2254.

[11] Christian Krattenthaler, The enumeration of lattice paths with respect to their number of turns. In Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol., Birkhäuser, 1997, pp. 29–58.

[12] Gopal Mohanty, Lattice Path Counting and Applications, Academic Press, 1979.

[13] Aleks Owczarek and Thomas Prellberg, Enumeration of area-weighted Dyck paths with restricted height, Australas. J. Combin. 54 (2012), 13–18.

[14] Richard P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Univ. Press, 1997.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A05, 15A09, 15B05. Keywords: Catalan number, Motzkin number, transfer matrix, trigonometric sum.

(Concerned with sequence \underline{A000129}, \underline{A001519}, \underline{A005207}, \underline{A006012}, \underline{A024175}, \underline{A024537}, \underline{A080937}, \underline{A094286}, \underline{A094287}, \underline{A094288}, \underline{A124302}, and \underline{A147748}.)

Received August 6 2014; revised versions received December 3 2014; December 23 2014. Published in Journal of Integer Sequences, December 26 2014.

Return to Journal of Integer Sequences home page.