On a Generalization of the Narayana Triangle

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

By studying various ways of describing the Narayana triangle, we provide a number of generalizations of this triangle and study some of their properties. In some cases, the diagonal sums of these triangles provide examples of Somos-4 sequences via their Hankel transforms.

1 Introduction

In this note, we shall construct a generalization of the Narayana triangle by two means, and show that both constructions lead to the same result. The first is based on a closed expression for the general term of the triangle, inspired by a trinomial expression. The second construction is inspired by a certain bivariate continued fraction expression for the generating function of the Narayana triangle. This expression also allows us to easily investigate the diagonal sums of the the generalized Narayana triangles under study. In certain circumstances (but not all), the Hankel transforms of these diagonal sums turn out to be generalized Somos-4 sequences.

The Narayana triangle, and the polynomials for which it is the coefficient array, have many applications that span such areas as combinatorics [7, 11, 15, 20, 34, 36], probability [26, 35] and statistics [26, 35], random matrix theory [13, 14, 24] and wireless communications [2, 18, 25, 38] . We have previously studied [2] methods to describe this triangle, or more correctly, the three closely related triangles that are each commonly called the Narayana triangle. Thus we distinguish between the triangle N_{1}(n, k) \underline{A131198} that has general term

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

the triangle N_{2} \underline{A090181} that has general term

N_{2}(n, k) = [k ≤ n]N_{1}(n, n − k) = 0^{n+k} + \frac{1}{n + 0^{nk}} \binom{n}{k}\binom{n}{k − 1}  (1)
= \frac{1}{n − k + 1}\binom{n − 1}{n − k}\binom{n}{k},  (2)

(this is the reversal of N_{1}), and the triangle N = N_{3} \underline{A001263} which has general term

N_{3}(n, k) = \frac{1}{k + 1}\binom{n}{k}\binom{n + 1}{k}.

Thus N = N_{3} is the familiar “Pascal-like” triangle that begins

N_{3} = ( \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 clearly have N(n, k) = N(n, n − k). A number triangle with this property will be called “Pascal-like”. Some generalizations of the Narayana numbers have been studied for instance in [36].

During this paper, we will use the following notational conventions. For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f(x) = ∑_{k=0}^{∞} a_{k}x^{k} is called the ordinary generating function or g.f. of the sequence. The element of the sequence a_{n} is thus the coefficient of x^{n} in this series. We denote this by a_{n} = [x^{n}]f(x). For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number \underline{A000045}, while C_{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x} is the nth Catalan number \underline{A000108}. The power series f(x) = ∑_{k=0}^{∞} a_{k} \frac{x^{k}}{k!} is called the exponential generating function or e.g.f. of the sequence. We use the notation 0^{n} = [x^{n}]1 for the sequence 1, 0, 0, 0, …, \underline{A000007}. Thus 0^{n} = [n = 0] = δ_{n,0} = \binom{0}{n}. Here, we have used the Iverson bracket notation [17], defined by [P] = 1 if the proposition P is true, and [P] = 0 if P is false.

For a power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} with f(0) = 0 we define the reversion or compositional inverse of f to be the power series f̄(x) such that f(f̄(x)) = x. We sometimes write f̄ = Revf.

The Hankel transform [9, 23] of a sequence a_{n} is the sequence h_{n} = |a_{i+j}|_{0≤i,j≤n}. For certain sequences, this may be calculated by means of continued fraction representations [21, 22]. We shall use continued fractions [4, 39] extensively in what follows. We also use some moment or integral representations of sequences, which derive for instance from the theory of orthogonal polynomials [8, 16, 37]. In particular we recall that

C_{n} = \frac{1}{2π} ∫_{0}^{4} x^{n} \frac{\sqrt{x(4 − x)}}{x} dx

and

\binom{2n}{n} = \frac{1}{π} ∫_{0}^{4} x^{n} \frac{1}{\sqrt{x(4 − x)}} dx.

We shall have occasion to use the language of Riordan arrays in this note. The Riordan group [30, 33] 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 [33]. 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. Also called the reversion of f, we will use the notation f̄ = Rev(f) as well.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences Z^{N} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series Z[[x]] by

(g, f) : A(x) ↦ (g, f) · A(x) = g(x)A(f(x)).

By an abuse of language, if a_{n} has g.f. A(x) and b_{n} has g.f. g(x)A(f(x)), we may also write

