Convolution and Sulanke Numbers

Claudio de Jesús Pita Ruiz Velasco^{1} Universidad Panamericana Mexico City, Mexico

                        cpita@up.edu.mx

Abstract

We show that the Sulanke numbers appear naturally in certain type of convolutions of sequences. We obtain explicit formulas for them and study some of their properties. By generalizing the procedure used to study Sulanke numbers we obtain new sequences with similar properties.

1 Introduction

The Sulanke numbers s_{n,m}, n, m ∈ ℤ, (\underline{A064861} of The On-Line Encyclopedia of Integer Sequences) are defined by

s_{n,m} = \{ \begin{matrix}s_{n,m−1} + s_{n−1,m}, & if & n + m is even; \\ s_{n,m−1} + 2s_{n−1,m}, & if & n + m is odd, \end{matrix}

together with the initial conditions s_{0,0} = 1 and s_{n,m} = 0 if n < 0 or m < 0. These numbers were introduced by R. Sulanke [8], in relation with a problem that involves to the so-called central Delannoy numbers (\underline{A001850} of The On-Line Encyclopedia of Integer Sequences). (Some comments about these numbers will be given shortly.)

The Sulanke numbers can be viewed in a triangular format as follows:

s_{0,0} (1)
s_{0,1} (1)  s_{1,0} (2)
s_{0,2} (1)  s_{1,1} (3)  s_{2,0} (2)
s_{0,3} (1)  s_{1,2} (5)  s_{2,1} (8)  s_{3,0} (4)
s_{0,4} (1)  s_{1,3} (6)  s_{2,2} (13)  s_{3,1} (12)  s_{4,0} (4)
⋮  ⋮  ⋮  ⋮

1Work partially supported by CONACyT (Mexico), project 49187.

The rules to fill out this triangle are

\begin{aligned}s_{n−1,m} & & & & s_{n,m−1} \\ & ↘ + & & + ↙ \\ & & s_{n,m} \end{aligned}  or  \begin{aligned}2s_{n−1,m} & & & & s_{n,m−1} \\ & ↘ + & & + ↙ \\ & & s_{n,m} \end{aligned}

depending if n + m is even or odd, respectively.

In a rectangular format Sulanke numbers can be displayed as follows:

s_{0,0} (1) s_{0,1} (1) s_{0,2} (1) s_{0,3} (1) s_{0,4} (1) ⋯
s_{1,0} (2) s_{1,1} (3) s_{1,2} (5) s_{1,3} (6) s_{1,4} (8) ⋯
s_{2,0} (2) s_{2,1} (8) s_{2,2} (13) s_{2,3} (25) s_{2,4} (33) ⋯
s_{3,0} (4) s_{3,1} (12) s_{3,2} (38) s_{3,3} (63) s_{3,4} (129) ⋯
s_{4,0} (4) s_{4,1} (28) s_{4,2} (66) s_{4,3} (192) s_{4,4} (321) ⋯
⋮  ⋮  ⋮  ⋮  ⋮

and the rules to fill out this rectangular array are

s_{n−1,m} ; \begin{matrix}↓ \\ + \end{matrix} ; s_{n,m−1} ⟶ + s_{n,m}  or  2s_{n−1,m} ; \begin{matrix}↓ \\ + \end{matrix} ; s_{n,m−1} ⟶ + s_{n,m}

depending if n + m is even or odd, respectively.

The numbers s_{i,i}, i = 0, 1, 2, …, corresponding to the vertical central line in the triangular format, or to the diagonal in the rectangular format, are called central Delannoy numbers. Sulanke [9] presents a list of 29 configurations counted by the central Delannoy numbers, some of them related with lattice paths in the integer plane. It turns out that Sulanke numbers have to do with a bijection between two of these configurations. The central Delannoy numbers form a subset of the Delannoy numbers, introduced by Henri Delannoy [3] by the end of the 19th century. (Two nice articles are [1, 2], where one can learn historical, mathematical, and historical-mathematical aspects of the life and work of H. Delannoy.) For n, m ∈ ℤ, the Delannoy numbers d_{n,m} are defined as d_{n,m} = d_{n−1,m} + d_{n−1,m−1} + d_{n,m−1}, together with the initial condition d_{0,0} = 1 and d_{n,m} = 0 if n < 0 or m < 0. Two immediate consequences of this definition are the following: (1) d_{n,0} = d_{0,n} = 1, (2) d_{n,1} = d_{1,n} = 2n+1, for all n = 0, 1, 2, . . .. One can also see that d_{n,m} = d_{m,n}, so the matrix of Delannoy numbers is symmetric. Some of the d_{i,j} numbers are

1 1 1 1 1 ⋯
1 3 5 7 9
1 5 13 25 41
1 7 25 63 129
1 9 41 129 321
⋮  ...

where rows are labeled by i and columns by j (both non-negative integers). The numbers in the diagonal d_{i,i} = (1, 3, 13, 63, 321, …), denoted simply as d_{i}, are the central Delannoy numbers.

An explicit formula for d_{i,j} is

d_{i,j} = ∑_{k=0}^{min(i,j)} \binom{i}{k}\binom{j}{k}2^{k},  (1)

so the central Delannoy numbers are

d_{i} = ∑_{k=0}^{i} \binom{i}{k}^{2}2^{k}.  (2)

Thus, Sulanke numbers s_{i,j} are related with Delannoy numbers d_{i,j} by s_{i,i} = d_{i}. In fact, these two sets of numbers have a larger intersection (as we will see in section 3).

Let us use the Pascal triangle parametrization of the indices n, m in the Sulanke numbers, so that s_{n,m} stands for the number in the line n (beginning with the 0 line) and in the position m of that line (beginning with m = 0). (We also set s_{n,m} = 0 if m < 0 or m > n.) Thus we get a family of sequences labeled by the row number (we use the same notation s_{n,m} for the sequence in the line n), namely,

s_{0,m} = (1, 0, 0, …) ,
s_{1,m} = (1, 2, 0, 0, …) ,
s_{2,m} = (1, 3, 2, 0, 0, …) ,
s_{3,m} = (1, 5, 8, 4, 0, 0, …) ,

and so on. We will see in section 3 that these sequences have some interesting properties under convolution. For example we have s_{1,m} ∗ s_{2,m} = s_{3,m} and s_{2,m} ∗ s_{4,m} = s_{6,m} (however, s_{1,m} ∗ s_{3,m} is not equal to s_{4,m}). It turns out that the s_{n,m} numbers are in fact coefficients of certain polynomials, and that they are naturally involved in certain combinatorial formulas, some of them involving convolutions of sequences. We also obtain explicit formulas for the elements of these sequences.

Is there a natural way of generalizing the Sulanke numbers pattern? For example, if we move from (mod 2) to (mod 3), is there a formula f that involves s_{n,m−1}, s_{n−1,m}, s_{n−1,m−1}, s_{n−2,m}, s_{n,m−2}, … such that

s_{n,m} = \{ \begin{matrix}s_{n,m−1} + s_{n−1,m}, & if & n + m ≡ 0 (mod 3); \\ s_{n,m−1} + 2s_{n−1,m}, & if & n + m ≡ 1 (mod 3); \\ f, & if & n + m ≡ 2 (mod 3), \end{matrix}

so that the properties of Sulanke numbers (or the natural generalizations of them) are also valid in this new case? Can we expect something similar if we move to (mod p), where p is a given positive integer? We show in section 4 a procedure that does this work. In section 5 we present two concrete examples in order to see in those particular cases how the generalization showed in section 4 works, and in section 6 we present some (also natural) lines on which this work can be continued, and open questions that remain unanswered in this article as well. Section 2 is devoted to present the most important facts of the mathematical tool with we will work in sections 3, 4 and 5.

2 Preliminaries

The main tool with we will be working in this article is the so called “Z transform”, of which we will recall some important facts in this section. (This transform can be considered as the discrete equivalent of the Laplace transform. The books [5, 10] devote some chapters to the theory.) This is a nice tool (as hopefully can be seen in this work) that is seldom used within mathematical world. However, Z transform is a fruitful tool in engineering studies related to discrete systems. It is common to find engineering books containing complete “mathematical chapters” in which this transform is explained. (Ogata’s book [6] is an example.)

The Z transform maps complex sequences a = (a_{0}, a_{1}, a_{2}, …) into complex (holomorphic) functions A : U ⊂ ℂ → ℂ given by the Laurent series

A (z) = ∑_{n=0}^{∞} \frac{a_{n}}{z^{n}} .

The simplest case is the sequence δ = (1, 0, 0, …), which Z transform is the constant function A (z) = 1. If a is an eventually zero sequence, a = (a_{0}, a_{1}, …, a_{k}, 0, 0, …) say, its Z transform is the rational function A (z) = ∑_{n=0}^{k} \frac{a_{n}}{z^{n}} defined in ℂ⧹ \{0\}. In general, the Z transform of the sequence a = (a_{0}, a_{1}, a_{2}, …) is a holomorphic function defined outside the closure \overline{D} of the disk D of convergence of the Taylor series ∑_{n=0}^{∞} a_{n}z^{n}. We will also denote the Z transform of the sequence a = (a_{n})_{n=0}^{∞} by Z (a_{n}).

We mention some of the most important properties of the Z transform, which we will be using throughout this work without further comments. Avoiding the details of the regions of convergence, we have that:

(a) Z is linear and injective.

(b) Advance-shifting property. For k ∈ ℕ we have

Z (a_{n+k}) = z^{k} (Z (a_{n}) − a_{0} − \frac{a_{1}}{z} − ⋯ − \frac{a_{k−1}}{z^{k−1}} ) .  (3)

Here a_{n+k} is the sequence a_{n+k} = (a_{k}, a_{k+1}, …).

(c) Delay-shifting property. For k ∈ ℕ we have

Z (a_{n−k}) = z^{−k}Z (a_{n}) .  (4)

Here a_{n−k} is the sequence a_{n−k} = (0, 0, …, 0, a_{0}, a_{1}, a_{2}, …) (with k zeros at the beginning).

(d) Multiplication by the sequence n = (0, 1, 2, …). If Z (a_{n}) = A (z), then

Z (na_{n}) = −z \frac{d}{dz} A (z) .  (5)

The proof of these facts are easy exercises left to the reader.

The convolution of the sequence a = (a_{0}, a_{1}, a_{2}, …) with the sequence b = (b_{0}, b_{1}, b_{2}, …), denoted by a∗b, is the sequence a∗b = (a_{n} ∗ b_{n})_{n=0}^{∞}, where a_{n}∗b_{n} = ∑_{i=0}^{n} a_{i}b_{n−i}. (Sometimes we will simply say “the sequence a_{n}” when referring to the sequence a = (a_{0}, a_{1}, a_{2}, …), so when we say “the convolution a_{n} ∗ b_{n}” we must understand that this is a sequence with generic term a_{n} ∗ b_{n} defined before.) Some easy examples are 1 ∗ 1 = n + 1 and n ∗ 1 = \binom{n}{2}, where 1 is the constant sequence (1, 1, …). It is easy to check that convolution is commutative and associative, and that also distributes over the sum. One can see at once that the sequence δ = (1, 0, 0, …) acts neutrally under convolution, i.e., a_{n} ∗ δ = a_{n} for any sequence a_{n}. A common expression we will find in this work is a_{n} ∗ a_{n} ∗ ⋯ ∗ a_{n}, where a_{n} is a given sequence and it convolves with itself k times. We will denote this convolution as ∗^{k}a_{n}. Also we will be facing frequently the convolution of two eventually zero sequences a = (a_{0}, a_{1}, …, a_{m}, 0, 0, …) and b = (b_{0}, b_{1}, …, b_{l}, 0, 0, …). In this case we have that a_{i} ∗ b_{i} = ∑_{j=0}^{m} a_{j}b_{i−j}, for i = 0, 1, …, m + l, and a_{i} ∗ b_{i} = 0 for i > m + l. Equivalently, if we consider the polynomials P_{m} (z) = ∑_{i=0}^{m} a_{i}z^{i} and Q_{l} (z) = ∑_{i=0}^{l} b_{i}z^{i}, then the product P_{m} (z) Q_{l} (z) is a polynomial of degree m + l which coefficients are the elements of the sequence a ∗ b. That is

(∑_{i=0}^{m} a_{i}z^{i}) (∑_{i=0}^{l} b_{i}z^{i}) = ∑_{i=0}^{m+l} (a_{i} ∗ b_{i}) z^{i}.

More generally, if P_{m_{k}} (z) = ∑_{i=0}^{m_{k}} a_{k,i}z^{i}, k = 1, 2, …, n, are n given polynomials, then

∏_{k=1}^{n}P_{m_{k}} (z) = ∑_{i=0}^{m_{1}+m_{2}+···+m_{n}} (a_{1,i} ∗ a_{2,i} ∗ ⋯ ∗ a_{n,i}) z^{i},

where

a_{1,i} ∗ a_{2,i} ∗ ⋯ ∗ a_{n,i} = ∑_{j_{n−1}=0}^{m_{1}+m_{2}+···+m_{n−1}} ⋯ ∑_{j_{2}=0}^{m_{1}+m_{2}} ∑_{j_{1}=0}^{m_{1}} a_{1,j_{1}}a_{2,j_{2}−j_{1}}a_{3,j_{3}−j_{2}} ⋯ a_{n,i−j_{n−1}}.

It is not difficult to see that

Z ((a_{1})_{n} ∗ (a_{2})_{n} ∗ ⋯ ∗ (a_{k})_{n}) = Z ((a_{1})_{n}) Z ((a_{2})_{n}) ⋯ Z ((a_{k})_{n}) ,  (6)

(the so called Convolution Theorem), where (a_{1})_{n} , (a_{2})_{n} , …, (a_{k})_{n} are given sequences.

Now we list the Z transforms of some sequences which we will be using throughout this work. We begin with the constant sequence 1, which Z transform is plainly

Z (1) = ∑_{n=0}^{∞} \frac{1}{z^{n}} = \frac{1}{1 − z^{−1}} = \frac{z}{z − 1},  (7)

valid for |z| > 1. By multiplying 1 times n we get the Z transform of the sequence n

Z (n) = −z \frac{d}{dz} \frac{z}{z − 1} = \frac{z}{(z − 1)^{2}} .  (8)

Similarly we obtain

Z (n^{2}) = −z \frac{d}{dz} \frac{z}{(z − 1)^{2}} = \frac{z (z + 1)}{(z − 1)^{3}},  (9)

and

Z (n^{3}) = −z \frac{d}{dz} \frac{z (z + 1)}{(z − 1)^{3}} = \frac{z (z^{2} + 4z + 1)}{(z − 1)^{4}}.  (10)

All these transforms are also valid for |z| > 1. We will be also using that, for given p non-negative integer, the sequence \binom{n}{p} has Z transform

Z (\binom{n}{p}) = \frac{z}{(z − 1)^{p+1}} .  (11)

The proof of this fact is an easy induction exercise that we leave for the reader. Note that if 0 ≤ p_{0} ≤ p, then we have according to (3) that

Z (\binom{n + p_{0}}{p}) = \frac{z^{p_{0}+1}}{(z − 1)^{p+1}} .  (12)

Observe also that for given p_{1}, p_{2}, …, p_{k} non-negative integers, we have that (according to (6) and (11))

Z (\binom{n}{p_{1}} ∗ \binom{n}{p_{2}} ∗ ⋯ ∗ \binom{n}{p_{k}}) = z^{k−1} \frac{z}{(z − 1)^{p_{1}+p_{2}+···+p_{k}+k}} .  (13)

Thus, from (3) and (11) we obtain that

\binom{n}{p_{1}} ∗ \binom{n}{p_{2}} ∗ ⋯ ∗ \binom{n}{p_{k}} = \binom{n + k − 1}{p_{1} + p_{2} + ⋯ + p_{k} + k − 1}.  (14)

To end this section, we explore some interesting facts that (13) and (14) offer to us. What we will do now has the flavor of what we will be doing in sections 3, 4 and 5. We begin by expanding the polynomial z^{k−1} in powers of z − 1. We have that

z^{k−1} = ∑_{i=0}^{k−1} \binom{k − 1}{i} (z − 1)^{k−1−i} .

What we want to stress in this expression is that, for each k ∈ ℕ, it produces the sequence a_{k,i} = (a_{k,0}, a_{k,1}, …, a_{k,k−1}, 0, 0, …) formed by the coefficients a_{k,i} = \binom{k−1}{i}. Let us write this expansion as follows:

z^{k−1} = ∑_{i=0}^{k−1} a_{k,i} (z − 1)^{k−1−i} ,  (15)

and let us see how some properties of the numbers a_{k,i} appear naturally, and also some formulas where they are involved as well. We set a_{k,i} = 0 for i < 0.

From (13) and (15) we have that

Z (\binom{n}{p_{1}} ∗ \binom{n}{p_{2}} ∗ ⋯ ∗ \binom{n}{p_{k}}) = ∑_{i=0}^{k−1} a_{k,i} (z − 1)^{k−1−i} \frac{z}{(z − 1)^{p_{1}+p_{2}+···+p_{k}+k}}

= ∑_{i=0}^{k−1} a_{k,i} \frac{z}{(z − 1)^{p_{1}+p_{2}+···+p_{k}+i+1}} ,

and then, from (11) we obtain that

\binom{n}{p_{1}} ∗ \binom{n}{p_{2}} ∗ ⋯ ∗ \binom{n}{p_{k}} = ∑_{i=0}^{k−1} a_{k,i}\binom{n}{p_{1} + p_{2} + ⋯ + p_{k} + i},

or

∑_{i=0}^{k−1} \binom{k − 1}{i}\binom{n}{p_{1} + p_{2} + ⋯ + p_{k} + i} = \binom{n + k − 1}{p_{1} + p_{2} + ⋯ + p_{k} + k − 1},

which is certainly a nice identity.

Now, by using (15) we can easily obtain that

∑_{i=0}^{k} a_{k+1,i} (z − 1)^{k−i} = ∑_{i=0}^{k} (a_{k,i} + a_{k,i−1}) (z − 1)^{k−i} ,

and then we conclude that a_{k+1,i} = a_{k,i} + a_{k,i−1}, which is simply the well-known property

\binom{k}{i} = \binom{k − 1}{i} + \binom{k − 1}{i − 1}.

Now, for given k_{1}, k_{2}, …, k_{p} ∈ ℕ, we plainly have that

z^{k_{1}−1}z^{k_{2}−1} ⋯ z^{k_{p}−1} = z^{(k_{1}+k_{2}+···+k_{p}−p+1)−1}.

From this trivial observation together with (15) we obtain that

a_{k_{1},i} ∗ a_{k_{2},i} ∗ ⋯ ∗ a_{k_{p},i} = a_{k_{1}+k_{2}+···+k_{p}−p+1,i}.  (16)

Explicitly (16) looks like

∑_{j_{p−1}=0}^{k_{p}−1} ⋯ ∑_{j_{2}=0}^{k_{3}−1} ∑_{j_{1}=0}^{k_{2}−1} \binom{k_{1} − 1}{i − j_{1} − j_{2} − ⋯ − j_{p−1}}\binom{k_{2} − 1}{j_{1}}\binom{k_{3} − 1}{j_{2}} ⋯ \binom{k_{p} − 1}{j_{p−1}}

= \binom{k_{1} + k_{2} + ⋯ + k_{p} − p}{i},

which is a version of the also well-known Vandermonde convolution.

3 Sulanke numbers

We begin by considering the sequence n^{2} which Z transform (recall (9)) can be written as follows:

Z (n^{2}) = \frac{z (z + 1)}{(z − 1)^{3}} = \frac{z}{(z − 1)^{2}} + 2\frac{z}{(z − 1)^{3}} ,  (17)

which means that (recall (11))

n^{2} = \binom{n}{1} + 2\binom{n}{2}.  (18)

Now let k be a given natural number and consider the convolution ∗^{k}n^{2}. We have

Z (∗^{k}n^{2}) = \frac{z^{k} (z + 1)^{k}}{(z − 1)^{3k}} = z \frac{z^{k−1} (z + 1)^{k}}{(z − 1)^{3k}} .  (19)

Let a_{k,i}, i = 0, 1, …, 2k − 1, be the coefficients in the expansion of the polynomial z^{k−1} (z + 1)^{k} in powers of z − 1. That is

z^{k−1} (z + 1)^{k} = ∑_{i=0}^{2k−1} a_{k,i} (z − 1)^{2k−1−i} .  (20)

Thus we have

Z (∗^{k}n^{2}) = z \frac{z^{k−1} (z + 1)^{k}}{(z − 1)^{3k}} = z \frac{∑_{i=0}^{2k−1} a_{k,i} (z − 1)^{2k−1−i}}{(z − 1)^{3k}} = ∑_{i=0}^{2k−1} a_{k,i} \frac{z}{(z − 1)^{k+i+1}} ,

which in turn implies that

∗^{k}n^{2} = ∑_{i=0}^{2k−1} a_{k,i}\binom{n}{k + i}.  (21)

Thus, for each k ∈ ℕ we have the sequence a_{k,i} = (a_{k,0}, a_{k,1}, …, a_{k,2k−1}, 0, 0, …). Now let us consider the convolution ∗^{k}n^{2} ∗ n, which Z transform is

Z (∗^{k}n^{2} ∗ n) = \frac{z^{k} (z + 1)^{k}}{(z − 1)^{3k}} \frac{z}{(z − 1)^{2}} = z \frac{z^{k} (z + 1)^{k}}{(z − 1)^{3k+2}} .  (22)

Let b_{k,i}, i = 0, 1, …, 2k, be the coefficients in the expansion of the polynomial z^{k} (z + 1)^{k} in powers of z − 1. That is

z^{k} (z + 1)^{k} = ∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k−i} .  (23)

Thus we have that

Z (∗^{k}n^{2} ∗ n) = z \frac{∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k−i}}{(z − 1)^{3k+2}} = ∑_{i=0}^{2k} b_{k,i} \frac{z}{(z − 1)^{k+i+2}} ,

