On Integer-Sequence-Based Constructions of Generalized Pascal Triangles

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

We introduce an integer sequence based construction of invertible centrally symmetric number triangles, which generalize Pascal’s triangle. We characterize the row sums and central coefficients of these triangles, and examine other properties. Links to the Narayana numbers are explored. Use is made of the Riordan group to elucidate properties of a special one-parameter subfamily. An alternative exponential approach to constructing generalized Pascal triangles is briefly explored.

1 Introduction

In this article, we look at two methods of using given integer sequences to construct generalized Pascal matrices. In the first method, we look at the number triangle associated with the square matrix BDB′, where B is the binomial matrix \binom{n}{k} and D is the diagonal matrix defined by the given integer sequence. We study this construction in some depth, and characterize the sequences related to the central coefficients of the resulting triangles in a special case. We study the cases of the Fibonacci and Jacobsthal numbers in particular. The second construction is defined in terms of a generalization of exp(M), where M is a sub-diagonal matrix defined by the integer sequence in question. Our look at this construction is less detailed. It is a measure of the ubiquity of the Narayana numbers that they arise in both contexts.

The plan of the article is as follows. We begin with an introductory section, where we define what this article will understand as a generalized Pascal matrix, as well as looking at the binomial transform, the Riordan group, and the Narayana numbers, all of which will be used in subsequent sections. The next preparatory section looks at the reversion of the expressions \frac{x}{1+αx+βx^{2}} and \frac{x(1−ax)}{1−bx}, which are closely related to subsequent work. We then introduce the first family of generalized Pascal triangles, and follow this by looking at those elements of this family that correspond to the “power” sequences n → r^{n}, while the section after that takes the specific cases of the Fibonacci and Jacobsthal numbers. We close the study of this family by looking at the generating functions of the columns of these triangles in the general case.

The final section briefly studies an alternative construction based on a generalized matrix exponential construction.

2 Preliminaries

Pascal’s triangle, with general term \binom{n}{k}, n, k ≥ 0, has fascinated mathematicians by its wealth of properties since its discovery [3]. Viewed as an infinite lower-triangular matrix, it is invertible, with an inverse whose general term is given by (−1)^{n−k}\binom{n}{k}. Invertibility follows from the fact that \binom{n}{n} = 1. It is centrally symmetric, since by definition, \binom{n}{k} = \binom{n}{n−k}. All the terms of this matrix are integers.

By a generalized Pascal triangle we shall understand a lower-triangular infinite integer matrix T = T (n, k) with T (n, 0) = T (n, n) = 1 and T (n, k) = T (n, n − k). We shall index all matrices in this paper beginning at the (0, 0)-th element.

We shall use transformations that operate on integer sequences during the course of this note. An example of such a transformation that is widely used in the study of integer sequences is the so-called binomial transform [21], which associates to the sequence with general term a_{n} the sequence with general term b_{n} where

b_{n} = ∑_{k=0}^{n} \binom{n}{k}a_{k}.  (1)

If we consider the sequence with general term a_{n} to be the vector a = (a_{0}, a_{1}, …) then we obtain the binomial transform of the sequence by multiplying this (infinite) vector by the lower-triangle matrix B whose (n, k)-th element is equal to \binom{n}{k}:

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This transformation is invertible, with

a_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}b_{k}.  (2)

We note that B corresponds to Pascal’s triangle. Its row sums are 2^{n}, while its diagonal sums are the Fibonacci numbers F (n + 1). If B^{m} denotes the m−th power of B, then the n−th term of B^{m}a where a = \{a_{n}\} is given by ∑_{k=0}^{n} m^{n−k}\binom{n}{k}a_{k}.

If A(x) is the ordinary generating function of the sequence a_{n}, then the generating function of the transformed sequence b_{n} is \frac{1}{1−x}A(\frac{x}{1−x}). The binomial transform is an element of the Riordan group, which can be defined as follows.

The Riordan group [11], [16] is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + … and f(x) = f_{1}x + f_{2}x^{2} + … where f_{1} ≠ 0 [16]. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair f, g is denoted by (g, f) or R(g, f). The group law is then given by

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

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

If M is the matrix (g, f), and a = {a_{n}} is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)).

Example 1. As an example, the Binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. More generally, B^{k} is the element (\frac{1}{1−kx}, \frac{x}{1−kx}) of the Riordan group. It is easy to show that the inverse B^{−k} of B^{k} is given by (\frac{1}{1+kx}, \frac{x}{1+kx}).

The row sums of the matrix (g, f) have generating function g(x)/(1 − f(x)) while the diagonal sums of (g, f) have generating function g(x)/(1 − xf(x)).

We shall frequently refer to sequences by their sequence number in the On-Line Encylopedia of Integer Sequences [13], [14]. For instance, Pascal’s triangle is \underline{A007318} while the Fibonacci numbers are \underline{A000045}.

Example 2. An example of a well-known centrally symmetric invertible triangle that is not an element of the Riordan group is the Narayana triangle Ñ, defined by

Ñ(n, k) = \frac{1}{k + 1}\binom{n}{k}\binom{n + 1}{k} = \frac{1}{n + 1}\binom{n + 1}{k + 1}\binom{n + 1}{k}

for n, k ≥ 0. Other expressions for Ñ(n, k) are given by

Ñ(n, k) = \binom{n}{k}^{2} − \binom{n}{k + 1}\binom{n}{k − 1} = \binom{n + 1}{k + 1}\binom{n}{k} − \binom{n + 1}{k}\binom{n}{k + 1}.

This triangle begins

Ñ = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 6 & 6 & 1 & 0 & 0 & … \\ 1 & 10 & 20 & 10 & 1 & 0 & … \\ 1 & 15 & 50 & 50 & 15 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We shall characterize this matrix in terms of a generalized matrix exponential construction later in this article. Note that in the literature, it is often the triangle Ñ(n − 1, k − 1) = \frac{1}{n} \binom{n}{k}\binom{n}{k−1} that is referred to as the Narayana triangle. Alternatively, the triangle Ñ(n − 1, k) = \frac{1}{k+1} \binom{n−1}{k}\binom{n}{k} is referred to as the Narayana triangle. We shall denote this latter triangle by N(n, k). We then have

N = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 6 & 6 & 1 & 0 & 0 & … \\ 1 & 10 & 20 & 10 & 1 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Note that for n, k ≥ 1, N(n, k) = \frac{1}{n} \binom{n}{k}\binom{n}{k+1}. We have, for instance,

Ñ(n−1, k−1) = \frac{1}{n}\binom{n}{k}\binom{n}{k − 1} = \binom{n}{k}^{2}−\binom{n − 1}{k}\binom{n + 1}{k} = \binom{n}{k}\binom{n − 1}{k − 1}−\binom{n}{k − 1}\binom{n − 1}{k}.

The last expression represents a 2 × 2 determinant of adjacent elements in Pascal’s triangle. The Narayana triangle is \underline{A001263}.

A related identity is the following, [2], [1]:

∑_{k=0}^{n−1} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}x^{k} = ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n − 1}{2k}c(k)x^{k}(1 + x)^{n−2k−1}  (3)

where c(n) is the n-th Catalan number c(n) = \binom{2n}{n}/(n + 1), \underline{A000108}. This identity can be interpreted in terms of Motzkin paths, where by a Motzkin path of length n we mean a lattice path in Z^{2} between (0, 0) and (n, 0) consisting of up-steps (1, 1), down-steps (1, −1) and horizontal steps (1, 0) which never goes below the x-axis. Similarly, a Dyck path of length 2n is a lattice path in Z^{2} between (0, 0) and (2n, 0) consisting of up-paths (1, 1) and down-steps (1, −1) which never go below the x-axis. Finally, a (large) Schröder path of length n is a lattice path from (0, 0) to (n, n) containing no points above the line y = x, and composed only of steps (0, 1), (1, 0) and (1, 1).

For instance, the number of Schröder paths from (0, 0) to (n, n) is given by the large Schröder numbers 1, 2, 6, 22, 90, … which correspond to z = 2 for the Narayana polynomials [17], [19]

N_{n}(z) = ∑_{k=1}^{n} \frac{1}{n}\binom{n}{k − 1}\binom{n}{k}z^{k}.

3 On the series reversion of \frac{x}{1+αx+βx^{2}} and \frac{x(1−ax)}{1−bx}

A number of the properties of the triangles that we will study are related to the special cases of the series reversions of \frac{x}{1+αx+βx^{2}} and \frac{x(1−ax)}{1−bx} where b = a − 1, α = a + 1 and β = b + 1.

We shall develop results relating to these reversions in full generality in this section and specialize later at the appropriate places.

Solving the equation

\frac{y}{1 + αy + βy^{2}} = x

yields

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

while solving the equation

\frac{y(1 − ay)}{1 − by} = x

leads to

y_{2} = \frac{1 + bx − \sqrt{(1 + bx)^{2} − 4ax}}{2a}.

We shall occasionally use the notation y_{1}(α, β) and y_{2}(a, b) where relevant for these functions. Note for instance that \frac{y_{2}(1,0)}{x} = \frac{1−\sqrt{1−4x}}{2x} is the generating function of the Catalan numbers.