(g, f) · a_{n} = b_{n}.

Example 1. The binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

The row sums of the matrix (g, f) have generating function

(g, f) · \frac{1}{1 − x} = \frac{g(x)}{1 − f(x)}

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

In similar fashion we can also define exponential Riordan arrays [g, f], using the e.g.f [5, 10] instead of the ordinary generating function. For instance, the identity matrix is given by [1, x] and the binomial matrix is given by [e^{x}, x].

If a_{n} is the sequence a_{0}, a_{1}, a_{2}, … with g.f. f(x), then the sequence a_{0}, 0, a_{1}, 0, a_{2}, 0, … with g.f. f(x^{2}) is called the aeration of a_{n}.

Many interesting examples of number triangles, including Riordan arrays, can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences [31, 32]. Sequences are frequently referred to by their OEIS number. For instance, the matrix B is \underline{A007318}. We observe that the Narayana triangles are not Riordan arrays.

2 Trinomials and the Narayana triangle

In order to explore how we might generalize the Narayana triangle N, we start with the following observation concerning powers of trinomials (the paper [28] provides an introduction to the combinatorics of trinomials).

Proposition 2. The number triangle with general term

[x^{2k}](1 + \sqrt{α}x + x^{2})^{n}

is “Pascal-like”.

Proof. We first calculate T (n, k). We have

T (n, k) = [x^{2k}](1 + βx + x^{2})^{n}, β = \sqrt{α},
= [x^{2k}] ∑_{j=0}^{n} \binom{n}{j}x^{2j}(1 + βx)^{n−j}

= [x^{2k}] ∑_{j=0}^{n} \binom{n}{j}x^{2j} ∑_{i=0}^{n−j} \binom{n − j}{i}β^{i}x^{i}

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

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

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

We now wish to show that T (n, k) = T (n, n − k), or that

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

To do this, we will show that the coefficients of powers of α are equal on both sides of the sought identity. We have on the one hand that

\binom{n}{j}\binom{n − j}{2k − 2j}α^{k−j} = \binom{n}{n − j}\binom{n − j}{2k − 2j}α^{k−j}
= \binom{n}{2k − 2j}\binom{n − 2k + 2j}{n − j − 2k + 2j}α^{k−j}
= \binom{n}{2(k − j)}\binom{n − 2(k − j)}{n + j − 2k}α^{k−j}
= \binom{n}{2u}\binom{n − 2u}{n − k − u}α^{u}, u = k − j.

On the other hand, we have

\binom{n}{j}\binom{n − j}{2(n − k) − 2j}α^{n−k−j} = \binom{n}{n − k − u}\binom{u + k}{2u}α^{u}, u = n − k − j
= \binom{n}{u + k}\binom{u + k}{2u}α^{u}
= \binom{n}{2u}\binom{n − 2u}{k − u}α^{u}
= \binom{n}{2u}\binom{n − 2u}{n − k − u}α^{u}.

We are indebted to an anonymous referee for the following simpler proof of the above result. Observe that x^{2n}f_{n}(1/x) = f_{n}(x), where f_{n}(x) = (1 + \sqrt{α}x + x^{2})^{n}. Hence we have

T (n, k) = [x^{2k}]f_{n}(x)
= [x^{2k}]x^{2n}f_{n}(1/x)
= [x^{2k−2n}]f_{n}(1/x)
= [x^{2n−2k}]f_{n}(x) = T (n, n − k).

Example 3. Pascal’s triangle The binomial triangle \binom{n}{k} is given by

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

Example 4. The triangle with general term

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

begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 4 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 9 & 9 & 1 & 0 & 0 & 0 & … \\ 1 & 16 & 34 & 16 & 1 & 0 & 0 & … \\ 1 & 25 & 90 & 90 & 25 & 1 & 0 & … \\ 1 & 36 & 195 & 328 & 195 & 36 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This is \underline{A124216}.

We can easily characterize the central coefficients of the triangle with general term ∑_{j=0}^{n} \binom{n}{j}\binom{n−j}{2k−2j}r^{k−j}, such as the numbers 1, 4, 34, 328, … for r = 2 above.

Proposition 5. The central coefficients T (2n, n) of the triangle with general term ∑_{j=0}^{n} \binom{n}{j}\binom{n−j}{2k−2j}r^{k−j} have moment representation

