Sequences Involving Square Zig-Zag Shapes

László Németh Institute of Mathematics University of Sopron Bajcsy Zs. u. 4 Sopron H9400 Hungary

              nemeth.laszlo@uni-sopron.hu

László Szalay Department of Mathematics University J. Selye Hradná str. 21 Komárno 945 01 Slovakia and Institute of Mathematics University of Sopron Bajcsy Zs. u. 4 Sopron H9400 Hungary

              szalay.laszlo@uni-sopron.hu

Abstract

We define a so-called square k-zig-zag shape as a part of the regular square grid. Considering the shape as a k-zig-zag digraph, we give values of its vertices according to the number of the shortest paths from a base vertex. It provides several integer sequences, whose higher-order homogeneous recurrences are determined by the help of a special matrix recurrence.

1 Introduction

The present paper studies diagonal and zig-zag paths on a particular k +1 wide, infinite part of the usual square lattice, and along these paths we determine linear recurrence sequences that are mostly defined in the On-Line Encyclopedia of Integer Sequences (OEIS, [9]) without combinatorial interpretations. In this manner our investigation, among others, gives them geometrical and combinatorial background. The consideration of zig-zag shapes is not an isolated challenge. For example, Baryshnikov and Romik [2] examined the so-called Young diagrams, which are similar to our construction, and defined a kind of ‘zig-zag’ numbers by the help of the alternating permutations. Stanley [10] published a survey in which he dealt with the ‘zig-zag’ shapes and the alternating permutations. Recently, Ahmad et al. [1] studied some graph-theoretic properties of special zig-zag polyomino chains.

This article proceeds our work on the variants of Pascal’s arithmetic triangle for which there are several approaches to generalize or extend (see, for instance, [4]). One recent variation is called hyperbolic Pascal triangles, see [3], where we described how to construct them as we follow and generalize the connection between the classical Pascal triangle and the Euclidean regular square mosaic. The principal idea behind is to leave the Euclidean plane because in the hyperbolic plane there exist infinitely many regular mosaics. These are characterized by Schläfli’s symbol {p, q}, where p and q denote two positive integers (p, q ≥ 3). The parameters indicate that for regular p-gons of cardinality exactly q meet at each vertex. A well-defined part of each regular mosaic leads to an infinite graph such that each vertex possesses a value, giving the number of distinct shortest paths from the fixed base vertex. The structured version of the graph with labeled vertices is called hyperbolic Pascal triangle.

More generally, if we consider an infinite connected graph G, the number of the shortest paths from a fixed base vertex to the other vertices analogously generates its ‘G-Pascal triangle’. In this paper, we present a natural family of graphs called zig-zag shape, and investigate its properties, especially the ‘G-Pascal triangle’ of the graph. In this sense, we give a non-trivial example of ‘G-Pascal triangles’, which may be the object of further studies.

Returning to the hyperbolic Pascal triangle linked to mosaic {4, 5} one finds the Fibonacci sequence (\underline{A000045} in the OEIS [9]) by going along a specific zig-zag path. The authors proved in [3, 7] that all the integer linear homogeneous recurrence sequences {f_{i}}_{i≥0} defined by

f_{i} = αf_{i−1} ± f_{i−2}, (i ≥ 2),

where α ∈ ℕ, α ≥ 2, and f_{0} < f_{1} are positive integers with gcd(f_{0}, f_{1}) = 1, appear along corresponding zig-zag paths in this hyperbolic Pascal triangle. This interesting result also inspired us to examine zig-zag paths on certain parts of the Euclidean square mosaic.

2 Square zig-zag shapes