Proposition 3. Let α = a+1, β = b+1, and assume that b = a−1 (and hence, β = α−1). Then

\frac{y_{2}}{x} − y_{1} = 1.

Proof. Straight-forward calculation.

Note that 1 is the generating function of 0^{n} = 1, 0, 0, 0, . . ..

Example 4. Consider the case a = 2, b = 1. Let α = 3 and β = 2, so we are considering \frac{x}{1+3x+2x^{2}} and \frac{x(1−2x)}{1−x}. We obtain

y_{1}(3, 2) = \frac{1 − 3x − \sqrt{1 − 6x + x^{2}}}{4x}
\frac{y_{2}(2, 1)}{x} = \frac{1 + x − \sqrt{1 − 6x + x^{2}}}{4x}
\frac{y_{2}(2, 1)}{x} − y_{1}(3, 2) = 1.

Thus y_{1}(3, 2) is the generating function for 0, 1, 3, 11, 45, 197, 903, 4279, … while \frac{y_{2}(2,1)}{x} is the generating function for 1, 1, 3, 11, 45, 197, 903, 4279, . . .. These are the little Schröder numbers \underline{A001003}.

Example 5. We consider the case a = 1, b = 1 − r, that is, the case of \frac{x(1−x)}{1−(1−r)x}. We obtain

\frac{y_{2}(1, 1 − r)}{x} = \frac{1 − (r − 1)x − \sqrt{(1 + (1 − r)x)^{2} − 4x}}{2x}
= \frac{1 − (r − 1)x − \sqrt{1 − 2(r + 1)x + (r − 1)^{2}x^{2}}}{2x}

Example 6. We calculate the expression \frac{y_{2}(1,1−r)}{rx} − \frac{1−r}{r}. We get

\frac{y_{2}(1, 1 − r)}{rx} − \frac{1 − r}{r} = \frac{1 − (r − 1)x − \sqrt{1 − 2(r + 1)x + (r − 1)^{2}x^{2}}}{2rx} + \frac{2(r − 1)x}{2rx}
= \frac{1 + (r − 1)x − \sqrt{1 − 2(r + 1)x + (r − 1)^{2}x^{2}}}{2rx}
= \frac{y_{2}(r, r − 1)}{x}.

In other words,

\frac{y_{2}(r, r − 1)}{x} = \frac{y_{2}(1, 1 − r)}{rx} − \frac{1 − r}{r}.

A well-known example of this is the case of the large Schröder numbers with generating function \frac{1−x−\sqrt{1−6x+x^{2}}}{2x} and the little Schröder numbers with generating function \frac{1+x−\sqrt{1−6x+x^{2}}}{4x}. In this case, r = 2. Generalizations of this “pairing” for r > 2 will be studied in a later section. For r = 1 both sequences coincide with the Catalan numbers c(n).

Proposition 7. The binomial transform of

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

is

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

Proof. The binomial transform of y_{1} is

\frac{1}{1 − x} \{1 − \frac{αx}{1 − x} − \sqrt{1 − \frac{2αx}{1 − x} + (α^{2} − 4β)\frac{x^{2}}{(1 − x)^{2}}} \} /(2β \frac{x^{2}}{(1 − x)^{2}} )

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

Example 8. The binomial transform of 1, 3, 11, 45, 197, 903, … with generating function \frac{1−3x−\sqrt{1−6x+x^{2}}}{4x^{2}} is 1, 4, 18, 88, 456, 2464, 13736, …, \underline{A068764}, with generating function \frac{1−4x−\sqrt{1−8x+8x^{2}}}{4x^{2}} . Thus the binomial transform links the series reversion of x/(1 + 3x + 2x^{2}) to that of x/(1 + 4x + 2x^{2}). We note that this can be interpreted in the context of Motzkin paths as an incrementing of the colours available for the H(1, 0) steps.

We now look at the general terms of the sequences generated by y_{1} and y_{2}. We use the technique of Lagrangian inversion for this. We begin with y_{1}. In order to avoid notational overload, we use a and b rather than α and β, hoping that confusion won’t arise.

Since for y_{1} we have y = x(1 + ay + by^{2}) we can apply Lagrangian inversion to get the following expression for the general term of the sequence generated by y_{1}:

[t^{n}]y_{1} = \frac{1}{n}[t^{n−1}](1 + at + bt^{2})^{n}.

At this point we remark that there are many ways to develop the trinomial expression, and the subsequent binomial expressions. Setting these different expressions equal for different combinations of a and b and different relations between a and b can lead to many interesting combinatorial identities, many of which can be interpreted in terms of Motzkin paths. We shall confine ourselves to the derivation of two particular expressions. First of all,

[t^{n}]y_{1} = \frac{1}{n}[t^{n−1}](1 + at + bt^{2})^{n}
= \frac{1}{n}[t^{n−1}] ∑_{k=0}^{n} \binom{n}{k}(at + bt^{2})^{k}

= \frac{1}{n}[t^{n−1}] ∑_{k=0}^{n} \binom{n}{k}t^{k} ∑_{j=0}^{k} \binom{k}{j}a^{j}b^{k−j}t^{k−j}

= \frac{1}{n}[t^{n−1}] ∑_{k=0}^{n} ∑_{j=0}^{k} \binom{n}{k}\binom{k}{j}a^{j}b^{k−j}t^{2k−j}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{k}{n − k − 1}a^{2k−n+1}b^{n−k−1}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{k}{2k − n + 1}a^{2k−n+1}b^{n−k−1}.

Of the many other possible expressions for [t^{n}]y_{1}, we cite the following examples:

[t^{n}]y_{1} = \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{k + 1}{2k − n − 1}b^{2k−n+1}b^{n−k−1}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{k}{2k − n + 1}b^{n−k−1}a^{2k−n+1}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{n − k}{k − 1}b^{k−1}a^{n−2k+1}

= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k + 1}\binom{n − k − 1}{k + 1}b^{k}a^{n−2k}.

We shall be interested at a later stage in generalized Catalan sequences. The following interpretation of [t^{n}]y_{1} is therefore of interest.

Proposition 9.

[t^{n}]y_{1} = ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n − 1}{2k}c(k)a^{n−2k−1}b^{k}.

Proof.

[t^{n}]y_{1} = \frac{1}{n}[t^{n−1}](1 + at + bt^{2})^{n}
= \frac{1}{n}[t^{n−1}](at + (1 + bt^{2}))^{n}
= \frac{1}{n}[t^{n−1}] ∑_{j=0}^{n} a^{j}t^{j}(1 + bt^{2})^{n−j}
= \frac{1}{n}[t^{n−1}] ∑_{j=0}^{n} ∑_{k=0}^{n−j} \binom{n}{j}\binom{n − j}{k}a^{j}b^{k}t^{2k+j}
= \frac{1}{n} ∑_{k=0} \binom{n}{n − 2k − 1}\binom{2k + 1}{k}a^{n−2k−1}b^{k}
= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{2k + 1}\binom{2k + 1}{k}a^{n−2k−1}b^{k}
= \frac{1}{n} ∑_{k=0} \frac{n}{2k + 1}\binom{n − 1}{n − 2k − 1}\frac{2k + 1}{k + 1}\binom{2k}{k}a^{n−2k−1}b^{k}
= ∑_{k=0} \binom{n − 1}{2k}c(k)a^{n−2k−1}b^{k}.

Corollary 10.

c(n) = 0^{n} + ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n − 1}{2k}c(k)2^{n−2k−1}
c(n + 1) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − 1}{2k}c(k)2^{n−2k}.

Proof. The sequence c(n) − 0^{n}, or 0, 1, 2, 5, 14, …, has generating function

\frac{1 − \sqrt{1 − 4x}}{2x} − 1 = \frac{1 − 2x − \sqrt{1 − 4x}}{2x}

which corresponds to y_{1}(2, 1).

This is the formula of Touchard [20], with adjustment for the first term. Corollary 11.

[t^{n}]y_{1}(r + 1, r) = ∑_{k=0}^{n−1} \frac{1}{n}\binom{n}{k}\binom{n}{k + 1}r^{k}.

Proof. By the proposition, we have

[t^{n}]y_{1}(r + 1, r) = ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n − 1}{2k}c(k)(r + 1)^{n−2k−1}r^{k}.

The result then follows from identity (3).

This therefore establishes a link to the Narayana numbers. Corollary 12. Let s_{n}(a, b) be the sequence with general term

s_{n}(a, b) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}c(k)a^{n−2k}b^{k}.

Then the binomial transform of this sequence is the sequence s_{n}(a + 1, b) with general term

s_{n}(a + 1, b) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}c(k)(a + 1)^{n−2k}b^{k}.

Proof. This is a re-interpretation of the results of Proposition 7.

We now take a quick look at [t^{n}]y_{2}. In this case, we have

y = x\frac{1 − by}{1 − ay}

so we can apply Lagrangian inversion. Again, various expressions arise depending on the order of expansion of the binomial expressions involved. For instance,

