Further Results on Paths in an n-Dimensional Cubic Lattice

Rigoberto Flórez

Department of Mathematics and Computer Science

The Citadel Charleston, SC 29409

USA

rigo.florez@citadel.edu

Leandro Junes

Department of Mathematics, Computer Science and Information Systems

California University of Pennsylvania

California, PA 15419

USA

junes@calu.edu

José L. Ramírez Departamento de Matemáticas

Universidad Nacional de Colombia Bogotá Colombia

jlramirezr@unal.edu.co

Abstract

We study paths formed by integer n-tuples in an n-dimensional cubic lattice. We establish some connections between these paths, Riordan arrays, coefficients of Chebyshev polynomials of the second kind, and k-colored Motzkin paths.

1 Introduction

A three-dimensional cubic lattice is a lattice in ℝ^{3} formed by integer triplets. We study properties of three-dimensional lattice walks in the upper half of the three-dimensional cubic lattice. In particular, we count the number of paths of length k that are in three-dimensional cubic lattice beginning at the origin and ending on the xy-plane. This gives another answer to a question raised by Deutsch [5] in 2000. The problem asks: A 3-dimensional lattice walk of length n takes n successive unit steps, each in one of the six coordinate directions. How many 3-dimensional lattice walks of length n are there that begin at the origin and never go below the horizontal plane? The answer to Deutsch’s question is [1, 5]

∑_{k=0}^{n} \binom{n}{k}\binom{k}{⌈k/2⌉}4^{n−k}.

This problem generalizes, naturally, to an n-dimensional cubic lattice.

Deutsch’s problem is a generalization, to three dimensions, of the following problem proposed by Sands [24] in 1990: What is the number of different walks, in the plane, with n steps such that each step moves one unit either north, south, east, or west, starting at the origin and remaining in the upper half-plane? Hirschhorn [12] proved in 1991 that the number of such paths is \binom{2n+1}{n}. Later, Guy [9] gave a short proof of the same result. In the same paper, Guy studied this problem from the point of view of one-dimensional and two-dimensional arrays using the Pascal semi-triangle and Pascal semi-pyramid, respectively. He found some interesting relations with Catalan numbers as well as several combinatorial identities that were used in the entries of the mentioned arrays. Guy, Krattenthaler, and Sagan [10] gave combinatorial proofs for several two-dimensional results. The three-dimensional case was also studied by Guy [9].

In this paper we answer an open question that Guy proposed in [10]. Is it possible to find a closed formula for the number of paths, in the three-dimensional cube, that can not go below the plane z = 0? We give such a formula as well as other closed formulas. In addition, Nkwanta [20] generalizes several problems proposed by Sands and Deutsch to n-dimensional case using Riordan arrays. He also shows a bijection between the lattice paths of length k and k-colored Motzkin paths. In 2017, Dershowitz [6] obtained a bijection between Dyck paths and 2-dimensional lattice paths that end in the x-axis. He also considered the n-dimensional case with the same condition. We provide several relations and counting results involving walks in the n-dimensional cubic lattice and Riordan arrays.

We also study Riordan arrays from the perspective of the height of a path. The height at which a path P ends, in the n-dimensional cubic lattice, is the last value of the last n-tuple (vertex or point) of the path. For simplicity, we call this value the height of P. Those heights give rise to a Riordan array A_{3}. We have found that the entries of A_{3}^{−1} are the coefficients of Chebyshev polynomials of the second kind (shifted four units up). Using the generating function obtained from A_{3}, we find a closed formula that answers the open question given by Guy in [9]. Since A_{3} and A_{3}^{−1} are infinite matrices, we found a fractal associated to those matrices. Visually, these fractals look like half of the Sierpiński fractal.

Finally, we provide several sequences and conjectures about paths in the 3-dimensional cubic lattice. These sequences/conjectures are based on numerical experimentation.

Most proofs in this paper use generating functions that are constructed using the symbolic method introduced by Flajolet and Sedgewick [7].

2 Background

An n-dimensional cubic lattice is a lattice L in ℝ^{n} formed by points in ℤ^{n}. If p_{i} is a point in ℤ^{n} with p_{0} = (0, 0, …, 0), then a path P = (p_{0}, p_{1}, …, p_{m}) of length m is a concatenation of p_{0}, p_{1}, …, p_{m} where the distance between p_{i} and p_{i+1} is one for i ∈ {0, 1, …, m − 1}. A step in P is a pair of two consecutive points (p_{i}, p_{i+1}) for i ∈ {0, …, m − 1}. We identify the path P = (p_{0}, p_{1}, …, p_{m}) with its broken-line graph obtained by joining p_{i} to p_{i+1} with a line segment for i ∈ {0, …, m − 1}. We denote by e_{i} the n-tuple (0, …, 1, …, 0) where 1 is in the i-th position and zeros elsewhere for 1 ≤ i ≤ n. Since p_{0} = (0, 0, …, 0), we have that p_{1} = e_{i} for some 1 ≤ i ≤ n. It is easy to see that p_{j} can be written in either of the forms p_{j} = p_{j−1} + e_{r} or p_{j} = p_{j−1} − e_{r}, for some 1 ≤ r ≤ n and 1 ≤ j ≤ m. Note that e_{r} gives the orientation of the step p_{j−1}p_{j}. For example, if a path P is in ℤ^{3} with p_{5} = p_{4} + (0, 1, 0), then the step p_{4}p_{5} is parallel to the positive direction of the yaxis. Now it is easy to see that a path P = (p_{0}, p_{1}, p_{3}, …, p_{m−1}, p_{m}) can be written in the form P = (p_{0}, p_{0} ± e_{j_{1}}, p_{1} ± e_{j_{2}}, …, p_{m−1} ± e_{j_{m}}) where ± indicates the orientation of each step. For simplicity, we represent P = (p_{0}, p_{0} ± e_{j_{1}}, p_{1} ± e_{j_{2}}, …, p_{m−1} ± e_{j_{m}}) as P = (±e_{j_{1}})(±e_{j_{2}}) ⋯ (±e_{j_{m}}) and we say that (±e_{j_{1}}), (±e_{j_{2}}), …, (±e_{j_{m}}) are the components of P, (see Figures 1 and 2).

We use C_{n}^{±}(k) to mean the set of all paths of length k in the n-dimensional cubic lattice. We divide C_{n}^{±}(k) into subfamilies depending on the behavior of the path. We now give definitions and notation for those families. If P = (±e_{j_{1}})(±e_{j_{2}}) ⋯ (±e_{j_{k}}), then we define V_{r} := (±e_{j_{1}})+(±e_{j_{2}})+⋯+(±e_{j_{r}}), the algebraic combination of the first r components of P for 0 < r ≤ k, i.e., V_{r} is the sum of the components of any initial subpath of P with r steps. We denote C_{n}(k) the subset of C_{n}^{±}(k) formed by all paths P = (±e_{j_{1}})(±e_{j_{2}}) ⋯ (±e_{j_{k}}) that satisfy that the nth coordinate of V_{k} is zero. We use C_{n}^{≥}(k) to denote all paths in C_{n}^{±}(k) with P = (±e_{j_{1}})(±e_{j_{2}}) ⋯ (±e_{j_{k}}) and that nth coordinate of V_{r} is non-negative for all 0 < r ≤ k. We now let C_{n}^{+}(k) be C_{n}^{≥}(k) ∩ C_{n}(k). Finally, we let C_{n} = ⋃_{i=0}^{∞} C_{n}(i); C_{n}^{≥} = ⋃_{i=0}^{∞} C_{n}^{≥}(i) and C_{n}^{+} = ⋃_{i=0}^{∞} C_{n}^{+}(i).