Consider the Euclidean square lattice and take k consecutive pieces of squares. This is the 0th layer of the k–zig-zag shape. The upper corners are the 1st, 2nd, …, kth and (k + 1)st vertices according to Figure 1. Extend this by an extra 0th vertex, which is the base vertex. We color it by yellow in the figures, and we join it to the 1st vertex by an extra edge. We denote the vertices of the 0th line by small boxes in Figure 1. Now move the 0the layer to reach the right-down position in the square lattice to obtain the 1st layer, and repeat this procedure with the latest layer infinitely many times. Thus, we define the square k–zig-zag shape or graph, where k ≥ 1 is the size of the array. Finally, we label the vertices such that a label gives the number of different shortest paths from the base vertex. Figure 2 illustrates the first few layers of the square 4–zig-zag digraph, the vertices are denoted by shaded boxes with their label values and the directed edges are the black arrows. (Certain black arrows are re-colored by red for some reason. There are also particular blue arrows in the Figure; their role will be discussed later.) Let a_{i,j} denote the label of the vertice located in ith row and jth position (0 ≤ j ≤ k + 1, 0 ≤ i). Clearly, the fundamental rule of the construction is given by

a_{i,j} = \begin{cases}1, & if i = 0; \\ a_{i−1,1}, & if j = 0, 1 ≤ i; \\ a_{i,j−1} + a_{i−1,j+1}, & if 1 ≤ j ≤ k, 1 ≤ i; \\ a_{i,k}, & if j = k + 1, 1 ≤ i. \end{cases}  (1)

For fixed k ≥ 1 and given 0 ≤ j ≤ k + 1, let A_{j}^{(k)} be the sequence defined by A_{j}^{(k)} = (a_{i,j})_{i=0}^{∞}. The sequence A_{j}^{(k)} is the jth right-down diagonal sequence of the square k–zig-zag shape. In Figure 2, the blue arrows represent the sequence A_{1}^{(4)}. We found A_{0}^{(k)} = (1, A_{1}^{(k)}) and A_{k}^{(k)} = A_{k+1}^{(k)}.

Let Z_{j}^{(k)}, j ∈ {0, 1, …, k} be the jth zig-zag sequence of the square k–zig-zag shape, where Z_{j}^{(k)} is the merged sequence of A_{j}^{(k)} and A_{j+1}^{(k)}. (In Figure 2, the red arrows represent the zig-zag sequence Z_{3}^{(4)}.) More precisely, Z_{j}^{(k)} = (z_{i,j})_{i=0}^{∞}, where

z_{i,j} = \begin{cases}a_{ℓ,j}, & if i = 2ℓ; \\ a_{ℓ,j+1}, & if i = 2ℓ + 1. \end{cases}  (2)

Since Z_{0}^{(k)} and Z_{k}^{(k)} are the ‘double’ of A_{0}^{(k)} and A_{k}^{(k)}, respectively, usually we examine sequences for j ∈ {1, 2, …, k − 1}.

Now we record the two main theorems of this paper. The second one is a simple corollary of the first one.

Theorem 1 (Main 1). Given k ≥ 1. Then all the right-down diagonal sequences A_{j}^{(k)} for j ∈ \{0, 1, …, k, k + 1\} have the same (⌊\frac{k}{2}⌋ + 1)-th order homogeneous linear recurrence relation

a_{n,j} = \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix}(−1)^{i}\binom{k + 1 − i}{i + 1}a_{n−1−i,j}, n ≥ ⌊\frac{k}{2}⌋ + 1.

Figure 1: Zig-zag shape Figure 2: Square 4–zig-zag digraph (k = 4)

Theorem 2 (Main 2). Fixing k ≥ 1, the zig-zag sequences Z_{j}^{(k)} for j ∈ {0, 1, …, k} satisfy a (2 ⌊\frac{k}{2}⌋ + 2)-th order homogeneous linear recurrence relation given by

z_{n,j} = \begin{matrix}⌊ & \frac{k}{2} & ⌋ \\ ∑ \\ i=0 \end{matrix}(−1)^{i}\binom{k + 1 − i}{i + 1}z_{n−1−2i,j}, n ≥ 2 ⌊\frac{k}{2}⌋ + 2.

For example, in case k = 4 (see Figure 2) the sequences