[t^{n}]y_{2} = \frac{1}{n}[t^{n−1}] (\frac{1 − bt}{1 − at})^{n}
= \frac{1}{n}[t^{n−1}](1 − bt)^{n}(1 − at)^{−n}
= \frac{1}{n}[t^{n−1}] ∑_{k=0}^{n} ∑_{j=0} \binom{n}{k}\binom{n + j − 1}{j}a^{j}(−b)^{k}t^{k+j}
= \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{2n − k − 2}{n − 1}a^{n−k−1}(−b)^{k}.

A more interesting development is given by the following.

[t^{n}]\frac{y_{2}}{x} = [t^{n+1}]y_{2}
= \frac{1}{n + 1}[t^{n}](1 − bt)^{n+1}(1 − at)^{−(n+1)}
= \frac{1}{n + 1}[t^{n}] ∑_{k=0}^{n+1} \binom{n + 1}{k}(−bt)^{n+1−k} ∑_{j=0} \binom{−n − 1}{j}(−at)^{j}

= \frac{1}{n + 1}[t^{n}] ∑_{k=0}^{n+1} ∑_{j=0} \binom{n + 1}{k}\binom{n + j}{j}(−b)^{n−k+1}a^{j}t^{n+1−k+j}

= \frac{1}{n + 1} ∑_{j=0} \binom{n + 1}{j + 1}\binom{n + j}{j}(−b)^{n−j}a^{j}

= ∑_{j=0}^{n} \frac{1}{j + 1}\binom{n}{j}\binom{n + j}{j}a^{j}(−b)^{n−j}.

An alternative expression obtained by developing for k above is given by

[t^{n}]\frac{y_{2}}{x} = ∑_{k=0}^{n+1} \frac{1}{n − k + 1}\binom{n}{k}\binom{n + k − 1}{k − 1}a^{k−1}(−b)^{n−k+1}.

Note that the underlying matrix with general element \frac{1}{k+1} \binom{n}{k}\binom{n+k}{k} is \underline{A088617}, whose general element gives the number of Schröder paths from (0, 0) to (2n, 0), having k U(1, 1) steps. Recognizing that ∑_{j=0}^{n} \frac{1}{j+1} \binom{n}{j}\binom{n+j}{j}a^{j}(−b)^{n−j} is a convolution, we can also write

[t^{n}]\frac{y_{2}}{x} = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k}\binom{n + k}{k}a^{k}(−b)^{n−k}

= ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{n}{n − k}\binom{2n − k}{n − k}a^{n−k}(−b)^{k}

= ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{n}{k}\binom{2n − k}{n}a^{n−k}(−b)^{k}

= ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{2n − k}{k}\binom{2n − k − k}{n − k}a^{n−k}(−b)^{k}

= ∑_{k=0}^{n} \binom{2n − k}{k}\frac{1}{n − k + 1}\binom{2n − 2k}{n − k}a^{n−k}(−b)^{k}

= ∑_{k=0}^{n} \binom{2n − k}{k}c(n − k)a^{n−k}(−b)^{k}

= ∑_{k=0}^{n} \binom{n + k}{2k}c(k)a^{k}(−b)^{n−k}.

Again we note that the matrix with general term \binom{n}{k}\binom{2n−k}{k} \frac{1}{n−k+1} is \underline{A060693}, whose general term counts the number of Schröder paths from (0, 0) to (2n, 0), having k peaks. \binom{n+k}{2k}c(k) is another expression for \underline{A088617}. Gathering these results leads to the next proposition.

Proposition 13. [t^{n}]\frac{y_{2}(a,b)}{x} is given by the equivalent expressions

∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k}\binom{n + k}{k}a^{k}(−b)^{n−k}

= ∑_{k=0}^{n} \binom{n + k}{2k}c(k)a^{k}(−b)^{n−k}

= ∑_{k=0}^{n} \binom{2n − k}{k}c(n − k)a^{n−k}(−b)^{k}.

We summarize some of these results in Table 1, where c_{n} = c(n) = \frac{1}{n+1} \binom{2n}{n}, and P (x) = 1 − 2(r + 1)x + (r − 1)^{2}x^{2}, and N(n, k) = \frac{1}{n} \binom{n}{k}\binom{n}{k+1}. We use the terms “Little sequence” and “large sequence” in analogy with the Schröder numbers. In [12] we note that the terms “Little Schröder”, “Big Schröder” and “Bigger Schröder” are used. For instance, the numbers 1, 3, 11, 45, … appear there as the “Bigger Schröder” numbers.

Table 1. Summary of section results

Large sequence, S_{n}  Little sequence, s_{n}  Larger sequence s_{n} − 0^{n}
e.g. 1, 2, 6, 22, 90, …  e.g. 1, 1, 3, 11, 45, …  e.g. 0, 1, 3, 11, 45, …
\frac{x(1−x)}{1−(1−r)x}  \frac{x(1−rx)}{1−(r−1)x}  \frac{x}{1+(r+1)x+rx^{2}}
\frac{1−(r−1)x−\sqrt{P (x)}}{2x}  \frac{1+(r−1)x−\sqrt{P (x)}}{2rx}  \frac{1−(r+1)x−\sqrt{P (x)}}{2rx}
a_{0} = 1, a_{n} = \frac{1}{n} ∑_{k=0}^{n} \binom{n}{k}\binom{n}{k−1}r^{k} a_{0} = 1, a_{n} = ∑_{k=0}^{n} N(n, k)r^{k}  ∑_{k=0}^{n−1} N(n, k)r^{k}
∑_{k=0}^{n} \binom{n+k}{2k}c_{k}(r − 1)^{n−k}  ∑_{k=0}^{n} \binom{n+k}{2k}c_{k}r^{k}(1 − r)^{n−k} ∑_{k=0} \binom{n−1}{2k}c_{k}(r + 1)^{n−2k−1}r^{k}
∑_{k=0}^{n} \binom{2n−k}{k}c_{n−k}(r − 1)^{k}  ∑_{k=0}^{n} \binom{2n−k}{k}c_{n−k}r^{n−k}(1 − r)^{k}  -

Table 2. Little and Large sequences in OEIS

r  s_{n}  S_{n}  Triangle
1 A000984 A000984 A007318
2 A001003 A006318 A008288
3 A007564 A047891 A081577
4 A059231 A082298 A081578
5 A078009 A082301 A081579
6 A078018 A082302 A081580
7 A081178 A082305
8 A082147 A082366
9 A082181 A082367
10 A082148

Note that by Example 6 we can write

s_{n} = \frac{1}{r}S_{n} + \frac{(r − 1)0^{n}}{r} .

4 Introducing the family of centrally symmetric invertible triangles

The motivation for the construction that follows comes from the following easily established proposition.

Proposition 14.

\binom{n}{k} = ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j} = ∑_{j=0}^{k} \binom{k}{j}\binom{n − k}{j}.

Proof. We consider identity 5.23 of [4]:

\binom{r + s}{r − p + q} = ∑_{j} \binom{r}{p + j}\binom{s}{q + j}

itself a consequence of Vandermonde’s convolution identity. Setting r = k, s = n − k, p = q = 0, we obtain

\binom{n}{k} = ∑_{j} \binom{k}{j}\binom{n − k}{j}.

Now let a_{n} represent a sequence of integers with a_{0} = 1. We define an infinite array of numbers for n, k ≥ 0 by

T (n, k) = ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}a_{j}.

and call it the triangle associated with the sequence a_{n} by this construction. That it is a number triangle follows from the next proposition.

Proposition 15. The matrix with general term T (n, k) is an integer-valued centrally symmetric invertible lower-triangular matrix.

Proof. All elements in the sum are integers, hence T (n, k) is an integer for all n, k ≥ 0. T (n, k) = 0 for k > n since then n − k < 0 and hence the sum is 0. We have

T (n, n) = ∑_{j=0}^{n−n} \binom{n}{j}\binom{n − n}{j}a_{j} = ∑_{j=0}^{0} \binom{n}{j}\binom{0}{j}a_{j} = \binom{n}{0}\binom{0}{0}a_{0} = 1

which proves that the matrix is invertible. Finally, we have

T (n, n − k) = ∑_{j=0}^{n−(n−k)} \binom{n − k}{j}\binom{n − (n − k)}{j}a_{j}

= ∑_{j=0}^{k} \binom{n − k}{j}\binom{k}{j}a_{j}
= T (n, k).

It is clear that Pascal’s triangle corresponds to the case where a_{n} is the sequence 1, 1, 1, . . .. Occasionally we shall use the above construction on sequences a_{n} for which a_{0} = 0. In

this case we still have a centrally symmetric triangle, but it is no longer invertible, since for example T (0, 0) = 0 in this case.

By an abuse of notation, we shall often use T (n, k; a_{n}) to denote the triangle associated to the sequence a_{n} by the above construction, when explicit mention of a_{n} is required.

The associated square symmetric matrix with general term

T_{sq}(n, k) = ∑_{j=0}^{n} \binom{k}{j}\binom{n}{j}a_{j}

is easy to describe. We let D = D(a_{n}) = diag(a_{0}, a_{1}, a_{2}, …). Then

T_{sq} = BDB′

is the square symmetric (infinite) matrix associated to our construction. Note that when a_{n} = 1 for all n, we get the square Binomial or Pascal matrix \binom{n+k}{k}.