For example, Figure 1 depicts the 14 paths in C_{2}^{+}(3). Figure 2 depicts the 17 paths in C_{3}^{+}(2).

One of the goals of this paper is to study the enumerate problem of the families of lattice paths C_{n}^{+}(k), C_{n}(k), C_{n}^{≥}(k) and C_{n}^{±}(k). Most of the proofs in this paper are done using generating functions according to paths length.

Figure 1: All paths of C_{2}^{+}(3).

3 Special case of Generating function for paths in a cube

In this section we count paths in the three-dimensional cube. We classify those paths in families. For example, we have the family of paths where each path never goes below of the plane z = 0 but ends on it. There is a family of paths where each path goes below z = 0 and ends on it. There is another family of paths where each path ends above the plane z = 0 and so on. Therefore, we divide the section in several subsections depending on the nature of the family of paths.

3.1 Counting paths that never go below the horizontal plane

The main theorem in this section counts the total number of lattice paths of length m, in the three-dimensional cube that end at the xy-plane and never go below it. The proof uses generating functions (the technique used to obtain the generating function is based on the symbolic method introduced in [7]). We give some necessary notation. We denote by a_{3}(m) the total number of paths of length m in C_{3}^{+}(m). That is, a_{3}(m) = |C_{3}^{+}(m)|.

Theorem 1. If C_{n} is the nth Catalan number, then

(1) the generating function for the total number of paths of length i in C_{3}^{+} is given by

T_{3}(z) := ∑_{i=0}^{∞} a_{3}(i)z^{i} = \frac{1 − 4z − \sqrt{1 − 8z + 12z^{2}}}{2z^{2}} ,  (1)

Figure 2: All paths of C_{3}^{+}(2).

(2) the number of paths, in the three-dimensional cube, of length m that end in the horizontal plane and never go below it is given by

a_{3}(m) = ∑_{i=0}^{⌊m/2⌋} C_{i}\binom{m}{2i}4^{m−2i}.

Proof. From the first return decomposition a nonempty three-dimensional lattice path P in C_{3}^{+} may be decomposed using one of the following forms

e_{3}P′(−e_{3})P′′; e_{1}P′; −e_{1}P′; e_{2}P′; −e_{2}P′,

where P′ and P′′ are paths (possibly empty) in C_{3}^{+} (see Figure 3).

Figure 3: Factoring a path P in C_{3}^{+}.

Using the symbolic method we obtain

T_{3}(z) = z^{2}T_{3}^{2}(z) + 4zT_{3}(z) + 1.  (2)

This proves part (1).

Proof of part (2): It is easy to see that

T_{3}(z) = \frac{1}{1 − 4z} · \frac{1 − \sqrt{1 − 4z^{2}/(1 − 4z)^{2}}}{2z^{2}/(1 − 4z)^{2}} = \frac{1}{1 − 4z} · \frac{1 − \sqrt{1 − 4u}}{2u} = \frac{1}{1 − 4z} · C(u), (3)

where u = z^{2}/(1 − 4z)^{2} and C(z) is the generating function of the Catalan numbers. Thus,

C(z) := ∑_{n=0}^{∞} C_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} .

Hence,

T_{3}(z) = ∑_{i=0}^{∞} C_{i} (\frac{z^{2i}}{(1 − 4z)^{2i+1}} ) = ∑_{i=0}^{∞} ∑_{m=0}^{∞} C_{i}\binom{m + 2i}{m}4^{m}z^{2i+m}.

If we take s = 2i + m, then

T_{3}(z) = ∑_{i=0}^{∞} ∑_{s=2i}^{∞} C_{i}\binom{s}{s − 2i}4^{s−2i}z^{s}.

This proves part (2), completing the proof of the theorem.

The following sequence gives some values for the total number of paths of length 0 − 9 in the three-dimensional cube, that end at the xy-plane and never go below the mentioned plane. From (2) it is easy to see that

a_{3}(1) = 1, and a_{3}(n) = 4a_{3}(n − 1) + ∑_{i=1}^{n−1} a_{3}(i − 1)a_{3}(n − i − 1).

This sequence appears in OEIS as \underline{A005572} [28]. So, a_{3}(m) for m = 0, 1, …, 9 is given by

1, 4, 17, 76, 354, 1704, 8421, 42508, 218318, 1137400.

3.2 Riordan arrays for paths in three-dimensional space

We give an informal definition of height of a path P in C_{3}^{≥}(n). It is the third entry of the last vertex (point) of the path. That is, the value of the z coordinate of the ending point. In this section we construct an infinite matrix using the height of all paths in C_{3}^{≥}(n). The resulting matrix becomes a Riordan array. Theorem 6 gives a relationship between the sum of the entries on the nth rising diagonal of the Riordan array (found in this section) and the number of paths in C_{3}^{+} with no level steps at height 0 (it means no steps on the xyplane). We also provide a formula (given a length) that counts the total number of paths, in three-dimensional cube, that never go below to xy-plane. Several authors have used Riordan arrays as a technique to study lattice paths (see for example [3, 15, 20, 21, 22, 27]).

3.2.1 A short background about Riordan arrays

We recall that an infinite lower triangular matrix is called a (proper) Riordan array [26] if its kth column satisfies the generating function g(z) (f(z))^{k} for k ≥ 0, where g(z) and f(z) are formal power series with g(0) ≠ 0, f(0) = 0 and f′(0) ≠ 0. The matrix corresponding to the pair f(z), g(z) is denoted by (g(z), f(z)). If we multiply (g, f) by a column vector (c_{0}, c_{1}, …)^{T} with the generating function h(z), then the resulting column vector has generating function gh(f). This property is known as the Fundamental Theorem of Riordan arrays or summation property.

The product of two Riordan arrays (g(z), f(z)) and (h(z), l(z)) is defined by

(g(z), f(z)) ∗ (h(z), l(z)) = (g(z)h (f(z)) , l (f(z))) .

We recall that the set of all Riordan matrices is a group under the operator “ ∗ ” [26]. The identity element is I = (1, z), and the inverse of (g(z), f(z)) is

(g(z), f(z))^{−1} = (1/ (g ∘ \overline{f}) (z), \overline{f}(z)) ,  (4)

where \overline{f}(z) is the compositional inverse of f(z).

Rogers [23] introduced the concept of an A-sequence. Specifically, Rogers observed that every element d_{n+1,k+1} of a Riordan matrix (not belonging to 0 row or 0 column) could be expressed as a linear combination of the elements in the preceding row. Merlini et al. [14] introduced the Z-sequence, which characterizes 0 column, except for the element d_{0,0}. Therefore, the A-sequence, Z-sequence and the element d_{0,0} completely characterize a proper Riordan array. Summarizing, we have the following theorem.

Theorem 2 ([14]). An infinite lower triangular array D = [d_{n,k}]_{n,k∈ℕ} is a Riordan array if and only if d_{0,0} ≠ 0 and there are sequences A = (a_{0} ≠ 0, a_{1}, a_{2}, …) and Z = (z_{0}, z_{1}, z_{2}, …) such that if n, k ≥ 0, then

d_{n+1,k+1} = a_{0}d_{n,k} + a_{1}d_{n,k+1} + a_{2}d_{n,k+2} + ⋯,
d_{n+1,0} = z_{0}d_{n,0} + z_{1}d_{n,1} + z_{2}d_{n,2} + ⋯,

or equivalently