\begin{aligned}A_{0}^{(4)} & = (1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, …) & = & \underline{A080937}, \\ A_{1}^{(4)} & = (1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, …) & = & \underline{A080937} (i ≥ 1), \\ A_{2}^{(4)} & = (1, 3, 9, 28, 89, 286, 924, 2993, 9707, 31501, …) & = & \underline{A094790}, \\ A_{3}^{(4)} & = (1, 4, 14, 47, 155, 507, 1652, 5373, 17460, 56714, …) & = & \underline{A094789}, \\ A_{4}^{(4)} & = (1, 5, 19, 66, 221, 728, 2380, 7753, 25213, 81927, …) & = & \underline{A005021}, \end{aligned}

possess the common recurrence relation

a_{n,j} = 5a_{n−1,j} − 6a_{n−2,j} + a_{n−3,j}, n ≥ 3,

and

Z_{1}^{(4)} = (1, 1, 2, 3, 5, 9, 14, 28, 42, 89, 131, 286, 417, …)  = not in the OEIS,
Z_{2}^{(4)} = (1, 1, 3, 4, 9, 14, 28, 47, 89, 155, 286, 507, 924, …)  = \underline{A006053} (i ≥ 3),
Z_{3}^{(4)} = (1, 1, 4, 5, 14, 19, 47, 66, 155, 221, 507, 728, 1652, …) = not in the OEIS,

all satisfy the recursive rule

z_{n,j} = 5z_{n−2,j} − 6z_{n−4,j} + z_{n−6,j},  n ≥ 6.  (3)

For more examples see Section 6. Remark 3. The orders of recurrence relations in Theorem 1 and 2 are not always minimal. Some sequences could have lower order, for example, the minimal recurrence relation of the sequence Z_{2}^{(4)} is z_{n,j} = z_{n−1,j} + 2z_{n−2,j} − z_{n−3,j}. Of course, its 6-order extension is (3).

3 Recurrence relations of the square zig-zag shapes

First look at Figure 3 and the fundamental rule (1). We find that any item a_{n,j}, (n ≥ 1) is the sum of the certain items of (n − 1)st row. More precisely, if 0 < j < k + 1, then

a_{n,j} = a_{n−1,j+1} + a_{n,j−1} = a_{n−1,j+1} + a_{n−1,j} + a_{n,j−2} = ⋯ = ∑_{ℓ=1}^{j+1} a_{n−1,ℓ}.  (4)

Consider (4) for all j ∈ {1, 2, …, k + 1}. We obtain the system

a_{n,1} = a_{n−1,1} + a_{n−1,2} ; a_{n,2} = a_{n−1,1} + a_{n−1,2} + a_{n−1,3} ; a_{n,3} = a_{n−1,1} + a_{n−1,2} + a_{n−1,3} + a_{n−1,4} ; ⋮ ; a_{n,k−1} = a_{n−1,1} + a_{n−1,2} + a_{n−1,3} + a_{n−1,4} + ⋯ + a_{n−1,k−1} + a_{n−1,k} ; a_{n,k} = a_{n−1,1} + a_{n−1,2} + a_{n−1,3} + a_{n−1,4} + ⋯ + a_{n−1,k−1} + a_{n−1,k} + a_{n−1,k+1} ; a_{n,k+1} = a_{n−1,1} + a_{n−1,2} + a_{n−1,3} + a_{n−1,4} + ⋯ + a_{n−1,k−1} + a_{n−1,k} + a_{n−1,k+1}, (5)

which includes homogenous linear recurrence sequences.

Figure 3: Two consecutive rows

In matrix form

v_{n} = M · v_{n−1}, n ≥ 1,

where

v_{n} = ( a_{n,1} ; a_{n,2} ; a_{n,3} ; ⋮ ; a_{n,k} ; a_{n,k+1}) , v_{0} = (1 1 1 ⋮ 1 1) , and M^{(k+1)×(k+1)} = (\begin{matrix}1 & 1 & 0 & 0 & ⋯ & 0 & 0 \\ 1 & 1 & 1 & 0 & ⋯ & 0 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 0 & 0 \\ 1 & 1 & 1 & 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 \end{matrix}) .