Among the attributes of the triangles that we shall construct that interest us, the family of central sequences (sequences associated to T (2n, n) and its close relatives) will be paramount. The central binomial coefficients \binom{2n}{n}, \underline{A000984}, play an important role in combinatorics. We begin our examination of the generalized triangles by characterizing their ‘central coefficients’ T (2n, n). We obtain

T (2n, n) = ∑_{j=0}^{2n−n} \binom{2n − n}{j}\binom{n}{j}a_{j}

= ∑_{j=0}^{n} \binom{n}{j}^{2}a_{j}.

For the case of Pascal’s triangle with a_{n} given by 1, 1, 1, … we recognize the identity \binom{2n}{n} = ∑_{j=0}^{n} \binom{n}{j}^{2}. In like fashion, we can characterize T (2n + 1, n), for instance.

T (2n + 1, n) = ∑_{j=0}^{2n+1−n} \binom{2n + 1 − n}{j}\binom{n}{j}a_{j}

= ∑_{j=0}^{n+1} \binom{n + 1}{j}\binom{n}{j}a_{j}

which generalizes the identity \binom{2n+1}{n} = ∑_{j=0}^{n+1} \binom{n+1}{j}\binom{n}{j}. This is \underline{A001700}. We also have

T (2n − 1, n − 1) = ∑_{j=0}^{2n−1−n+1} \binom{2n − 1 − n + 1}{j}\binom{n − 1}{j}a_{j}

= ∑_{j=0}^{n} \binom{n − 1}{j}\binom{n}{j}a_{j}.

This generalizes the equation \binom{2n−1}{n−1} + 0^{n} = ∑_{j=0}^{n} \binom{n−1}{j}\binom{n}{j}. See \underline{A088218}.

In order to generalize the Catalan numbers c(n), \underline{A000108}, in our context, we note that c(n) = \binom{2n}{n}/(n + 1) has the alternative representation

c(n) = \binom{2n}{n} − \binom{2n}{n − 1} = \binom{2n}{n} − \binom{2n}{n + 1}.

This motivates us to look at T (2n, n) − T (2n, n − 1) = T (2n, n) − T (2n, n + 1). We obtain

T (2n, n) − T (2n, n − 1) = ∑_{j=0}^{n} \binom{n}{j}^{2}a_{j} − ∑_{j=0}^{2n−n+1} \binom{n − 1}{j}\binom{2n − n + 1}{j}a_{j}

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

= δ_{n,0}a_{n} + ∑_{j=0}^{n}(\binom{n}{j}^{2} − \binom{n − 1}{j}\binom{n + 1}{j})a_{j}

= δ_{n,0}a_{0} + ∑_{j=0}^{n} Ñ(n − 1, j − 1)a_{j}

where we use the formalism \binom{n−1}{n+1} = −1, for n = 0, and \binom{n−1}{n+1} = 0 for n > 0. We assume that Ñ(n, −1) = 0 and Ñ(−1, k) = \binom{1}{k} − \binom{0}{k} in the above. For instance, in the case of Pascal’s triangle, where a_{n} = 1 for all n, we retrieve the Catalan numbers. We have also established a link between these generalized Catalan numbers and the Narayana numbers. We shall use the notation

c(n; a(n)) = T (2n, n) − T (2n, n − 1) = T (2n, n) − T (2n, n + 1)

for this sequence, which we regard as a sequence of generalized Catalan numbers.

Example 16. We first look at the case a_{n} = 2^{n}. Thus

T (n, k) = ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}2^{j}

with matrix representation

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 5 & 5 & 1 & 0 & 0 & … \\ 1 & 7 & 13 & 7 & 1 & 0 & … \\ 1 & 9 & 25 & 25 & 9 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

which is the well-known Delannoy number triangle \underline{A008288}. We have

T (n, k) = ∑_{j=0}^{k} \binom{k}{j}\binom{n − j}{k}.

We shall generalize this identity later in this note.

As a Riordan array, this is given by

(\frac{1}{1 − x}, \frac{x(1 + x)}{1 − x}).

Anticipating the general case, we examine the row sums of this triangle, given by

∑_{k=0}^{n} ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}2^{j}.

Using the formalism of the Riordan group, we see that this sum has generating function given by

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

In other words, the row sums in this case are the numbers P ell(n + 1), \underline{A000129}, [29]. We look at the inverse binomial transform of these numbers, which has generating function

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

This is the generating function of the sequence 1, 1, 2, 2, 4, 4, …, \underline{A016116}, which is the doubled sequence of a_{n} = 2^{n}.

Another way to see this result is to observe that we have the factorization

(\frac{1}{1 − x}, \frac{x(1 + x)}{1 − x}) = (\frac{1}{1 − x}, \frac{x}{1 − x})(1, \frac{x(1 + 2x)}{1 + x})

where (\frac{1}{1−x}, \frac{x}{1−x}) represents the binomial transform. The row sums of the Riordan array (1, \frac{x(1+2x)}{1+x}) are 1, 1, 2, 2, 4, 4, . . ..

For this triangle, the central numbers T (2n, n) are the well-known central Delannoy numbers 1, 3, 13, 63, … or \underline{A001850}, with ordinary generating function \frac{1}{\sqrt{1−6x+x^{2}}} and exponential generating function e^{3x}I_{0}(2\sqrt{2}x) where I_{n} is the n-th modified Bessel function of the first kind [28]. They represent the coefficients of x^{n} in the expansion of (1 + 3x + 2x^{2})^{n}. We have

T (2n, n; 2^{n}) = ∑_{k=0}^{n} \binom{n}{k}^{2}2^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}.

The numbers T (2n+1, n) in this case are \underline{A002002}, with generating function (\frac{1−x}{\sqrt{1−6x+x^{2}}} − 1)/(2x) and exponential generating function e^{3x}(I_{0}(2\sqrt{2}x) + \sqrt{2}I_{1}(2\sqrt{2}x)). We note that T (2n − 1, n − 1) represents the coefficient of x^{n} in ((1 − x)/(1 − 2x))^{n}. It counts the number of peaks in all Schröder paths from (0, 0) to (2n, 0).

The numbers T (2n, n) − T (2n, n − 1) are 1, 2, 6, 22, 90, 394, 1806, … or the large Schröder numbers. These are the series reversion of \frac{x(1−x)}{1+x}. Thus the generating function of the sequence \frac{1}{2}(T (2n, n; 2^{n}) − T (2n, n − 1; 2^{n})) is

y_{2}(1, −1) = \frac{1 − x − \sqrt{1 − 6x + x^{2}}}{2x} .

We remark that in [23], the author states that “The Schröder numbers bear the same relation to the Delannoy numbers as the Catalan numbers do to the binomial coefficients.” This note amplifies on this statement, defining generalized Catalan numbers for a family of number triangles.

Example 17. We take the case a_{n} = (−1)^{n}. Thus

T (n, k) = ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}(−1)^{j}

with matrix representation

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 1 & 0 & 0 & 0 & … \\ 1 & −1 & −1 & 1 & 0 & 0 & … \\ 1 & −2 & −2 & −2 & 1 & 0 & … \\ 1 & −3 & −2 & −2 & −3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

As a Riordan array, this is given by

(\frac{1}{1 − x}, \frac{x(1 − 2x)}{1 − x}).

Again, we look at the row sums of this triangle, given by

∑_{k=0}^{n} ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}(−1)^{j}.

Looking at generating functions, we see that this sum has generating function given by

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

In other words, the row sums in this case are the numbers 1, 2, 2, 0, −4, −8, −8, … with exponential generating function exp(x)(sin(x)+cos(x)), \underline{A009545}. Taking the inverse binomial transform of these numbers, we get the generating function

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

This is the generating function of the sequence 1, 1, −1, −1, 1, 1, … which is the doubled sequence of a_{n} = (−1)^{n}.

Another way to see this result is to observe that we have the factorization

(\frac{1}{1 − x}, \frac{x(1 − 2x)}{1 − x}) = (\frac{1}{1 − x}, \frac{x}{1 − x})(1, \frac{x(1 − x)}{1 + x})

where (\frac{1}{1−x}, \frac{x}{1−x}) represents the binomial transform. The row sums of the Riordan array (1, \frac{x(1−x)}{1+x}) are 1, 1, −1, −1, 1, 1, . . ..

The central terms T (2n, n) turn out to be an ‘aerated’ signed version of \binom{2n}{n} given by 1, 0, −2, 0, 6, 0, −20, … with ordinary generating function \frac{1}{\sqrt{1+4x^{2}}} and exponential generating function I_{0}(2\sqrt{−1}x). They represent the coefficients of x^{n} in (1 − x^{2})^{n}. We have

T (2n, n; (−1)^{n}) = ∑_{k=0}^{n} \binom{n}{k}^{2}(−1)^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}(−1)^{k}2^{n−k}.

The terms T (2n + 1, n) turn out to be a signed version of \binom{n}{⌊n/2⌋}, namely

1, −1, −2, 3, 6, −10, −20, 35, 70, …

with ordinary generating function (\frac{1+2x}{\sqrt{1+4x^{2}}} − 1)/(2x) and exponential generating function I_{0}(2\sqrt{−1}x) + \sqrt{−1}I_{1}(2\sqrt{−1}x).