from where

∗^{k}n^{2} ∗ n = ∑_{i=0}^{2k} b_{k,i}\binom{n}{k + i + 1}.  (24)

Then we have sequences b_{k,i} = (b_{k,0}, b_{k,1}, …, b_{k,2k}, 0, 0, …) for each k ∈ ℕ. Observe that (23) makes sense for k = 0 if we simply set b_{0,0} = 1 (and then we understand (24) in this case —that is ∗^{0}n^{2} ∗ n— simply as n). So the sequences b_{k,i} are defined for k non-negative integers, where b_{0,i} = (1, 0, 0, …) is the δ sequence.

Proposition 1. The sequences a_{k,i} and b_{k,i} are related by

b_{k,i} = a_{k,i} + a_{k,i−1}.  (25)

a_{k+1,i} = b_{k,i} + 2b_{k,i−1}.  (26)

Proof. By using first (23) and then (20) we get

∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k−i} = (z − 1 + 1) ∑_{i=0}^{2k−1} a_{k,i} (z − 1)^{2k−1−i}

= ∑_{i=0}^{2k−1} a_{k,i} (z − 1)^{2k−i} + ∑_{i=1}^{2k} a_{k,i−1} (z − 1)^{2k−i}

= ∑_{i=0}^{2k} (a_{k,i} + a_{k,i−1}) (z − 1)^{2k−i} ,