T (2n, n) = \frac{1}{π} ∫_{\sqrt{r}−2}^{\sqrt{r}+2} \frac{x^{2n}}{\sqrt{4 − (x − \sqrt{r})^{2}}} dx.

Proof. We have

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

and

[x^{n}]\frac{1}{\sqrt{(1 − rx)^{2} − 4x^{2}}} = \frac{1}{π} ∫_{r−2}^{r+2} \frac{x^{n}}{\sqrt{4 − (x − r)^{2}}} dx,

where this last equation can be established using Stieltjes-Perron techniques ([1, 16, 19, 39]). Now

T (2n, n) = [x^{2n}](1 + \sqrt{r}x + x^{2})^{2n},

whence the assertion.

In order to relate the foregoing to the Narayana triangle, we use an “umbral” [29] approach. We recall that the Catalan numbers

C_{n} = \frac{1}{n + 1}\binom{2n}{n}

have the following moment representation:

C_{n} = \frac{1}{2π} ∫_{0}^{4} x^{n} \frac{\sqrt{x(4 − x)}}{x}dx = ∫_{ℝ} x^{n}dμ_{C}(x).

We now define

T_{C}(n, k) = ∫_{ℝ}[y^{2k}](1 + \sqrt{x}y + y^{2})^{n}dμ_{C}(x).

Lemma 6.

T_{C}(n, k) = ∑_{j=0}^{n} \binom{n}{j}\binom{n − j}{2(k − j)}C_{k−j}.

Proof.

T_{C}(n, k) = ∫_{ℝ}[y^{2k}](1 + \sqrt{x}y + y^{2})^{n}dμ_{C}
= \frac{1}{2π} ∫_{0}^{4}[y^{2k}](1 + \sqrt{x}y + y^{2})^{n} \frac{\sqrt{x(4 − x)}}{x}dx
= \frac{1}{2π} ∫_{0}^{4} ∑_{j=0}^{n} \binom{n}{j}\binom{n − j}{2(k − j)}x^{k−j} \frac{\sqrt{x(4 − x)}}{x}dx

= ∑_{j=0}^{n} \binom{n}{j}\binom{n − j}{2(k − j)}\frac{1}{2π} ∫_{0}^{4} x^{k−j} \frac{\sqrt{x(4 − x)}}{x}dx

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

Proposition 7.

T_{C}(n, k) = N(n, k).

Proof. We have

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

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

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

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

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

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

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

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

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

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

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

= \frac{1}{k + 1}\binom{n}{k}\binom{n + 1}{k},

or

T_{C}(n, k) = ∑_{j=0}^{n} \binom{n}{j}\binom{n − j}{2(k − j)}C_{k−j} = \frac{1}{k + 1}\binom{n}{k}\binom{n + 1}{k} = N(n, k).

Many interesting results about the Narayana triangle may be deduced from the above. An example is the following integral representation of the central coefficients of the Narayana triangle, which is the sequence \underline{A000891} with general term N(2n, n) = \frac{1}{n+1} \binom{2n}{n}\binom{2n+1}{n} = \frac{1}{2n+1} \binom{2n+1}{n}^{2} and begins

1, 3, 20, 175, 1764, 19404, 226512, 2760615, 34763300, …

Proposition 8. We have

N(2n, n) = \frac{1}{2π^{2}} ∫_{0}^{4} ∫_{\sqrt{y}−2}^{\sqrt{y}+2} \frac{x^{2n}}{\sqrt{4 − (x − \sqrt{y})^{2}}} \frac{\sqrt{y(4 − y)}}{y} dx dy  (3)

We have thus established that the Narayana triangle is intimately connected to the sequence of Catalan numbers. We now generalize this construction to general integer sequences a_{n} with a_{0} = 1. Thus if we are given an integer sequence (a_{n})_{n≥0} with a_{0} = 1, we define the number triangle with general term

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

to be the generalized Narayana triangle associated to a_{n}.

Example 9. a_{n} = 0^{n}, with term 1, 0, 0, 0, . . .. We have seen in example 3 that the generalized Narayana triangle associated to 0^{n} is Pascal’s triangle.

Example 10. a_{n} = 2^{n}. We have already met this example, where

T_{2^{n}}(n, k) = [x^{2k}](1 + \sqrt{2}x + x^{2})^{n}.

Example 11. We have

T\binom{2n}{n}(n, k) = \binom{n}{k}^{2}.