The generalized Catalan numbers T (2n, n) − T (2n, n − 1) are the numbers

1, −1, 0, 1, 0, −2, 0, 5, 0, −14, 0, …

with generating function y_{2}(1, 2) = \frac{1+2x−\sqrt{1+4x^{2}}}{2x}. This is the series reversion of \frac{x(1−x)}{1−2x}.

We note that the sequence T (2(n+1), n)−T (2(n+1), n+1) is (−1)^{n/2}c(n/2)(1+(−1)^{n})/2 with exponential generating function I_{1}(2\sqrt{−1}x)/(\sqrt{−1}x).

5 A one-parameter sub-family of triangles

The above examples motivate us to look at the one-parameter subfamily given by the set of triangles defined by the power sequences n → r^{n}, for r ∈ Z. The case r = 1 corresponds to Pascal’s triangle, while the case r = 0 corresponds to the ‘partial summing’ triangle with 1s on and below the diagonal.

Proposition 18. The matrix associated to the sequences n → r^{n}, r ∈ Z, is given by the Riordan array

(\frac{1}{1 − x}, \frac{x(1 + (r − 1)x)}{1 − x}) .

Proof. The general term T (n, k) of the above matrix is given by

T (n, k) = [x^{n}](1 + (r − 1)x)^{k}x^{k}(1 − x)^{−(k+1)}
= [x^{n−k}](1 + (r − 1)x)^{k}(1 − x)^{−(k+1)}
= [x^{n−k}] ∑_{j=0}^{k} \binom{k}{j}(r − 1)^{j}x^{j} ∑_{i=0} \binom{k + i}{i}x^{i}
= [x^{n−k}] ∑_{j=0}^{k} ∑_{i=0} \binom{k}{j}\binom{k + i}{i}(r − 1)^{j}x^{i+j}
= ∑_{j=0}^{k} \binom{k}{j}\binom{k + n − k − j}{n − k − j}(r − 1)^{j}
= ∑_{j=0}^{k} \binom{k}{j}\binom{n − j}{k}(r − 1)^{j}
= ∑_{j=0}^{k} \binom{k}{j}\binom{n − k}{j}r^{j}.

where the last equality is a consequence of identity (3.17) in [15]. Corollary 19. The row sums of the triangle defined by n → r^{n} are the binomial transforms of the doubled sequence n → 1, 1, r, r, r^{2}, r^{2}, …, i.e., n → r^{⌊ \frac{n}{2} ⌋}. Proof. The row sums of (\frac{1}{1−x}, \frac{x(1+(r−1)x)}{1−x}) are the binomial transform of the row sums of its product with the inverse of the binomial matrix. This product is

(\frac{1}{1 + x}, \frac{x}{1 + x})(\frac{1}{1 − x}, \frac{x(1 + (r − 1)x)}{1 − x}) = (1, \frac{x(1 + rx)}{1 + x}).

The row sums of this product have generating function given by

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

This is the generating function of 1, 1, r, r, r^{2}, r^{2} … as required.

We note that the generating function for the row sums of the triangle corresponding to r^{n} is \frac{1}{1−2x−(r−1)x^{2}} .

We now look at the term T (2n, n) for this subfamily. Proposition 20. T (2n, n; r^{n}) is the coefficient of x^{n} in (1 + (r + 1)x + rx^{2})^{n}.

Proof. We have (1 + (r + 1)x + rx^{2}) = (1 + x)(1 + rx). Hence

[x^{n}](1 + (r + 1)x + rx^{2})^{n} = [x^{n}](1 + x)^{n}(1 + rx)^{n}
= [x^{n}] ∑_{k=0}^{n} ∑_{j=0}^{n} \binom{n}{k}\binom{n}{j}r^{j}x^{k+j}
= ∑_{j=0}^{n} \binom{n}{n − j}\binom{n}{j}r^{j}
= ∑_{j=0}^{n} \binom{n}{j}^{2}r^{j}.

Corollary 21. The generating function of T (2n, n; r^{n}) is

\frac{1}{\sqrt{1 − 2(r + 1)x + (r − 1)^{2}x^{2}}} .

Proof. Using Lagrangian inversion, we can show that

[x^{n}](1 + ax + bx^{2})^{n} = [t^{n}]\frac{1}{\sqrt{1 − 2at + (a^{2} − 4b)t^{2}}}

(see exercises 5.3 and 5.4 in [30]). Then

[x^{n}](1 + (r + 1)x + rx^{2})^{n} = [t^{n}]\frac{1}{\sqrt{1 − 2(r + 1)t + ((r + 1)^{2} − 4r)t^{2}}}
= [t^{n}]\frac{1}{\sqrt{1 − 2(r + 1)t + (r − 1)^{2}t^{2}}}

Corollary 22.

∑_{k=0}^{n} \binom{n}{k}^{2}r^{k} = ∑_{k=0}^{n} \binom{n}{2k}\binom{2k}{k}(r + 1)^{n−2k}r^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n − k}{k}(r + 1)^{n−2k}r^{k}.

Proof. This follows since the coefficient of x^{n} in (1 + ax + bx^{2})^{n} is given by [9]

∑_{k=0}^{n} \binom{n}{2k}\binom{2k}{k}a^{n−2k}b^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n − k}{k}a^{n−2k}b^{k}.

Hence each term is equal to T (2n, n; r^{n}).

We now look at the sequence T (2n − 1, n − 1). Proposition 23. T (2n − 1, n − 1; r^{n}) is the coefficient of x^{n} in (\frac{1−(r−1)x}{1−rx})^{n} Proof. We have \frac{1−(r−1)x}{1−rx} = \frac{1−rx+x}{1−rx} = 1 + \frac{x}{1−rx}. Hence

[x^{n}](\frac{1 − (r − 1)x}{1 − rx})^{n} = [x^{n}](1 + \frac{x}{1 − rx})^{n}
= [x^{n}] ∑_{k=0}^{n} ∑_{k=0}^{n} \binom{n}{k}x^{k} ∑_{j=0} \binom{k + j − 1}{j}r^{j}x^{j}

= ∑_{j=0} \binom{n}{n − j}\binom{n − 1}{j}r^{j}

= ∑_{j=0} \binom{n}{j}\binom{n − 1}{j}r^{j}.

Corollary 24.

∑_{k=0}^{n} \binom{n}{k}\binom{n − 1}{k}r^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k − 1}{k}(1−r)^{n−k}r^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{2n − k − 1}{n − k}(1−r)^{k}r^{n−k}.

Proof. The coefficient of x^{n} in (\frac{1−ax}{1−bx})^{n} is seen to be

∑_{k=0}^{n} \binom{n}{k}\binom{n + k − 1}{k}(−a)^{n−k}r^{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{2n − k − 1}{n − k}(−a)^{k}r^{n−k}.

Hence all three terms in the statement are equal to T (2n − 1, n − 1; r^{n}).

We can generalize the results seen above for T (2n, n), T (2n + 1, n), T (2n − 1, n − 1) and T (2n, n) − T (2n, n − 1) as follows.

Proposition 25. Let T (n, k) = ∑_{k=0}^{n−k} \binom{k}{j}\binom{n−k}{j}r^{j} be the general term of the triangle associated to the power sequence n → r^{n}.

1. The sequence T (2n, n) has ordinary generating function \frac{1}{\sqrt{1−2(r+1)x+(r−1)^{2}x^{2}}} , exponen-

tial generating function e^{(r+1)x}I_{0}(2\sqrt{r}x), and corresponds to the coefficients of x^{n} in (1 + (r + 1)x + rx^{2})^{n}.

2. The numbers T (2n + 1, n) have generating function (\frac{1−(r−1)x}{\sqrt{1−2(r+1)x+(r−1)^{2}x^{2}}} − 1)/(2x) and

exponential generating function e^{(r+1)x}(I_{0}(2\sqrt{r}x) + \sqrt{r}I_{1}(2\sqrt{r}x)).

3. T (2n − 1, n − 1) represents the coefficient of x^{n} in ((1 − (r − 1)x)/(1 − rx))^{n}.

4. The generalized Catalan numbers c(n; r^{n}) = T (2n, n) − T (2n, n − 1) associated to the

triangle have ordinary generating function ^{\frac{1−(r−1)x−\sqrt{1−2(r+1)x+(r−1)^{2}x^{2}}}{2x}}.

5. The sequence c(n + 1; r^{n}) has exponential generating function \frac{1}{\sqrt{r}x}e^{(r+1)x}I_{1}(2\sqrt{r}x).

6. The sequence nc(n; r^{n}) = ∑_{k=0}^{n} \binom{n}{k}\binom{n+k}{k+1} \frac{r^{n−k}}{r+1} has exponential generating function

\frac{1}{\sqrt{r}x}e^{(r+1)x}I_{1}(2\sqrt{r}).

7. The sequence c(n; r^{n})−0^{n} is expressible as ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n−1}{2k}c(k)(r +1)^{n−2k−1}r^{k} and counts the number of Motzkin paths of length n in which the level steps have r + 1 colours and the up steps have r colours. It is the series reversion of \frac{x}{1+(r+1)x+rx^{2}} .