We know from [6, Lemma 6] that the characteristic polynomial of any recurrence sequence (r) defined by the linear combination of the recurrence sequences (a_{j}) = (a_{i,j})_{i≥0} of system (5), moreover the characteristic polynomial of the coefficient matrix M of system (5) coincide. (The reader find a more precise theorem in [8].) Consequently, we have to determine the characteristic polynomial p_{k}(x) of M, and then p_{k}(x) yields the common recurrence relation of the sequences {a_{j}} and their linear combinations.

Since

p_{k}(x) = |xI − M|,

where I is the appropriate unit matrix, we obtain

p_{0}(x) = x − 1,
p_{1}(x) = |\begin{matrix}x − 1 & −1 \\ −1 & x − 1 \end{matrix}| = x^{2} − 2x,

and

p_{k}(x) = |\begin{matrix}x − 1 & −1 & 0 & 0 & ⋯ & 0 & 0 \\ −1 & x − 1 & −1 & 0 & ⋯ & 0 & 0 \\ −1 & −1 & x − 1 & −1 & ⋯ & 0 & 0 \\ −1 & −1 & −1 & x − 1 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ −1 & −1 & −1 & −1 & ⋯ & x − 1 & −1 \\ −1 & −1 & −1 & −1 & ⋯ & −1 & x − 1 \end{matrix}|_{(k+1)×(k+1)}

= |\begin{matrix}x & −1 & 0 & 0 & ⋯ & 0 & 0 \\ −x & x & −1 & 0 & ⋯ & 0 & 0 \\ 0 & −x & x & −1 & ⋯ & 0 & 0 \\ 0 & 0 & −x & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ⋯ & x & −1 \\ 0 & 0 & 0 & 0 & ⋯ & −x & x − 1 \end{matrix}|_{(k+1)×(k+1)}

= x · |\begin{matrix}x & −1 & 0 & ⋯ & 0 & 0 \\ −x & x & −1 & ⋯ & 0 & 0 \\ 0 & −x & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x & −1 \\ 0 & 0 & 0 & ⋯ & −x & x − 1 \end{matrix}|_{k×k} + |\begin{matrix}−x & −1 & 0 & ⋯ & 0 & 0 \\ 0 & x & −1 & ⋯ & 0 & 0 \\ 0 & −x & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & x & −1 \\ 0 & 0 & 0 & ⋯ & −x & x − 1 \end{matrix}|_{k×k}

= x · p_{k−1}(x) − x · |\begin{matrix}x & −1 & ⋯ & 0 & 0 \\ −x & x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & x & −1 \\ 0 & 0 & ⋯ & −x & x − 1 \end{matrix}|_{(k−1)×(k−1)}

= x · p_{k−1}(x) − x · p_{k−2}(x).

In the calculation above, first we subtracted the second column of the determinant from the first column, then we subtracted the third column from the second one, and so on. Secondly, we expanded the determinant by its first row. Thirdly, we expanded the second determinant by its first column. Finally, for p_{k}(x) we have the binary recurrence relation

p_{k}(x) = x · p_{k−1}(x) − x · p_{k−2}(x).  (6)

To derive the explicit form of p_{k}(x) we solve the characteristic equation z^{2} − xz + x = 0 of (6). Note that the left-hand side is a quadratic polynomial in z. The solutions are z_{1} = \frac{1}{2}(x + \sqrt{x(x − 4)}) and z_{2} = \frac{1}{2}(x − \sqrt{x(x − 4)}).

By the fundamental theorem of homogenous linear recurrences p_{k}(x) = αz_{1}^{k} + βz_{2}^{k}, where α and β are determined by the linear equation system

p_{0}(x) = α + β,
p_{1}(x) = αz_{1} + βz_{2}.

Obviously,

\begin{aligned}α & = \frac{1}{2} \frac{x^{2} − 5x + 4 + (x − 3)\sqrt{x(x − 4)}}{x − 4}, \\ β & = \frac{1}{2} \frac{x^{2} − 5x + 4 − (x − 3)\sqrt{x(x − 4)}}{x − 4}. \end{aligned}  (7)