from where (25) follows. Also, from (20) with k replaced by k + 1, we get

∑_{i=0}^{2k+1} a_{k+1,i} (z − 1)^{2k+1−i} = (z + 1) z^{k} (z + 1)^{k}

= (z − 1 + 2) ∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k−i}

= ∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k+1−i} + 2 ∑_{i=1}^{2k+1} b_{k,i−1} (z − 1)^{2k+1−i}

= ∑_{i=0}^{2k+1} (b_{k,i} + 2b_{k,i−1}) (z − 1)^{2k+1−i} ,

from where (26) follows.

Thus, we have two kind of sequences, namely a_{k,i} and b_{k,i}, satisfying relations (25) and (26). We claim that these are precisely Sulanke numbers s_{n,m}. In fact, the elements a_{k,j}, j = 0, 1, 2, …, 2k − 1, correspond to the Sulanke numbers s_{j,2k−1−j}, and the elements b_{k,j}, j = 0, 1, 2, …, 2k, correspond to the Sulanke numbers s_{j,2k−j}. Reciprocally, the Sulanke numbers s_{n,m} with n + m even, correspond to the elements b_{\frac{n+m}{2} ,n}, and the Sulanke numbers s_{n,m} with n + m odd, correspond to the elements a_{\frac{n+m+1}{2} ,n}.

We will refer to the first index of the sequences a_{k,i} and b_{k,i} as the level of the sequence. Then, for each level k ∈ ℕ we have two types of sequences, namely a_{k,i} and b_{k,i}. Relation (25) tells us how we can obtain the sequence b_{k,i} in terms of the sequence a_{k,i} of the same level. And (26) tells us how we can move from level k to level k + 1 (we use the last sequence of the level k —namely b_{k,i}— to construct the first sequence of the level k + 1 —namely a_{k+1,i}—). In fact, we can begin with the sequence b_{0,i} = (1, 0, 0, …) in the level k = 0, and use (26) to move to level 1. We get

a_{1,i} = b_{0,i} + 2b_{0,i−1} = (1, 0, 0, …) + 2 (0, 1, 0, 0, …) = (1, 2, 0, 0, …) .

(If one wish, one can consider this sequence as the starting point, since this is (18).) Now, from (25) we get the sequence b_{1,i}

b_{1,i} = a_{1,i} + a_{1,i−1} = (1, 2, 0, 0, …) + (0, 1, 2, 0, 0, …) = (1, 3, 2, 0, 0, …) .

With (26) we move from level 1 to level 2 using b_{1,i}. We have that

a_{2,i} = b_{1,i} + 2b_{1,i−1} = (1, 3, 2, 0, 0, …) + 2 (0, 1, 3, 2, 0, 0, …) = (1, 5, 8, 4, 0, 0, …) ,

and we complete level 2 with (25)

b_{2,i} = a_{2,i} + a_{2,i−1} = (1, 5, 8, 4, 0, 0, …) + (0, 1, 5, 8, 4, 0, 0, …) = (1, 6, 13, 12, 4, 0, 0, …) ,

and so on.

Summarizing, the steps we follow for obtaining all the sequences a_{k,i} and b_{k,i} are

b_{0,i} ⟶^{(26)} \underbrace{a_{1,i} ⟶^{(25)} b_{1,i}}_{Level 1} ⟶^{(26)} \underbrace{a_{2,i} ⟶^{(25)} b_{2,i}}_{Level 2} ⟶^{(26)} a_{3,i} ⟶ ⋯,

Some of the first sequences are

b_{0,i} 1 0 0 …
a_{1,i} 1 2 0 0 …
b_{1,i} 1 3 2 0 0 …
a_{2,i} 1 5 8 4 0 0 …
b_{2,i} 1 6 13 12 4 0 0 …
a_{3,i} 1 8 25 38 28 8 0 0 …
b_{3,i} 1 9 33 63 66 36 8 0 0 …
a_{4,i} 1 11 51 129 192 168 80 16 0 0 …
b_{4,i} 1 12 62 180 321 360 248 96 16 0 0 …

It is possible to obtain the sequence a_{k+1,i} using only the sequence of the same type a_{k,i} of the previous level (and similarly for b_{k,i}). This is what the following corollary says.

Corollary 2. The following formulas hold

a_{k+1,i} = a_{k,i} + 3a_{k,i−1} + 2a_{k,i−2}.  (27)

b_{k+1,i} = b_{k,i} + 3b_{k,i−1} + 2b_{k,i−2}.  (28)

Proof. Combine (25) and (26) to get

a_{k+1,i} = b_{k,i} + 2b_{k,i−1} = a_{k,i} + a_{k,i−1} + 2 (a_{k,i−1} + a_{k,i−2}) = a_{k,i} + 3a_{k,i−1} + 2a_{k,i−2}.

Formula (28) is obtained similarly.

Thus, beginning with a_{1,i} = (1, 2, 0, 0, …) we obtain

a_{2,i} = a_{1,i} + 3a_{1,i−1} + 2a_{1,i−2} = (1, 5, 8, 4, 0, 0, …) ,

and then

a_{3,i} = a_{2,i} + 3a_{2,i−1} + 2a_{2,i−2} = (1, 8, 25, 38, 28, 8, 0, 0, …) ,

and so on. Similarly, from with b_{0,i} = (1, 0, 0, …) we obtain

b_{1,i} = b_{0,i} + 3b_{0,i−1} + 2b_{0,i−2} = (1, 3, 2, 0, 0, …) ,

and then

b_{2,i} = b_{1,i} + 3b_{1,i−1} + 2b_{1,i−2} = (1, 6, 13, 12, 4, 0, 0, …) ,

and so on.

Let us consider the numbers b_{k,k}. It is clear from (23) that

b_{k,k} = \frac{1}{k!} \frac{d^{k}}{dz^{k}} |_{z=1} z^{k} (z + 1)^{k} .

Since

\frac{d^{k}}{dz^{k}} (z^{k} (z + 1)^{k}) = ∑_{j=0}^{k} \binom{k}{j} (z^{k})^{(j)} ((z + 1)^{k})^{(k−j)} = ∑_{j=0}^{k} \binom{k}{j}\frac{k!}{(k − j)!} \frac{k!}{j!}z^{k−j} (z + 1)^{j} ,

we have that

b_{k,k} = \frac{1}{k!} ∑_{j=0}^{k} \binom{k}{j}\frac{k!}{(k − j)!} \frac{k!}{j!}z^{k−j} (z + 1)^{j}|_{z=1} = ∑_{j=0}^{k} \binom{k}{j}^{2}2^{j},

which are the central Delannoy numbers. A common expression for these numbers is

b_{k,k} = ∑_{j=0}^{k} \binom{k}{j}\binom{k + j}{j}.  (29)

(See [4, p. 48], Formula 2.8. The identity used here is an especial case.) Moreover, since a_{k+1,k} = b_{k,k} + 2b_{k,k−1}, we see that the numbers a_{k+1,k}, k = 0, 1, 2, …, are the elements above (or bellow) the diagonal formed by the central Delannoy numbers (called subcentral Delannoy numbers).

The following corollary tells us what is the sum of the elements of each of the sequences a_{k,i} and b_{k,i}.

Corollary 3. The sum of the elements of the sequences a_{k,i} and b_{k,i} is given by

∑_{j=0}^{2k−1} a_{k,j} = \frac{1}{2}6^{k} , ∑_{j=0}^{2k} b_{k,j} = 6^{k}.  (30)

Proof. These formulas are essentially (20) and (23), with z = 2. However, observe that we can also use formulas of corollary 2 to obtain

∑_{i=0}^{2k+1} a_{k+1,i} = ∑_{i=0}^{2k+1} (a_{k,i} + 3a_{k,i−1} + 2a_{k,i−2}) = 6 ∑_{i=0}^{2k−1} a_{k,i}.

That is, we have

∑_{i=0}^{2k−1} a_{k,i} = 6^{k−1} ∑_{i=0}^{1} a_{1,i} = 6^{k−1} (1 + 2) = \frac{1}{2}6^{k}.

Similarly one obtains

∑_{i=0}^{2k} b_{k+1,i} = 6^{k−1} ∑_{i=0}^{2} b_{1,i} = 6^{k−1} (1 + 3 + 2) = 6^{k}.

Now we establish the convolution relations between sequences a_{k,i} and b_{k,i}.

Proposition 4. Let k_{1}, k_{2} ∈ ℕ be given. The sequences a_{k,i} and b_{k,i} satisfy

a_{k_{1},i} ∗ b_{k_{2},i} = a_{k_{1}+k_{2},i}.  (31)

and

b_{k_{1},i} ∗ b_{k_{2},i} = b_{k_{1}+k_{2},i}.  (32)

Proof. From

(z^{k_{1}−1} (z + 1)^{k_{1}}) (z^{k_{2}} (z + 1)^{k_{2}}) = z^{k_{1}+k_{2}−1} (z + 1)^{k_{1}+k_{2}} ,

together with (20) and (23) we get at once (31). Similarly, from

(z^{k_{1}} (z + 1)^{k_{1}}) (z^{k_{2}} (z + 1)^{k_{2}}) = z^{k_{1}+k_{2}} (z + 1)^{k_{1}+k_{2}} ,

together with (23) we get (32).

Observe that in particular we have b_{k,i} ∗ b_{0,i} = b_{k,i} and a_{k,i} ∗ b_{0,i} = a_{k,i}, as expected, since b_{0,i} = (1, 0, 0, …) acts neutrally under convolution. Also note that b_{k,i} = ∗^{k}b_{1,i} and a_{k,i} = a_{1,i} ∗^{k−1} b_{1,i}, which means that beginning with the sequences a_{1,i} = (1, 2, 0, 0, …) and b_{1,i} = (1, 3, 2, 0, 0, …), it is possible to generate the family of the sequences a_{k,i} and b_{k,i} by convolutions among them.

Finally we will obtain explicit formulas for the elements of the sequences a_{k,i} and b_{k,i}.

Proposition 5. The elements of the sequences a_{k,i} and b_{k,i} can be obtained from the following formulas:

a_{k,i} = ∑_{j=0}^{k} \binom{k − 1}{2k − 1 − i − j}\binom{k}{j}2^{k−j}.  (33)

b_{k,i} = ∑_{j=0}^{k} \binom{k}{2k − i − j}\binom{k}{j}2^{k−j}.  (34)

Proof. According to (20) we have that