g(z) = \frac{g(0)}{1 − zZ(g(z))} and f(z) = z(A(f(z))),

where A and Z are the generating functions of the A-sequence and Z-sequence, respectively.

3.2.2 A Riordan array from heights of paths

If P = (±e_{j_{1}})(±e_{j_{2}}) ⋯ (±e_{j_{k}}) is a path in the n-dimensional cube, then the height of P is the nth coordinate of V_{k} where V_{k} = (±e_{j_{1}}) + (±e_{j_{2}}) + ⋯ + (±e_{j_{k}}) is the algebraic combination of all components of P. We denote by A_{3}(n, k) the subset of C_{3}^{±}(n) of all paths having height k and not passing below the plane z = 0. If a_{3}(n, k) denotes |A_{3}(n, k)| and b_{3}(n) denotes |C_{3}^{≥}(n)|, then a_{3}(n) = a_{3}(n, 0) and b_{3}(n) = ∑_{k=0}^{n} a_{3}(n, k). Note that the last component of the last step of any path in A_{3}(n, k) is one element of {±e_{1}, ±e_{2}, ±e_{3}}. Therefore, a_{3}(n, k) satisfies the following third order recurrence relation.

a_{3}(n, k) = a_{3}(n − 1, k − 1) + 4a_{3}(n − 1, k) + a_{3}(n − 1, k + 1)  (5)

with n, k ≥ 1, and the initial values a_{3}(0, 0) = 1 and a_{3}(n, k) = 0 if k > n (see Guy [9]). This sequence gives rise to an infinite lower triangular matrix. It is denoted by A_{3} = [a_{3}(n, k)]_{n,k≥0}. So,

A_{3} = [a_{3}(n, k)]_{n,k≥0} = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 17 & 8 & 1 & 0 & 0 & 0 & 0 & 0 \\ 76 & 50 & 12 & 1 & 0 & 0 & 0 & 0 \\ 354 & 288 & 99 & 16 & 1 & 0 & 0 & 0 \\ 1704 & 1605 & 700 & 164 & 20 & 1 & 0 & 0 \\ 8421 & 8824 & 4569 & 1376 & 245 & 24 & 1 & 0 \\ 42508 & 48286 & 28476 & 10318 & 2380 & 342 & 28 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}] .

From Theorem 2 we can prove that the matrix A_{3} is a Riordan matrix. Guy [9] also found a relation between this matrix and the sequences \underline{A005572}, \underline{A005573}, \underline{A052177}, \underline{A052178} and \underline{A052179}.

Theorem 3. The infinite triangular matrix A_{3} = [a_{3}(n, k)]_{n,k≥0} has a Riordan array expression given by

A_{3} = (T_{3}(z), zT_{3}(z)) ,

where

T_{3}(z) = \frac{1 − 4z − \sqrt{1 − 8z + 12z^{2}}}{2z^{2}} .

Proof. From the recurrence relation (5), we know that the A-sequence is (1, 4, 1, 0, 0, …). Therefore, A(z) = 1 + 4z + z^{2}. This implies that f(z) = z(1 + 4f(z) + f(z)^{2}). Therefore,

f(z) = \frac{1 − 4z − \sqrt{1 − 8z + 12z^{2}}}{2z} = zT_{3}(z).

Now, it is easy to see that the generating function of the 0th column is T_{3}(x).

The proof of Theorem 3 shows that the Riordan array A_{3} has A-sequence (1, 4, 1). Merlini et al. [18] studied a lattice path model in the plane that has an associated Riordan matrix with A-sequence (a, b, c). Merlini and Sprugnoli [16] study again this type model. In Section 5, we show a relationship between the coloured Motzkin path and the paths in the n-dimensional cube.

Corollary 4. In the three-dimensional cube the following hold:

(1) the generating function for the total number of paths of length i in C_{3}^{≥} is given by

H_{3}(z) := ∑_{i=0}^{∞} b_{3}(i)z^{i} = \frac{T_{3}(z)}{1 − zT_{3}(z)} = \frac{1 − 6z − \sqrt{1 − 8z + 12z^{2}}}{2z(6z − 1)} ,

(2) the number of paths of length m such that the paths never go below the horizontal plane is given by

b_{3}(m) = ∑_{n=0}^{m} \begin{aligned}⌊ & \frac{m−n}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{n + 2k + 1}{k}\binom{m}{n + 2k} (\frac{n + 1}{n + 2k + 1}) 4^{m−n−2k}.

Proof. From the Fundamental Theorem of Riordan arrays we have

(T_{3}(z), zT_{3}(z)) \frac{1}{1 − z} = \frac{T_{3}(z)}{1 − zT_{3}(z)} = ∑_{n=0}^{∞} ∑_{k=0}^{n} a_{3}(n, k)z^{n} = ∑_{n=0}^{∞} b_{3}(n)z^{n} = H_{3}(z).

After simplification we obtain the result that proves part (1).

Proof of part (2): It is easy to see that

H_{3}(z) = \frac{T_{3}(z)}{1 − zT_{3}(z)} = \frac{(1/(1 − 4z)) C(u)}{1 − (z/(1 − 4z)) C(u)},

where u = z^{2}/(1 − 4z)^{2} and C(z) is the generating function of the Catalan numbers. Therefore,

H_{3}(z) = \frac{1}{1 − 4z} ∑_{n=0}^{∞} (\frac{z}{1 − 4z} )^{n} C^{n+1}(u).

From [8, equation 5.70] we know that

C^{n}(z) = ∑_{k=0}^{∞} \binom{n + 2k}{k}\frac{n}{n + 2k} z^{k}.  (6)

This implies that

H_{3}(z) = ∑_{n=0}^{∞} ∑_{k=0}^{∞} \binom{n + 2k + 1}{k} (\frac{n + 1}{n + 2k + 1}) (\frac{z^{n}}{(1 − 4z)^{n+1}} ) u^{k}

= ∑_{n=0}^{∞} ∑_{k=0}^{∞} \binom{n + 2k + 1}{k} (\frac{n + 1}{n + 2k + 1}) (\frac{z^{n+2k}}{(1 − 4z)^{n+2k+1}} )

= ∑_{n=0}^{∞} ∑_{k=0}^{∞} ∑_{l=0}^{∞} \binom{n + 2k + 1}{k}\binom{n + 2k + l}{l} (\frac{n + 1}{n + 2k + 1}) 4^{l}z^{n+2k+l}.

This with t = n + 2k + l implies

H_{3}(z) = ∑_{n=0}^{∞} ∑_{k=0}^{∞} ∑_{t=n+2k}^{∞} \binom{n + 2k + 1}{k}\binom{t}{n + 2k} (\frac{n + 1}{n + 2k + 1}) 4^{t−n−2k}z^{t}.

Therefore,

b_{3}(m) = [z^{m}]H_{3}(z) = ∑_{n=0}^{m} \begin{aligned}⌊ & \frac{m−n}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{n + 2k + 1}{k}\binom{m}{n + 2k} (\frac{n + 1}{n + 2k + 1}) 4^{m−n−2k}.

This proves part (2).

The following sequence gives some values for the total number of paths of length 0 − 9 in three-dimensional cube that never go below the xy-plane. This sequence appears in OEIS as \underline{A005573}. So, b_{3}(m) for m = 0, 1, …, 9 is given by

1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838.

The previous theorem gives a closed formula that answers Guy’s question. Theorem 5 gives a closed formula for all entries of A_{3}.

Theorem 5. If m and n are non-negative integers, then