Hence we have proved the following theorem.

Theorem 4. The characteristic polynomial p_{k}(x) has degree k+1, it satisfies (6), its explicit formula with (7) is

p_{k}(x) = α (\frac{1}{2}(x + \sqrt{x(x − 4)}))^{k} + β (\frac{1}{2}(x − \sqrt{x(x − 4)}))^{k} .

Because each recurrence coefficient in (6) is one of ±x, the factorization of p_{k}(x) contains a factor x^{m} for some positive integer m. The next theorem provides, among others, the precise exponent m in the factorization of p_{k}(x).

Theorem 5. The characteristic polynomials p_{k}(x) can be given by

p_{k}(x) = x^{⌈^{\frac{k}{2}}⌉} ∑_{i=0}^{⌊\frac{k}{2}⌋+1}(−1)^{i}\binom{k + 2 − i}{i}x^{⌊^{\frac{k}{2}}⌋+1−i}, k ≥ 0.

Proof. Observe that ⌈\frac{k}{2}⌉ + ⌊\frac{k}{2}⌋ = k, and ⌊\frac{k}{2}⌋ + 1 = ⌊\frac{k+2}{2}⌋. Put n := k + 2. Thus,

p_{n−2}(x) = ∑_{i=0}^{⌊n/2⌋} \binom{n − i}{i}(−1)^{i}x^{n−1−i} = \frac{1}{x} ∑_{i=0}^{⌊n/2⌋} \binom{n − i}{i}x^{n−2i}(−x)^{i}.

Now we shall apply Theorem 1 of [5], but first, for the convenience of the readers we present it in

Lemma 6 ([5, Theorem 1]). The terms of the sequence (T_{n})_{n} given by

T_{n+1} = ∑_{i=0}^{⌊(n−p)/(q+r)⌋} \binom{n − qi}{p + ri}x^{n−p−(q+r)i}y^{p+ri}

satisfy the linear recurrence relation

T_{n} − x\binom{r}{1}T_{n−1} + x^{2}\binom{r}{2}T_{n−2} + ⋯ + (−1)^{r}x^{r}\binom{r}{r}T_{n−r} = y^{r}T_{n−r−q}.

We choose the parameters of Lemma 6 as r = q = 1, p = 0, and y = −x. Hence the terms T_{n+1} = ∑_{i=0}^{⌊n/2⌋} \binom{n−i}{i}(−x)^{i}x^{n−2i} satisfy T_{n} = xT_{n−1}+(−x)T_{n−2} for n ≥ 3. Consequently, p_{k}(x) = T_{n−2}(x)/x implies

p_{k+2}(x) = xp_{k+1} − xp_{k},  k ≥ 1.  (8)

Since the initial polynomials are

p_{0}(x) = \frac{1}{x}T_{3}(x) = \frac{1}{x}(x^{2} − x) = x − 1, and p_{1}(x) = \frac{1}{x}T_{4}(x) = \frac{1}{x}(x^{3} − 2x^{2}) = x^{2} − 2x,

then (8) is true for k = 0, too.

For example, the first few characteristic polynomials are

\begin{aligned}p_{0}(x) & = x − 1, \\ p_{1}(x) & = x(x − 2), \\ p_{2}(x) & = x(x^{2} − 3x + 1), \\ p_{3}(x) & = x^{2}(x^{2} − 4x + 3), \\ p_{4}(x) & = x^{2}(x^{3} − 5x^{2} + 6x − 1), \\ p_{5}(x) & = x^{3}(x^{3} − 6x^{2} + 10x − 4), \\ p_{6}(x) & = x^{3}(x^{4} − 7x^{3} + 15x^{2} − 10x + 1), \\ p_{7}(x) & = x^{4}(x^{4} − 8x^{3} + 21x^{2} − 20x + 5), \\ p_{8}(x) & = x^{4}(x^{5} − 9x^{4} + 28x^{5} − 35x^{2} + 15x − 1), \\ p_{9}(x) & = x^{5}(x^{5} − 10x^{4} + 36x^{3} − 56x^{2} + 35x − 6), \\ p_{10}(x) & = x^{5}(x^{6} − 11x^{5} + 45x^{4} − 84x^{3} + 70x^{2} − 21x + 1). \end{aligned}