Pascal’s triangle can be generated by the well-know recurrence

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

The following proposition gives the corresponding recurrence for the case of the triangle associated to the sequence n → r^{n}. Proposition 26. Let T (n, k) = ∑_{k=0}^{n−k} \binom{k}{j}\binom{n−k}{j}r^{j}. Then

T (n, k) = T (n − 1, k − 1) + (r − 1)T (n − 2, k − 1) + T (n − 1, k).

Proof. The triangle in question has Riordan array representation

(\frac{1}{1 − x}, \frac{x(1 + (r − 1)x)}{1 − x})

Thus the bivariate generating function of this triangle is given by

F (x, y) = \frac{1}{1 − x} \frac{1}{1 − y \frac{x(1+(r−1)x)}{1−x}}
= \frac{1}{1 − x − xy − (r − 1)x^{2}y}

In this simple case, it is possible to characterize the inverse of the triangle. We have Proposition 27. The inverse of the triangle associated to the sequence n → r^{n} is given by the Riordan array (1 − u, u) where

u = \frac{\sqrt{1 + 2(2r − 1)x + x^{2}} − x − 1}{2(r − 1)}.

Proof. Let (g^{∗}, f̄) = (\frac{1}{1−x}, \frac{x(1+(r−1)x)}{1−x})^{−1}. Then

\frac{f̄(1 + (r − 1)f̄)}{1 − f̄} = x ⇒ f̄ = \frac{\sqrt{1 + 2(2r − 1)x + x^{2}} − x − 1}{2(r − 1)}.

Since g^{∗} = \frac{1}{g∘f̄} = 1 − f̄ we obtain the result. Corollary 28. The row sums of the inverse of the triangle associated with n → r^{n} are 1, 0, 0, 0, . . .. Proof. The row sums of the inverse (1 − u, u) have generating function given by \frac{1−u}{1−u} = 1. In other words, the row sums of the inverse are 0^{n} = 1, 0, 0, 0, . . ..

Other examples of these triangles are given by \underline{A081577}, \underline{A081578}, \underline{A081579}, and \underline{A081580}.

6 The Jacobsthal and the Fibonacci cases

We now look at the triangles generated by sequences whose elements can be expressed in Binet form as a simple sum of powers. In the first example of this section, the powers are of integers, while in the second case (Fibonacci numbers) we indicate that the formalism can be extended to non-integers under the appropriate conditions.

Example 29. The Jacobsthal numbers J(n+1), \underline{A001045}, have generating function \frac{1}{1−x−2x^{2}} and general term J(n + 1) = 2.2^{n}/3 + (−1)^{n}/3. Using our previous examples, we see that the triangle defined by J(n + 1)

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 4 & 8 & 4 & 1 & 0 & 0 & … \\ 1 & 5 & 16 & 16 & 5 & 1 & 0 & … \\ 1 & 6 & 27 & 42 & 27 & 6 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

or \underline{A114202}, is the scaled sum of the Riordan arrays discussed above, given by

\frac{2}{3}(\frac{1}{1 − x}, \frac{x(1 + x)}{1 − x}) + \frac{1}{3}(\frac{1}{1 − x}, \frac{x(1 − 2x)}{1 − x}).

In particular, the k-th column of the triangle has generating function

g_{k}(x) = \frac{x^{k}}{(1 − x)^{k+1}} (\frac{2}{3}(1 + x)^{k} + \frac{1}{3}(1 − 2x)^{k})

= \frac{x^{k}}{(1 − x)^{k+1}} ∑_{j=0}^{k} \binom{k}{j}\frac{1}{3}(2 + (−2)^{j})x^{j}.

We recognize in the sequence \frac{1}{3}(2 + (−2)^{n}) the inverse binomial transform of J(n + 1). Obviously, the inverse binomial transform of the row sums of the matrix are given by

\frac{2}{3}2^{⌊ \frac{n}{2} ⌋} + \frac{1}{3}(−1)^{⌊ \frac{n}{2} ⌋}

or 1, 1, 1, 1, 3, 3, 5, 5, …, the doubled sequence of J(n + 1).

The terms T (2n, n) for this triangle can be seen to have generating function \frac{2}{3} \frac{1}{\sqrt{1−6x+x^{2}}} + \frac{1}{3} \frac{1}{\sqrt{1+4x^{2}}} and exponential generating function \frac{2}{3}e^{3x}I_{0}(2\sqrt{2}x) + \frac{1}{3}I_{0}(2\sqrt{−1}x).

The generalized Catalan numbers for this triangle are

1, 1, 4, 15, 60, 262, 1204, 5707, 27724, …

whose generating function is \frac{3−\sqrt{1+4x^{2}}−2\sqrt{1−6x+x^{2}}}{6x}.

To find the relationship between T (n, k) and its ‘previous’ elements, we proceed as follows, where we write T (n, k) = T (n, k; J(n + 1)) to indicate its dependence on J(n + 1).

T (n, k; J(n + 1)) = ∑_{j=0} \binom{k}{j}\binom{n − k}{j}(\frac{2}{3}2^{j} + \frac{1}{3}(−1)^{j})

= \frac{2}{3} ∑_{j=0} \binom{k}{j}\binom{n − k}{j}2^{j} + \frac{1}{3} ∑_{j=0} \binom{k}{j}\binom{n − k}{j}(−1)^{j}

= \frac{2}{3}T (n, k; 2^{n}) + \frac{1}{3}T (n, k; (−1)^{n})
= \frac{2}{3}(T (n − 1, k − 1; 2^{n}) + T (n − 2, k − 1; 2^{n}) + T (n − 1, k; 2^{n}))

+\frac{1}{3}(T (n − 1, k − 1; (−1)^{n}) − 2T (n − 2, k − 1; (−1)^{n}) + T (n − 1, k; (−1)^{n}))

= \frac{2}{3}T (n − 1, k − 1; 2^{n}) + \frac{1}{3}T (n − 1, k − 1; (−1)^{n})

+\frac{2}{3}(T (n − 2, k − 1; 2^{n}) − T (n − 2, k − 1; (−1)^{n}))

+\frac{2}{3}T (n − 1, k; 2^{n}) + \frac{1}{3}T (n − 1, k; (−1)^{n})

= T (n − 1, k − 1; J(n + 1)) + 2T (n − 2, k − 1; J(n)) + T (n − 1, k; J(n + 1)).

We see here the appearance of the non-invertible matrix based on J(n). This begins as

( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 3 & 5 & 3 & 0 & 0 & 0 & … \\ 0 & 4 & 9 & 9 & 4 & 0 & 0 & … \\ 0 & 5 & 14 & 21 & 14 & 5 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Example 30. We briefly look at the case of the Fibonacci sequence

F (n + 1) = ((\frac{1 + \sqrt{5}}{2})(\frac{1 + \sqrt{5}}{2})^{n} − (\frac{1 − \sqrt{5}}{2})(\frac{1 − \sqrt{5}}{2})^{n}) /\sqrt{5}.

Again, we can display the associated triangle

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 & … \\ 1 & 4 & 7 & 4 & 1 & 0 & 0 & … \\ 1 & 5 & 13 & 13 & 5 & 1 & 0 & … \\ 1 & 6 & 21 & 31 & 21 & 6 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

or \underline{A114197} as a sum of scaled ‘Riordan arrays’ as follows:

\frac{1 + \sqrt{5}}{2}(\frac{1}{1 − x}, \frac{x(1 + (\frac{1+\sqrt{5}}{2} − 1)x)}{1 − x}) − \frac{1 − \sqrt{5}}{2}(\frac{1}{1 − x}, \frac{x(1 + (\frac{1−\sqrt{5}}{2} − 1)x)}{1 − x}).

Hence the k-th column of the associated triangle has generating function given by

\frac{x^{k}}{(1 − x)^{k+1}} (\frac{1 + \sqrt{5}}{2}(1 + (\frac{1 + \sqrt{5}}{2} − 1)x)^{k} + \frac{1 − \sqrt{5}}{2}(1 + (\frac{1 − \sqrt{5}}{2} − 1)x)^{k}).

Expanding, we find that the generating function of the k-th column of the triangle associated to F (n + 1) is given by

\frac{x^{k}}{(1 − x)^{k+1}} ∑_{j=0}^{k} \binom{k}{j}b_{j}x^{j}

where the sequence b_{n} is the inverse binomial transform of F (n + 1). That is, we have

b_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}F (k + 1) = (ϕ(ϕ − 1)^{n} + \frac{1}{ϕ}(−\frac{1}{ϕ} − 1)^{n})/\sqrt{5}

where ϕ = \frac{1+\sqrt{5}}{2}.

Again, the inverse binomial transform of the row sums is given by F (⌊\frac{n}{2}⌋ + 1).

The term T (2n, n) in this case is ∑_{k=0}^{n} \binom{n}{k}^{2}F (k +1), or 1, 2, 7, 31, 142, 659, … (\underline{A114198}). This has ordinary generating function given by