Proof. We have

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

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

= \binom{n}{k}^{2}.

We can also deduce the following about the central terms \binom{2n}{n}^{2} of this triangle:

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

= \frac{1}{π^{2}} ∫_{0}^{4} ∫_{\sqrt{y}−2}^{\sqrt{y}+2} \frac{x^{2n}}{\sqrt{4 − (x − \sqrt{y})^{2}}} \frac{1}{\sqrt{y(4 − y)}} dx dy.

Example 12. The generalized Catalan triangle associated to the Fibonacci numbers F_{n+1} has general term

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

and begins

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

Note the N has row [1, 21, 105, 175, 105, 21, 1] where this triangle has [1, 21, 105, 173, 105, 21, 1]. This triangle is \underline{A162745}.

3 Continued fractions

It is known that N has a generating function given by the continued fraction [4, 6, 40]

g_{N}(x, y) = \frac{1}{1 − xy − \frac{x}{1 − \frac{xy}{1 − \frac{x}{1 − ⋯}}}}.

This can also be expressed as

g_{N}(x, y) = \frac{1 − x(1 + y) − \sqrt{1 − 2x(1 + y) + x^{2}(1 − y)^{2}}}{2x^{2}y} .  (4)

For our purposes, we find it easier to work with another continued fraction. Thus we have Proposition 13. The bivariate generating function of the Narayana triangle may be expressed in continued fraction form as:

g_{N}(x, y) = \frac{1}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − …}}}.  (5)

Proof. We may solve the equation

u(x, y) = \frac{1}{1 − x − xy − x^{2}yu(x, y)}

to obtain the corresponding closed form. We find

u(x, y) = g_{N}(x, y).

We recall that the Catalan numbers have generating function

g_{C}(x) = \frac{1 − \sqrt{1 − 4x}}{2x}

which is also given by

g_{C}(x) = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − …}}}.

Thus

g_{C}(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − …}}},

where in this case, α_{n} = 1 for n ≥ 1. These coefficients α_{n} = 1 are reproduced in equation (5) as the coefficients of x^{2}y.

This leads us to the following generalization: if a_{n} is a sequence with generating function expressible as

g_{a}(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − …}}},

then we define as the generalized Narayana triangle associated to g_{a} the number triangle with bivariate generating function given by

\frac{1}{1 − x − xy − \frac{α_{1}x^{2}y}{1 − x − xy − \frac{α_{2}x^{2}y}{1 − x − xy − …}}}.  (6)

We call sequences with generating functions of the above form g_{a}(x) “Catalan-like”. For such “Catalan-like” sequences, there is a binomial transform interpretation to this bivariate continued fraction. We can write it in the form

\frac{1}{1 − x(1 + y) − \frac{α_{1}x^{2}(\sqrt{y})^{2}}{1 − x(1 + y) − \frac{α_{2}x^{2}(\sqrt{y})^{2}}{1 − x(1 + y) − …}}}

which can then [4] be regarded as the (1 + y)-th binomial transform of the aeration of the Catalan-like sequence with g.f.

\frac{1}{1 − \frac{α_{1}\sqrt{y}x}{1 − \frac{α_{2}\sqrt{y}x}{1 − …}}}.

We can for instance easily characterize the row sums of these generalized Narayana triangles.

Proposition 14. Let N_{a} be the generalized Narayana triangle of the Catalan-like sequence a_{n}. Then the row sums of N_{a} are the second binomial transform of the aeration of a_{n}.

Proof. The row sums have continued fraction generating function given by (set y = 1):

\frac{1}{1 − 2x − \frac{α_{1}x^{2}}{1 − 2x − \frac{α_{2}x^{2}}{1 − 2x − …}}}

The result follows immediately from [4].

Obviously, the row sums of the second inverse binomial transform of a generalized Narayana triangle N_{a}, that is, of the triangle B^{−2}N_{a}, are equal to the aeration of a_{n}. We note that this triangle, up to signs, is also Pascal-like. The triangle B^{−1}N_{a} is of a specific shape, typified by B^{−1}N = B^{−1}N_{C}:

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 3 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & 2 & 6 & 1 & 0 & 0 & … \\ 0 & 0 & 0 & 10 & 10 & 1 & 0 & … \\ 0 & 0 & 0 & 5 & 30 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