4 Proofs of the main theorems

4.1 Right-down diagonal sequences

Now we are ready to give the recurrences of the right-down diagonal sequences A_{j}^{(k)} by the help of Theorem 5.

Theorem 7. In case of a fixed j we have the recurrence relation

0 = ∑_{i=0}^{⌊\frac{k}{2}⌋+1}(−1)^{i}\binom{k + 2 − i}{i}a_{n−i,j},  n ≥ ⌊\frac{k}{2}⌋ + 1, 0 ≤ j ≤ k + 1.  (9)

Proof. Recall that p_{k}(x) is not only the characteristic polynomial of M but also of any recurrence sequence of system (5), moreover, of any linear combination sequence of them.

This is why, if we substitute the power x^{i} by a_{i,j} in p_{k}(x) = 0 in Theorem 5, then since x ≠ 0, we get

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

Expressing the item a_{n,j} from recurrence equation (9) we obtain the result of Theorem 1. For example, the first few recurrence relations are

\begin{aligned}k = 0 : & a_{n,j} & = a_{n−1,j}, \\ k = 1 : & a_{n,j} & = 2a_{n−1,j}, \\ k = 2 : & a_{n,j} & = 3a_{n−1,j} − a_{n−2,j}, \\ k = 3 : & a_{n,j} & = 4a_{n−1,j} − 3a_{n−2,j}, \\ k = 4 : & a_{n,j} & = 5a_{n−1,j} − 6a_{n−2,j} + a_{n−2,j}, \\ k = 5 : & a_{n,j} & = 6a_{n−1,j} − 10a_{n−2,j} + 4a_{n−2,j}, \\ k = 6 : & a_{n,j} & = 7a_{n−1,j} − 15a_{n−2,j} + 10a_{n−2,j} − a_{n−3,j}, \\ k = 7 : & a_{n,j} & = 8a_{n−1,j} − 21a_{n−2,j} + 20a_{n−2,j} − 5a_{n−3,j}, \\ k = 8 : & a_{n,j} & = 9a_{n−1,j} − 28a_{n−2,j} + 35a_{n−2,j} − 15a_{n−3,j} + a_{n−3,j}, \\ k = 9 : & a_{n,j} & = 10a_{n−1,j} − 36a_{n−2,j} + 56a_{n−2,j} − 35a_{n−3,j} + 6a_{n−4,j}, \\ k = 10 : & a_{n,j} & = 11a_{n−1,j} − 45a_{n−2,j} + 84a_{n−2,j} − 70a_{n−3,j} + 21a_{n−4,j} − a_{n−5,j}. \end{aligned}

4.2 Zig-zag sequences

Theorem 2 is the simple corollary of Theorem 1. Indeed, we only merge two sequences satisfying the same recurrence relation. Hence the statement is obvious.

5 Sum of rows, columns, and left-down diagonal sequences

Let R^{(k)} = (r_{n}^{(k)}) be the sum sequence of the values of the nth row of square k–zig-zag shape. Considering the partial sum relation (4) we obtain

r_{n}^{(k)} = ∑_{j=0}^{k+1} a_{n,j} = a_{n,0} + a_{n+1,k}.

So, the recurrence sequence r_{n}^{(k)} is the linear combination of sequences A_{n}^{(k)}, therefore they have the same characteristic polynomial and the same recurrence relation.

Let C^{(k)} = (c_{n}^{(k)}) be the sum sequence of columns. As a_{n+1,0} = a_{n,1} = a_{n,0} + a_{n−1,2} = a_{n,0} + a_{n−1,1} + a_{n−2,3} = ⋯ = ∑_{j=0}^{min{n,k+1}−1} a_{n−j,j}, then