\frac{\frac{1+\sqrt{5}}{2\sqrt{5}}}{\sqrt{1 − 2(\frac{1+\sqrt{5}}{2} + 1)x + (\frac{1+\sqrt{5}}{2} − 1)^{2}x^{2}}} − \frac{\frac{1−\sqrt{5}}{2\sqrt{5}}}{\sqrt{1 − 2(\frac{1−\sqrt{5}}{2} + 1)x + (\frac{1−\sqrt{5}}{2} − 1)^{2}x^{2}}}

and exponential generating function

\frac{1 + \sqrt{5}}{2\sqrt{5}} exp(\frac{3 + \sqrt{5}}{2}x)I_{0}(2\sqrt{\frac{1 + \sqrt{5}}{2}}x) − \frac{1 − \sqrt{5}}{2\sqrt{5}} exp(\frac{3 − \sqrt{5}}{2}x)I_{0}(2\sqrt{\frac{1 − \sqrt{5}}{2}}x).

T (n, k) satisfies the following recurrence

T (n, k; F (n + 1)) = T (n − 1, k − 1; F (n + 1)) + T (n − 2, k − 1; F (n)) + T (n − 1, k; F (n + 1))

where the triangle associated to F (n) begins

( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 3 & 5 & 3 & 0 & 0 & 0 & … \\ 0 & 4 & 9 & 9 & 4 & 0 & 0 & … \\ 0 & 5 & 14 & 20 & 14 & 5 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We note that all Lucas sequences [27] can be treated in similar fashion.

7 The general case

Proposition 31. Given an integer sequence a_{n} with a_{0} = 1, the centrally symmetric invertible triangle associated to it by the above construction has the following generating function for its k-th column:

\frac{x^{k}}{1 − x} ∑_{j=0}^{k} \binom{k}{j}a_{j} (\frac{x}{1 − x})^{j} = \frac{x^{k}}{(1 − x)^{k+1}} ∑_{j=0}^{k} \binom{k}{j}b_{j}x^{j}

where b_{n} is the inverse binomial transform of a_{n}.

Proof. We have

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

= ∑_{j} \binom{k}{j}a_{j}[x^{n−k−j}](1 − x)^{−(j+1)}

= ∑_{j} \binom{k}{j}a_{j}[x^{n−k−j}] ∑_{i} \binom{j + i}{i}x^{i}

= ∑_{j} \binom{k}{j}a_{j}\binom{j + n − k − j}{n − k − j}

= ∑_{j} \binom{k}{j}\binom{n − k}{j}a_{j}
= T (n, k).

Similarly,

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

= ∑_{j} \binom{k}{j}b_{j}[x^{n−k−j}] ∑_{i} \binom{k + i}{i}x^{i}

= ∑_{j} \binom{k}{j}b_{j}\binom{k + n − k − j}{n − k − j}

= ∑_{j} \binom{k}{j}\binom{n − j}{k}b_{j}.

Now

∑_{j=0} \binom{k}{j}\binom{n − k}{j}a_{j} = ∑_{j=0} \binom{k}{j}\binom{n − k}{j} ∑_{i=0}^{j} \binom{j}{i}b_{i}

= ∑_{j} ∑_{i} \binom{k}{j}\binom{n − k}{j}\binom{j}{i}b_{i}

= ∑_{j} ∑_{i} \binom{k}{j}\binom{j}{i}\binom{n − k}{j}b_{i}

= ∑_{j} ∑_{i} \binom{k}{i}\binom{k − i}{j − i}\binom{n − k}{j}b_{i}

= ∑_{i} \binom{k}{i}b_{i} ∑_{j} \binom{k − i}{k − j}\binom{n − k}{j}

= ∑_{i} \binom{k}{i}b_{i}\binom{n − i}{k}

= ∑_{j} \binom{k}{j}\binom{n − j}{k}b_{j}.

Corollary 32. The following relationship exists between a sequence a_{n} and its inverse binomial transform b_{n}:

∑_{j} \binom{k}{j}\binom{n − k}{j}a_{j} = ∑_{j} \binom{k}{j}\binom{n − j}{k}b_{j}.

It is possible of course to reverse the above proposition to give us the following:

Proposition 33. Given a sequence b_{n}, the product of the triangle whose k-th column has ordinary generating function

\frac{x^{k}}{(1 − x)^{k+1}} ∑_{j=0}^{k} \binom{k}{j}b_{j}x^{j}

by the binomial matrix is the centrally symmetric invertible triangle associated to the binomial transform of b_{n}.

8 Exponential-factorial triangles

In this section, we briefly describe an alternative method that produces generalized Pascal matrices, based on suitably chosen sequences. For this, we recall that the binomial matrix B may be represented as

B = exp ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 3 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 4 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 5 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

while if we write a(n) = n then the general term \binom{n}{k} of this matrix can be written as

\binom{n}{k} = \frac{∏_{j=1}^{k} a(n − j + 1)}{∏_{j=1}^{k} a(j)}.

Furthermore,

B = ∑_{k=0} \frac{M^{k}}{∏_{j=1}^{k} a(j)}

where M is the sub-diagonal matrix formed from the elements of a(n).

We shall see that by generalizing this construction to suitably chosen sequences a(n) where a(0) = 0 and a(1) = 1, we can obtain generalized Pascal triangles, some of which are well documented in the literature. Thus we let T (n, k) denote the matrix with general term

T (n, k) = \frac{∏_{j=1}^{k} a(n − j + 1)}{∏_{j=1}^{k} a(j)} = \binom{n}{k}_{a(n)}.

Proposition 34. T (n, n−k) = T (n, k), T (n, 1) = a(n), T (n+1, 1) = T (n+1, n) = a(n+1)

Proof. To prove the first assertion, we assume first that k ≤ n − k. Then

T (n, k) = \frac{a(n) … a(n − k + 1)}{a(1) … a(k)}
= \frac{a(n) … a(n − k + 1)}{a(1) … a(k)} \frac{a(n − k) … a(k + 1)}{a(k + 1) … a(n − k)}
= T (n, n − k).

Secondly, if k > n − k, we have

T (n, n − k) = \frac{a(n) … a(k + 1)}{a(1) … a(n − k)}
= \frac{a(n) … a(k + 1)}{a(1) … a(n − k)} \frac{a(k) … a(n − k + 1)}{a(n − k + 1) … a(k)}
= T (n, k).

Next, we have

T (n, 1) = \frac{∏_{j=1}^{1} a(n − j + 1)}{∏_{j=1}^{1} a(j)}
= \frac{a(n − 1 + 1)}{a(1)} = a(n).

since a(1) = 1. Similarly,

T (n + 1, 1) = \frac{∏_{j=1}^{1} a(n + 1 − j + 1)}{∏_{j=1}^{1} a(j)}
= \frac{a(n + 1 − 1 + 1)}{a(1)} = a(n + 1).

Thus for those choices of the sequence a(n) for which the values of T (n, k) are integers, T (n, k) represents a generalized Pascal triangle with T (n, 1) = a(n + 1). We shall use the notation P_{a(n)} to denote the triangle constructed as above.

We define the generalized Catalan sequence associated to a(n) by this construction to be the sequence with general term

\frac{T (2n, n)}{a(n + 1)}.

Example 35. The Fibonacci numbers. The matrix P_{F (n)} with general term

\frac{∏_{j=1}^{k} F (n − j + 1)}{∏_{j=1}^{k} F (j)}

which can be expressed as

∑_{k=0} \frac{M_{F}^{k}}{∏_{j=1}^{k} F (j)}

where M_{F} is the sub-diagonal matrix generated by F (n):

M_{F} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 2 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 3 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 5 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

is the much studied Fibonomial matrix, \underline{A010048}, [8], [6], [7], [10], [24]. For instance, the generalized Catalan numbers associated to this triangle are the Fibonomial Catalan numbers, \underline{A003150}.

Example 36. Let a(n) = \frac{2^{n}}{2} − \frac{0^{n}}{2} . The matrix P_{a(n)} with general term

\frac{∏_{j=1}^{k} a(n − j + 1)}{∏_{j=1}^{k} a(j)}

which can be expressed as

∑_{k=0} \frac{M^{k}}{∏_{j=1}^{k} a(j)}

where M is the sub-diagonal matrix generated by a(n):

M = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 4 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 8 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 16 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

is given by

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 4 & 4 & 1 & 0 & 0 & … \\ 1 & 8 & 16 & 8 & 1 & 0 & … \\ 1 & 16 & 64 & 64 & 16 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This is \underline{A117401}. For this matrix, we have T (2n, n) = 2^{n^{2}} and c(n; a(n)) = 2^{n(n−1)}. This is easily generalized to the sequence n → \frac{k^{n}}{k} − \frac{0^{n}}{k}. For this sequence, we obtain T (2n, n) = k^{n^{2}} and c(n) = k^{n(n−1)}.

Example 37. We take the case a(n) = ⌊\frac{n+1}{2}⌋. In this case, we obtain the matrix

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 1 & 0 & 0 & 0 & … \\ 1 & 2 & 2 & 1 & 0 & 0 & … \\ 1 & 2 & 4 & 2 & 1 & 0 & … \\ 1 & 3 & 6 & 6 & 3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

which has general term

\binom{⌊\frac{n}{2}⌋}{⌊\frac{k}{2}⌋}\binom{⌈\frac{n}{2}⌉}{⌈\frac{k}{2}⌉}.

This triangle counts the number of symmetric Dyck paths of semi-length n with k peaks (\underline{A088855}). We note that for this triangle, T (2n, n) is \binom{n}{⌊ \frac{n}{2} ⌋}^{2} while T (2n, n) − T (2n, n − 1) is the sequence

1, 0, 2, 0, 12, 0, 100, 0, 980, 0, 10584 …

Example 38. The Jacobsthal numbers. Let a(n) = J(n) = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3} . We form the matrix with general term