where we see the aeration of the defining sequence appearing in the (2n, n)-positions. It is clear that the row sums of this triangle will be the binomial transform of the aeration of the defining sequence (in this case, we get the Motzkin numbers \underline{A001006}). The triangle B^{−1}N_{a} has generating function given by the continued fraction

\frac{1}{1 − xy − \frac{α_{1}x^{2}y}{1 − xy − \frac{α_{2}x^{2}y}{1 − xy − …}}}.

Example 15. The central binomial coefficients \binom{2n}{n} have g.f. given by

\frac{1}{1 − \frac{2x}{1 − \frac{x}{1 − \frac{x}{1 − …}}}}.

The corresponding generalized Narayana triangle thus has generating function

g(x, y) = \frac{1}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − …}}}}.

This is in fact the triangle \binom{n}{k}^{2}.

We have the following:

Proposition 16.

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

Proof. We obviously have

g(x, y) = \frac{1}{1 − x − xy − 2x^{2}yg_{N}(x, y)}.

Simplifying, we get the result. Corollary 17.

g(x, y) = ∑_{n=0}^{∞} P_{n} (\frac{1 + y}{1 − y} ) x^{n}(1 − y)^{n},

where P_{n} is the n-th Legendre polynomial. Proof. This follows since we have

\frac{1}{1 − 2ut + t^{2}} = ∑_{n=0}^{∞} P_{n}(u)t^{n}.

Example 18. The (large) Schröder numbers \underline{A006318} have generating function given by

\frac{1}{1 − \frac{2x}{1 − \frac{x}{1 − \frac{2x}{1 − \frac{x}{1 − …}}}}},

with coefficient pattern (2, 1, 2, 1, 2, 1, 2, 1, …). The corresponding generalized Narayana triangle thus has generating function

g_{S}(x, y) = \frac{1}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − …}}}}.

This triangle begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 4 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 9 & 9 & 1 & 0 & 0 & 0 & … \\ 1 & 16 & 36 & 16 & 1 & 0 & 0 & … \\ 1 & 25 & 100 & 100 & 25 & 1 & 0 & … \\ 1 & 36 & 225 & 402 & 225 & 36 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

We can obtain g_{S}(x, y) in closed form by solving the equation

g_{S}(x, y) = \frac{1}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − x^{2}yg_{S}(x, y)}}.

Example 19. The double factorials (2n − 1)!! = \frac{(2n)!}{n!2^{n}}, \underline{A001147}, have g.f. given by

\frac{1}{1 − \frac{x}{1 − \frac{2x}{1 − \frac{3x}{1 − …}}}}.

The triangle associated to this generating function thus has bivariate generating function

\frac{1}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − \frac{3x^{2}y}{1 − x − xy − \frac{4x^{2}y}{1 − x − xy − …}}}}.

This triangle begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 6 & 6 & 1 & 0 & 0 & 0 & … \\ 1 & 10 & 21 & 10 & 1 & 0 & 0 & … \\ 1 & 15 & 55 & 55 & 15 & 1 & 0 & … \\ 1 & 21 & 120 & 215 & 120 & 21 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The row sums of this triangle are \underline{A005425} with e.g.f. e^{2x+x^{2}/2}. The triangle has e.g.f. e^{x+xy+yx^{2}/2}. This is \underline{A100862}. It is the exponential Riordan array

[e^{x}, x(1 + \frac{x}{2})] ,

with general term [5]

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

Example 20. The Fibonacci numbers F (n + 1) have generating function

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

We thus associate to it the triangle with bivariate generating function

\frac{1}{1 − x − xy − \frac{x^{2}y}{1 − x − xy − \frac{x^{2}y}{1 − x − xy + \frac{x^{2}y}{1 − x − xy}}}}.

This can be expressed as

\frac{(1 − x − xy)^{3}}{1 − 4x(1 + y) + x^{2}(6 + 11y + 6y^{2}) − 2x^{3}(2 + 5y + 5y^{2} + 2y^{3}) + x^{4}(1 + 3y + 3y^{2} + 3y^{3} + y^{4})}.

It is natural to ask if these two notions of generalized Narayana triangle coincide. That the answer is in the affirmative follows from the following theorem.

Theorem 21. Let a_{n} be a sequence whose generating function can be expressed as a continued fraction

g_{a}(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − …}}},

which may be finite or infinite. Then the generalized Narayana triangle associated to g_{a} with bivariate generating function