c_{n}^{(k)} = ∑_{j=0}^{min\{n,k+1\}} a_{n−j,j} = \begin{cases}a_{n+1,0}, & if n ≤ k; \\ a_{n+1,0} + a_{n−k−1,k+1}, & if n > k. \end{cases}

Let D^{(k)} = (d_{n}^{(k)}) be the left-down diagonal sequence, where

d_{n} = \begin{cases}∑_{ℓ=0}^{ℓ≤ \frac{n}{2} , 2ℓ≤k} a_{\frac{n}{2} −ℓ,2ℓ}, & if n is even; \\ ∑_{ℓ=0}^{ℓ≤ \frac{n}{2} , 2ℓ≤k+1} a_{\frac{n}{2} −ℓ,2ℓ+1}, & if n is odd. \end{cases}

Since all the A_{j}^{(k)} sequence satisfy the same recurrence relation, then C^{(k)} and D^{(k)} are so.

For example, see Figure 4 when k = 4.

R^{(4)} = (6, 20, 68, 226, 742, 2422, 7884, 25630, 83268, 270444, …)  = not in the OEIS,
C^{(4)} = (1, 2, 5, 14, 42, 132, 422, 1360, 4400, 14262, 46270, …)  = not in the OEIS,
(d_{2n}^{(k)}) = (1, 2, 6, 19, 61, 197, 638, 2069, 6714, 21794, 70755, …)  = \underline{A052975},
(d_{2n+1}^{(k)}) = (1, 3, 10, 33, 108, 352, 1145, 3721, 12087, 39254, 127469, …) = \underline{A060557},
D^{(4)} = (1, 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, 352, 638, 1145, 2069, …) = \underline{A028495}.

6 Examples

In this section, we give some example sequences with different k values appearing in the On-Line Encyclopedia of Integer Sequences [9] (see Table 1 and Table 2).

k = 0 A_{0}^{(0)} = A_{1}^{(0)} =\underline{A000012}.
k = 1 A_{1}^{(1)}=\underline{A000079}
k = 2 A_{0}^{(2)}=\underline{A001519}  A_{1}^{(2)}=\underline{A001519}^{∗}  A_{2}^{(2)}=\underline{A001906}^{∗}
k = 3 A_{0}^{(3)}=\underline{A124302}  A_{1}^{(3)}=\underline{A000244}  A_{2}^{(3)}=\underline{A000244}  A_{3}^{(3)}=\underline{A003462}
k = 4 These sequences are presented in Section 2.
k = 5 A_{0}^{(5)}=\underline{A024175}  A_{1}^{(5)}=\underline{A024175}^{∗}  A_{2}^{(5)}=\underline{A094803}  A_{3}^{(5)} =\underline{A007070}
A_{4}^{(5)}=\underline{A094806}  A_{5}^{(5)}=\underline{A094811}
k = 6 A_{0}^{(6)}=\underline{A080938}  A_{1}^{(6)}=\underline{A080938}^{∗}  A_{2}^{(6)}=\underline{A094826}  A_{3}^{(6)} =\underline{A094827}
A_{4}^{(6)}=\underline{A094828}  A_{5}^{(6)}=\underline{A094829}  A_{6}^{(6)}=\underline{A094256}
k = 7 A_{0}^{(7)}=\underline{A033191}  A_{1}^{(7)}=\underline{A033191}^{∗}  A_{2}^{(7)}=\underline{A033190}  A_{3}^{(7)} =\underline{A094667}
\begin{matrix}A_{4}^{(7)}=\underline{A030191}; \\ \underline{A093131} & ∗ \end{matrix}  A_{5}^{(7)}=\underline{A094788}  A_{6}^{(7)}=\underline{A094825}  A_{7}^{(7)}=\underline{A094865}^{∗∗}
k = 8 A_{0}^{(8)}=\underline{A211216}  A_{1}^{(8)}=\underline{A211216}^{∗}  A_{4}^{(8)}=\underline{A224422}  A_{5}^{(8)} =\underline{A221863}
k = 9 A_{5}^{(9)}=\underline{A216263}