a_{3}(n, k) = \frac{k + 1}{n + 1} ∑_{l=0}^{⌊ \frac{n−k}{2} ⌋} \binom{n + 1}{n − k − l}\binom{n − k − l}{l}4^{n−k−2l}.

Proof. Let M(z) = zT_{3}(z) then from (2) we obtain

M(z) = z(M(z)^{2} + 4M(z) + 1) = zP (z),

where P (z) = z^{2} + 4z + 1. From the Lagrange Inversion Formula (cf. [17])

a_{3}(n, k) = [z^{n}] (z^{k}T_{3}(z)^{k+1}) = [z^{n+1}]M(z)^{k+1}

= \frac{k + 1}{n + 1}[z^{n−k}] (z^{2} + 4z + 1)^{n+1}

= \frac{k + 1}{n + 1}[z^{n−k}] (∑_{i=0}^{n+1} \binom{n + 1}{i}z^{i}(z + 4)^{i})

= \frac{k + 1}{n + 1}[z^{n+1}] (∑_{i=0}^{n+1} ∑_{l=0}^{i} \binom{n + 1}{i}\binom{i}{l}4^{i−l}z^{i+l+k+1})

= \frac{k + 1}{n + 1}[z^{n+1}] (∑_{m=0}^{2n+2} ∑_{l=0}^{⌊ \frac{m}{2} ⌋} \binom{n + 1}{m − l}\binom{m − l}{l}4^{m−2l}z^{m+k+1}) .

If we take m = n − k, we obtain the desired result.

Theorem 6. In the three-dimensional cube the following hold:

(1) the generating function U_{3}(z) for the total number of paths of length i in C_{3}^{+} with no level steps at height 0 is given by

U_{3}(z) := ∑_{n=0}^{∞} u_{3}(n)z^{n} = \frac{1}{1 − z^{2}T_{3}(z)},

(2) the sum of entries of the rising diagonal of the Riordan array A_{3} = [a_{3}(n, k)]_{n,k≥0} is

u_{3}(n + 2) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋} a(n − i, i).

Proof. From the first return decomposition a nonempty three-dimensional lattice path P in C_{3}^{+} with no level steps at height 0 may be decomposed as e_{3}P′(−e_{3})P′′ where P′ and P′′ are three dimensional lattice paths (possibly empty) in C_{3}^{+} such that P′′ does not have level steps at height 0. Then

U_{3}(z) = 1 + z^{2}T_{3}(z)U_{3}(z).

This proves part (1).

Proof of part (2): From the definition of the Riordan array we have

L(z) = ∑_{n=0}^{∞} ∑_{k=0}^{∞} a(n − k, k)z^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{∞}[z^{n−k}]gf^{k}z^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{∞} gf^{k}z^{k}

= \frac{g}{1 − zf} = \frac{T_{3}(z)}{1 − z^{2}T_{3}(z)}.

Therefore, comparing coefficients we get that

U_{3}(z) = z^{2}L(z) + 1.

This proves part (2).

The following sequence gives some values for the total number of paths of length 0 − 10 in paths C_{3}^{+} with no level steps at height 0. This sequence appears in OEIS as \underline{A185132}. So, u_{3}(n) for n = 0, 1, …, 10 is given by

1, 4, 18, 84, 405, 2004, 10126, 52048, 271338, 1431400, 7627348.

3.2.3 The inverse matrix of the Riordan array

Since A_{3} = [a_{3}(n, k)]_{n,k≥0} is a Riordan matrix and the set of all Riordan matrices is a group, the inverse matrix of A_{3} exists. So, it is natural to ask: what properties does the inverse matrix of A_{3} satisfy? In this section we analyze the inverse matrix A_{3}^{−1} and in particular, we study the combinatorial interpretation of the unsigned entries of the matrix A_{3}^{−1}. We found that there is a combinatorial relation between the entries of A_{3}^{−1} and the words over the alphabet {0, 1, 2, 3}. There is also another relation between the matrix A_{3}^{−1} and the matrix of coefficients of Chebyshev’s polynomials of the second kind. Finally we present two fractals resulting from both matrices A_{3} and A_{3}^{−1}.

From (4) we obtain that the inverse matrix A_{3}^{−1} is given by the Riordan matrix

F̃ := [f̃(n, k)]_{n,k≥0} = A_{3}^{−1} = (\frac{1}{1 + 4z + z^{2}} , \frac{z}{1 + 4z + z^{2}} ) .  (7)

In general if a Riordan matrix [a_{n,k}]_{n,k≥0} = (g(z), f(z)) is given, then the alternating Riordan matrix defined by [(−1)^{n+k}a_{n,k}]_{n,k≥0} can be found by the product of Riordan matrices as follows

(1, −z)(g(z), f(z))(1, −z) = (g(−z), −f(−z)).

Now from (7) it is easy to see that g(z) = 1/(1 + 4z + z^{2}) and f(z) = z/(1 + 4z + z^{2}). Therefore,

F := [f(n, k)]_{n,k≥0} := [(−1)^{n+k}f̃(n, k)]_{n,k≥0} = (\frac{1}{1 − 4z + z^{2}} , \frac{z}{1 − 4z + z^{2}} ) .

We now express this matrix explicitly as follows (see also \underline{A207823}).

F = [f(n, k)]_{n,k≥0} = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 15 & 8 & 1 & 0 & 0 & 0 & 0 & 0 \\ 56 & 46 & 12 & 1 & 0 & 0 & 0 & 0 \\ 209 & 232 & 93 & 16 & 1 & 0 & 0 & 0 \\ 780 & 1091 & 592 & 156 & 20 & 1 & 0 & 0 \\ 2911 & 4912 & 3366 & 1200 & 235 & 24 & 1 & 0 \\ 10864 & 21468 & 17784 & 8010 & 2120 & 330 & 28 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}] .

From the Fundamental Theorem of Riordan arrays we have

F (x, y) := ∑_{n=0}^{∞} ∑_{m=0}^{∞} f(n, m)x^{m}z^{n} = (\frac{1}{1 − 4z + z^{2}} , \frac{z}{1 − 4z + z^{2}} ) \frac{1}{1 − xz}

= \frac{1}{1 − (4 + x)z + z^{2}} .

Therefore, the element f(n, m) satisfies the following recurrence relation.

f(n, m) = 4f(n − 1, m) + f(n − 1, m − 1) − f(n − 2, m),  (8)

with n, m ≥ 1, and the initial values f(0, 0) = 1 and f(n, m) = 0 if m > n.

Note that from [11, Theorems 4.1 and 4.2] we obtain generating functions for the Asequence and the Z-sequence of the Riordan array F̃ (and therefore for F). So, we have

AF̃(z) = \frac{z}{zT_{3}(z)} = \frac{1 − 4z + \sqrt{1 − 8z + 12z^{2}}}{2}
ZF̃(z) = \frac{1}{zT_{3}(z)}(1 − T_{3}(z)) = \frac{−1 − 4z + \sqrt{1 − 8z + 12z^{2}}}{2z}

and

A_{F}(z) = \frac{z}{zT_{3}(−z)} = \frac{1 + 4z + \sqrt{1 + 8z + 12z^{2}}}{2}
= 1 + 4z − z^{2} + 4z^{3} − 17z^{4} + 76z^{5} − 354z^{6} + 1704z^{7} − 8421z^{8} + ⋯

Z_{F}(z) = \frac{1}{zT_{3}(−z)}(1 − T_{3}(−z)) = \frac{−1 + 4z + \sqrt{1 + 8z + 12z^{2}}}{2z}
= 4 − z + 4z^{2} − 17z^{3} + 76z^{4} − 354z^{5} + 1704z^{6} − 8421z^{7} + ⋯