\frac{1}{1 − x − xy − \frac{α_{1}x^{2}y}{1 − x − xy − \frac{α_{2}x^{2}y}{1 − x − xy − …}}}

coincides with the generalized Narayana triangle associated to a_{n}, and thus has general term

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

Proof. We have

g(x, y) = \frac{1}{1 − x(1 + y) − \frac{α_{1}x^{2}y}{1 − x(1 + y) − \frac{α_{2}x^{2}y}{1 − x(1 + y) − …}}}

which is thus seen to be the g.f. of the (1 + y)-th binomial transform of \sqrt{y}^{n} times the aeration of the sequence with g.f.

\frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − …}}}.

Thus the triangle in question is given by

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

Corollary 22. The Narayana polynomials N(x) = ∑_{k=0}^{n} N(n, k)x^{k} satisfy

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

4 Diagonal sums of triangles

The diagonal sums of the Narayana triangle, that is, the sequence with general term

r_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} N(n − k, k),

which begins

1, 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, 2283, …

(\underline{A004148}) have important applications in the area of secondary RNA structures [27]. By our results above (see Equations (4) and (5)), we see that this sequence has generating function

g_{N}(x, x) = \frac{1 − x − x^{2} − \sqrt{1 − 2x − x^{2} − 2x^{3} + x^{4}}}{2x^{3}}

which can be expressed in continued fraction form as

g_{N}(x, x) = \frac{1}{1 − x − x^{2} − \frac{x^{3}}{1 − x − x^{2} − \frac{x^{3}}{1 − x − x^{2} − …}}}.

The Hankel transform (h_{n})_{n≥0} of this sequence is the periodic sequence \underline{A046980} which begins

1, 1, 0, −1, −1, −1, 0, 1, 1, 1, 0, −1, −1, −1, 0, 1, 1, 1, 0, −1, −1, …,

with generating function \frac{1+x−x^{3}}{1+x^{4}} . This sequence, for those terms for which it makes sense, satisfies the Somos-4 equation

h_{n} = \frac{h_{n−1}h_{n−3} − h_{n−2}^{2}}{h_{n−4}} .

Example 23. We consider the generalized Narayana triangle associated to the central binomial coefficients \binom{2n}{n}. This triangle has general term \binom{n}{k}^{2}, and thus the diagonal sums d_{n} are given by

d_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}^{2}.

The generating function of this sequence \underline{A051286}, which begins

1, 1, 2, 5, 11, 26, 63, 153, 376, 931, 2317, …,

is given by

\frac{1}{\sqrt{1 − 2x(1 + x) + x^{2}(1 − x)^{2}}} = ∑_{n=0}^{∞} P_{n} (\frac{1 + x}{1 − x}) x^{n}(1 − x)^{n},

or in continued fraction form, as

\frac{1}{1 − x − x^{2} − \frac{2x^{3}}{1 − x − x^{2} − \frac{x^{3}}{1 − x − x^{2} − …}}}.

Its Hankel transform h_{n} \underline{A174882} begins

1, 1, −2, −8, −16, −16, 32, 128, 256, 256, −512, …

with g.f. \frac{1+x−2x^{2}−8x^{3}}{1+16x^{4}} . This sequence is a (\frac{3}{2}, −1) Somos-4 sequence, in the sense that we have

h_{n} = \frac{\frac{3}{2}h_{n−1}h_{n−3} − h_{n−2}^{2}}{h_{n−4}} , n ≥ 4.

We note in passing that the sequence given by the logarithms (to base 2) of |h_{n}| is the sequence (see \underline{A098181}) that begins

0, 0, 1, 3, 4, 4, 5, 7, 8, 8, 9, 11, 12, …

with generating function \frac{x^{2}(1+x)}{(1−x)^{2}(1+x^{2})} and general term

\frac{1}{2} \{2n − 1 + cos (\frac{πn}{2}) − sin (\frac{πn}{2})\} = \frac{1}{2} \{2n − 1 + (−1)^{\binom{n+1}{2}}\} .

Note that using the language of Riordan arrays, and the result of Proposition 16, we have the following expressions for the generating function of the diagonal sums:

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

In fact we have the following result.

Proposition 24.

d_{n} = (\frac{1}{1 + rx + x^{2}} , \frac{x}{1 + rx + x^{2}} ) · [u^{n}](1 + (r + 1)u + u^{2})^{n},