\frac{∏_{j=1}^{k} J(n − j + 1)}{∏_{j=1}^{k} J(j)}

which can be expressed as

∑_{k=0} \frac{M_{J}^{k}}{∏_{j=1}^{k} J(j)}

where M_{J} is the sub-diagonal matrix generated by J(n):

M_{J} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 3 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 5 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 11 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We obtain the matrix

P_{J(n)} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 5 & 15 & 5 & 1 & 0 & … \\ 1 & 11 & 55 & 55 & 11 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We recognize in this triangle the unsigned version of the q-binomial triangle for q = −2, \underline{A015109}, whose k-th column has generating function

x^{k} \frac{1}{∏_{j=0}^{k}(1 − (−2)^{j}x)}.

Using the above notation, this latter signed triangle is therefore P_{(−1)^{n}J(n)}. Note that

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

is the generating function for (−1)^{n}J(n).

The generating function of the k-th column of P_{J(n)} is given by

x^{k} ∏_{j=0}^{k} \frac{1}{(1 − (−1)^{(j+k mod 2)}2^{j}x)}.

The generalized Catalan numbers for P_{J(n)} are given by \frac{P_{J(n)}(2n,n)}{J(n+1)}. These are \underline{A015056}

1, 1, 5, 77, 5117, 1291677, …

We can generalize these results to the following:

Proposition 39. Let a(n) be the solution to the recurrence

a(n) = (r − 1)a(n − 1) + r^{2}a(n − 2),  a(0) = 0,  a(1) = 1.

Then P_{a(n)} is a generalized Pascal triangle whose k-th column has generating function given by

x^{k} ∏_{j=0}^{k} \frac{1}{(1 − (−1)^{(j+k mod 2)}r^{j}x)}.

Example 40. The Narayana and related triangles. The Narayana triangle Ñ is a generalized Pascal triangle in the sense of this section. It is known that the generating function of its k-th column is given by

x^{k} \frac{∑_{j=0}^{k} N(k, j)x^{j}}{(1 − x)^{2k+1}} .

Now a(n) = Ñ(n, 1) = \binom{n+1}{2} satisfies a(0) = 0, a(1) = 1. It is not difficult to see that, in fact, Ñ = P\binom{n+1}{2}. See [5]. T (2n, n) for this triangle is \underline{A000891}, with exponential generating

function I_{0}(2x)I_{1}(2x)/x. We note that is this case, the numbers generated by Ñ(2n, n)/a(n+ 1) do not produce integers. However the sequence Ñ(2n, n) − Ñ(2n, n + 1) turns out to be the product of successive Catalan numbers c(n)c(n + 1). This is \underline{A005568}.

The triangle P\binom{n+2}{3} is \underline{A056939} with matrix

P\binom{n+2}{3} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 4 & 1 & 0 & 0 & 0 & … \\ 1 & 10 & 10 & 1 & 0 & 0 & … \\ 1 & 20 & 50 & 20 & 1 & 0 & … \\ 1 & 30 & 175 & 175 & 30 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

The k-th column of this matrix has generating function

x^{k} \frac{∑_{j=0}^{k} N_{3}(k, j)x^{j}}{(1 − x)^{3k+1}}

where N_{3}(n, k) is the triangle of 3-Narayana numbers, [18], \underline{A087647}.

P\binom{n+3}{4} is the number triangle \underline{A056940}.

9 Acknowledgments

The author wishes to thank Laura L. M. Yang for her careful reading of this manuscript and her helpful comments. The author also thanks an anonymous referee for their pertinent comments and suggestions.

References

[1] W. Y. C. Chen, S. H. F. Yan and L. L. M. Yang, Identities from weighted 2-Motzkin

   paths, published electronically at http://arxiv.org/pdf/math.CO/0410200.pdf, 2006.

[2] C. Coker, Enumerating a class of lattice paths, Discrete Math. 271 (2003) 13–28.

[3] A. W. F. Edwards, Pascal’s Arithmetical Triangle, Johns Hopkins University Press, 2002.

[4] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[5] G. Helms, Binomial-(“Pascal”)-Matrix: a beautiful identity, available electronically at

   141.51.96.22/files/PascalDreieckMatrixLog.pdf, 2006.

[6] I. M. Gessel, X. G. Viennot, Determinants, Paths, and Plane Partitions, available

   electronically at http://people.brandeis.edu/∼gessel/homepage/papers/pp.pdf,

2006.

[7] E. Krot, An Introduction to Finite Fibonomial Calculus, published electronically at

   http://arxiv.org/pdf/math.CO/0503210.pdf, 2006.

[8] D. E. Knuth, The Art of Computer Programming, Addison-Wesley, Reading, MA, Vol. 1, pp. 84,492.

[9] T. D. Noe, On the divisibility of generalized central binomial coefficients, Preprint, 2005,

   available electronically at http://www.sspectra.com/math/Trinomial.pdf, 2006.

[10] T. M. Richardson, The Filbert matrix, published electronically at

   http://arxiv.org/pdf/math.RA/9905079.pdf, 2006.

[11] L. W. Shapiro, S. Getu, W-J. Woan and L.C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

[12] L. W. Shapiro, Bijections and the Riordan group, Theoretical Comp. Sci. 307 (2003) 403–413.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

   cally at http://www.research.att.com/∼njas/sequences/, 2006.

[14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices of the AMS, 50 (2003), 912–915.

[15] R. Sprugnoli, Combinatorial Identities. Published electronically at

   http://www.dsi.unifi.it/∼resp/GouldBK.pdf, 2006.

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

[17] R. A. Sulanke, Counting lattice paths by Narayana polynomials, Electronic J. Combin. 7 (2000), #R40.

[18] R. A. Sulanke, Generalizing Narayana and Schröder numbers to higher dimensions, Electron. J. Combin. 11 (1) (2004), #R54.

[19] R. A. Sulanke, The Narayana distribution, J. Statist. Plann. and Infer. 101(2002) 311– 346.

[20] J. Touchard, Sur certaines equations fonctionelles, in: Proceedings of the International Congress on Mathematics, University of Toronto Press, Toronto, 1928, pp. 465–472.

[21] E. W. Weisstein, http://mathworld.wolfram.com/BinomialTransform.html/, 2006.
[22] E. W. Weisstein, http://mathworld.wolfram.com/CatalanNumber.html/, 2006.
[23] E. W. Weisstein, http://mathworld.wolfram.com/DelannoyNumber.html/, 2006.
[24] E. W. Weisstein, http://mathworld.wolfram.com/FibonacciCoefficient.html/,

2006.

[25] E. W. Weisstein, http://mathworld.wolfram.com/FibonacciNumber.html/, 2006.
[26] E. W. Weisstein, http://mathworld.wolfram.com/JacobsthalNumber.html/, 2006.
[27] E. W. Wesstein, http://mathworld.wolfram.com/LucasSequence.html/, 2006.

[28] E. W. Weisstein,

   http://mathworld.wolfram.com/ModifiedBesselFunctionoftheFirstKind.html/,

2006.

[29] E. W. Weisstein, http://mathworld.wolfram.com/PellNumber.html/, 2006.

[30] H. S. Wilf, Generatingfunctionology, Academic Press, 1994.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 05A19, 11B37, 11B65. Keywords: Pascal’s triangle, Narayana numbers, Catalan numbers, Schröder numbers, Delannoy numbers, Fibonacci numbers, Jacobsthal numbers.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A000129}, \underline{A000891}, \underline{A000984}, \underline{A001003}, \underline{A001045}, \underline{A001263}, \underline{A001700}, \underline{A001850}, \underline{A002002}, \underline{A003150}, \underline{A005568}, \underline{A006318}, \underline{A007318}, \underline{A007564}, \underline{A008288}, \underline{A009545}, \underline{A010048}, \underline{A015056}, \underline{A015109}, \underline{A016116}, \underline{A047891}, \underline{A056939}, \underline{A056940}, \underline{A059231}, \underline{A060693}, \underline{A078009}, \underline{A078018}, \underline{A081178}, \underline{A081577}, \underline{A081578}, \underline{A081579}, \underline{A081580}, \underline{A082147}, \underline{A082148}, \underline{A082181}, \underline{A082201}, \underline{A082301}, \underline{A082302}, \underline{A082305}, \underline{A082366}, \underline{A082367}, \underline{A087647}, \underline{A088218}, \underline{A088617}, \underline{A088855}, \underline{A114197}, \underline{A114198}, \underline{A114202}, \underline{A117401}. )

Received December 7 2005; revised version received April 21 2006. Published in Journal of Integer Sequences, May 19 2006.

Return to Journal of Integer Sequences home page.