Therefore, the element f(n, m) can be calculated by a complex linear combination of elements in the previous row:

f(n + 1, k + 1) = f(n, k) + 4f(n, k + 1) − f(n, k + 2) + 4f(n, k + 3) − 17f(n, k + 4) + ⋯

This observation was made by the anonymous referee. The generating function A_{F}(z) can be also obtain from Theorem 3.2 of [14].

We observe that the matrix F is related to the coefficients of Chebyshev polynomials of the second kind U_{n}(x). Recall that those polynomials are defined recursively as follows: U_{0}(x) = 1, U_{1}(x) = 2x and U_{n}(x) = 2xU_{n−1}(x) − U_{n−2}(x) for n ≥ 2. Equivalently,

U_{n}(x) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix}(−1)^{k}\binom{n − k}{k}(2x)^{n−2k}  (9)

= ∑_{k=0}^{n}(−1)^{(n−k)/2}\binom{(n + k)/2}{k} (\frac{1 + (−1)^{n−k}}{2} ) (2x)^{k}.  (10)

The ordinary generating function of the polynomials U_{n}(x) is

U(x, z) := ∑_{n=0}^{∞} U_{n}(x)z^{n} = \frac{1}{1 − 2xz + z^{2}} .

Thus,

U (\frac{x + 4}{2}, z) = \frac{1}{1 − (x + 4)z + z^{2}} = F (x, y).

Therefore, this proves the following theorem. Theorem 7. If m and n are non-negative integers, then

f(n, m) = u(n, m), where u(n, m) = [z^{n}x^{m}]U ((x + 4)/2, z) .

The following theorem gives an explicit expression for the entries f(n, m). Theorem 8. If m and n are non-negative integers, then

f(n, m) = ∑_{k=m}^{n}(−1)^{(n−k)/2}\binom{(n + k)/2}{k}\binom{k}{m} (\frac{1 + (−1)^{n−k}}{2} ) 4^{k−m}.

Proof. Theorem 7 and Equation (10) imply that

f(n, m) = [x^{m}]U_{n} (\frac{x + 4}{2})

= [x^{m}] ∑_{k=0}^{n}(−1)^{(n−k)/2}\binom{(n + k)/2}{k} (\frac{1 + (−1)^{n−k}}{2} ) (x + 4)^{k}

= [x^{m}] ∑_{k=0}^{n} ∑_{j=0}^{k}(−1)^{(n−k)/2}\binom{(n + k)/2}{k}\binom{k}{j} (\frac{1 + (−1)^{n−k}}{2} ) 4^{k−j}x^{j}

= [x^{m}] ∑_{j=0}^{n} [∑_{k=j}^{n}(−1)^{(n−k)/2}\binom{(n + k)/2}{k}\binom{k}{j} (\frac{1 + (−1)^{n−k}}{2} ) 4^{k−j}] x^{j}

= ∑_{k=m}^{n}(−1)^{(n−k)/2}\binom{(n + k)/2}{k}\binom{k}{m} (\frac{1 + (−1)^{n−k}}{2} ) 4^{k−m}.

This completes the proof.

Using the combinatorial interpretation given in the sequence \underline{A261711} we obtain the following theorem. Theorem 9. The entry f(n, m) of the matrix F counts the number of words over the alphabet Σ := {0, 1, 2, 3} of length n + m having exactly m occurrences of the word 01.

Proof. Let g(n, m) be the number of words over the alphabet Σ := {0, 1, 2, 3} of length n + m with exactly m occurrences of the word 01. For example, g(3, 2) = 12 with the words being

      01010       01011       01012       01013       01001       01101
      01201       01301       00101       10101       20101       30101.

We show that g(n, m) satisfies the recurrence relation given in (8) with the same initial values. Let w be a word over the alphabet Σ where w has length n + m and with exactly m occurrences of the word 01. Thus, |w| = n + m and |w|_{01} = m (the number of 01’s in w). The word w can be written in the form w = w_{1}a where a and w are words over Σ with |a| = 1, |w_{1}| = n + m − 1 and |w_{1}|_{01} = m, then there are 4g(n − 1, m) ways. However, we have to subtract the cases where the last symbol of w_{1} is 0 and a = 1. In this case we have g(n − 2, m) ways.

On the other hand, the word w can also be written as w = w_{1}01 with |w_{1}| = n + m − 2 and |w_{1}|_{01} = m − 1. So, there are g(n − 1, m − 1) ways to do it. Hence,

g(n, m) = 4g(n − 1, m) − g(n − 2, m) + g(n − 1, m − 1) for n, m ≥ 1.

It is easy to see that that g(0, 0) = 1 and g(n, m) = 0 for m > n. Therefore, this holds g(n, m) = f(n, m).

3.2.4 Fractals from the Riordan arrays

A natural question for infinite numerical arrays is: what is the parity behavior between the entries of the numerical array? (See, for example, the Sierpiński fractal.) Trying to answer this question for our matrices A_{3} and A_{3}^{−1} we evaluated (using Mathematica^{◯^{R}}) their entries mod 2 and we found two interesting fractals (see Figure 4). An easy way to construct both fractals –without using Mathematica^{◯^{R}}– is as follows. The entries of the fractal in Figure 4 part (a) are obtained by evaluating the equation (5) mod 2. The entries of the fractal in Figure 4 part (b) are obtained by evaluating the equation (8) mod 2. Merlini and Nocentini [13] have studied some relations between Riordan arrays and fractal patterns.

3.3 Counting paths in three-dimensional cube

The main theorem of this section counts the total number of paths, in three-dimensional cube, of length m that end in the horizontal plane. Again the proof uses generating functions.

Theorem 10. In the three-dimensional cube the following hold:

(1) the generating function for the total number of paths of length i in C_{3} is given by

G_{3}(z) := ∑_{i=0}^{∞} g_{3}(i)z^{i} = \frac{1}{\sqrt{1 − 8z + 12z^{2}}} ,

Figure 4: (a) Matrix A_{3} mod 2 (b) Matrix A_{3}^{−1} mod 2.

(2) the number of paths, in three-dimensional cube, of length m that end in the horizontal plane is given by

g_{3}(m) = \frac{1}{2^{m}} ∑_{k=0}^{m} \binom{2m − 2k}{m − k}\binom{2k}{k}3^{k}.

Proof. From the first return decomposition a nonempty three-dimensional lattice path T in C_{3} may be decomposed as

e_{3}P (−e_{3})T′; (−e_{3})P (e_{3})T′; e_{1}T′; −e_{1}T′; e_{2}T′; −e_{2}T′,

where P is a path (possibly empty) in C_{3}^{+} and T′ is a path (possibly empty) in C_{3}. Therefore,

G_{3}(z) = 2z^{2}T_{3}(z)G_{3}(z) + 4zG_{3}(z) + 1.

So, from equation (1) on page 4 we obtain

G_{3}(z) = \frac{1}{1 − 4z − 2z^{2}T_{3}(z)} = \frac{1}{\sqrt{1 − 8z + 12z^{2}}} .  (11)

This proves part (1).

Proof of part (2): Noe [19] showed that

∑_{i=0}^{∞} T_{i}x^{i} = \frac{1}{\sqrt{1 − 2bx − (b^{2} − 4c)x^{2}}} ,

where

T_{n} = \frac{1}{4^{n}} ∑_{k=0}^{n} \binom{2n − 2k}{n − k}\binom{2k}{k}(b + 2\sqrt{c})^{k}(b − 2\sqrt{c})^{n−k}.