for any integer r. Example 25. We consider the generalized Narayana triangle associated to 2^{n}C_{n},which has generating function

\frac{1}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − \frac{2x^{2}y}{1 − x − xy − …}}}

and general term

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

Then the diagonal sums of this triangle (\underline{A025245}) begin

1, 1, 2, 5, 11, 26, 65, 163, 416, 1081, 2837, …

and have generating function

\frac{1}{1 − x − x^{2} − \frac{2x^{3}}{1 − x − x^{2} − \frac{2x^{3}}{1 − x − x^{2} − …}}}

or

\frac{1 − x − x^{2} − \sqrt{1 − 2x − x^{2} − 6x^{3} + x^{4}}}{4x^{3}} .

The Hankel transform h_{n} of the diagonal sums begins

1, 1, −2, −12, −64, −64, 6656, 143360, 3342336, −105906176, −15837691904, …. It is a (4, −4) Somos-4 sequence in the sense that

h_{n} = \frac{4h_{n−1}h_{n−3} − 4h_{n−2}^{2}}{h_{n−4}} , n ≥ 4.

We can in fact conjecture the following: Conjecture 26. The Hankel transform of the sequence with generating function

g(x) = \frac{1}{1 − αx − βx^{2} − γx^{3}g(x)}

is a (γ^{2}, −βγ^{2}) Somos-4 sequence.

Example 27. A Gaussian integer Somos-4 sequence. We note the following consequence of this conjecture: the (complex) sequence with generating function

\frac{1}{1 − x − x^{2} − \frac{ix^{3}}{1 − x − x^{2} − \frac{ix^{3}}{1 − x − x^{2} − \frac{ix^{3}}{1 − x − x^{2} − …}}}},

where i = \sqrt{−1}, has a Hankel transform that is a (−1, 1) Somos-4 sequence:

h_{n} = \frac{−h_{n−1}h_{n−3} + h_{n−2}^{2}}{h_{n−4}} , n ≥ 4.

This corresponds to the diagonal sums of the triangle with general term

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

This sequence begins

1, 1, 2, 3 + i, 5 + 3i, 8 + 9i, 11 + 22i, 11 + 51i, −6 + 111i, −75 + 228i, −291 + 439i, …

with Hankel transform beginning

1, 1, 1 + i, −i, 3i, 2 − 3i, −2 + 4i, 6 + 7i, −4 + 15i, −24 + 29i, −39 − 15i ….

Example 28. The sums of the diagonals of the Narayana triangle associated to the Schröder numbers begin

1, 1, 2, 5, 11, 26, 63, 153, 376, 933, 2331, …

and have generating function

\frac{1 − 2x − x^{2} + x^{3} + x^{4} − \sqrt{1 − 4x + 2x^{2} + 2x^{3} + 7x^{4} − 2x^{5} − 9x^{6} − 2x^{7} + x^{8}}}{2x^{3}(1 − x − x^{2})}

corresponding to the continued fraction

\frac{1}{1 − x − x^{2} − \frac{2x^{3}}{1 − x − x^{2} − \frac{x^{3}}{1 − x − x^{2} − \frac{2x^{3}}{1 − x − x^{2} − …}}}}.

We note that the Hankel transform of this sequence is not a Somos-4 sequence.

References

[1] P. Barry, Riordan arrays, orthogonal polynomials as moments, and Hankel transforms, J. Integer Seq., 14 (2011), Article 11.2.2.

[2] P. Barry and A. Hennessy, A note on Narayana triangles and related polynomials, Riordan arrays, and MIMO capacity calculations, J. Integer Seq., 14 (2011), Article 11.3.8.

[3] P. Barry, Generalized Catalan numbers, Hankel transforms and Somos-4 sequences, J. Integer Seq., 13 (2010) Article 10.7.2.

[4] P. Barry, Continued fractions and transformations of integer sequences, J. Integer Seq., 12 (2009), Article 09.7.6.

[5] P. Barry, On a family of generalized Pascal triangles defined by exponential Riordan arrays, J. Integer Seq., 10 (2007), Article 07.3.5.

[6] P. Brändén, A. Claesson, and E. Steingrímsson, Catalan continued fractions and increasing subsequences in permutations, Discrete Math., 258, (2002), 275–287.

[7] F. Chapoton, Enumerative Properties of generalized associahedra, Sim. Lothar. Combin. 51 p. 16 Art. B51b.