∑_{i=0}^{2k−1} a_{k,i} (z − 1)^{2k−1−i} = z^{k−1} (z + 1)^{k}

= (∑_{i=0}^{k−1} \binom{k − 1}{i} (z − 1)^{i}) (∑_{j=0}^{k} \binom{k}{j} (z − 1)^{j} 2^{k−j})

= ∑_{i=0}^{k−1} ∑_{j=0}^{k} \binom{k − 1}{i}\binom{k}{j} (z − 1)^{i+j} 2^{k−j}

= ∑_{i=0}^{2k−1} (∑_{j=0}^{k} \binom{k − 1}{2k − 1 − i − j}\binom{k}{j}2^{k−j}) (z − 1)^{2k−1−i} ,

from where (33) follows. Similarly, from (23) we have that

∑_{i=0}^{2k} b_{k,i} (z − 1)^{2k−i} = z^{k} (z + 1)^{k}

= (∑_{i=0}^{k} \binom{k}{i} (z − 1)^{i}) (∑_{j=0}^{k} \binom{k}{j} (z − 1)^{j} 2^{k−j})

= ∑_{i=0}^{k} ∑_{j=0}^{k} \binom{k}{i}\binom{k}{j} (z − 1)^{i+j} 2^{k−j}

= ∑_{i=0}^{2k} (∑_{j=0}^{k} \binom{k}{2k − i − j}\binom{k}{j}2^{k−j}) (z − 1)^{2k−i} ,

from where (34) follows.

Observe that from (34) we obtain at once that

b_{k,k} = ∑_{j=0}^{k} \binom{k}{k − j}\binom{k}{j}2^{k−j},

which are the central Delannoy numbers.

Thus, in this section we have proved the following theorem.

Theorem 6. Let b_{0,i} = (1, 0, 0, …) be given. For k ∈ ℕ, define the sequences a_{k,i} = (a_{k,0}, a_{k,1}, …, a_{k,2k−1}, 0, 0, …) and b_{k,i} = (b_{k,0}, b_{k,1}, …, b_{k,2k}, 0, 0, …) by means of the the relations

b_{k,i} = a_{k,i} + a_{k,i−1},
a_{k+1,i} = b_{k,i} + 2b_{k,i−1}.

(a) There exist a bijection between the elements of the sequences a_{k,i} and b_{k,i} and Sulanke numbers.

(b) For i = 0, 1, 2, …, the numbers b_{i,i} are the central Delannoy numbers, and the numbers a_{i+1,i} are the subcentral Delannoy numbers.

(c) The elements of the sequences a_{k,i} and b_{k,i} are involved in the following formulas

∗^{k}n^{2} = ∑_{i=0}^{2k−1} a_{k,i}\binom{n}{k + i},

∗^{k}n^{2} ∗ n = ∑_{i=0}^{2k} b_{k,i}\binom{n}{k + i + 1}.

(d) The sequences a_{k,i} and b_{k,i} satisfy the following convolution relations

b_{k_{1},i} ∗ b_{k_{2},i} = b_{k_{1}+k_{2},i},
a_{k_{1},i} ∗ b_{k_{2},i} = a_{k_{1}+k_{2},i}.

(e) The following formulas for the sum of the elements of each sequence hold

∑_{i=0}^{2k−1} a_{k,i} = \frac{1}{2}6^{k} , ∑_{i=0}^{2k} b_{k,i} = 6^{k}.

(f) The elements of the sequences a_{k,i} and b_{k,i} can be calculated explicitly as follows:

a_{k,i} = ∑_{j=0}^{k} \binom{k − 1}{2k − 1 − i − j}\binom{k}{j}2^{k−j},

b_{k,i} = ∑_{j=0}^{k} \binom{k}{2k − i − j}\binom{k}{j}2^{k−j}.

4 The general case

In this section we will follow the procedure we used to study Sulanke numbers in previous section, but now in the natural generalized setting, in which the sequence n^{2} is replaced by the sequence n^{p}, where p is a given positive integer. We begin with the following lemma.

Lemma 7. For given p ∈ ℕ, there exists a polynomial Q_{p−1} (z) (of degree p − 1) such that

Z (n^{p}) = \frac{zQ_{p−1} (z)}{(z − 1)^{p+1}} .  (35)

Proof. By induction. For p = 1 it is clear (Q_{0} (z) = 1). Now

Z (n^{p+1}) = −z \frac{d}{dz} Z (n^{p}) = \frac{zQ_{p} (z)}{(z − 1)^{p+2}} ,

where

Q_{p} (z) = (1 + pz) Q_{p−1} (z) + z (1 − z) Q′_{p−1} (z)

is a polynomial of degree p, as wanted.

Remark 8. Lemma 7 has a nice surprise in its proof. The formula satisfied by the polynomials Q_{p} (z) shows us that these are the famous Eulerian polynomials (see Riordan’s book [7, p. 215]). In fact, if we write Q_{p} (z) = ∑_{i=0}^{p} a_{p,i}z^{i}, we easily see that the coefficients a_{p,i} satisfy the well-known relation a_{p,i} = (p + 1 − i) a_{p−1,i−1} + (1 + i) a_{p−1,i} corresponding to Eulerian numbers (\underline{A008292} of The On-Line Encyclopedia of Integer Sequences). In section 6 we will comment some consequences of this fact.

We define the coefficients ^{p}(a_{1})_{1,i} by

Q_{p−1} (z) = ∑_{i=0}^{p−1}^{p}(a_{1})_{1,i} (z − 1)^{p−1−i} .  (36)

Thus we have

Z (n^{p}) = \frac{zQ_{p−1} (z)}{(z − 1)^{p+1}} = ∑_{i=0}^{p−1}^{p}(a_{1})_{1,i} \frac{z}{(z − 1)^{i+2}} ,

and then

n^{p} = ∑_{i=0}^{p−1}^{p}(a_{1})_{1,i} \binom{n}{i + 1}.  (37)

The following table contains the sequences ^{p}(a_{1})_{1,i} for p ≤ 4.

\begin{matrix}\begin{matrix}^{p}(a_{1})_{1,i} = \\ (^{p}(a_{1})_{1,0} , …,^{p}(a_{1})_{1,p−1} , 0, 0, …) \end{matrix} & n^{p} = ∑_{i=0}^{p−1} ^{p}(a_{1})_{1,i} \binom{n}{i + 1} \\ ^{1}(a_{1})_{1,i} = (1, 0, 0, …) & n = \binom{n}{1} \\ ^{2}(a_{1})_{1,i} = (1, 2, 0, 0, …) & n^{2} = \binom{n}{1} + 2\binom{n}{2} \\ ^{3}(a_{1})_{1,i} = (1, 6, 6, 0, 0, …) & n^{3} = \binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3} \\ ^{4}(a_{1})_{1,i} = (1, 14, 36, 24, 0, 0, …) & n^{4} = \binom{n}{1} + 14\binom{n}{2} + 36\binom{n}{3} + 24\binom{n}{4} \end{matrix}

Table 1. The sequences ^{p}(a_{1})_{1,i}.

Now let k ∈ ℕ be given. We have

Z (∗^{k}n^{p}) = z \frac{z^{k−1}Q_{p−1}^{k} (z)}{(z − 1)^{k(p+1)}}.  (38)

Define the coefficients ^{p}(a_{1})_{k,i} by

z^{k−1}Q_{p−1}^{k} (z) = ∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} (z − 1)^{kp−1−i} .  (39)

Then we write (38) as

Z (∗^{k}n^{p}) = ∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} \frac{z}{(z − 1)^{k+i+1}} ,

which implies that

∗^{k}n^{p} = ∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} \binom{n}{k + i}.  (40)

Now, for 1 ≤ l ≤ p − 1 we have

Z (∗^{k}n^{p} ∗ n^{l}) = \frac{z^{k}Q_{p−1}^{k} (z)}{(z − 1)^{k(p+1)}} \frac{zQ_{l−1} (z)}{(z − 1)^{l+1}} = z \frac{z^{k}Q_{p−1}^{k} (z) Q_{l−1} (z)}{(z − 1)^{k(p+1)+l+1}},  (41)

and define the coefficients ^{p}(a_{l+1})_{k,i} by

z^{k}Q_{p−1}^{k} (z) Q_{l−1} (z) = ∑_{i=0}^{kp+l−1}^{p}(a_{l+1})_{k,i} (z − 1)^{kp+l−1−i} .  (42)

Then

Z (∗^{k}n^{p} ∗ n^{l}) = ∑_{i=0}^{kp+l−1}^{p}(a_{l+1})_{k,i} \frac{z}{(z − 1)^{k+i+2}} ,

which implies that

∗^{k}n^{p} ∗ n^{l} = ∑_{i=0}^{kp+l−1}^{p}(a_{l+1})_{k,i} \binom{n}{k + i + 1}.  (43)

In particular, if we set l = 1 in (42) we get

z^{k}Q_{p−1}^{k} (z) = ∑_{i=0}^{kp}^{p}(a_{2})_{k,i} (z − 1)^{kp−i} ,  (44)

and (43) is in this case

∗^{k}n^{p} ∗ n = ∑_{i=0}^{kp}^{p}(a_{2})_{k,i} \binom{n}{k + i + 1}.  (45)

Thus, for each power p ∈ ℕ, p ≥ 2, we have the following family of p sequences, labeled by the level k ∈ ℕ

p(a_{1})_{k,i} = (^{p}(a_{1})_{k,0} , …,^{p}(a_{1})_{k,kp−1} , 0, 0, …) ,
p(a_{2})_{k,i} = (^{p}(a_{2})_{k,0} , …,^{p}(a_{2})_{k,kp} , 0, 0, …) ,
p(a_{3})_{k,i} = (^{p}(a_{3})_{k,0} , …,^{p}(a_{3})_{k,kp+1} , 0, 0, …) ,
⋮
p(a_{p−1})_{k,i} = (^{p}(a_{p−1})_{k,0} , …,^{p}(a_{p−1})_{k,(k+1)p−2} , 0, 0, …) ,
p(a_{p})_{k,i} = (^{p}(a_{p})_{k,0} , …,^{p}(a_{p})_{k,(k+1)p−1} , 0, 0, …) .

If in (42) we set k = 0 we get

Q_{l−1} (z) = ∑_{i=0}^{l−1}^{p}(a_{l+1})_{0,i} (z − 1)^{l−1−i} ,

and then, by comparing with (36) we see that the level k = 0 of the sequences ^{p}(a_{l+1})_{k,i}, 1 ≤ l ≤ p − 1, correspond to the level k = 1 of the sequences ^{l}(a_{1})_{1,i}. That is, for each p ∈ ℕ, p ≥ 2, the beginning of the families of sequences ^{p}(a_{m})_{k,i}, m = 1, 2, …, p, looks as follows:

p(a_{2})_{0,i} = ^{1}(a_{1})_{1,i} = (1, 0, 0,) ,
p(a_{3})_{0,i} = ^{2}(a_{1})_{1,i} = (1, 2, 0, 0, …) ,
p(a_{4})_{0,i} = ^{3}(a_{1})_{1,i} = (1, 6, 6, 0, 0, …) ,

⋮

p(a_{p})_{0,i} = ^{p−1}(a_{1})_{1,i} = (^{p−1}(a_{1})_{1,0} , …,^{p−1}(a_{1})_{1,p−2} , 0, 0, …) ,