Therefore, setting b = 4 and c = 1 we obtain the equation in part (2), completing the proof of the theorem.

Note that the number g_{3}(m) is equal to the generalized central trinomial coefficient of (1 + 4x + x^{2})^{n}. Then

g_{3}(n) = ∑_{k=0}^{⌊n/2⌋} \binom{2k}{k}\binom{n}{2k}4^{n−2k}.

This sequence appears in OEIS as \underline{A081671}. So, g_{3}(n) for n = 0, 1, …, 10 is given by

1, 4, 18, 88, 454, 2424, 13236, 73392, 411462, 2325976, 13233628.

In the following theorem we obtain another formula to the sequence g_{3}(m).

Theorem 11. The number of paths, in three-dimensional cube, of length m that end in the horizontal plane is given by

g_{3}(m) = 4^{m} + ∑_{n=1}^{m} \begin{aligned}⌊ & \frac{m−2n}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{n + 2k}{k}\binom{s}{2n + 2k} (\frac{n}{n + 2k} ) 2^{2m−4k−3n}.

Proof. The Equations (3) and (11) imply that

G_{3}(z) = \frac{1}{1 − 4z − 2z^{2}T_{3}(z)} = \frac{1}{1 − 4z − 2z^{2} (1/(1 − 4z)) C(u)}

= \frac{1}{1 − 4z} (\frac{1}{1 − 2uC(u)}) = \frac{1}{1 − 4z} ∑_{n=0}^{∞}(2uC(u))^{n},

where u = z^{2}/(1 − 4z)^{2} and C(z) is the generating function of the Catalan numbers. From identity (6) we have

G_{3}(z) = \frac{1}{1 − 4z} + ∑_{n=1}^{∞} ∑_{k=0}^{∞} \binom{n + 2k}{k} (\frac{n}{n + 2k} ) (\frac{z^{2n+2k}}{(1 − 4z)^{2n+2k+1}} ) 2^{n}

= \frac{1}{1 − 4z} + ∑_{n=1}^{∞} ∑_{k=0}^{∞} ∑_{l=0}^{∞} \binom{n + 2k}{k}\binom{2n + 2k + l}{l} (\frac{n}{n + 2k} ) 2^{n+2l}z^{2n+2k+l}.

This with t = 2n + 2k + l implies that

G_{3}(z) = \frac{1}{1 − 4z} + ∑_{n=1}^{∞} ∑_{k=0}^{∞} ∑_{l=t−2n−2k}^{∞} \binom{n + 2k}{k}\binom{t}{2n + 2k} (\frac{n}{n + 2k} ) 2^{2t−3n−4k}z^{t}.

Therefore,

[z^{m}]G_{3}(z) = 4^{m} + ∑_{n=1}^{m} \begin{aligned}⌊ & \frac{m−2n}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{n + 2k}{k}\binom{m}{2n + 2k} (\frac{n}{n + 2k} ) 2^{2m−3n−4k}.

This proves the theorem.

Theorem 12 studies the case in which a path does not need to end in the horizontal plane. That is, we study the family of paths in C_{3}^{±}. Theorem 12 was originally proved by Guy.

Theorem 12. In three-dimensional cube it holds that

(1) The generating function for the total number of paths of length i in C_{3}^{±} is given by

W_{3}(z) := ∑_{i=0}^{∞} w_{3}(i)z^{i} = \frac{1}{1 − 6z} ,

(2) the number of paths, in three-dimensional cube, of length m is given by

w_{3}(m) = 6^{m}.

Proof. First of all we note that from the first return decomposition a nonempty threedimensional lattice path J in C_{3}^{±} may be decomposed as

e_{3}J′; (−e_{3})J′; e_{1}J′; (−e_{1})J′; e_{2}J′; (−e_{2})J′,

where J′ is a path (possibly empty) in C_{3}^{±}. Therefore, we have that

W_{3}(z) = 6zW_{3}(z) + 1.

Therefore

W_{3}(z) = \frac{1}{1 − 6z} .

This proves part (1) and (2).

4 Generating functions for paths in the n-space

In this section we generalize the results given in Section 3 for paths in three-dimensional cube to paths in the n-dimensional cube. In Section 3 we classify the families of paths depending on the plane z = 0. The generalization is focused depending on the hyperplane x_{n} = 0. Since the results here are a natural generalization of Section 3, we omit some details. Whoever is interested in these problems from the point of view of Riordan arrays can see Nkwanta [20].

Theorem 13. If C_{n} is the nth Catalan number, then

(1) the generating function for the total number of paths of length i in C_{n}^{+} is given by

T_{n}(z) := ∑_{i=0}^{∞} a_{n}(i)z^{i} = \frac{1 − 2(n − 1)z − \sqrt{1 − 4(n − 1)z + 4(n − 2)nz^{2}}}{2z^{2}}

= \frac{1}{1 − 2(n − 1)z − \frac{z^{2}}{1 − 2(n − 1)z − \frac{z^{2}}{1 − 2(n − 1)z − \frac{z^{2}}{...}}}}

(2) the number of paths in C_{n}^{+}(m) is given by

a_{n}(m) = ∑_{i=0}^{⌊m/2⌋} C_{i}\binom{m}{2i}(2(n − 1))^{m−2i}.  (12)

Proof. We prove part (1), the proof of part (2) is similar to Theorem 1 and we omit it. From the first return decomposition a nonempty n-dimensional lattice path P in C_{n}^{+} may be decomposed as

e_{n}P′(−e_{n})P′′, ±e_{1}P′, ±e_{2}P′, …, ±e_{n−1}P′,

where P′ is a path (possibly empty) in C_{n}^{+}.

Therefore

T_{n}(z) = z^{2}T_{n}^{2}(z) + 2(n − 1)zT_{n}(z) + 1.

This proves part (1).

For example, if n = 2, we obtain

T_{2}(z) = \frac{1 − 2z − \sqrt{1 − 4z}}{2z^{2}} = ∑_{n=0}^{∞} C_{n+1}z^{n}.

Therefore, a_{2}(m) = C_{m+1}, where C_{m} is the mth Catalan number. Moreover, from Equation (12) we get

C_{m+1} = ∑_{i=0}^{⌊m/2⌋} C_{i}\binom{m}{2i}2^{m−2i}.

This identity is known as Touchard’s formula. In 2017 Dershowitz [6] found a bijection between the paths of C_{2}^{+} and Dyck paths.

If a_{n}(m, k) is the total number of lattice paths with height k in C_{n}^{+}(m), then a_{n}(m, k) satisfies the third order recurrence relation

a_{n}(m, k) = a_{n}(m − 1, k − 1) + 2(n − 1)a_{3}(m − 1, k) + a_{3}(m − 1, k + 1).

Therefore, the infinite triangular matrix A_{n} = [a_{n}(m, k)]_{m,k≥0} has the Riordan array expression

A_{n} = (T_{n}(z), zT_{n}(z)) ,

with A-sequence equal to (1, 2(n − 1), 1).

Theorem 14. In the n-dimensional cube the following hold:

(1) the generating function for the total number of paths of length i in C_{n}^{≥} is given by

H_{n}(z) := ∑_{i=0}^{∞} b_{n}(i)z^{i} = \frac{T_{n}(z)}{1 − zT_{n}(z)}

= \frac{1 − 2nz − \sqrt{1 − 4(n − 1)z + 4(n − 2)nz^{2}}}{2z(2nz − 1)}
= \frac{1}{1 − 2(n − 1)z − \frac{z^{2}}{1 − 2(n − 1)z − \frac{z^{2}}{1 − 2(n − 1)z − \frac{z^{2}}{...}}}}