[8] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

[9] A. Cvetković, P. Rajković, and M. Ivković, Catalan numbers, the Hankel transform and Fibonacci numbers, J. Integer Seq., 5 (2002), Article 02.1.3.

[10] E. Deutsch and L. Shapiro, Exponential Riordan arrays, Lecture Notes, Nankai University, 2004, available electronically at

   http://www.combinatorics.net/ppt2004/Louis%20W.%20Shapiro/shapiro.htm,

2010.

[11] T. Doslić, Morgan trees and Dyck paths, Croatica Chemica Acta, 75 (4) (2002), 881–889.

[12] T. Doslić, D. Svrtan, and D. Veljan, Discrete Math. 285 (2004), 67–82.

[13] I. Dumitriu, Eigenvalue Statistics for Beta-Ensembles, Thesis, MIT, 2003.

[14] I. Dumitriu and E. Rassart, Path counting and random matrix theory, Electron. J. Combin., 10 (2003), 35–47.

[15] S. Fomin and N. Reading, Root systems and generalized associahedra, in Geometric Combinatorics, IAS/Park City Math. Ser., 13, Amer. Math. Soc., 2007, pp. 63–131.

[16] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press, Oxford, 2003.

[17] I. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison–Wesley, 1994.

[18] I. Groh, S. Plass, and S. Stand, Capacity approximation for uncorrelated MIMO channels using random matrix methods. In Proc. 2006 Second International Symposium on Communications, Control and Signal Processing, (ISCCSP 2006), Marrakech, Morocco, pp. 13–16.

[19] P. Henrici, Applied and Computational Complex Analysis: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions, vol. 3, Wiley Classics Library, 1993.

[20] V. P. Kostov, A. Martínez-Finkelshtein, and B. Z. Shapiro, Narayana numbers and Schur-Szegö composition, J. Approx. Theory, 161 (2009), 464–476.

[21] C. Krattenthaler, Advanced determinant calculus, available electronically at

http://www.mat.univie.ac.at/~slc/wpapers/s42kratt.pdf, 2010.

[22] C. Krattenthaler, Advanced determinant calculus: A complement, Linear Algebra Appl., 411 (2005), 68–166.

[23] J. W. Layman, http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html The Hankel transform and some of its properties, J. Integer Seq., 4, (2001), Article 01.1.5.

[24] V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues in certain sets of random matrices, Math. USSR Sb. 1 (1967), 457–483.

[25] R. Müller, A random matrix model of communications via antenna arrays, IEEE Trans. Inform. Theory,48, (2002), 2495–2506.

[26] T. V. Narayana, Lattice Path Combinatorics with Statistical Applications, Univ. of Toronto Press, 1979.

[27] A. Nkwanta, Lattice paths and RNA secondary structures, African Americans in Mathematics DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 34, Amer. Math. Soc., 1997, 137–147.

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

[29] S. Roman, The Umbral Calculus, Dover Publications, 2005.

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

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

cally at http://oeis.org, 2011.

[32] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

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

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

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

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

[37] G. Szegö, Orthogonal Polynomials, 4th ed., Amer. Math. Soc., 1975.

[38] A. Tulino and S. Verdú, Random Matrix Theory and Wireless Communications, Now Publishers Inc., Hanover, MA, 2004.

[39] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2000.

[40] D. Zeilberger, Six études in generating functions, Internat. J. Comput. Math., 29 (1989), 201–215.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 05A10, 05A15, 11B37, 11Y55, 15A15, 15A30, 30B70. Keywords: Narayana triangle, continued fraction, Riordan array, Hankel determinant, Hankel transform, Somos-4.

(Concerned with sequences \underline{A000007}, \underline{A000045}, \underline{A000108}, \underline{A000891}, \underline{A001006}, \underline{A001147}, \underline{A001263}, \underline{A004148}, \underline{A005425}, \underline{A006318}, \underline{A007318}, \underline{A025245}, \underline{A025250}, \underline{A025253}, \underline{A046980}, \underline{A050512}, \underline{A051286}, \underline{A090181}, \underline{A098181}, \underline{A100862}, \underline{A124216}, \underline{A131198}, \underline{A162745}, and \underline{A174882}.)

Received September 23 2010; revised version received March 22 2011. Published in Journal of Integer Sequences, March 26 2011.

Return to Journal of Integer Sequences home page.