↓ move to level 1

p(a_{1})_{1,i} = (^{p}(a_{1})_{1,0} , …,^{p}(a_{1})_{1,p−1} , 0, 0, …) ,
p(a_{2})_{1,i} = (^{p}(a_{2})_{1,0} , …,^{p}(a_{2})_{1,p−1} ,^{p}(a_{2})_{1,p} , 0, 0, …) ,

⋮

Proposition 9. The sequences ^{p}(a_{m})_{k,i}, m = 1, 2, …, p, are related as follows:

First,

p(a_{2})_{k,i} = ^{p}(a_{1})_{k,i} +^{p}(a_{1})_{k,i−1} .  (46)

For 2 ≤ l ≤ p − 1 we have

p(a_{l+1})_{k,i} = ∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j} ) (^{p}(a_{2})_{k,i−j}) ,  (47)

Finally,

p(a_{1})_{k+1,i} = ∑_{j=0}^{p−1} (^{p}(a_{1})_{1,j}) (^{p}(a_{2})_{k,i−j}) .  (48)

Proof. From (44) and (39) we get

∑_{i=0}^{kp}^{p}(a_{2})_{k,i} (z − 1)^{kp−i} = z (z^{k−1}Q_{p−1}^{k} (z))

= (z − 1 + 1) ∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} (z − 1)^{kp−1−i}

= ∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} (z − 1)^{kp−i} + ∑_{i=1}^{kp}^{p}(a_{1})_{k,i−1} (z − 1)^{kp−i}

= ∑_{i=0}^{kp} (^{p}(a_{1})_{k,i} +^{p}(a_{1})_{k,i−1}) (z − 1)^{kp−i} ,

which shows (46). From (42) and (44) we get

∑_{i=0}^{kp+l−1}^{p}(a_{l+1})_{k,i} (z − 1)^{kp+l−i−1} = (z^{k}Q_{p−1}^{k} (z)) Q_{l−1} (z)

= ∑_{i=0}^{kp}^{p}(a_{2})_{k,i} (z − 1)^{kp−i} ∑_{j=0}^{l−1}^{l}(a_{1})_{1,j} (z − 1)^{l−1−j}

= ∑_{i=0}^{kp} ∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j}) (^{p}(a_{2})_{k,i}) (z − 1)^{kp+l−1−i−j}

= ∑_{i=0}^{kp+l−1} (∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j} ) (^{p}(a_{2})_{k,i−j})) (z − 1)^{kp+l−i−1} ,

from where (47) follows. From (39) (with k replaced by k + 1), together with (36) and (44) we have that

∑_{i=0}^{(k+1)p−1}^{p}(a_{1})_{k+1,i} (z − 1)^{(k+1)p−1−i} = z^{k}Q_{p−1}^{k+1} (z)

= Q_{p−1} (z) (z^{k}Q_{p−1}^{k} (z))

= (∑_{j=0}^{p−1}^{p}(a_{1})_{1,j} (z − 1)^{p−1−j}) (∑_{i=0}^{kp}^{p}(a_{2})_{k,i} (z − 1)^{kp−i})

= ∑_{i=0}^{kp} ∑_{j=0}^{p−1} (^{p}(a_{1})_{1,j}) (^{p}(a_{2})_{k,i}) (z − 1)^{(k+1)p−1−i−j}

= ∑_{i=0}^{(k+1)p−1} ∑_{j=0}^{p−1} (^{p}(a_{1})_{1,j}) (^{p}(a_{2})_{k,i−j}) (z − 1)^{(k+1)p−1−i} ,

which proves (48).

Thus, beginning with the sequence ^{p}(a_{1})_{k,i}, we use (46) to construct the sequence ^{p}(a_{2})_{k,i}. Using this later sequence, together with the sequences ^{l}(a_{1})_{1,j} of the level 1 of previous powers l, l = 2, 3, …, p − 1, we construct the sequences ^{p}(a_{3})_{k,i} ,^{p}(a_{4})_{k,i} , …,^{p}(a_{p})_{k,i} with (47). Finally, with (48) we move from the level k to the level k + 1, constructing the first sequence of this new level, namely ^{p}(a_{1})_{k+1,i}. And thus a new story begins at the level k + 1: Following the relations (46) and (47) we construct the remaining p − 1 sequences of the new level k + 1. Observe that (47) is consistent with the fact ^{p}(a_{l+1})_{0,i} = ^{l}(a_{1})_{1,i} already noticed, since ^{p}(a_{2})_{0,i} = (1, 0, 0, …).

We can write the sequences ^{p}(a_{m})_{k,i}, m = 1, 2, …, p, in a “Sulanke style” as follows:

s_{m,n} = \{ s_{m,n−1} + s_{m−1,n},  if m + n ≡ 0 (mod p); s_{m,n−1} + 2s_{m−1,n},  if m + n ≡ 1 (mod p); s_{m,n−2} + 6s_{m−1,n−1} + 6s_{m−2,n},  if m + n ≡ 2 (mod p); ⋮ \begin{matrix}^{p}(a_{1})_{1,0} s_{m,n−p+1} +^{p}(a_{1})_{1,1} s_{m−1,n−p+2} \\ + ⋯ +^{p}(a_{1})_{1,p−1} s_{m−p+1,n} \end{matrix} , if m + n ≡ (p − 1) (mod p),

together with the initial condition s_{0,0} = 1, and the fact that s_{m,n} = 0 if m < 0 or n < 0. The correspondence with our sequences ^{p}(a_{m})_{k,i}, m = 1, 2, …, p, is

p(a_{2})_{k,i} ⟷ s_{i,kp−i}
p(a_{3})_{k,i} ⟷ s_{i,kp+1−i}
p(a_{4})_{k,i} ⟷ s_{i,kp+2−i}
⋮
p(a_{p})_{k,i} ⟷ s_{i,(k+1)p−2−i}
p(a_{1})_{k,i} ⟷ s_{i,kp−1−i}

Corollary 10. By means of the sequence ^{p}(a_{2})_{1,i} of level 1, we can construct each sequence p(a_{m})_{k+1,i}, m = 1, 2, 3, …, p, of level k + 1 using only the sequence of the same type ^{p}(a_{m})_{k,i} of the previous level k, as follows:

p(a_{m})_{k+1,i} = ∑_{j=0}^{p} (^{p}(a_{2})_{1,j}) (^{p}(a_{m})_{k,i−j}) .  (49)

Proof. By substituting (46) in (48) we get

p(a_{1})_{k+1,i} = ∑_{j=0}^{p−1} (^{p}(a_{1})_{1,j}) (^{p}(a_{2})_{k,i−j})

= ∑_{j=0}^{p−1} (^{p}(a_{1})_{1,j}) (^{p}(a_{1})_{k,i−j} +^{p}(a_{1})_{k,i−j−1})

= ∑_{j=0}^{p} (^{p}(a_{1})_{1,j} +^{p}(a_{1})_{1,j−1}) (^{p}(a_{1})_{k,i−j})

= ∑_{j=0}^{p} (^{p}(a_{2})_{1,j}) (^{p}(a_{1})_{k,i−j}) ,

which proves (49) for m = 1 . Now, we use (46) and the case m = 1 previously proved to obtain

p(a_{2})_{k+1,i} = ^{p}(a_{1})_{k+1,i} +^{p}(a_{1})_{k+1,i−1}

= ∑_{j=0}^{p} (^{p}(a_{2})_{1,j}) (^{p}(a_{1})_{k,i−j} +^{p}(a_{1})_{k,i−j−1})

= ∑_{j=0}^{p} (^{p}(a_{2})_{1,j}) (^{p}(a_{2})_{k,i−j}) ,

which proves (49) for m = 2. For 2 ≤ l ≤ p − 1 use (47) and the case m = 2 previously proved to get

p(a_{l+1})_{k+1,i} = ∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j} ) (^{p}(a_{2})_{k+1,i−j})

= ∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j} ) ∑_{s=0}^{p} (^{p}(a_{2})_{1,s}) (^{p}(a_{2})_{k,i−j−s})

= ∑_{s=0}^{p} (^{p}(a_{2})_{1,s}) ∑_{j=0}^{l−1} (^{l}(a_{1})_{1,j} ) (^{p}(a_{2})_{k,i−j−s})

= ∑_{s=0}^{p} (^{p}(a_{2})_{1,s}) (^{p}(a_{l+1})_{k,i−s}) ,

as wanted.

Corollary 11. Let us denote the sum ∑_{j=0}^{p} ^{p}(a_{2})_{1,j} by ^{p}S_{2}. The sum of the elements of the sequence ^{p} (a_{m})_{k,i} can be calculated as follows:

For m = 1

∑_{i=0}^{kp−1}^{p}(a_{1})_{k,i} = \frac{1}{2} (^{p}S_{2})^{k} .  (50)

For m = 2, 3, …, p

∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k,i} = Q_{m−2} (2) (^{p}S_{2})^{k} .  (51)

Proof. If in (45) we substitute l by m − 1 and set z = 2, we obtain

∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k,i} = 2^{k}Q_{p−1}^{k} (2) Q_{m−2} (2) ,  (52)

where m = 1, 2, …, p. In particular if we set m = 2 we get

∑_{i=0}^{kp}^{p}(a_{2})_{k,i} = 2^{k}Q_{p−1}^{k} (2) = (^{p}S_{2})^{k} .  (53)

(since Q_{0} (z) = 1). Combining these two expressions we obtain (51). From (53) and (39) we see at once that (50) holds.

Observe that by using (52) and (53) we can write

∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k,i} = (^{p}S_{2})^{k−1} 2Q_{p−1} (2) Q_{m−2} (2) ,

and then (again from (52) with k = 1)

∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k,i} = (^{p}S_{2})^{k−1} ∑_{i=0}^{p+m−2}^{p}(a_{m})_{1,i}.  (54)

Thus, by knowing ^{p}S_{2} and the value of the sum of the elements of the sequence ^{p}(a_{m})_{1,i} at the level k = 1, we can obtain the sum of the elements of the sequence ^{p}(a_{m})_{k,i} at the level k.

We comment that it is possible to obtain (54) from (49) as follows:

∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k,i} = ∑_{i=0}^{kp+m−2} ∑_{j=0}^{p} (^{p}(a_{2})_{1,j}) (^{p}(a_{m})_{k−1,i−j})

= ∑_{j=0}^{p}^{p}(a_{2})_{1,j} ∑_{i=0}^{kp+m−2}^{p}(a_{m})_{k−1,i−j}

= ∑_{j=0}^{p}^{p}(a_{2})_{1,j} ∑_{i=j}^{kp+m−2}^{p}(a_{m})_{k−1,i−j}

= (∑_{j=0}^{p}^{p}(a_{2})_{1,j}) ( ∑_{i=0}^{(k−1)p+m−2}^{p}(a_{m})_{k−1,i}) ,

from where we obtain (54). Proposition 12. Let k_{1}, k_{2} ∈ ℕ be given. The following convolution relations hold

p(a_{1})_{k_{1},i} ∗^{p}(a_{2})_{k_{2},i} = ^{p}(a_{1})_{k_{1}+k_{2},i} ,  (55)
p(a_{2})_{k_{1},i} ∗^{p}(a_{2})_{k_{2},i} = ^{p}(a_{2})_{k_{1}+k_{2},i} ,  (56)