(2) the number of paths that belong to C_{n}^{≥}(m) is given by

b_{n}(m) = ∑_{i=0}^{m} \begin{aligned}⌊ & \frac{m−i}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{i + 2k + 1}{k}\binom{m}{i + 2k} (\frac{i + 1}{i + 2k + 1}) (2(n − 1))^{m−2k−i}.  (13)

Proof. We prove part (1), the proof of part (2) is analogous to the proof of Corollary 4 and we omit it.

From the first return decomposition a nonempty n-dimensional lattice path P in C_{n}^{≥} may be decomposed as P′, P′e_{n}H′ where P′ is a path (possibly empty) in C_{n}^{+} and H′ is a path (possibly empty) in C_{n}^{≥}.

Therefore

H_{n}(z) = T_{n}(z) + zT_{n}(z)H_{n}(z).

This proves part (1).

It is easy to see that using Guy [9, Equation (1)], the Equation (13) for n = 2 becomes

b_{2}(m) = \binom{2m + 1}{m} = ∑_{i=0}^{m} \begin{aligned}⌊ & \frac{m−i}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{i + 2k + 1}{k}\binom{m}{i + 2k} (\frac{i + 1}{i + 2k + 1}) 2^{m−2k−i}.

Theorem 14 part (2) with n = 3 proves the the problem 10795 [5]. This problem was originally proposed by Deutsch and solved by Brawner [1] (without using generating functions).

Theorem 15. In the n-dimensional cube the following hold:

(1) the generating function for the total number of paths of length i in C_{n} is given by

G_{n}(z) := ∑_{i=0}^{∞} g_{n}(i)z^{i} = \frac{1}{\sqrt{1 − 4(n − 1)z + 4(n − 2)nz^{2}}} ,

(2) the number of paths, in three-dimensional cube, of length m that end in the horizontal plane is given by

g_{n}(m) = \frac{1}{2^{m}} ∑_{k=0}^{m} \binom{2m − 2k}{m − k}\binom{2k}{k}n^{k}(n − 2)^{n−k}.

Theorem 16. In the n-dimensional cube the following hold:

(1) the generating function for the total number of paths of length i in C_{n}^{±} is given by

W_{n}(z) := ∑_{i=0}^{∞} w_{n}(i)z^{i} = \frac{1}{1 − 2nz} ,

(2) the number of paths, in the n-dimensional cube, of length m is given by

w_{n}(m) = (2n)^{m}.

5 A relation with the k-colored Motzkin paths

A Motzkin path of length n is a lattice path of ℤ × ℤ running from (0, 0) to (n, 0) that never passes below the x-axis and whose permitted steps are the up diagonal step U = (1, 1), the down diagonal step D = (1, −1) and the horizontal step H = (1, 0), called rise, fall, and level step, respectively. The number of Motzkin paths of length n is the nth Motzkin number m_{n}, (see \underline{A001006}). A grand Motzkin path of length n is a Motzkin path without the condition that it never passes below the x-axis. The number of grand Motzkin paths of

n Sequence  A-Sequence
2 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796  \underline{A000108}
3 1, 4, 17, 76, 354, 1704, 8421, 42508, 218318  \underline{A005572}
4 1, 6, 37, 234, 1514, 9996, 67181, 458562, 3172478 \underline{A025230}
5 1, 8, 65, 536, 4482, 37968, 325509, 2821400  -
Table 1: Sequence a_{n}(m) for n = 2, 3, 4, 5.

length n is the nth grand Motzkin number gm_{n} (see \underline{A002426}). A k-colored Motzkin path is a Motzkin path such that each horizontal step is colored with one of k specific colors. The number of k-colored Motzkin paths of length n is the nth k-colored Motzkin number m_{k,n}. The generating functions of these type of lattices where also studied by Callan [2]. Analogously, we have k-colored grand Motzkin paths, the number of k-colored grand Motzkin paths of length n is denoted by gm_{k,n}.

It is easy to obtain a bijection between the 4-colored Motzkin paths of length m and three-dimensional lattice path of C_{3}^{+}(m). That is, we identify the north-east step (U) with e_{3} = (1, 0, 0), the south-east step (D) with −e_{3} and the 4-colored horizontal steps with ±e_{1} and ±e_{2}. Therefore, we obtain Theorem 17 (it was proved originally by Nkwanta using Riordan arrays). By similar reasons as we obtained Theorem 17, we obtain also Theorem 18. From Theorem 13 part (2), the bijection given in Theorem 17 and the recurrence relation given in [29] (see also [25]) we obtain the Corollary 19.

Theorem 17. The number of lattice paths of length k in C_{n}^{+} is equal to the number of 2(n − 1)-colored Motzkin paths of length k. Thus, a_{n}(k) = m_{2(n−1),k}.

Theorem 18. The number of lattice paths of length k in C_{n} is equal to the number of 2(n − 1)-colored grand Motzkin paths of length k. Thus, g_{n}(k) = gm_{2(n−1),k}.

Corollary 19. The numbers a_{n}(m) given in Theorem 13 part (2), satisfy the recurrence relation

(m + 2)a_{n}(m) = 2(n − 1)(2m + 1)a_{n}(m − 1) + (6 − 2n)(m − 1)a_{n}(m − 2).

6 Tables and sequences from experimentation

From formula (12) we obtain the Table 1 (see Theorem 1 part (2), Theorem 13). That is, we show the first few terms of the sequence a_{n}(m) for n = 2, 3, 4, 5. Note that a_{2}(3) = 14 and a_{3}(3) = 17, (see Figures 1 and 2). From Theorem 14 part (2) we obtain the Table 2. That is, we show the first few terms of the sequence b_{n}(m) for n = 2, 3, 4, 5. From Theorem 15 part (2) we obtain the Table 3. That is, we show the first few terms of the sequence g_{n}(m) for n = 2, 3, 4, 5. Note that the sequence \underline{A098410} is equal to the number of paths from (0, 0) to (n, 0) using steps U = (1, 1), H = (1, 0) and D = (1, −1), the H steps can have 6 colors.

n Sequence  A-Sequence
2 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716  \underline{A001700}
3 1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838  \underline{A005573}
4 1, 7, 50, 363, 2670, 19846, 148772, 1122995, 8525398, 65030706  -
5 1, 9, 82, 755, 7014, 65658, 618612, 5860611, 55784710, 533147438  -
Table 2: Sequence b_{n}(m) for n = 2, 3, 4, 5.
n Sequence  A-Sequence
2 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620 \underline{A000984}
3 1, 4,18, 88, 454, 2424, 13236, 73392, 411462 \underline{A081671}
4 1, 6, 38, 252, 1734, 12276, 88796, 652728 \underline{A098410}
5 1, 16, 258, 4192, 68614, 1130976, 18766356  -
Table 3: Sequence g_{n}(m) for n = 2, 3, 4, 5.

Proposition 20. For k ≥ 1, the number of paths in C_{3}^{+}(k) that are completely contained in the xy-plane is 4^{k}.

Proposition 20 is easy to prove, we omit it. Motivated by Proposition 20, we have the following conjectures. Conjecture 1: For k ≥ 1, the number of paths in C_{3}^{+}(k) that are completely contained in the xz−plane is (see Table 4 first line)

∑_{i=1}^{k+1} \frac{\binom{2 i}{i} \binom{k}{i−1}}{i + 1}.

Conjecture 2: For k ≥ 1, the number of paths in C_{3}^{+}(k) that are completely contained in the yz−plane is