∗n ≥ 1, ^{∗∗}n ≥ 3.

Table 1: Sequences A_{j}^{(k)} appearing in the OEIS

k = 0 Z_{0}^{(0)}=\underline{A000001}
k = 1 Z_{1}^{(2)}=\underline{A000045}, Fibonacci sequence Z_{2}^{(2)}=\underline{A001906}^{∗}
k = 3 Z_{0}^{(3)}=\underline{A124302}  Z_{1}^{(3)}=\underline{A000244}  Z_{2}^{(3)}=\underline{A232801}^{∗}  Z_{3}^{(3)}=\underline{A052993}
k = 4 These sequences are presented in Section 2.

∗n ≥ 1.

Table 2: Sequences Z_{j}^{(k)} appearing in the OEIS

7 Acknowledgments

For L. Sz., this work was supported by Hungarian National Foundation for Scientific Research Grant Nos. 128088 and 130909. The authors would like to thank the anonymous referee for carefully reading the manuscript, and for the useful suggestions and improvements.

Figure 4: Sum of rows, columns, and left-down diagonal sequences

References

[1] S. Ahmad, H. M. A. Siddiqui, A. Ali, M. R. Farahani, M. Imran, and I. N. Cangul, On Wiener index and Wiener polarity index of some polyomino chains, J. Discrete Math. Sci. Cryptogr. 22 (2019), 1151–1164.

[2] Y. Baryshnikov and D. Romik, Enumeration formulas for Young tableaux in a diagonal strip, Israel J. Math. 178 (2010), 157–186.

[3] H. Belbachir, L. Németh, and L. Szalay, Hyperbolic Pascal triangles, Appl. Math. Comput. 273 (2016), 453–464.

[4] H. Belbachir and L. Szalay, On the arithmetic triangles, S̆iauliai Math. Sem. 9 (2014), 15–26.

[5] H. Belbachir, T. Komatsu, and L. Szalay, Linear recurrences associated to rays in Pascal’s triangle and combinatorial identities, Math. Slovaca 64 (2014), 287–300.

[6] L. Németh, The growing ration of hyperbolic regular mosaics with bounded cells, Armen. J. Math. 9 (2017), 1–19.

[7] L. Németh and L. Szalay, Recurrence sequences in the hyperbolic Pascal triangle corresponding to the regular mosaic {4, 5}, Ann. Math. Inform. 46 (2016), 165–173.

[8] L. Németh and L. Szalay, Power sums in hyperbolic Pascal triangles, An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat. 26 (2018), 189–203.

[9] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

    at https://oeis.org.

[10] R. P. Stanley, A survey of alternating permutations, combinatorics and graphs, Contemp. Math. 531 (2010), 165–196.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11Y55, 05C38, 05A10. Keywords: zig-zag digraph, recurrence sequence, zig-zag sequence.

(Concerned with sequences \underline{A000001}, \underline{A000012}, \underline{A000045}, \underline{A000079}, \underline{A000244}, \underline{A001519}, \underline{A001906}, \underline{A003462}, \underline{A005021}, \underline{A006053}, \underline{A007070}, \underline{A024175}, \underline{A028495}, \underline{A030191}, \underline{A033190}, \underline{A033191}, \underline{A052975}, \underline{A052993}, \underline{A060557}, \underline{A080937}, \underline{A080938}, \underline{A093131}, \underline{A094256}, \underline{A094667}, \underline{A094788}, \underline{A094789}, \underline{A094790}, \underline{A094803}, \underline{A094806}, \underline{A094811}, \underline{A094825}, \underline{A094826}, \underline{A094827}, \underline{A094828}, \underline{A094829}, \underline{A094865}, \underline{A124302}, \underline{A124302}, \underline{A211216}, \underline{A216263}, \underline{A221863}, \underline{A224422}, and \underline{A232801}.)

Received December 16 2020; revised version received March 17 2021. Published in Journal of Integer Sequences, April 20 2021.

Return to Journal of Integer Sequences home page.