and, for 2 ≤ l ≤ p − 1

p(a_{l+1})_{k_{1},i} ∗^{p}(a_{2})_{k_{2},i} = ^{p}(a_{l+1})_{k_{1}+k_{2},i} .  (57)

Proof. From (39) and (44) we see that

(z^{k_{1}−1}Q_{p−1}^{k_{1}} (z)) (z^{k_{2}}Q_{p−1}^{k_{2}} (z)) = z^{k_{1}+k_{2}−1}Q_{p−1}^{k_{1}+k_{2}} (z) .

This shows (55). By using (44) we also have

(z^{k_{1}}Q_{p−1}^{k_{1}} (z)) (z^{k_{2}}Q_{p−1}^{k_{2}} (z)) = z^{k_{1}+k_{2}}Q_{p−1}^{k_{1}+k_{2}} (z) ,

which shows (56).Now, if 2 ≤ l ≤ p − 1 we use (42) and (44) to write

(z^{k_{1}}Q_{p−1}^{k_{1}} (z) Q_{l−1} (z)) (z^{k_{2}}Q_{p−1}^{k_{2}} (z)) = z^{k_{1}+k_{2}}Q_{p−1}^{k_{1}+k_{2}} (z) Q_{l−1} (z) ,

from where (57) follows.

5 Cases p = 3 and p = 4

We follow the same steps of previous section in the cases p = 3 and p = 4. In the case p = 3 we have

Z (n^{3}) = \frac{z (z^{2} + 4z + 1)}{(z − 1)^{4}}.  (58)

Since z^{2} + 4z + 1 = (z − 1)^{2} + 6 (z − 1) + 6, we have the first sequence ^{3}(a_{1})_{1,i} = (1, 6, 6, 0, 0, …). Thus

Z (n^{3}) = \frac{z}{(z − 1)^{2}} + 6\frac{z}{(z − 1)^{3}} + 6\frac{z}{(z − 1)^{4}} ,

and then

n^{3} = \binom{n}{1} + 6\binom{n}{2} + 6\binom{n}{3}.  (59)

For k ∈ ℕ we have that

Z (∗^{k}n^{3}) = z \frac{z^{k−1} (z^{2} + 4z + 1)^{k}}{(z − 1)^{4k}} ,

and we define the coefficients ^{3}(a_{1})_{k,i} by

z^{k−1} (z^{2} + 4z + 1)^{k} = ∑_{i=0}^{3k−1}^{3}(a_{1})_{k,i} (z − 1)^{3k−1−i} .  (60)

Then

Z (∗^{k}n^{3}) = ∑_{i=0}^{3k−1}^{3}(a_{1})_{k,i} \frac{z}{(z − 1)^{k+i+1}} ,

which means that

∗^{k}n^{3} = ∑_{i=0}^{3k−1}^{3}(a_{1})_{k,i} \binom{n}{k + i}.  (61)

Now, from the sequence ∗^{k}n^{3} ∗ n, which has Z transform

Z (∗^{k}n^{3} ∗ n) = z \frac{z^{k} (z^{2} + 4z + 1)^{k}}{(z − 1)^{4k+2}} ,

we define the coefficients ^{3}(a_{2})_{k,i} by

z^{k} (z^{2} + 4z + 1)^{k} = ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} (z − 1)^{3k−i} .  (62)

When k = 0 we have ^{3}(a_{2})_{0,0} = 1, so the sequence ^{3}(a_{2})_{0,i} is ^{3}(a_{2})_{0,i} = (1, 0, 0, …). Then we have

Z (∗^{k}n^{3} ∗ n) = ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} \frac{z}{(z − 1)^{k+i+2}} ,

from where

∗^{k}n^{3} ∗ n = ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} \binom{n}{k + i + 1}.  (63)

Next we consider the sequence ∗^{k}n^{3} ∗ n^{2} , which has Z transform

Z (∗^{k}n^{3} ∗ n^{2}) = z \frac{z^{k} (z^{2} + 4z + 1)^{k} (z + 1)}{(z − 1)^{4k+3}},

and define ^{3}(a_{3})_{k,i} by

z^{k} (z^{2} + 4z + 1)^{k} (z + 1) = ∑_{i=0}^{3k+1}^{3}(a_{3})_{k,i} (z − 1)^{3k+1−i} .  (64)

When k = 0 the polynomial z^{k} (z^{2} + 4z + 1)^{k} (z + 1) is equal to z + 1 = (z − 1) + 2, so we set ^{3}(a_{3})_{0,0} = 1 and ^{3}(a_{3})_{0,1} = 2. Thus ^{3}(a_{3})_{0,i} = (1, 2, 0, 0, …). Then we have

Z (∗^{k}n^{3} ∗ n^{2}) = ∑_{i=0}^{3k+1}^{3}(a_{3})_{k,i} \frac{z}{(z − 1)^{k+i+2}} ,

which means that

∗^{k}n^{3} ∗ n^{2} = ∑_{i=0}^{3k+1}^{3}(a_{3})_{k,i} \binom{n}{k + i + 1}.  (65)

Now we establish relations among the sequences ^{3}(a_{1})_{k,i} , ^{3}(a_{2})_{k,i} and ^{3}(a_{3})_{k,i}. From (60) and (62) we have

∑_{i=0}^{3k}^{3}(a_{2})_{k,i} (z − 1)^{3k−i} = z ∑_{i=0}^{3k−1}^{3}(a_{1})_{k,i} (z − 1)^{3k−1−i} ,

and from here we obtain that

3(a_{2})_{k,i} = ^{3}(a_{1})_{k,i} +^{3}(a_{1})_{k,i−1} .  (66)

Now, by from (62) and (64) we get

∑_{i=0}^{3k+1}^{3}(a_{3})_{k,i} (z − 1)^{3k+1−i} = (z + 1) ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} (z − 1)^{3k−i} ,

and from here we get

3(a_{3})_{k,i} = ^{3}(a_{2})_{k,i} + 2 (^{3}(a_{2})_{k,i−1}) .  (67)

Finally, from (60) (with k replaced by k + 1) and (62) we have that

∑_{i=0}^{3k+2}^{3}(a_{1})_{k+1,i} (z − 1)^{3k+2−i} = (z^{2} + 4z + 1) ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} (z − 1)^{3k−i} ,

and from this expression we get

3(a_{1})_{k+1,i} = ^{3}(a_{2})_{k,i} + 6 (^{3}(a_{2})_{k,i−1}) + 6 (^{3}(a_{2})_{k,i−2}) .  (68)

Thus we have three kind of sequences ^{3}(a_{1})_{k,i} ,^{3}(a_{2})_{k,i} and ^{3}(a_{3})_{k,i} related as follows:

\begin{matrix}^{3}(a_{2})_{k,i} = ^{3}(a_{1})_{k,i} +^{3}(a_{1})_{k,i−1} , \\ ^{3}(a_{3})_{k,i} = ^{3}(a_{2})_{k,i} + 2 (^{3}(a_{2})_{k,i−1}) , \\ ^{3}(a_{1})_{k+1,i} = ^{3}(a_{2})_{k,i} + 6 (^{3}(a_{2})_{k,i−1}) + 6 (^{3}(a_{2})_{k,i−2}) . \end{matrix}

We can begin with ^{3}(a_{2})_{0,i} = (1, 0, 0, …), and then use (67) to obtain ^{3}(a_{3})_{0,i} = ^{3}(a_{2})_{k,i} + 2 (^{3}(a_{2})_{k,i−1}) = (1, 0, 0, …) + 2 (0, 1, 0, 0, …) = (1, 2, 0, 0, …). Now we move to level 1 with (68)

3(a_{1})_{1,i} = ^{3}(a_{2})_{0,i} + 6 (^{3}(a_{2})_{0,i−1}) + 6 (^{3}(a_{2})_{0,i−2}) = (1, 6, 6, 0, 0, …) .

(This sequence is (59) and can be taken as the starting point.) Continuing with the level k = 1 we have according to (66) that

3(a_{2})_{1,i} = ^{3}(a_{1})_{1,i} +^{3}(a_{1})_{1,i−1} = (1, 7, 12, 6, 0, 0, …) ,

and according to (67)

3(a_{3})_{1,i} = ^{3}(a_{2})_{1,i} + 2 (^{3}(a_{2})_{1,i−1}) = (1, 9, 26, 30, 12, 0, 0, …) ,

and now we move to level k = 2 with (68)

3(a_{1})_{2,i} = ^{3}(a_{2})_{1,i} + 6 (^{3}(a_{2})_{1,i−1}) + 6 (^{3}(a_{2})_{1,i−2})
= (1, 13, 60, 120, 108, 36, 0, 0, …) ,

and son on. The first sequences are

3(a_{2})_{0,i} 1 0 0 …
3(a_{3})_{0,i} 1 2 0  0 …
3(a_{1})_{1,i} 1 6 6  0  0 …
3(a_{2})_{1,i} 1 7 12 6  0  0  …
3(a_{3})_{1,i} 1 9 26 30 12  0  0  …
3(a_{1})_{2,i} 1 13 60 120 108 36  0  0  …
3(a_{2})_{2,i} 1 14 73 180 228 144 36  0  0 …
3(a_{3})_{2,i} 1 16 101 326 588 600 324  72  0  0 …
3(a_{1})_{3,i} 1 20 163 702 1746 2592 2268 1080 216 0  0 …
3(a_{2})_{3,i} 1 21 183 865 2448 4338 4860 3348 1296 216 0 0 …
3(a_{3})_{3,i} 1 23 225 1231 4178 9234 13536 13068 7992 2808 432 0 0 …

We can write the sequences ^{3}(a_{1})_{k,i} ,^{3}(a_{2})_{k,i} and ^{3}(a_{3})_{k,i} in a “Sulanke style” as follows:

s_{m,n} = \{ \begin{matrix}s_{m,n−1} + s_{m−1,n}, & if & m + n ≡ 0 (mod 3); \\ s_{m,n−1} + 2s_{m−1,n}, & if & m + n ≡ 1 (mod 3); \\ s_{m,n−2} + 6s_{m−1,n−1} + 6s_{m−2,n}, & if & m + n ≡ 2 (mod 3), \end{matrix}

together with the initial condition s_{0,0} = 1, and the fact that s_{m,n} = 0 if m < 0 or n < 0. The correspondence with our sequences ^{3}(a_{1})_{k,i} ,^{3}(a_{2})_{k,i} and ^{3}(a_{3})_{k,i} is ^{3}(a_{2})_{k,i} ↔ s_{i,3k−i}, 3(a_{3})_{k,i} ↔ s_{i,3k+1−i} and ^{3}(a_{1})_{k,i} ↔ s_{i,3k−1−i}.

Combining (66) and (68) we obtain that

3(a_{1})_{k+1,i} = ^{3}(a_{1})_{k,i} + 7 (^{3}(a_{1})_{k,i−1}) + 12 (^{3}(a_{1})_{k,i−2}) + 6 (^{3}(a_{1})_{k,i−3}) .

One can see easily that the same relation is valid if a_{1} is substituted by a_{2} or a_{3}. That is, we have that

3(a_{m})_{k+1,i} = ^{3}(a_{m})_{k,i} + 7 (^{3}(a_{m})_{k,i−1}) + 12 (^{3}(a_{m})_{k,i−2}) + 6 (^{3}(a_{m})_{k,i−3}) ,  (69)

for m = 1, 2, 3. For example, if m = 1 we have ^{3}(a_{1})_{1,i} = (1, 6, 6, 0, 0, …). Thus, with (69) we obtain

3(a_{1})_{2,i} = ^{3}(a_{1})_{1,i} + 7 (^{3}(a_{1})_{1,i−1}) + 12 (^{3}(a_{1})_{1,i−2}) + 6 (^{3}(a_{1})_{1,i−3})
= (1, 13, 60, 120, 108, 36, 0, 0, …) .

Again (69) gives us

3(a_{1})_{3,i} = ^{3}(a_{1})_{2,i} + 7 (^{3}(a_{1})_{2,i−1}) + 12 (^{3}(a_{1})_{2,i−2}) + 6 (^{3}(a_{1})_{2,i−3})
= (1, 20, 163, 702, 1746, 2592, 2268, 1080, 216, 0, 0, …) ,

and so on.

Now, since ^{3}S_{2} = ∑_{j=0}^{3} ^{3}(a_{2})_{1,j} = 1 + 7 + 12 + 6 = 26, we have according to (50) and (51)

∑_{i=0}^{3k−1}^{3}(a_{1})_{k,i} = \frac{1}{2} (26)^{k} , ∑_{i=0}^{3k}^{3}(a_{2})_{k,i} = 26^{k} , ∑_{i=0}^{3k+1}^{3}(a_{3})_{k,i} = 3 (26)^{k} .

Finally we establish relations involving convolutions of the sequences ^{3}(a_{1})_{k,i} ,^{3}(a_{2})_{k,i} and 3(a_{3})_{k,i}. For given k_{1}, k_{2} ∈ ℕ, we have

(z^{k_{1}−1} (z^{2} + 4z + 1)^{k_{1}}) (z^{k_{2}} (z^{2} + 4z + 1)^{k_{2}}) = z^{k_{1}+k_{2}−1} (z^{2} + 4z + 1)^{k_{1}+k_{2}} ,

and then, from (60) and (62) we obtain that

(^{3}(a_{1})_{k_{1},i}) ∗ (^{3}(a_{2})_{k_{2},i}) = ^{3}(a_{1})_{k_{1}+k_{2},i} .

Similarly, since

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

we have according to (62) that

(^{3}(a_{2})_{k_{1},i}) ∗ (^{3}(a_{2})_{k_{2},i}) = ^{3}(a_{2})_{k_{1}+k_{2},i} .

Finally, since

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

we have according to (62) and (64) that

(^{3}(a_{3})_{k_{1},i}) ∗ (^{3}(a_{2})_{k_{2},i}) = ^{3}(a_{3})_{k_{1}+k_{2},i} .

We mention that it is possible to give explicit formulas for the elements of the sequences ^{3}(a_{1})_{k,i}, ^{3}(a_{2})_{k,i} and ^{3}(a_{3})_{k,i}, just by doing the explicit expansions of the polynomials z^{k−1} (z^{2} + 4z + 1)^{k}, z^{k} (z^{2} + 4z + 1)^{k} and z^{k} (z^{2} + 4z + 1)^{k} (z + 1) in powers if z − 1, corresponding to (60), (62) and (64), respectively. We omit the details of the calculations and only show the corresponding expressions (just for the records)

3(a_{1})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} \binom{k − 1}{3k − 1 − i − j_{1} − j_{2}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}6^{k−j_{2}},

3(a_{2})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} \binom{k}{3k − i − j_{1} − j_{2}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}6^{k−j_{2}},

3(a_{3})_{k,i} = ∑_{j_{3}=0}^{1} ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} \binom{k}{3k + 1 − i − j_{1} − j_{2} − j_{3}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}\binom{2}{j_{3} + 1}6^{k−j_{2}}.

Now we present the results in the case p = 4. We have

n^{4} = \binom{n}{1} + 14\binom{n}{2} + 36\binom{n}{3} + 24\binom{n}{4}.

The coefficients ^{4}(a_{1})_{k,i}, ^{4}(a_{2})_{k,i}, ^{4}(a_{3})_{k,i} and ^{4}(a_{4})_{k,i} are defined by

z^{k−1} (z + 1)^{k} (z^{2} + 10z + 1)^{k} = ∑_{i=0}^{4k−1}^{4}(a_{1})_{k,i} (z − 1)^{4k−1−i} ,

z^{k} (z + 1)^{k} (z^{2} + 10z + 1)^{k} = ∑_{i=0}^{4k}^{4}(a_{2})_{k,i} (z − 1)^{4k−i} ,

z^{k} (z + 1)^{k+1} (z^{2} + 10z + 1)^{k} = ∑_{i=0}^{4k+1}^{4}(a_{3})_{k,i} (z − 1)^{4k+1−i} ,

z^{k} (z + 1)^{k} (z^{2} + 10z + 1)^{k} (z^{2} + 4z + 1) = ∑_{i=0}^{4k+2}^{4}(a_{4})_{k,i} (z − 1)^{4k+2−i} .

These coefficients are involved in the formulas

\begin{matrix}∗^{k}n^{4} = ∑_{i=0}^{4k−1}^{4}(a_{1})_{k,i} \binom{n}{k + i}, \\ ∗^{k}n^{4} ∗ n = ∑_{i=0}^{4k}^{4}(a_{2})_{k,i} \binom{n}{k + i + 1}, \\ ∗^{k}n^{4} ∗ n^{2} = ∑_{i=0}^{4k+1}^{4}(a_{3})_{k,i} \binom{n}{k + i + 1}, \\ ∗^{k}n^{4} ∗ n^{3} = ∑_{i=0}^{4k+2}^{4}(a_{4})_{k,i} \binom{n}{k + i + 1}. \end{matrix}

The relations among coefficients are in this case

\begin{matrix}^{4}(a_{2})_{k,i} = ^{4}(a_{1})_{k,i} +^{4}(a_{1})_{k,i−1} , \\ ^{4}(a_{3})_{k,i} = ^{4}(a_{2})_{k,i} + 2 (^{4}(a_{2})_{k,i−1}) , \\ ^{4}(a_{4})_{k,i} = ^{4}(a_{2})_{k,i} + 6 (^{4}(a_{2})_{k,i−1}) + 6 (^{4}(a_{2})_{k,i−2}) , \\ ^{4}(a_{1})_{k+1,i} = ^{4}(a_{2})_{k,i} + 14 (^{4}(a_{2})_{k,i−1}) + 36 (^{4}(a_{2})_{k,i−2}) + 24 (^{4}(a_{2})_{k,i−3}) . \end{matrix}

The formula that allows us to construct each sequence at the level k + 1 in terms of the sequence of the same type at the level k is

4(a_{m})_{k+1,i} = ^{4}(a_{m})_{k,i} + 15 (^{4}(a_{m})_{k,i−1}) + 50 (^{4}(a_{m})_{k,i−2}) + 60 (^{4}(a_{m})_{k,i−3}) + 24 (^{4}(a_{m})_{k,i−4}) , where m = 1, 2, 3.4.

The sums of the elements of each sequence are

\begin{matrix}∑_{i=0}^{4k−1}^{4}(a_{1})_{k,i} = \frac{1}{2} (150)^{k} , & ∑_{i=0}^{4k+1}^{4}(a_{3})_{k,i} = 3 (150)^{k} , \\ ∑_{i=0}^{4k}^{4}(a_{2})_{k,i} = (150)^{k} , & ∑_{i=0}^{4k+2}^{4}(a_{4})_{k,i} = 13 (150)^{k} . \end{matrix}

For k_{1}, k_{2} ∈ ℕ, we have the following convolution relations

\begin{matrix}^{4}(a_{1})_{k_{1},i} ∗^{4}(a_{2})_{k_{2},i} = ^{4}(a_{1})_{k_{1}+k_{2},i} , \\ ^{4}(a_{2})_{k_{1},i} ∗^{4}(a_{2})_{k_{2},i} = ^{4}(a_{2})_{k_{1}+k_{2},i} , \\ ^{4}(a_{3})_{k_{1},i} ∗^{4}(a_{2})_{k_{2},i} = ^{4}(a_{3})_{k_{1}+k_{2},i} , \\ ^{4}(a_{4})_{k_{1},i} ∗^{4}(a_{2})_{k_{2},i} = ^{4}(a_{4})_{k_{1}+k_{2},i} . \end{matrix}

The first sequences in this case are

4(a_{2})_{0,i} 1 0 0 …
4(a_{3})_{0,i} 1 2 0  0  …
4(a_{4})_{0,i} 1 6 6  0  0  …
4(a_{1})_{1,i} 1 14 36 24  0  0  …
4(a_{2})_{1,i} 1 15 50 60  24  0  0  …
4(a_{3})_{1,i} 1 17 80 160 144  48  0  0  …
4(a_{4})_{1,i} 1 21 146 450 684 504 144  0  0  …
4(a_{1})_{2,i} 1 29 296 1324 3024 3696 2304 576  0  0  …
4(a_{2})_{2,i} 1 30 325 1620 4348 6720 6000 2880 576  0  0 …
4(a_{3})_{2,i} 1 32 385 2270 7588 15416 19440 14880 6336 1152 0 0 …
4(a_{4})_{2,i} 1 36 511 3750 16018 42528 72408 79200 53856 20736 3456 0 0 …

We can write these sequences in a “Sulanke style” as follows:

s_{m,n} = \{ \begin{matrix}s_{m,n−1} + s_{m−1,n}, & if & m + n ≡ 0 (mod 4); \\ s_{m,n−1} + 2s_{m−1,n}, & if & m + n ≡ 1 (mod 4); \\ s_{m,n−2} + 6s_{m−1,n−1} + 6s_{m−2,n}, & if & m + n ≡ 2 (mod 4); \\ s_{m,n−3} + 14s_{m−1,n−2} + 36s_{m−2,n−1} + 24s_{m−3,n}, & if & m + n ≡ 3 (mod 4), \end{matrix}

together with the initial condition s_{0,0} = 1, and the fact that s_{m,n} = 0 if m < 0 or n < 0. The correspondence with our sequences a_{k,i}, b_{k,i} and c_{k,i} is ^{4}(a_{2})_{k,i} ↔ s_{i,4k−i}, ^{4}(a_{3})_{k,i} ↔ s_{i,4k+1−i}, 4(a_{4})_{k,i} ↔ s_{i,4k+2−i} and ^{4}(a_{1})_{k,i} ↔ s_{i,4k−1−i}.

In this case we also have the following explicit formulas for the elements of the sequences

4(a_{1})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} ∑_{j_{3}=0}^{k} \binom{k − 1}{4k − 1 − i − j_{1} − j_{2} − j_{3}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}\binom{k}{j_{3}}2^{2k−j_{2}−j_{3}}6^{k−j_{2}},

4(a_{2})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} ∑_{j_{3}=0}^{k} \binom{k}{4k − i − j_{1} − j_{2} − j_{3}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}\binom{k}{j_{3}}2^{2k−j_{2}−j_{3}}6^{k−j_{2}},

4(a_{3})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} ∑_{j_{3}=0}^{k+1} \binom{k}{4k + 1 − i − j_{1} − j_{2} − j_{3}}\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}\binom{k + 1}{j_{3}}2^{2k+1−j_{2}−j_{3}}6^{k−j_{2}},