∑_{i=1}^{k+1} \frac{\binom{2 i}{i}\binom{k}{i−1}}{i + 1}.

For the Conjecture 1 see Table 4 first line and for the Conjecture 2 see Table 4 second line. Notice that first and second lines in Tables 4 are exactly the same.

The following sequences/conjectures are based on our experimentation. We do not prove and/or provide any closed formulas for any of them here. We leave them as conjectures for future work.

If we define the altitude of a path P in C_{3}^{+}(k) as the largest z-value of all the points in P, then we have the following conjecture. Conjecture 3: The number of paths in C_{3}^{+}(k) that have altitude 1 is

\frac{3^{k}}{2} − 4^{k} + \frac{5^{k}}{2} .

plane  Sequence  A-Sequence
xz-plane 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369 \underline{A002212}(k + 1)
yz-plane 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369 \underline{A002212}(k + 1)

Table 4: Paths in C_{3}^{+}(k) completely contained in the xz-plane or the yz-plane.

h Sequence  A-Sequence
0 4, 16, 64, 256, 1024, 4096, 16384, 65536 \underline{A002212}
1 0, 1, 12, 97, 660, 4081, 23772, 133057, 724260 \underline{A016753}
2 0, 0, 0, 1, 20, 243, 2324, 19271, 145404  -
3 0, 0, 0, 0, 0, 1, 28, 453, 5556  -

Table 5: All paths of altitude h in C_{3}^{+}(k).

We say that a path P = (p_{0}, p_{1}, …, p_{k}) in C_{3}^{+}(k) has a right corner, if there are three points p_{i}, p_{i+1}, p_{i+2} ∈ \{p_{0}, p_{1}, …, p_{k}\} such that the vectors \overrightarrow{p_{i}p_{i+1}} and \overrightarrow{p_{i+1}p_{i+2}} are perpendicular. Using this definition, we have Table 6.

We say that a path P = (p_{0}, p_{1}, …, p_{k}) in C_{3}^{+}(k) has an overlap, if there are four points p_{i}, p_{i+1}, p_{i+2}, p_{i+3} ∈ {p_{0}, p_{1}, …, p_{k}} such that p_{i} = p_{i+3} and p_{i+1} = p_{i+2}. Using this definition, we have Table 7.

Remark 21. Some of the results of this paper were discovered by using the counting automata methodology (see De Castro et al. [4]).

7 Acknowledgments

The authors thank the referees for their comments which helped to improve the article. The first author was partially supported by The Citadel Foundation and the Mathematics department of Universidad Sergio Arboleda. The last author started working on this project when he was in a short research visit at The Citadel.

r Sequence  A-Sequence
0 4, 9, 16, 34, 64, 133, 256, 526, 1024  -
1 0, 8, 40, 112, 304, 736, 1768, 4048, 9232  -
2 0, 0, 20, 136, 552, 1808, 5380, 14760, 38936  -
3 0, 0, 0, 72, 512, 2576, 9856, 33832, 104832  -

Table 6: All paths in C_{3}^{+}(k) with exactly “r” right corners.

t Sequence  A-Sequence
0 4, 12, 40, 152, 608, 2476, 10240, 42972, 182904  -
1 0, 5, 32, 132, 580, 2764, 13420, 64260, 306388  -
2 0, 0, 4, 65, 416, 2052, 10448, 55688, 297516  -
3 0, 0, 0, 5, 96, 953, 6212, 34904, 197824  -

Table 7: All paths in C_{3}^{+}(k) with exactly “t” overlaps.

References

[1] J. Brawner, Three-dimensional lattice walks in the upper half-space, solution of problem #10795, Amer. Math. Monthly, 108 (2001), 980.

[2] D. Callan, On generating functions involving the square root of a quadratic polynomial, J. Integer Seq. 10 (2007), Article 07.5.2.

[3] G. S. Cheon, H. Kim, and L. W. Shapiro, A generalization of Lucas polynomial sequence, Discrete Appl. Math. 157 (2009), 920–927.

[4] R. De Castro, A. Ramírez, and J. L. Ramírez, Applications in enumerative combinatorics of infinite weighted automata and graphs, Sci. Ann. Comput. Sci. 24 (2014), 137–171.

[5] E. Deutsch, Problem #10795: Three-dimensional lattice walks in the upper half-space, Amer. Math. Monthly, 107 (2000), 367.

[6] N. Dershowitz, Touchard’s Drunkard, J. Integer Seq. 20 (2017), Article 17.1.5.

[7] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge, 2009.

[8] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.

[9] R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Seq. 3 (2000), Article 00.1.6.

[10] R. K. Guy, C. Krattenthaler, and B. Sagan, Lattice paths, reflections, and dimensionchanging bijections, Ars Combin. 34 (1992), 3–15.

[11] T-X. He and R. Sprugnoli, the, Discrete Appl. Math. 309 (2009), 3962–3974.

[12] M. Hirschhorn, Problem 1517, Crux Mathematicorum 17 (1991), 119–122.

[13] D. Merlini and M. Nocentini, Patterns in Riordan arrays, Second International Symposium on Riordan Arrays and Related Topics, Lecco, Italy, 2015.

[14] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canadian J. Math. 49 (1997), 301–320.

[15] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math. 91 (1999), 197–213.

[16] D. Merlini and R. Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Math. 340 (2017), 160–174.

[17] D. Merlini, R. Sprugnoli, and M. C. Verri, Lagrange inversion: when and how, Acta Appl. Math. 94 (2006), 233–249.

[18] D. Merlini, R. Sprugnoli, and M. C. Verri, Algebraic and combinatorial properties of simple, coloured walks, in Trees in Algebra and Programming: Prod. CAAP 1994, Lecture Notes in Comput. Sci., Vol. 787, Springer, 1994, pp. 218–233.

[19] T. D. Noe, On the divisibility of generalized central trinomial coefficients, J. Integer Seq. 9 (2006), Article 06.2.7.

[20] A. Nkwanta, Riordan matrices and higher-dimensional lattice walks, J. Statist. Plann. Inference, 140 (2010), 2321–2334.

[21] J. L. Ramírez and V. F. Sirvent, A generalization of the k-bonacci sequence from Riordan arrays, Electron. J. Combin. 22 (2015), Art. P1.38.

[22] J. L. Ramírez and V. F. Sirvent, Generalized Schröder matrix and its combinatorial interpretation, Linear Multilinear Algebra, In Press, 2017.

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

[24] B. Sands, Problem 1517, Crux Mathematicorum, 16 (1990), 44.

[25] M. Schork, On the recursion relation of Motzkin numbers of higher rank, Online J. Anal. Comb. 2 (2007).

[26] L. W. Shapiro, S. Getu, W. Woan, and L. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[27] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[28] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[29] W. Woan, A recursive relation for weighted Motzkin, J. Integer Seq. 8 (2005), Article 05.1.6.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19, 15A24. Keywords: lattice paths, Riordan arrays, combinatorial proof.

(Concerned with sequences

\underline{A000108}, \underline{A000984}, \underline{A001006}, \underline{A001700}, \underline{A002426}, \underline{A005572}, \underline{A005573}, \underline{A025230},\underline{A052177}, \underline{A052178}, \underline{A052179}, \underline{A081671}, \underline{A098410}, \underline{A185132}, \underline{A207823}, \underline{A261711})

Received April 16 2017; revised versions received October 11 2017; November 20 2017. Published in Journal of Integer Sequences, December 20 2017.

Return to Journal of Integer Sequences home page.