4(a_{4})_{k,i} = ∑_{j_{1}=0}^{k} ∑_{j_{2}=0}^{j_{1}} ∑_{j_{3}=0}^{k}(\binom{k}{4k−i−j_{1}−j_{2}−j_{3}}+6\binom{k + 1}{4k−i+2−j_{1}−j_{2}−j_{3}})\binom{k}{j_{1}}\binom{j_{1}}{j_{2}}\binom{k}{j_{3}}2^{2k−j_{2}−j_{3}}6^{k−j_{2}}.

6 Final remarks

The case p = 2 corresponding to Sulanke numbers seems not to be just a particular case of the generalized setting presented in section 4. In fact, we have the following conjecture.

Conjecture 13. Let p ∈ ℕ be given. The convolutions ∗^{k}n^{2p} ∗ n^{l}, l = 0, 1, …, 2p − 1, have a factorization passing through identities (21) and (24) where Sulanke numbers a_{k,i} and b_{k,i} are involved (or some identities similar to them).

For example, we have the following expressions for the sequences ∗^{k}n^{4}, ∗^{k}n^{4} ∗ n, ∗^{k}n^{4} ∗ n^{2} and ∗^{k}n^{4} ∗ n^{3}

∗^{k}n^{4} = ∗^{k} (δ + 12n) ∗ ∑_{i=0}^{2k−1} a_{k,i}\binom{n}{k + i},

∗^{k}n^{4} ∗ n = ∗^{k} (δ + 12n) ∗ ∑_{i=0}^{2k} b_{k,i}\binom{n}{k + i + 1},

∗^{k}n^{4} ∗ n^{2} = ∗^{k} (δ + 12n) ∗ ∑_{i=0}^{2k+1} a_{k+1,i}\binom{n}{k + i + 1},

∗^{k}n^{4} ∗ n^{3} = ∗^{k} (δ + 12n) ∗ ∑_{i=0}^{2k} b_{k,i} (\binom{n}{k + i + 1} + 6\binom{n + 1}{k + i + 3}) .

In order to show each one of these identities one can verify that both sides of each one have the same Z transform. For example, for the first identity we have (by using that Z (δ) = 1, the convolution theorem and (19))

Z (∗^{k} (δ + 12n) ∗ ∑_{i=0}^{2k−1} a_{k,i}\binom{n}{k + i}) = (1 + \frac{12z}{(z − 1)^{2}} )^{k} \frac{z^{k} (z + 1)^{k}}{(z − 1)^{3k}}

= \frac{z^{k} (z + 1)^{k} (z^{2} + 10z + 1)^{k}}{(z − 1)^{5k}}

= Z (∗^{k}n^{4}) .

The fact that Q_{p−1} (z) are the Eulerian polynomials (see remark 8) opens a new possibility for developing the ideas of this work. The model we followed here were Sulanke numbers, so we were interested in the expansion of Q_{p−1} (z) in powers of z − 1, from which we defined the sequence ^{p}(a_{1})_{1,i} as the coefficients of such expansion. This led us to the first important formula of section 4, namely

n^{p} = ∑_{i=0}^{p−1}^{p}(a_{1})_{1,i} \binom{n}{i + 1}.  (70)

But if we leave Q_{p−1} (z) simply as Q_{p−1} (z) = ∑_{i=0}^{p−1} a_{p−1,i}z^{i}, we obtain from (35) that

Z (n^{p}) = \frac{zQ_{p−1} (z)}{(z − 1)^{p+1}} = \frac{z ∑_{i=0}^{p−1} a_{p−1,i}z^{i}}{(z − 1)^{p+1}} = ∑_{i=0}^{p−1} a_{p−1,i}z^{i} \frac{z}{(z − 1)^{p+1}} ,

and then

n^{p} = ∑_{i=0}^{p−1} a_{p−1,i}\binom{n + i}{p}.  (71)

This is (a version of) the well-known Worpitzky’s identity (obtained by J. Worpitzky [11] in 1882). It is clear that both formulas (70) and (71) have the same flavor: they show how n^{p} decomposes as a linear combination of binomial coefficients. In (70) the binomial coefficients are \binom{n}{1}, \binom{n}{2}, …, \binom{n}{p}, and the coefficients of them are the (generalized) Sulanke numbers p(a_{1})_{1,0} ,^{p}(a_{1})_{1,1} , …,^{p}(a_{1})_{1,p−1}, respectively. In the Worpitzky’s formula (71) the binomial coefficients are \binom{n}{p}, \binom{n+1}{p}, …, \binom{n+p−1}{p}, and the coefficients of them are the Eulerian numbers a_{p−1,0}, a_{p−1,1}, …, a_{p−1,p−1}, respectively. It is natural to expect that a similar structure to that showed in section 4 occur if we begin with Worpitzky’s identity instead of (70). In this case we expect sequences ^{p}(b_{m})_{k,i} involved (as coefficients) in formulas that express convolutions ∗^{k}n^{p} ∗ n^{m−1} as linear combinations of binomial coefficients. And clearly these sequences p(b_{m})_{k,i} have to do with Eulerian numbers. For example, in the case p = 4 we have four kind of sequences ^{4}(b_{1})_{k,i} ,^{4}(b_{2})_{k,i} ,^{4}(b_{3})_{k,i} and ^{4}(b_{4})_{k,i} related by

4(b_{2})_{k,i} = ^{4}(b_{1})_{k,i−1} ,
4(b_{3})_{k,i} = ^{4}(b_{2})_{k,i} +^{4}(b_{2})_{k,i−1} ,
4(b_{4})_{k,i} = ^{4}(b_{2})_{k,i} + 4 (^{4}(b_{2})_{k,i−1}) +^{4}(b_{2})_{k,i−2} ,
4(b_{1})_{k+1,i} = ^{4}(b_{2})_{k,i} + 11 (^{4}(b_{2})_{k,i−1}) + 11 (^{4}(b_{2})_{k,i−2}) +^{4}(b_{2})_{k,i−3} .

For m = 1, 2, 3, 4, we can obtain the sequence ^{4}(b_{m})_{k+1,i} in the level k + 1 by using only the sequence ^{4}(b_{m})_{k,i} of the same type in the level k

4(b_{m})_{k+1,i} = ^{4}(b_{m})_{k,i−1} + 11 (^{4}(b_{m})_{k,i−2}) + 11 (^{4}(b_{m})_{k,i−3}) +^{4}(b_{m})_{k,i−4} .

These sequences are involved in the following formulas

∗^{k}n^{4} = ∑_{i=0}^{4k−1}^{4}(b_{1})_{k,i} \binom{n + i}{5k − 1},

∗^{k}n^{4} ∗ n = ∑_{i=0}^{4k}^{4}(b_{2})_{k,i} \binom{n + i}{5k + 1},

∗^{k}n^{4} ∗ n^{2} = ∑_{i=0}^{4k+1}^{4}(b_{3})_{k,i} \binom{n + i}{5k + 2},

∗^{k}n^{4} ∗ n^{3} = ∑_{i=0}^{4k+2}^{4}(b_{4})_{k,i} \binom{n + i}{5k + 3},

which could be called Worpitzky-type identities.

Beginning with ^{4}(b_{2})_{0,i} = (1, 0, 0, …) we can construct all the sequences ^{4}(b_{3})_{0,i} ,^{4}(b_{4})_{0,i} and ^{4}(b_{m})_{k,i}, k ∈ ℕ, m = 1, 2, 3, 4. Some of them are

4(b_{2})_{0,i} 1 0 0 …
4(b_{3})_{0,i} 1 1 0 0 …
4(b_{4})_{0,i} 1 4 1 0 0 …
4(b_{1})_{1,i} 1 11 11 1 0  0 …
4(b_{2})_{1,i} 0 1 11 11 1  0  0 …
4(b_{3})_{1,i} 0 1 12 22 12 1  0  0 …
4(b_{4})_{1,i} 0 1 15 56 56 15  1  0  0 …
4(b_{1})_{2,i} 0 1 22 143 244 143 22  1  0  0 …
4(b_{2})_{2,i} 0 0 1 22 143 244 143 22  1  0  0 …
4(b_{3})_{2,i} 0 0 1 23 165 387 387 165 23  1  0 0 …
4(b_{4})_{2,i} 0 0 1 26 232 838 1262 838 232 26 1 0 0 …
4(b_{1})_{3,i} 0 0 1 33 396 2060 4422 4422 2060 396 33 1 0 0 …
4(b_{2})_{3,i} 0 0 0 1 33 396 2060 4422 4422 2060 396 33 1 0 0 …

We have the same convolution relations of those obtained in the Sulanke case, namely

4(b_{1})_{k_{1},i} ∗^{4}(b_{2})_{k_{2},i} = ^{4}(b_{1})_{k_{1}+k_{2},i} ,
4(b_{2})_{k_{1},i} ∗^{4}(b_{2})_{k_{2},i} = ^{4}(b_{2})_{k_{1}+k_{2},i} ,
4(b_{3})_{k_{1},i} ∗^{4}(b_{2})_{k_{2},i} = ^{4}(b_{3})_{k_{1}+k_{2},i} ,
4(b_{4})_{k_{1},i} ∗^{4}(b_{2})_{k_{2},i} = ^{4}(b_{4})_{k_{1}+k_{2},i} .

Finally, questions about generating functions of the sequences presented in this work, and questions about combinatorial content of the identities obtained here as well, are tasks that remain to do in future works.

7 Acknowledgments

I wish to thank the anonymous referee for his/her valuable comments and suggestions.

References

[1] J.-M. Autebert, A.-M. Décaillot, S. R. Schwer, Henri-Auguste Delannoy et la publication des œuvres posthumes d’Édouard Lucas, Gaz. Math. 95 (2003), 51–62.

[2] Cyril Banderier & Sylviane Schwer, Why Delannoy numbers? J. Statist. Plann. Inference 135 (2005), 40–54.

[3] Henri Delannoy, Emploi de l’échiquier pour la résolution de divers problèmes de probabilité, Comptes rendus du Congrès Annuel de L’Association Française Pour L’Avancement des Sciences, Bordeaux, 24 (1895), 70–90.

[4] G. P. Egorychev, Integral Representations and the Computation of Combinatorial Sums, Transl. Math. Monogr. 59, AMS, 1984.

[5] Urs Graf, Applied Laplace Transforms and z-Transforms for Scientists and Engineers. A Computational Approach using a ‘Mathematica’ Package, Birkhäuser, 2004.

[6] K. Ogata, Discrete-Time Control Systems, Prentice-Hall, 1994.

[7] John Riordan, Introduction to Combinatorial Analysis, Dover, 2002.

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

[9] Robert A. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Seq. 6 (2003), Article 03.1.5.

[10] Robert Vich, Z Transform Theory and Applications, D. Reidel Publishing Company, 1987.

[11] J. Worpitzky, Studien über die Bernoullischen und Eulerschen Zahlen, J. Reine Angew. Math. 94 (1883), 203–232.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B83. Keywords: Convolutions of sequences, Z transform, binomial identities, Worpitzky-type identities.

(Concerned with sequences \underline{A001850}, \underline{A008292}, and \underline{A064861}.)

Received August 31 2009; revised version received January 13 2010. Published in Journal of Integer Sequences, January 18 2010.

Return to Journal of Integer Sequences home page.