Jacobsthal Decompositions of Pascal’s Triangle, Ternary Trees, and Alternating Sign Matrices

Paul Barry School of Science Waterford Institute of Technology Ireland

                     pbarry@wit.ie

Abstract

We examine Jacobsthal decompositions of Pascal’s triangle and Pascal’s square from a number of points of view, making use of bivariate generating functions, which we derive from a truncation of the continued fraction generating function of the Narayana number triangle. We establish links with Riordan array embedding structures. We explore determinantal links to the counting of alternating sign matrices and plane partitions and sequences related to ternary trees. Finally, we examine further relationships between bivariate generating functions, Riordan arrays, and interesting number squares and triangles.

1 Introduction

In this partly expository article, we use the language of generating functions and Riordan arrays to explore decompositions of Pascal’s triangle and other number triangles and number squares. The decompositions that we study are shown to be related to the Jacobsthal numbers. Such decompositions have been studied in [3, 4], and we extend these studies to a more general context. The language of Riordan arrays presents itself as a unifying theme, and the interaction between Riordan arrays and bivariate generating functions becomes an important tool in the exploration of resulting sequences. The embedding of Riordan arrays in number squares was first studied in [5, 19]. Phenomena related to those studied here may also be observed in [16].

Strong links become apparent between these explorations and the results of [10]. The Hankel transform becomes an important tool, and we find many sequences whose Hankel transforms are related to counting alternating sign matrices and plane partitions.

The article is organized as follows.

• This Introduction

• The Jacobtshal decomposition of Pascal’s triangle

• A Narayana inspired Jacobsthal decomposition

• A Jacobsthal decomposition of 2^{n}.

• The matrices Ã, A^{H}, A^{V} and M and their associated Riordan arrays

• A Jacobsthal decomposition of the Pascal square S

• A further Jacobsthal of Pascal’s triangle

• Jacobsthal decompositions, ternary trees and ASM’s

• Generalizations

We continue this section with a brief overview of Riordan arrays, an introduction to alternating sign matrices, the Hankel transform of a sequence, some notational conventions, and three examples.

At its simplest, a Riordan array is formally defined by a pair of power series, say g(x) = ∑_{n=0} g_{n}x^{n} and f(x) = ∑_{n=0} f_{n}x^{n}, where g(0) = 1 and f(x) = x + f_{2}x^{2} + f_{3}x^{2} + ⋯, with integer coefficients (such Riordan arrays are called “proper” Riordan arrays). The pair (g, f) is then associated to the lower-triangular invertible matrix whose (n, k)-th element T_{n,k} is given by

T_{n,k} = [x^{n}]g(x)f(x)^{k}.

We sometimes write (g(x), f(x)) although the variable “x” here is a dummy variable, in that

T_{n,k} = [x^{n}]g(x)f(x)^{k} = [t^{n}]g(t)f(t)^{k}.

Here, [x^{n}] is the operator that extracts the coefficient of x^{n} in a power series [18].

The Fundamental Theorem of Riordan arrays (FTRA) [23] says that the action of a Riordan array on a power series, namely

(g(x), f(x)) · a(x) = g(x)a(f(x)),

is realized in matrix form by

(T_{n,k}) ( a_{0} ; a_{1} ; a_{2} ; a_{3} ; ⋮ ) = ( b_{0} ; b_{1} ; b_{2} ; b_{3} ; ⋮ ) ,

where the power series a(x) expands to give the sequence a_{0}, a_{1}, a_{2}, …, and the image sequence b_{0}, b_{1}, b_{2}, … has generating function g(x)a(f(x)).

The inverse of the Riordan array (g, f) is given by

(g(x), f(x))^{−1} = (\frac{1}{g(f̄(x))}, f̄(x)) .

Here, f̄(x) is the compositional inverse or the reversion of the power series f(x). Thus we have f̄(f(x)) = x and f(f̄(x)) = x. The power series f̄(x) is the solution to the equation f(u) = x that satisfies u(0) = 0.

The group law for Riordan arrays is given by

(g(x), f(x)) · (u(x), v(x)) = (g(x)u(f(x)), v(f(x)).

The above definitions refer to ordinary Riordan arrays, where the defining power series are ordinary generating functions such as g(x) = ∑_{n=0}^{∞} g_{n}x^{n}. When we use exponential generating functions g(x) = ∑_{n=0}^{∞} g_{n} \frac{x^{n}}{n!} and f(x) = ∑_{n=0}^{∞} f_{n} \frac{x^{n}}{n!} , (again with g(0) = 1 and f_{0} = 0, f_{1} = 1) we get the exponential Riordan array [g(x), f(x)] with general term

\frac{n!}{k!}[x^{n}]g(x)f(x)^{k}.

For instance, the exponential Riordan array [e^{x}, x] gives the binomial matrix (\binom{n}{k}).

Where possible, we shall refer to known sequences and triangles by their OEIS numbers [24, 25]. For instance, the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} with g.f. c(x) = \frac{1−\sqrt{1−4x}}{2x} is the sequence \underline{A000108}, the Fibonacci numbers are \underline{A000045}, the Jacobsthal numbers J_{n} = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3} are \underline{A001045}, and the Motzkin numbers M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k} are \underline{A001006}. The Robbins numbers are \underline{A005130}. We index all sequences beginning with the 0-th element, while all two-dimensional arrays are indexed starting with the (0, 0)-th element in the top left hand corner. When displaying number arrays, it is left understood that they are of infinite extent downwards and to the right, and only a suitable truncation is shown.

The binomial matrix B = (\binom{n}{k}) is \underline{A007318}. As a Riordan array, this is given by

B = (\frac{1}{1 − x}, \frac{x}{1 − x}) .

Its inverse is given by the matrix

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

In the sequel we shall use the Iverson bracket [S], which is equal to 1 if the statement S is true, and 0 otherwise [11].

An alternating sign matrix (ASM) is a square matrix of 0’s, 1’s and −1’s such that the sum of each row and each column is 1 and the non-zero entries in each row and column alternate in sign. These matrices generalize the permutation matrices. For instance, there are 7 alternating sign matrices of size 3, comprised of the 3! = 6 permutation matrices of size 3 along with the matrix

( \begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix} ) .

The alternating sign matrices of size n are counted by the Robbins numbers \underline{A005130}

1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, …,

with general term

A_{n} = ∏_{k=0}^{n−1} \frac{(3k + 1)!}{(n + k)!}.

These numbers also count the number of descending plane partitions whose parts do not exceed n. Here, a plane partition is a two-dimensional array of nonnegative integers n_{i,j} (with positive integer indices i and j) that is non-increasing in both indices, that is, that satisfies

n_{i,j} ≥ n_{i,j+1} and n_{i,j} ≥ n_{i+1,j} for all i, j.

A plane partitions may be represented visually by the placement of a stack of n_{i,j} unit cubes above the point (i, j) in the plane, giving a three-dimensional solid tied to the origin and aligned with the coordinate axes.

It has been shown [8] that A_{n} is odd only when n is a Jacobsthal number, where the Jacobsthal numbers J_{n} are defined by

J_{n} = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3} ,

with generating function

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

Binary trees are counted by the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}, with generating function

c(x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

The reversion of the power series xc(x) is given by x(1 − x). Ternary trees are counted by the numbers T_{n} = \frac{1}{2n+1} \binom{3n}{n}, which generalize the Catalan numbers. The ternary numbers have generating function

t(x) = \frac{2}{\sqrt{3x}} sin (\frac{1}{3} sin^{−1} \sqrt{\frac{27x}{4}}) .

The reversion of the power series xt(x) is given by x(1 − xc(x)).

The Hankel transform [15] of a sequence a_{n} is the sequence h_{n} of determinants |a_{i+j}|_{0≤i,j≤n}. For instance, the Hankel transform of the Catalan numbers is given by the all 1’s sequence

1, 1, 1, 1, 1, …,

while the Hankel transform of the ternary numbers begins

1, 2, 11, 170, 7429, 920460, 323801820, 323674802088, ….

This sequence (\underline{A051255}) counts the number of cyclically symmetric transpose complement plane partitions in a (2n + 2) × (2n + 2) × (2n + 2) box.

If the sequence a_{n} has a generating function g(x), then the bivariate generating function of the Hankel matrix |a_{i+j}|_{i,j≥0} is given by

\frac{xg(x) − yg(y)}{x − y}.

In the case that a sequence a_{n} has g.f. g(x) expressible in the continued fraction form [27]

g(x) = \frac{a_{0}}{1 − α_{0}x − \frac{β_{1}x^{2}}{1 − α_{1}x − \frac{β_{2}x^{2}}{1 − α_{2}x − \frac{β_{3}x^{2}}{1 − α_{3}x − ⋯}}}}

then we have the Heilermann formula [14]

h_{n} = a_{0}^{n+1}β_{1}^{n}β_{2}^{n−1} ⋯ β_{n−1}^{2}β_{n} = a_{0}^{n+1} ∏_{k=1}^{n} β_{k}^{n+1−k}.  (1)

Note that this independent from α_{n}.

We note that α_{n} and β_{n} are in general not integers (even if both a_{n} and h_{n} are integer valued). It is clear also that a Hankel transform has an infinite number of pre-images, since we are free to assign values to the α_{n} coefficients. For instance, a sequence a_{n} and its binomial transform ∑_{k=0}^{n} \binom{n}{k} have the same Hankel transform, and the expansion of the INVERT transform of g(x) given by \frac{g(x}{1−xg(x)} and that of g(x) will have the same Hankel transform.

Letting H ( \begin{matrix}u_{1} & … & u_{k} \\ v_{1} & … & v_{k} \end{matrix} ) be the determinant of Hankel type with (i, j)-th term μ_{u_{i}+v_{j}},

and setting

Δ_{n} = H ( \begin{matrix}0 & 1 & … & n \\ 0 & 1 & … & n \end{matrix} ) , Δ′_{n} = H_{n} ( \begin{matrix}0 & 1 & … & n − 1 & n \\ 0 & 1 & … & n − 1 & n + 1 \end{matrix} ) ,

we have

α_{n} = \frac{Δ′_{n}}{Δ_{n}} − \frac{Δ′_{n−1}}{Δ_{n−1}} ,  β_{n} = \frac{Δ_{n−2}Δ_{n}}{Δ_{n−1}^{2}} .  (2)

Example 1. In this example, we re-interpret a result of [10]. The sequence that begins

1, \sqrt{3}, 5, 10\sqrt{3}, 66, 154\sqrt{3}, 1122, 2805\sqrt{3}, 21505, 55913\sqrt{3}, 442221, 1179256\sqrt{3}, 9524760, …

with generating function

g_{A}(x) = \frac{(1 − (1 − 3\sqrt{3}x)^{\frac{1}{3}} )}{\sqrt{3}x}

which has a continued fraction expression as

g_{A}(x) = \frac{1}{1 − \sqrt{3}x − \frac{2x^{2}}{1 − \frac{3\sqrt{3}}{2}x − \frac{\frac{7}{4}x^{2}}{1 − \frac{3\sqrt{3}}{2}x − \frac{\frac{12}{7}x^{2}}{1 − \frac{3\sqrt{3}}{2}x − \frac{\frac{143}{84}x^{2}}{1 − ⋯}}}}}.

has a Hankel transform that begins

1, 2, 7, 42, 429, 7436, 218348, ….

We note that the reversion of the power series

xg_{A}(x) = x\frac{(1 − (1 − 3\sqrt{3}x)^{\frac{1}{3}} )}{\sqrt{3}}

is given by

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

The above implies that the numbers 1, 2, 7, 42, … are the Hankel transform of the moments of family of monic orthogonal polynomials that satisfy

P_{n}(x) = (x − α_{n})P_{n−1} − β_{n}P_{n−2},

where the sequences α_{n} and β_{n} begin

\sqrt{3}, \frac{3\sqrt{3}}{2}, \frac{3\sqrt{3}}{2}, …,

and

2, \frac{7}{4}, \frac{12}{7}, \frac{143}{84}, …,

respectively. Since the Hankel transform depends only on the β-sequence, the sequence v_{n} with generating function

\frac{1}{1 − \frac{2x^{2}}{1 − \frac{\frac{7}{4}x^{2}}{1 − \frac{\frac{12}{7}x^{2}}{1 − \frac{\frac{143}{84}x^{2}}{1 − ⋯}}}}},

which begins

1, 0, 2, 0, \frac{15}{2}, 0, \frac{273}{8}, 0, \frac{5471}{32}, 0, …,

will have A_{n+1} as its Hankel transform. The generating function g_{A}(x) then corresponds to the following transformation of the sequence of fractions above.

• A 3\sqrt{3}-binomial transform (i.e. ∑_{k=0}^{n}(3\sqrt{3})^{n−k}v_{k})

• An invert transform with parameter \frac{\sqrt{3}}{2} (i.e g(x) → _{\frac{g(x)}{1− \frac{\sqrt{3}}{2} xg(x)}})

We now note that the sequence with generating function

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

which will have the continued fraction expression

\frac{1}{1 − \frac{x^{2}}{1 − \sqrt{3}x − \frac{2x^{2}}{1 − \frac{3\sqrt{3}}{2}x − \frac{\frac{7}{4}x^{2}}{1 − \frac{3\sqrt{3}}{2}x − \frac{\frac{12}{7}x^{2}}{1 − ⋯}}}}},

has Hankel transform

1, 1, 2, 7, 42, 429, 7436, 218348, ….

This sequence begins

1, 0, 1, \sqrt{3}, 6, 12\sqrt{3}, 80, 187\sqrt{3}, 1364, 3412\sqrt{3}, 26170, 68067\sqrt{3}, 538533, ….
△

Example 2. In this example, we use the previous example to re-interpret results of [7]. We begin by multiplying the sequence β_{n} in g_{A}(x) above by n^{2}, to get a new β-sequence that begins

2, 7, \frac{108}{7}, \frac{1400}{33}, \frac{8721}{143}, ….

We then find that that the generating function

\frac{1}{1 − \frac{2x^{2}}{1 − \frac{7x^{2}}{1 − \frac{\frac{108}{7}x^{2}}{1 − \frac{\frac{572}{21}x^{2}}{1 − ⋯}}}}}

expands to give the integer sequence μ_{n}

1, 0, 2, 0, 18, 0, 378, 0, 14562, 0, 897642, …,

which by construction has its Hankel transform equal to

A_{n+1} ∏_{k=0}^{n} k!^{2}.

The exponential generating function of this sequence is

g_{μ}(x) = \frac{3}{1 + 2 cos(\sqrt{3}x)},

and we have the moment representation

μ_{n} = ∫_{−∞}^{∞} x^{n} sinh (\frac{πx}{3\sqrt{3}}) ; sinh (\frac{πx}{\sqrt{3}}) dx.

The associated family of orthogonal polynomials is the continuous Hahn polynomials [13]

P_{n}(x) = i^{n} (\frac{2}{3})_{n} _{3}F_{2}(−n, n + 1, \frac{1}{3} + \frac{ix}{3\sqrt{3}}; \frac{2}{3}, 1; 1).

The normalized moment matrix for this family begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 9 & 0 & 1 & 0 & 0 & 0 \\ 18 & 0 & \frac{171}{7} & 0 & 1 & 0 & 0 \\ 0 & 189 & 0 & \frac{155}{3} & 0 & 1 & 0 \\ 378 & 0 & \frac{6903}{7} & 0 & \frac{1035}{11} & 0 & 1 \end{matrix} ) .

A related matrix is the exponential Riordan array

[\frac{3}{1 + 2 cos(\sqrt{3}x)}, ln (\frac{1 + \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)}{1 − \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)})] = [\frac{3}{1 + 2 cos(\sqrt{3}x)}, 2 tanh^{−1} (\frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x))] ,

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 8 & 0 & 1 & 0 & 0 & 0 \\ 18 & 0 & 20 & 0 & 1 & 0 & 0 \\ 0 & 148 & 0 & 40 & 0 & 1 & 0 \\ 378 & 0 & 658 & 0 & 70 & 0 & 1 \end{matrix} ) .

Multiplying this matrix on the right by the binomial matrix [e^{x}, x], we obtain the matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 & 0 \\ 9 & 11 & 3 & 1 & 0 & 0 & 0 \\ 39 & 44 & 26 & 4 & 1 & 0 & 0 \\ 189 & 273 & 130 & 50 & 5 & 1 & 0 \\ 1107 & 1602 & 1093 & 300 & 85 & 6 & 1 \end{matrix} ) .

By the product rule, this is the exponential Riordan array

[\frac{3}{1 + 2 cos(\sqrt{3}x)} (\frac{1 + \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)}{1 − \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)}) , ln (\frac{1 + \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)}{1 − \frac{1}{\sqrt{3}} tan (\frac{\sqrt{3}}{2}x)})] .

The sequence

1, 1, 3, 9, 189, 1107, …

is \underline{A080635}(n + 1) where \underline{A080635} counts the number of permutations on n letters without double falls and without initial falls. The generating function for the sequence 1, 1, 3, 9, … can be expressed as

\frac{d}{dx} (\frac{\sqrt{3}}{2} tan (\frac{\sqrt{3}}{2}x + \frac{π}{6} ) − \frac{1}{2}) = \frac{3}{2 (1 + cos (\sqrt{3}x + \frac{π}{3}))}.

As a continued fraction, this generating function is given by

\frac{1}{1 − x − \frac{1.2x^{2}}{1 − 2x − \frac{2.3x^{2}}{1 − 3x − \frac{3.4x^{2}}{1 − 4x − \frac{4.5x^{2}}{1 − ⋯}}}}},

and the sequence has Hankel transform \underline{A059332} which begins

1, 2, 24, 3456, 9953280, 859963392000, 3120635156889600000, …,

with general term

(n + 1)! ∏_{k=0}^{n} k!^{2}.

We finish this example by looking at the related generating function

\frac{−1}{1 − 2 cos (\sqrt{3}x)},

which expands to give the sequence that begins

1, 0, 6, 0, 198, 0, 16254, 0, 2490102, 0, 613089486, 0, 221391950598, 0, …

The generating function of this sequence may be expressed as the following continued fraction.

\frac{1}{1 − \frac{3.1.2.x^{2}}{1 − \frac{3.3.3.x^{2}}{1 − \frac{3.4.5.x^{2}}{1 − \frac{3.6.6.x^{2}}{1 − \frac{3.7.8.x^{2}}{1 − \frac{3.9.9.x^{2}}{1 − ⋯}}}}}}},

where the β-sequence begins

6, 27, 60, 108, 168, 243, 330, …

with the factorization shown, where the alternate addition of (2, 1) and (1, 2) explains the pattern. The Hankel transform of this sequence is then given by

h_{n} = 3^{\binom{n+1}{2}} ∏_{k=0}^{n} k!^{2}A_{n+1}^{(3)},

where A_{n}^{(3)} is \underline{A059477}, which counts the 3-enumeration of alternating sign matrices. It is clear then that the generating function

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

which expands to the sequence that begins

1, 0, 2, 0, 22, 0, 602, 0, 30742, 0, 2523002, 0, 303692662, …

has Hankel transform

∏_{k=0}^{n} k!^{2}A_{n+1}^{(3)}.

We have

\frac{−1}{1 − 2 cos(x)} = \frac{1}{1 − \frac{1.2.x^{2}}{1 − \frac{3.3.x^{2}}{1 − \frac{4.5.x^{2}}{1 − \frac{6.6.x^{2}}{1 − \frac{7.8.x^{2}}{1 − \frac{9.9.x^{2}}{1 − ⋯}}}}}}}.

The β-sequence in this case is

2, 9, 20, 36, 56, 81, 110, 144, …

which is \underline{A173102}, the number of partitions x + y = z with \{x, y, z\} in \{1, 2, 3, .., 3n\} and z > y ≥ x. △

In this article, we shall have occasion to use bivariate generating functions for number triangles and number squares. For instance, Pascal’s triangle (\binom{n}{k}) has bivariate generating function

\frac{1}{1 − x − xy}

while the equivalent number square (\binom{n+k}{k}) has bivariate generating function

\frac{1}{1 − x − y} .

For a number square with general term a_{i,j}, we shall call the principal minor sequence the sequence of determinants |a_{i,j}|_{0≤i,j≤n−1}.

The (centrally symmetric) Narayana triangle [2] is the number triangle with general term

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

which begins

N = ( \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 & 175 & 105 & 21 & 1 \end{matrix} ) .

It counts the number of Dyck n-paths with exactly k peaks, as well as the number of noncrossing set partitions of [n] into k blocks. Its bivariate generating function my be expressed as the continued fraction

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

Thus we have have

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

and it follows that [17]

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

The row sums of this triangle have generating function

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

which is the generating function of the shifted Catalan numbers C_{n+1}. The diagonal sums of this triangle have generating function

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

which is the generating function of the sequence that begins

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

which arises in enumerating secondary structures of RNA molecules. The corresponding square array with general term

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

which begins

N^{(s)} = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 \\ 1 & 6 & 20 & 50 & 105 & 196 & 336 \\ 1 & 10 & 50 & 175 & 490 & 1176 & 2520 \\ 1 & 15 & 105 & 490 & 1764 & 5292 & 13860 \\ 1 & 21 & 196 & 1176 & 5292 & 19404 & 60984 \\ 1 & 28 & 336 & 2520 & 13860 & 60984 & 226512 \end{matrix} ) ,

has generating function

N^{(s)}(x, y) = N (x, y/x) = \frac{1 − x − y − \sqrt{(1 − y)^{2} − 2(1 + y)x + x^{2}}}{2xy} .

These results are general. For a number triangle with generating function g(x, y), its row sums and diagonal sums have generating functions of g(x, 1) and g(x, x) respectively, while the corresponding number square has generating function g (x, \frac{y}{x}). Similarly if f(x, y) is the generating function of a number square S with general term s_{n,k}, then the corresponding number triangle will have general term s_{n−k,k} (for k ≤ n, and 0 otherwise), and generating function f(x, xy).

In the sequel, we shall see the interaction between Riordan arrays and bivariate generating functions. The fundamental result that we use is as follows. We suppose given two Riordan arrays R(x) = (g(x), f(x)) and S(y) = (u(y), v(y)) with corresponding matrices R and S, and a bivariate generating function h(x, y) that expands to give a number square (or triangle) H = (h_{i,j}). Then the bivariate power series

R(x)S(y)h(x, y) = g(x)v(y)h(f(x), v(y))

expands to give the number square (or triangle)

RHS^{T} .

Example 3. We let R = (\frac{1}{1+x}, \frac{x}{1+x}) be the inverse binomial matrix, and S = (\frac{1}{1+y}, \frac{y}{1+y}) also be the inverse binomial matrix. We let h(x, y) = N^{(s)}(x, y), the generating function of the symmetric Narayana square. We then obtain that

R(x)S(y)h(x, y) = \frac{1}{1 + x} \frac{1}{1 + y} N^{(s)} (\frac{x}{1 + x}, \frac{y}{1 + y} ) = \frac{1 − xy − \sqrt{1 − 2xy(2y + 3) − x^{2}y(3y + 4)}}{2xy(1 + x)(1 + y)}

is the generating function of the number square that begins

( \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} ) ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 3 & 6 & 10 & 15 & 21 \\ 1 & 6 & 20 & 50 & 105 & 196 \\ 1 & 10 & 50 & 175 & 490 & 1176 \\ 1 & 15 & 105 & 490 & 1764 & 5292 \\ 1 & 21 & 196 & 1176 & 5292 & 19404 \end{matrix} ) ( \begin{matrix}1 & −1 & 1 & −1 & 1 & −1 \\ 0 & 1 & −2 & 3 & −4 & 5 \\ 0 & 0 & 1 & −3 & 6 & −10 \\ 0 & 0 & 0 & 1 & −4 & 10 \\ 0 & 0 & 0 & 0 & 1 & −5 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 7 & 7 & 2 & 0 \\ 0 & 0 & 7 & 33 & 45 & 25 \\ 0 & 0 & 2 & 45 & 183 & 296 \\ 0 & 0 & 0 & 25 & 296 & 1118 \end{matrix} ) .

The diagonal sums of this new number square

1, 0, 2, 2, 7, 14, 37, 90, 233, 602, 1586, 4212, 11299, …

then have generating function (setting y = x) given by

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

which shows them to be the alternating sums of the Motzkin numbers

∑_{k=0}^{n}(−1)^{n−k}M_{k}.

This is the sequence \underline{A187306}. △

2 The Jacobsthal decomposition of Pascal’s triangle

The Jacobsthal decomposition of Pascal’s triangle [3, 4] finds expression in the statements

∑_{k=0}^{n} \binom{n}{k} = 2^{n} = J̃_{n} + J_{n} + J_{n},  (3)

J̃_{n} = ∑_{(n+k) mod 3=0} \binom{n}{k}

J_{n} = ∑_{(n+k) mod 3=1} \binom{n}{k}

J_{n} = ∑_{(n+k) mod 3=2} \binom{n}{k},

and

B = ([(n + k) mod 3 = 0]\binom{n}{k})+([(n + k) mod 3 = 1]\binom{n}{k})+([(n + k) mod 3 = 2]\binom{n}{k}) ,

where

B = (\frac{1}{1 − x}, \frac{x}{1 − x})

is the binomial matrix with (n, k)-th element \binom{n}{k}. Here, we have used the Iverson notation [P] which is 1 if P is true and 0 otherwise [11], along with the notation (g(x), f(x)) for the Riordan array whose (n, k)-th matrix element is given by [x^{n}]g(x)f(x)^{k} [22, 26]. For a matrix (A_{i,j}), we shall use the notation |A_{i,j}|_{n} to denote the determinant |A_{i,j}|_{0≤i,j≤n}. The Hankel transform of a sequence a_{n} is the sequence of determinants |a_{i+j}|_{n}. For a power series f(x) with f(0) = 0, we denote by f̄(x) or Rev(f)(x) the unique power series that satisfies f̄(f(x)) = x.

The sequence J_{n} of Jacobsthal numbers \underline{A001045} has generating function

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

and J̃_{n} is the sequence \underline{A078008} with generating function

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

Where known, we shall use the OEIS [24, 25] naming convention for integer sequences in this note.

We have

J_{n} = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3} ,

and

J̃_{n} = J_{n} + (−1)^{n}.

The following table illustrates the decomposition.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & … \\ J̃_{n} & 1 & 0 & 2 & 2 & 6 & 10 & 22 & … \\ J_{n} & 0 & 1 & 1 & 3 & 5 & 11 & 21 & … \\ J_{n} & 0 & 1 & 1 & 3 & 5 & 11 & 21 & … \\ 2^{n} & 1 & 2 & 4 & 8 & 16 & 32 & 64 & … \end{matrix}

We can see this decomposition in the following colored rendering of B.

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} ) \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 1 \\ 2 & 3 & 3 \\ 6 & 5 & 5 \\ 10 & 11 & 11 \\ . & . & . \end{matrix}

The equation (3) is equivalent to the statement that

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

We note that the triangle with general element

[(n + k) mod 3 = 0]\binom{n}{k}

is a centrally symmetric triangle that begins

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

Our previous notes on this decomposition concentrated on Pascal’s triangle. In this note, we shall be partly motivated by considering the square array version of Pascal’s triangle, namely the number square S with general element \binom{n+k}{k} which has bivariate generating function

\frac{1}{1 − x − y} .

We note that as a matrix,

S = B · B^{t},

where B is the usual lower triangular binomial matrix with general element \binom{n}{k} and bivariate generating function

\frac{1}{1 − x − xy} .

The square array S matrix begins

S = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 2 & 3 & 4 & 5 & 5 & … \\ 1 & 3 & 6 & 10 & 21 & 28 & … \\ 1 & 4 & 10 & 20 & 35 & 56 & … \\ 1 & 5 & 15 & 35 & 70 & 126 & … \\ 1 & 6 & 21 & 56 & 126 & 252 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The square matrix S is symmetric by construction. Note that if we write

S = B · I · B^{t},

where I is the identity matrix, then this suggests that matrices of the form

B · A · B^{t}

may be of interest, especially when A is also symmetric. Note that the transition from S to B is seen in the following expression

\frac{1}{1 − x − y} → \frac{1}{1 − x − xy} ,

that is, occurrences of y go to xy. This corresponds to the general term S_{n,k} going to S_{n−k,k}. We clearly have a corresponding Jacobsthal decomposition of the Pascal square array S given by

S = ([(n+2k) mod 3 = 0]\binom{n + k}{k})+([(n+2k) mod 3 = 1]\binom{n + k}{k})+([(n+2k) mod 3 = 2]\binom{n + k}{k}).

For instance, the matrix ([(n + 2k) mod 3 = 0]\binom{n+k}{k}) begins

( \begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 1 & … \\ 0 & 2 & 0 & 0 & 5 & 0 & 0 & … \\ 0 & 0 & 6 & 0 & 0 & 21 & 0 & … \\ 1 & 0 & 0 & 20 & 0 & 0 & 84 & … \\ 0 & 5 & 0 & 0 & 70 & 0 & 0 & … \\ 0 & 0 & 21 & 0 & 0 & 252 & 0 & … \\ 1 & 0 & 0 & 84 & 0 & 0 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

with diagonal sums J̃_{n} while the matrix ([(n + 2k) mod 3 = 1]\binom{n+k}{k}) begins

( \begin{matrix}0 & 0 & 1 & 0 & 0 & 1 & 0 & … \\ 1 & 0 & 0 & 4 & 0 & 0 & 7 & … \\ 0 & 3 & 0 & 0 & 15 & 0 & 0 & … \\ 0 & 0 & 10 & 0 & 0 & 56 & 0 & … \\ 1 & 0 & 0 & 35 & 0 & 0 & 210 & … \\ 0 & 6 & 0 & 0 & 126 & 0 & 0 & … \\ 0 & 0 & 28 & 0 & 0 & 462 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

with diagonal sums J_{n}. The matrix ([(n + 2k) mod 3 = 2]\binom{n+k}{k}) is the transpose of this latter matrix, again with diagonal sums J_{n}.

3 A Narayana inspired Jacobsthal decomposition

Our starting point in this section is a simple truncation of the generating function of the Narayana triangle \underline{A001263}. Thus we take the centrally symmetric version of Narayana’s triangle, which has general term

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

and whose generating function can be expressed by the continued fraction

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

We now take the simple truncation

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

This is the generating function of the centrally symmetric triangle of k-part order-consecutive partitions of n \underline{A056241} [12], which 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 & 19 & 10 & 1 & 0 & … \\ 1 & 15 & 45 & 45 & 15 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This triangle has general term

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

The corresponding square array A then has generating function

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

and general term

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

This matrix begins

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 & … \\ 1 & 6 & 19 & 45 & 90 & 161 & 266 & … \\ 1 & 10 & 45 & 141 & 357 & 784 & 1554 & … \\ 1 & 15 & 90 & 357 & 1107 & 2907 & 6765 & … \\ 1 & 21 & 161 & 784 & 2907 & 8953 & 24068 & … \\ 1 & 28 & 266 & 1554 & 6765 & 24068 & 73789 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We note that we have

|1| = 1, | \begin{matrix}1 & 1 \\ 1 & 3 \end{matrix} | = 2, | \begin{matrix}1 & 1 & 1 \\ 1 & 3 & 6 \\ 1 & 6 & 19 \end{matrix} | = 11, …,

and this principal minor sequence continues

1, 2, 11, 170, 7429, ….

We now wish to find the generating function of the matrix given by

Ã = B^{−1} · A(B^{t})^{−1}.

This g.f. is given by

f̃(x, y) = \frac{1}{(1 + x)(1 + y)}g̃ (\frac{x}{1 + x}, \frac{y}{1 + y} ) ,

corresponding to a bilateral inverse binomial transform. We obtain

f̃(x, y) = \frac{1 − xy}{1 − xy^{2} − 3xy − x^{2}y} .

The sequence corresponding to the diagonal sums of the square matrix with generating function f̃(x, y) then has generating function f̃(x, x), where

f̃(x, x) = \frac{1 − x^{2}}{1 − x^{3} − 3x^{2} − x^{3}} = \frac{1 − x}{1 − x − 2x^{2}} .

Proposition 4. The diagonal sums of the inverse binomial conjugate of the square array of k-part order-consecutive partitions of n are given by the Jacobsthal numbers J̃_{n}.

The matrix Ã begins

Ã = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 6 & 5 & 1 & 0 & 0 & … \\ 0 & 0 & 5 & 20 & 21 & 8 & 1 & … \\ 0 & 0 & 1 & 21 & 70 & 84 & 45 & … \\ 0 & 0 & 0 & 8 & 84 & 252 & 330 & … \\ 0 & 0 & 0 & 1 & 45 & 330 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We have [10]

Ã = (\binom{n + k}{2k − n}) = (\binom{n + k}{2n − k}) .

Again, the principal minor sequence begins

1, 2, 11, 170, ….

Structurally, this matrix contains two copies of the Riordan array [22, 26]

R = (\frac{1}{\sqrt{1 − 4x}}, xc(x)^{3}) ,

\underline{A159965} (with general element \binom{2n+k}{n+2k}) which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 6 & 5 & 1 & 0 & 0 & 0 & … \\ 20 & 21 & 8 & 1 & 0 & 0 & … \\ 70 & 84 & 45 & 11 & 1 & 0 & … \\ 252 & 330 & 220 & 78 & 14 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

emanating from the main diagonal which is common to both copies. Here,

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

is the generating function of the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}, \underline{A000108}.

The general element of the matrix Ã is given by [10]

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

This matrix has been studied by Gessel and Xin [10] in the context of ternary trees and alternating sign matrices (ASM’s). An immediate consequence of the fact that Ã = (\binom{n+k}{2n−k}) is the following expression for the Jacobsthal numbers J̃_{n}.

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

Thus J̃_{n} can be exhibited as the row sums of the triangle ˜ Ã with general term

˜Ã_{n,k} = \binom{n}{3k − n} = ∑_{j=0}^{n−k} \binom{k}{n − k − j}\binom{n − k}{k − j}.

The triangle ˜ Ã begins

˜Ã = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & 6 & 0 & 0 & 0 & … \\ 0 & 0 & 5 & 5 & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This is distinct from the modular triangle for J̃_{n} of Section 2. The matrix ˜ Ã is seen to have generating function

˜f̃(x, y) = f̃(x, xy) = \frac{1 − x^{2}y}{1 − x^{3}y^{2} − 3x^{2}y − x^{3}y} .

The row sums of this matrix have generating function

˜f̃(x, 1) = \frac{1 − x}{1 − x − 2x^{2}} = ∑_{n=0}^{∞} J̃_{n}x^{n}

as anticipated.

The link between the matrix Ã and the Riordan array R = (\frac{1}{\sqrt{1−4x}}, xc(x)^{3}) is given by the following.

Ã_{n+k,n} = \binom{n + k + n}{2(n + k) − n} = \binom{2n + k}{n + 2k},

and hence we have

Ã_{n+k,n} = R_{n,k}, Ã_{n,k} = R_{k,n−k}.

Proposition 5. Let Ã be the matrix with (n, k)-th term \binom{n+k}{2n−k}, with bivariate generating function

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

Let R be the Riordan array (\frac{1}{\sqrt{1−4x}}, xc(x)^{3}). Then we have

Ã_{n,k} = R_{k,n−k} if k ≤ n, Ã_{n,k} = R_{n,k−n} for k > n,

and

R_{n,k} = Ã_{n+k,n} = Ã_{n,n+k}.

We finish this section by noting that if we pre-pend the matrix A with a row 1, 0, 0, 0, … (or alternatively with a column 1, 0, 0, 0, …), to get a matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 \\ 1 & 6 & 19 & 45 & 90 & 161 & 266 \\ 1 & 10 & 45 & 141 & 357 & 784 & 1554 \\ 1 & 15 & 90 & 357 & 1107 & 2907 & 6765 \\ 1 & 21 & 161 & 784 & 2907 & 8953 & 24068 \end{matrix} )

then we obtain a matrix whose principal minor sequence begins

1, 1, 3, 26, 646, 45885, 9304650, 5382618660, ….

This is \underline{A005156}.

Similarly, the matrix with g.f.

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

that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 3 & 6 & 10 & 15 & 21 \\ 0 & 1 & 6 & 19 & 45 & 90 & 161 \\ 0 & 1 & 10 & 45 & 141 & 357 & 784 \\ 0 & 1 & 15 & 90 & 357 & 1107 & 2907 \\ 0 & 1 & 21 & 161 & 784 & 2907 & 8953 \end{matrix} )

has a principal minor sequence that begins

1, 1, 2, 11, 170, 7429, 920460, 323801820, 323674802088, ….

4 A Jacobsthal decomposition of 2^{n}

We wish to find an alternative matrix interpretation of the equation

2^{n} = J̃_{n} + J_{n} + J_{n}.

To this end, we consider the matrix A^{H} with bivariate generating function

g_{H}(x, y) = \frac{x(1 + x)}{1 − xy^{2} − 3xy − x^{2}y} .

The diagonal sums of this matrix have generating function

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

and hence they correspond to the Jacobsthal numbers J_{n}. Similarly, the matrix A^{V} with generating function

g_{V} (x, y) = \frac{y(1 + y)}{1 − xy^{2} − 3xy − x^{2}y}

has diagonal sums equal to the Jacobsthal numbers J_{n}. We thus obtain that the matrix

Ã + A^{H} + A^{V}

has diagonal sums equal to the sequence 2^{n}, thus giving us another matrix interpretation of the identity

2^{n} = J̃_{n} + J_{n} + J_{n}.

This sum matrix has generating function

f̃(x, y) + g_{H}(x, y) + g_{V} (x, y) = \frac{1 + y + y^{2} + x(1 − y) + x^{2}}{1 − xy^{2} − 3xy − x^{2}y} .

The matrix A^{H}, with general element

\binom{n + k}{2k − n + 2} = \binom{n + k}{2n − k − 2}

begins

A^{H} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 4 & 10 & 6 & 1 & 0 & 0 & … \\ 0 & 1 & 15 & 35 & 28 & 9 & 1 & … \\ 0 & 0 & 7 & 56 & 126 & 120 & 55 & … \\ 0 & 0 & 1 & 36 & 210 & 462 & 495 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Within this matrix we recognise two Riordan arrays. One is (c′(x), xc(x)^{3}), with general term \binom{2n+k+1}{n−k}, which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 10 & 6 & 1 & 0 & 0 & 0 & 0 \\ 35 & 28 & 9 & 1 & 0 & 0 & 0 \\ 126 & 120 & 55 & 12 & 1 & 0 & 0 \\ 462 & 495 & 286 & 91 & 15 & 1 & 0 \\ 1716 & 2002 & 1365 & 560 & 136 & 18 & 1 \end{matrix} ) ,

and the Riordan array

(\frac{1 − \sqrt{1 − 4x}}{2x\sqrt{1 − 4x}}, xc(x)^{3})

with general term \binom{2n+k+2}{n−k}, which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 15 & 7 & 1 & 0 & 0 & 0 & 0 \\ 56 & 36 & 10 & 1 & 0 & 0 & 0 \\ 210 & 165 & 66 & 13 & 1 & 0 & 0 \\ 792 & 715 & 364 & 105 & 16 & 1 & 0 \\ 3003 & 3003 & 1820 & 680 & 153 & 19 & 1 \end{matrix} ) .

We note that the principal minor sequence of matrix obtained by removing the top row of A^{H} begins

1, 3, 26, 646, 45885, 9304650, 5382618660, 8878734657276, ….

Similarly, the related matrix (\binom{n+k−1}{2k−n}) has a principal minor sequence that begins

1, 1, 3, 26, 646, 45885, 9304650, 5382618660, 8878734657276, ….

The matrix A^{V} is the transpose of A^{H}. This matrix has general term

\binom{n + k}{2n − k + 2} = \binom{n + k}{2k − n − 2},

and begins

( \begin{matrix}0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 4 & 1 & 0 & 0 \\ 0 & 0 & 1 & 10 & 15 & 7 & 1 \\ 0 & 0 & 0 & 6 & 35 & 56 & 36 \\ 0 & 0 & 0 & 1 & 28 & 126 & 210 \\ 0 & 0 & 0 & 0 & 9 & 120 & 462 \\ 0 & 0 & 0 & 0 & 1 & 55 & 495 \end{matrix} ) .

As with the matrix A^{H}, we obtain the above two sequences as principal minor sequences for the matrices with general terms \binom{n+k+1}{2n−k} and \binom{n+k−1}{2k−n}, respectively. It is clear that the diagonal sums of both A^{H} and A^{V} are the Jacobsthal numbers J_{n}. The sum matrix Ã + A^{H} + A^{V} is then given by the symmetric matrix that begins

Ã + A^{H} + A^{V} = ( \begin{matrix}1 & 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 4 & 4 & 1 & 0 & 0 & … \\ 1 & 4 & 8 & 15 & 16 & 7 & 1 & … \\ 0 & 4 & 15 & 32 & 57 & 64 & 37 & … \\ 0 & 1 & 16 & 57 & 126 & 219 & 256 & … \\ 0 & 0 & 7 & 64 & 219 & 492 & 847 & … \\ 0 & 0 & 1 & 37 & 256 & 847 & 1914 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This has general term

\binom{n + k}{2n − k} + \binom{n + k}{2n − k − 2} + \binom{n + k}{2n − k + 2}.

We then have

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

We find the following expressions for the Jacobsthal numbers.

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

and

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

Finally we note that we have

Ã_{n,k} = A_{n,k−1}^{H} + A_{n−1,k}^{V}.

5 A basic building block

We have

f̃(x, y) = \frac{1 − xy}{1 − xy^{2} − 3xy − x^{2}y} ,

which indicates that the matrix M with generating function

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

is a basic building block. Indeed, we have

Ã_{n,k} = M_{n,k} − M_{n−1,k−1}.

The symmetric matrix M = (M_{n,k}) begins

M = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 3 & 1 & 0 & 0 & 0 & … \\ 0 & 1 & 9 & 6 & 1 & 0 & … \\ 0 & 0 & 6 & 29 & 27 & 9 & … \\ 0 & 0 & 1 & 27 & 99 & 111 & … \\ 0 & 0 & 0 & 9 & 111 & 351 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We have

M_{n,k} = ∑_{l=0} Ã_{n−l,k−l} = ∑_{l=0}^{∞} ∑_{j=0}^{n} \binom{k − l}{n − l − j}\binom{n − l}{k − l − j}.

This follows since

\frac{1}{1 − xy^{2} − 3xy − x^{2}y} = \frac{1}{1 − xy^{2} − 3xy − x^{2}y} ∑_{l=0} x^{l}y^{l}(1 − xy) = ∑_{l=0} \frac{x^{l}y^{l}(1 − xy)}{1 − xy^{2} − 3xy − x^{2}y} .

Proposition 6. We have

M_{n,k} = ∑_{j=0} \binom{n − j}{j}\binom{n − 2j}{k − n + j}3^{2n−k−3j}.

Proof. We recall that

[x^{n}]\frac{1}{1 − ax − bx^{2}} = ∑_{j=0}^{⌊ \frac{n}{2} ⌋} \binom{n − j}{j}a^{n−2j}b^{j}.

Then we have

M_{n,k} = [x^{n}y^{k}]\frac{1}{1 − y(y + 3)x − yx^{2}}
= [y^{k}] ∑_{j=0} \binom{n − j}{j}(y(y + 3))^{n−2j}y^{j}
= [y^{k}] ∑_{j=0} \binom{n − j}{j}y^{n−j}(y + 3)^{n−2j}
= ∑_{j=0} \binom{n − j}{j}[y^{k−n+j}](y + 3)^{n−2j}
= ∑_{j=0} \binom{n − j}{j}[y^{k−n+j}] ∑_{l=0}^{n−2j} \binom{n − 2j}{l}y^{l}3^{n−2j−l}
= ∑_{j=0}^{⌊ \frac{n}{2} ⌋} \binom{n − j}{j}\binom{n − 2j}{k − n + j}3^{2n−k−3j}.

Other expressions for M_{n,k} are

M_{n,k} = ∑_{j=0}^{n} \binom{n − j}{k − n + j}\binom{2n − 2j − k}{j}3^{2n−3j−k} = ∑_{j=0}^{k} \binom{j}{k − j}\binom{2j − k}{n − j}3^{3j−n−k}.

The diagonal sums of M have generating function

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

and hence

∑_{k=0}^{n} M_{n−k,k} = ∑_{k=0}^{n}(−1)^{n−k}J_{k+1} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} J̃_{n−2k}.

This is \underline{A053088}.

6 The matrices Ã, A^{H}, A^{V} and M and their associated

Riordan arrays

We have seen that the matrix Ã can be associated with the Riordan array

(\frac{1}{\sqrt{1 − 4x}}, xc(x)^{3}) ,

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 6 & 5 & 1 & 0 & 0 & 0 & … \\ 20 & 21 & 8 & 1 & 0 & 0 & … \\ 70 & 84 & 45 & 11 & 1 & 0 & … \\ 252 & 330 & 220 & 78 & 14 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

In a similar way the matrix A^{H} which begins

A^{H} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 4 & 10 & 6 & 1 & 0 & 0 & … \\ 0 & 1 & 15 & 35 & 28 & 9 & 1 & … \\ 0 & 0 & 7 & 56 & 126 & 120 & 55 & … \\ 0 & 0 & 1 & 36 & 210 & 462 & 495 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and its transpose A^{V} can be associated with two Riordan arrays. Moving in a north-east direction from the sub-diagonal diagonal of A^{H}, we get the Riordan array

(\frac{c(x)}{\sqrt{1 − 4x}}, xc(x)^{3})

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 3 & 1 & 0 & 0 & 0 & 0 & … \\ 10 & 6 & 1 & 0 & 0 & 0 & … \\ 35 & 28 & 9 & 1 & 0 & 0 & … \\ 126 & 120 & 55 & 12 & 1 & 0 & … \\ 462 & 495 & 286 & 91 & 15 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Moving south-west, we get the Riordan array

(\frac{c(x)^{2}}{\sqrt{1 − 4x}}, xc(x)^{3})

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 4 & 1 & 0 & 0 & 0 & 0 & … \\ 15 & 7 & 1 & 0 & 0 & 0 & … \\ 56 & 36 & 10 & 1 & 0 & 0 & … \\ 210 & 165 & 66 & 13 & 1 & 0 & … \\ 792 & 715 & 364 & 105 & 16 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

It is noteworthy that these three Riordan arrays are “embedded” in the Riordan array

(\frac{1}{\sqrt{1 − 4x}}, xc(x))

with general term \binom{2n−k}{n−k} \underline{A092392} which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 6 & 3 & 1 & 0 & 0 & 0 & … \\ 20 & 10 & 4 & 1 & 0 & 0 & … \\ 70 & 35 & 15 & 5 & 1 & 0 & … \\ 252 & 126 & 56 & 21 & 6 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We can look at the above associations in a broader context [1]. Thus given any Riordan array R = (g(x), f(x)), we can associate three Riordan arrays with it in a natural way. These are

(g(x), x (\frac{f(x)}{x})^{3}) , (g(x)\frac{f(x)}{x}, x (\frac{f(x)}{x})^{3}) , and (g(x) (\frac{f(x)}{x})^{2} , x (\frac{f(x)}{x})^{3}) .

These Riordan arrays are “embedded” in the original Riordan array (g(x), f(x)) since they can be obtained by taking every third column of the original array, suitably shifted. The (n, k)-th elements of these Riordan arrays are then given by, respectively,

R_{n+2k,3k}, R_{n+2k+1,3k+1}, R_{n+2k+2,3k+2}.

Thus the Riordan array

(\frac{1}{\sqrt{1 − 4x}}, xc(x))

gives rise to the three Riordan arrays

(\frac{1}{\sqrt{1 − 4x}}, xc(x)^{3}) , (\frac{c(x)}{\sqrt{1 − 4x}}, xc(x)^{3}) , (\frac{c(x)^{2}}{\sqrt{1 − 4x}}, xc(x)^{3}) ,

with general (n, k)-th terms

\binom{2n + k}{n − k}, \binom{2n + k + 1}{n − k}, \binom{2n + k + 2}{n − k}.

Taking the (k, n − k) terms we get, respectively, matrices with the following terms

\binom{n + k}{2n − k}, \binom{n + k + 1}{2n − k + 1}, \binom{n + k + 2}{2n − k + 2}.

These are the (n, k)-th elements of the matrices

(Ã_{n,k}), (A_{n+1,k}^{V}), (A_{n+2,k}^{H}).

An alternative starting point is the Riordan array

(\frac{1}{2 − c(x)}, xc(x))

\underline{A100100} which has (n, k)-th term

\binom{2n − k − 1}{n − k}.

The three matrices that we obtain at the end of the process are then

(A_{n,k−1}^{H} + 0^{n+k}), (Ã_{n,k}), (A_{n+1,k}^{V}).

Finally, we see that the matrix M is associated with the Riordan array

(\frac{1}{(1 − x)\sqrt{1 − 4x}}, xc(x)^{3}) ,

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 3 & 1 & 0 & 0 & 0 & 0 & … \\ 9 & 6 & 1 & 0 & 0 & 0 & … \\ 29 & 27 & 9 & 1 & 0 & 0 & … \\ 99 & 111 & 54 & 12 & 1 & 0 & … \\ 351 & 441 & 274 & 90 & 15 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

7 A Jacobsthal decomposition of the Pascal square array S

In this section we shall find a Jacobsthal decomposition of the square array S = (\binom{n+k}{k}) with generating function

\frac{1}{1 − x − y} .

This is based on the following easily established result.

Proposition 7. We have the identity of generating functions

\frac{1}{1 − x − y} = \frac{1 − xy}{1 − x^{3} − 3xy − y^{3}} + \frac{x(1 + x)}{1 − x^{3} − 3xy − y^{3}} + \frac{y(1 + y)}{1 − x^{3} − 3xy − y^{3}} .

Proposition 8. The diagonal sums of the matrix with generating function \frac{1−xy}{1−x^{3}−3xy−y^{3}} are given by the Jacobsthal numbers J̃_{n}.

Proof. Setting y = x in the generating function \frac{1−xy}{1−x^{3}−3xy−y^{3}} , we obtain

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

Proposition 9. The diagonal sums of the matrix with generating function \frac{x(1+x)}{1−x^{3}−3xy−y^{3}} are given by the Jacobsthal numbers J_{n}.

Proof. Letting y = x in the generating function \frac{x(1+x)}{1−x^{3}−3xy−y^{3}} , we obtain

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

Proposition 10. The diagonal sums of the matrix with generating function \frac{y(1+y)}{1−x^{3}−3xy−y^{3}} are given by the Jacobsthal numbers J_{n}.

Proposition 11. The three matrices with respective bivariate generating functions \frac{1−xy}{1−x^{3}−3xy−y^{3}} , \frac{x(1+x)}{1−x^{3}−3xy−y^{3}} , \frac{y(1+y)}{1−x^{3}−3xy−y^{3}} provide a Jacobsthal decomposition for the Pascal square array with general element \binom{n+k}{k}, in the sense that the diagonal sums of these triangles verify the identity

2^{n} = J̃_{n} + J_{n} + J_{n},

where the diagonal sums of the Pascal square array are given by the sequence 2^{n}.

Let Â be the matrix that has generating function \frac{1−xy}{1−x^{3}−3xy−y^{3}} . Then Â begins

Â = ( \begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 1 & … \\ 0 & 2 & 0 & 0 & 5 & 0 & 0 & … \\ 0 & 0 & 6 & 0 & 0 & 21 & 0 & … \\ 1 & 0 & 0 & 20 & 0 & 0 & 84 & … \\ 0 & 5 & 0 & 0 & 70 & 0 & 0 & … \\ 0 & 0 & 21 & 0 & 0 & 252 & 0 & … \\ 1 & 0 & 0 & 84 & 0 & 0 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

with diagonal sums J̃_{n}. Let Â^{H} be the matrix that has generating function \frac{x(1+x)}{1−x^{3}−3xy−y^{3}} . Then Â^{H} begins

Â^{H} = ( \begin{matrix}0 & 1 & 1 & 0 & 1 & 1 & 0 & … \\ 0 & 0 & 3 & 3 & 0 & 6 & 6 & … \\ 0 & 0 & 0 & 9 & 9 & 0 & 27 & … \\ 0 & 1 & 1 & 0 & 29 & 29 & 0 & … \\ 0 & 0 & 6 & 6 & 0 & 99 & 99 & … \\ 0 & 0 & 0 & 27 & 27 & 0 & 351 & … \\ 0 & 1 & 1 & 0 & 111 & 111 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

with diagonal sums J_{n}. The transpose of this matrix then gives us the matrix Â^{V} with generating function \frac{y(1+y)}{1−x^{3}−3xy−y^{3}} . Thus we have

Â^{V} = ( \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & … \\ 1 & 3 & 0 & 1 & 6 & 0 & 1 & … \\ 0 & 3 & 9 & 0 & 6 & 27 & 0 & … \\ 1 & 0 & 9 & 29 & 0 & 27 & 111 & … \\ 1 & 6 & 9 & 29 & 99 & 0 & 111 & … \\ 0 & 6 & 27 & 0 & 99 & 351 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The matrix Â^{V} again has J_{n} as diagonal sums. Thus we have the following decomposition for the square array S.

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 & … \\ 1 & 4 & 10 & 20 & 35 & 56 & 84 & … \\ 1 & 5 & 15 & 35 & 70 & 126 & 210 & … \\ 1 & 6 & 30 & 56 & 126 & 252 & 462 & … \\ 1 & 7 & 28 & 84 & 210 & 462 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 2 & 3 & 3 + 1 & 5 & 6 & 6 + 1 & … \\ 1 & 3 & 6 & 9 + 1 & 9 + 6 & 21 & 27 + 1 & … \\ 1 & 1 + 3 & 1 + 9 & 20 & 29 + 6 & 29 + 27 & 84 & … \\ 1 & 5 & 6 + 9 & 6 + 29 & 70 & 99 + 27 & 99 + 111 & … \\ 1 & 6 & 21 + 9 & 27 + 29 & 27 + 99 & 252 & 351 + 111 & … \\ 1 & 1 + 6 & 1 + 27 & 84 & 111 + 99 & 111 + 351 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

As before, we have a basic building block, namely the matrix M̂ that has generating function

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

This matrix begins

M̂ = ( \begin{matrix}1 & 0 & 0 & 1 & 0 & 0 & 1 & … \\ 0 & 3 & 0 & 0 & 6 & 0 & 0 & … \\ 0 & 0 & 9 & 0 & 0 & 27 & 0 & … \\ 1 & 0 & 0 & 29 & 0 & 0 & 111 & … \\ 0 & 6 & 0 & 0 & 99 & 0 & 0 & … \\ 0 & 0 & 27 & 0 & 0 & 351 & 0 & … \\ 1 & 0 & 0 & 111 & 0 & 0 & 1275 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The principal diagonal elements form the sequence \underline{A006134} with general term ∑_{k=0}^{n} \binom{2k}{k}. The diagonal sums yield the sequence \underline{A053088} with generating function

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

We now calculate a closed form expression for the term M̂_{n,k}. We have

M̂_{n,k} = [x^{n}y^{k}]\frac{1}{1 − x^{3} − 3xy − y^{3}} .

Thus

M̂_{n,k} = \frac{1}{1 − (x^{3} + 3xy + y^{3})}
= [x^{n}y^{k}] ∑_{i=0}^{∞}(x^{3} + y(3x + y^{2}))^{i}
= [x^{n}y^{k}] ∑_{i=0} ∑_{j=0} \binom{i}{j}x^{3j}y^{i−j}(3x + y^{2})^{i−j}
= [x^{n}y^{k}] ∑_{i=0} ∑_{j=0} \binom{i}{j}x^{3j}y^{i−j}\binom{i − j}{l}y^{2l}(3x)^{i−j−l}
= [x^{n}y^{k}] ∑_{i=0} ∑_{j=0} \binom{i}{j}\binom{i − j}{l}3^{i−j−l}y^{i−j+2l}x^{i+2j−l}
= [y^{k}] ∑_{i=0} ∑_{j=0} \binom{i}{j}\binom{i − j}{i + 2j − n}3^{n−3j}y^{3i+3j−2n}

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

As noted, we have

M̂_{n,n} = ∑_{k=0}^{n} \binom{2k}{k} = ∑_{k=0}^{⌊ \frac{n}{3} ⌋} \binom{n − k}{k}\binom{n − 2k}{k}3^{n−3k},

which is \underline{A006134}. The Hankel transform of this sequence is given by

[x^{n}]\frac{1 − 2x}{1 − 2x + 4x^{2}} ,

which is \underline{A120580}. The Hankel transform of the sequence M̂_{n+3,n} is of some note. The sequence M̂_{n+3,n} begins

1, 6, 27, 111, 441, 1728, 6733, 26181, 101763, …,

and it has a Hankel transform h_{n} that begins

1, −9, −9, −9, 90, 25, 25, −315, −49, −49, 756, ….

The generating function of this sequence can be conjectured to be given by

f_{1}(x^{3}) + xf_{2}(x^{3}) + x^{2}f_{3}(x^{3}),

where

f_{1}(x) = \frac{1 − 6x + x^{2}}{(1 + x)^{3}} , f_{2}(x) = −\frac{9f_{1}(x)}{(1 + x)}, f_{3}(x) = \frac{f_{1}(x) − 1}{x}.

Thus we can conjecture that

h_{n} = [x^{n}]\frac{1 − 9x − 9x^{2} − 5x^{3} + 54x^{4} − 11x^{5} − 5x^{6} − 9x^{7} − 3x^{8} + x^{9} + x^{11}}{(1 + x^{3})^{4}} .

8 Another Jacobsthal decomposition of Pascal’s triangle

The Jacobsthal decomposition of S provided by the identity

\frac{1}{1 − x − y} = \frac{1 − xy}{1 − x^{3} − 3xy − y^{3}} + \frac{x(1 + x)}{1 − x^{3} − 3xy − y^{3}} + \frac{y(1 + y)}{1 − x^{3} − 3xy − y^{3}}

can be translated into a statement about a Jacobsthal decomposition of B by using the transformation x → xy. Thus we get

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

This decomposition takes the matrix form

B = (M̂_{n−k,k} − M̂_{n−k−1,k−1}) + (M̂_{n−k−1,k} + M̂_{n−k−2,k}) + (M̂_{n−k,k−1} + M̂_{n−2,k−2}).

We have the following proposition.

Proposition 12. The Jacobsthal decomposition component ([(n + k) mod 3 = 0]\binom{n}{k}) has generating function

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

and general element

([(n + k) mod 3 = 0]\binom{n}{k}) = M̂_{n−k,k} − M̂_{n−k−1,k−1}.

The two components (M̂_{n−k−1,k} + M̂_{n−k−2,k}) and (M̂_{n−k,k−1} + M̂_{n−2,k−2}) corresponding to \frac{x(1+x)}{1−x^{3}−3x^{2}y−x^{3}y^{3}} and \frac{xy(1+xy)}{1−x^{3}−3x^{2}y−x^{3}y^{3}} respectively are distinct from the J_{n} components of the modular decomposition of Section 2. They begin

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

and

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

respectively.

We can visualize this Jacobsthal decomposition as follows.

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 & 3 + 1 & 6 & 1 + 3 & 1 & 0 & … \\ 1 & 5 & 9 + 1 & 1 + 9 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 1 \\ 2 & 3 & 3 \\ 6 & 5 & 5 \\ 10 & 11 & 11 \\ . & . & . \end{matrix}

9 Jacobsthal decompositions, ternary trees and ASMs

A significant result of the paper [10] by Gessel and Xin is that the sequence of n×n principal minors of the Jacobsthal decomposition matrix Ã is equal to the Hankel transform of the ternary numbers \frac{1}{2n+1} \binom{3n}{n}. This Hankel transform begins

1, 2, 11, 170, 7429, 920460, 323801820, …

and represents the number of cyclically symmetric transpose complement plane partitions whose Ferrers diagrams fit in an (n + 1) × (n + 1) × (n + 1) box \underline{A051255} [6]. The method of proof consists of interpreting an appropriate sequence of elementary row and column operations algebraically on generating functions, in such a way as to show the equivalence of the respective determinants. In fact, we can express the relevant methods in terms of Riordan arrays as follows.

Proposition 13. Let

D(x, y) = ∑_{i,j=0}^{∞} d_{i,j}x^{i}y^{j}

be a bivariate generating function. Let [D(x, y)]_{n} be the determinant of the n × n matrix

(d_{i,j})_{0≤i,j≤n−1}.

Finally, let R = (g, f) and S = (u, v) be proper Riordan arrays. Then we have the following equality of determinants.

[D(x, y)]_{n} = [R(x)S(y)D(x, y)]_{n}.

Proof. By the FTRA, we have

[R(x)S(y)D(x, y)]_{n} = [g(x)u(y)D(f(x), v(y))]_{n}.

By a combination of the Product Rule and the Composition Rule [10], the result now follows.

Corollary 14. Let f(x) = xg(x). Then

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [\frac{x − y}{f̄(x) − f̄(y)}]_{n} .

Proof. This follows since

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [(1, f̄(x))(1, f̄(y))\frac{f(x) − f(y)}{x − y}]_{n} .

Example 15. The Hankel transform of the Catalan numbers C_{n} is the all 1’s sequence. This follows since if f(x) = xc(x), then f̄(x) = x(1 − x). Hence

[\frac{xc(x) − yc(y)}{x − y}]_{n} = [\frac{x − y}{x(1 − x) − y(1 − y)}]_{n} = [\frac{1}{1 − x − y} ]_{n} = [\binom{n + k}{k}]_{n} = 1.

△

Corollary 16. Let g(x) = 1 + f(x) where f(0) = 0. Then

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [\frac{f̄(x)(1 + x) − f̄(y)(1 + y)}{f̄(x) − f̄(y)}]_{n} .

Proof. We have

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [(1, f̄(x))(1, f̄(y))\frac{xg(x) − yg(y)}{x − y}]_{n} ,

and the result now follows by the FTRA.

This result is useful when f̄(x) is an easier function to deal with than f(x).

Example 17. The Hankel transform of the sequence with g.f. 1 + xc(x) is 1 − n. The sequence that begins

1, 1, 1, 2, 5, 14, 42, 132, 429, …

has generating function g(x) = 1 + xc(x). Here, f(x) = xc(x) with f̄(x) = x(1 − x). Hence

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [\frac{x(1 − x)(1 + x) − y(1 − y)(1 + y)}{x(1 + x) − y(1 + y)}]_{n} = [\frac{x^{2} + xy + y^{2} − 1}{x + y − 1}]_{n} .

Thus we are looking at determinants of the form

| \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 3 & 6 & 10 & 15 & 21 \\ 0 & 1 & 4 & 10 & 20 & 35 & 56 \\ 0 & 1 & 5 & 15 & 35 & 70 & 126 \\ 0 & 1 & 6 & 21 & 56 & 126 & 252 \end{matrix} | .

These determinants evaluate to give the sequence

1, 0, −1, −2, −3, −4, −5, −6, ….

Now the expression \frac{xg(x)−yg(y)}{x−y} in this case is the generating function for the Hankel matrix of the sequence 1, 1, 1, 2, 5, 14, 42, . . .. We conclude that this sequence has Hankel transform 1 − n. △

This leads us to inspect other sequences of principal minors related to our Jacobsthal decomposition matrices for combinatorial significance.

The following sequences are relevant

\begin{matrix}Annnnnn/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\ \underline{A005130} & 1 & 1 & 2 & 7 & 42 & 429 & 7436 & 218348 & … \\ \underline{A005156} & 1 & 1 & 3 & 26 & 646 & 45885 & 9304650 & 5382618660 & … \\ \underline{A005161} & 1 & 1 & 1 & 2 & 6 & 33 & 286 & 4420 & … \\ \underline{A051255} & 1 & 1 & 2 & 11 & 170 & 7429 & 920460 & 323801820 & … \\ \underline{A059475} & 1 & 2 & 10 & 140 & 5544 & 622908 & 198846076 & 180473355920 & … \\ \underline{A059489} & 1 & 5 & 66 & 2431 & 252586 & 74327145 & 62062015500 & 147198472495020 & … \end{matrix}

where we have

Annnnnn Description
\underline{A005130} Robbin’s numbers: the number of n × n alternating sign matrices (ASM’s)
\underline{A005156} Number of 2n × 2n off-diagonally symmetric alternating sign matrices
\underline{A005161} Alternating sign (2n + 1) × (2n + 1) matrices symmetric with respect to both axes
\underline{A051255} Cyclically symmetric transpose complement plane partitions in a 2n × 2n × 2n box
\underline{A059475} Number of 2n × 2n half-turn symmetric alternating-sign matrices (HTSASM’s).
\underline{A059489} Expansion of generating function A_{UU}^{2}(4n; 1, 1, 1)

We then find the following relationships between the above combinatorially significant sequences and the indicated Jacobsthal related determinant sequences.

Annnnnn  Determinant sequence
\underline{A005130}^{2}(n)  |A_{i−2,j}^{V} + A_{i,j−1}^{H}|_{n}
\underline{A005156}(n)  |Ã_{i,j} − Ã_{i−1,j−1}|_{n}, |A_{n,k−1}^{H} + 0^{n+k}|_{n}
\underline{A005156}(n + 1) |A_{i+1,j}^{H}|_{n}, |A_{i,j+1}^{V}|_{n}, |A_{i+1,j}^{H} − A_{i−1,k}^{H}|_{n}, |A_{i+2,j}^{H} − A_{i+1,j−1}^{H}|_{n}
\underline{A005161}(n)  |\binom{i+j−1}{2i−j} + Ã_{i−1,j−1}|_{n}
\underline{A005161}^{2}(n + 1) |Ã_{i,j−1} − Ã_{i−1,j}|_{n}, |Ã_{i−1,j} − Ã_{i,j−1}|_{n}
\underline{A051255}(n + 1) |Ã_{i,j}|_{n} = |\binom{i+j}{2j−i}|_{n}
\underline{A059489}  |2Ã_{i,j} + Ã_{i−1,j−1} − 0^{i+j}|_{n}

For instance, the determinants |A_{i−2,j}^{V} + A_{i,j−1}^{H}|_{n} form the principal minor sequence of the matrix with general term

\binom{n + k − 2}{2n − k − 2} + \binom{n + k − 1}{2k − n}

and generating function

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

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 4 & 1 & 0 & 0 & 0 \\ 0 & 0 & 7 & 14 & 7 & 1 & 0 \\ 0 & 0 & 2 & 25 & 50 & 35 & 10 \\ 0 & 0 & 0 & 13 & 91 & 182 & 156 \\ 0 & 0 & 0 & 2 & 64 & 336 & 672 \end{matrix} ) .

This principal minor sequence begins

1, 1, 4, 49, 1764, 184041, 55294096, …,

which is

1^{2}, 1^{2}, 7^{2}, 42^{2}, 429^{2}, 7436^{2}, …

where the number of ASM’s is counted by

1, 1, 7, 42, 429, 7436, ….

We note that the diagonal sums of the above array are given by the sequence

1, 1, 1, 2, 4, 8, 16, 32, …,

with generating function \frac{1−x−x^{2}}{1−2x}. It is interesting to note that the above matrix contains a copy of the Riordan array

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

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 4 & 1 & 0 & 0 & 0 & 0 \\ 7 & 14 & 7 & 1 & 0 & 0 & 0 \\ 25 & 50 & 35 & 10 & 1 & 0 & 0 \\ 91 & 182 & 156 & 65 & 13 & 1 & 0 \\ 336 & 672 & 660 & 352 & 104 & 16 & 1 \end{matrix} ) .

We recall that the Pascal-like square array A has general term

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

and generating function

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

Since

A = B · Ã · B^{t},

where B and all its principal n × n minors are 1, the principal minor sequence |A_{i,j}|_{n} of A is also equal to the Hankel transform of the ternary numbers \frac{1}{2n+1} \binom{3n}{n}. We now look at the determinant sequences obtained by shifting the array. Thus we draw up a table of the sequences

a_{n,k} = |A_{i,j+k}|_{n}.

We obtain

\begin{matrix}a_{n,0} & 1, 2, 11, 170, 7429, 920460, 323801820, 323674802088, … \\ a_{n,1} & 1, 3, 26, 646, 45885, 9304650, 5382618660, 8878734657276, … \\ a_{n,2} & 1, 4, 50, 1862, 202860, 64080720, 58392132084, 152999330069300, … \\ a_{n,3} & 1, 5, 85, 4508, 720360, 340695828, 471950744980, 1902127155119620, … \\ a_{n,4} & 1, 6, 133, 9660, 2184570, 1497234156, 3059986601386, 18453777416486958, … \\ a_{n,5} & 1, 7, 196, 18900, 5874066, 5676110726, 16681862439814, 146965218343914152, …, \end{matrix}

where the first two sequences are \underline{A051255}(n + 1) and \underline{A005156}(n + 1) respectively. We note that these sequences occur in [21], as an aerated table

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 11 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 26 & 0 & 5 & 0 & 1 & 0 & 0 & 0 \\ 170 & 0 & 50 & 0 & 6 & 0 & 1 & 0 & 0 \\ 0 & 646 & 0 & 85 & 0 & 7 & 0 & 1 & 0 \\ 7429 & 0 & 1862 & 0 & 133 & 0 & 8 & 0 & 1 \end{matrix} ) ,

related to the “raise and peel” model of a one-dimensional fluctuating interface.

A similar array may be obtained by considering the square array associated to the matrix (A_{n,k−1}^{H} + 0^{n+k}). This matrix, with general element

A_{n,k−1}^{H} + 0^{n+k} = \binom{n + k − 1}{2k − n},

has generating function given by

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

so that the generating function of the corresponding square array of numbers is given by

\frac{1}{(1 − x)(1 − y)}w (\frac{x}{1 − x}, \frac{y}{1 − y} ) ,

or

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

This array begins

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\ 1 & 4 & 10 & 20 & 35 & 56 & 84 & … \\ 1 & 7 & 26 & 71 & 161 & 322 & 588 & … \\ 1 & 11 & 56 & 197 & 554 & 1338 & 2892 & … \\ 1 & 16 & 106 & 463 & 1570 & 4477 & 11242 & … \\ 1 & 22 & 183 & 967 & 3874 & 12827 & 36895 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and it has its general (n, k)-th element given

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

This array is not symmetric, so that it and its transpose produce two different arrays of determinants corresponding to the shifted arrays. For the above array, we obtain the array of determinant sequences that follows.

\begin{matrix}a_{n,0}^{H} & 1, 1, 3, 26, 646, 45885, 9304650, … \\ a_{n,1}^{H} & 1, 1, 4, 50, 1862, 202860, 64080720, … \\ a_{n,2}^{H} & 1, 1, 5, 85, 4508, 720360, 340695828, … \\ a_{n,3}^{H} & 1, 1, 6, 133, 9660, 2184570, 1497234156, … \\ a_{n,4}^{H} & 1, 1, 7, 196, 18900, 5874066, 5676110726, … \\ a_{n,5}^{H} & 1, 1, 8, 276, 34452, 14358828, 19109017928, …, \end{matrix}

while the transpose of the square array yields the following array of determinant sequences

\begin{matrix}a_{n,0}^{H,t} & 1, 1, 3, 26, 646, 45885, 9304650, 5382618660, … \\ a_{n,1}^{H,t} & 1, 2, 11, 170, 7429, 920460, 323801820, 323674802088, … \\ a_{n,2}^{H,t} & 1, 3, 26, 646, 45885, 9304650, 5382618660, 8878734657276, … \\ a_{n,3}^{H,t} & 1, 4, 50, 1862, 202860, 64080720, 58392132084, 152999330069300, … \\ a_{n,4}^{H,t} & 1, 5, 85, 4508, 720360, 340695828, 471950744980, 1902127155119620, … \\ a_{n,5}^{H,t} & 1, 6, 133, 9660, 2184570, 1497234156, 3059986601386, 18453777416486958, … \\ a_{n,6}^{H,t} & 1, 7, 196, 18900, 5874066, 5676110726, 16681862439814, 146965218343914152, …, \end{matrix} .

There is another sequence besides \frac{1}{2n+1} \binom{3n}{n} that is closely related, via its Hankel transform and that of correlative sequences, to ASM’s. To introduce this sequence w_{n}, we look at two Riordan arrays. They are

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

and

(1, x(1 − x^{2}))^{−1}.

The sequence we wish to study has generating function given by

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

Now

(1, x(1 − x^{2}))^{−1} = (1, \frac{2}{\sqrt{3}} sin (\frac{1}{3} sin^{−1} (\frac{3\sqrt{3}x}{2}))) ,

and hence we have

g(x) = \frac{1}{1 − \frac{2}{\sqrt{3}} sin (\frac{1}{3} sin^{−1} (\frac{3\sqrt{3}x}{2}))}.

Note that \frac{2}{\sqrt{3}} sin (\frac{1}{3} sin^{−1} (\frac{3\sqrt{3}x}{2})) is the g.f. of the aerated ternary numbers

0, 1, 0, 1, 0, 3, 0, 12, 0, 55, 0, 273, 0, ….

We have

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

The sequence w_{n} or \underline{A047749} starts

1, 1, 1, 2, 3, 7, 12, 30, 55, 143, 273, …

The g.f. of w_{n} is equal to

g(x) = 1 + Rev\frac{x(1 + 2x)}{(1 + x)^{3}},

where the sequence with g.f. Rev\frac{x(1+2x)}{(1+x)^{3}} begins

0, 1, 1, 2, 3, 7, 12, 30, 55, 143, 273, ….

Now the Hankel transform h_{n} of w_{n} begins

1, 0, −1, 0, 9, 0, −676, 0, 417316, 0, −2105433225, …

so that \sqrt{|h_{2n}|} is given by

1, 1, 3, 26, 646, 45885, 9304650, …, or \underline{A005156}. The Hankel transform of t_{n+1} is given by

1, 1, 2, 6, 33, 286, 4420, 109820, 4799134, …,

or \underline{A005161}.

We can now apply the process of Gessel and Xin to find a square array whose determinant sequence is equal to the Hankel transform of w_{n}.

Substituting into the Hankel expression

\frac{xg(x) − yg(y)}{x − y},

we get

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

which simplifies to

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

Dividing through by (1 + x)(1 + y), we obtain

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

Now taking a bilateral binomial transform of this generating function, we obtain

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

This generates the symmetric square array that begins

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & … \\ 1 & 2 & 3 & 5 & 6 & 9 & 10 & … \\ 1 & 2 & 5 & 7 & 13 & 16 & 26 & … \\ 1 & 3 & 6 & 13 & 19 & 35 & 45 & … \\ 1 & 3 & 9 & 16 & 35 & 51 & 96 & … \\ 1 & 4 & 10 & 26 & 45 & 96 & 141 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We note that the main diagonal is given by the central trinomial coefficients \underline{A002426}. The triangle version of this square array is \underline{A169623} [20]. We now calculate the shifted determinant sequences for this array. These begin

\begin{matrix}d_{n,0} & 1, 0, −1, 0, 9, 0, −676, … \\ d_{n,1} & 1, 1, 2, 6, 33, 286, 4420, … \\ d_{n,2} & 1, 0, −2, 0, 44, 0, −8500, … \\ d_{n,3} & 1, 1, 3, 12, 104, 1300, 32300, … \\ d_{n,4} & 1, 0, −3, 0, 130, 0, −54910, … \\ d_{n,5} & 1, 1, 4, 20, 250, 4250, 158270, … \\ d_{n,6} & 1, 0, −4, 0, 300, 0, −247646, … \end{matrix}

We now notice that there is a close relationship between this array and that of the determinant sequences a_{n,k}^{H,t}. Dropping the superscript H, t for legibility, we can conjecture that for r ≥ 1, we have

d_{n,2r−1} = a_{\frac{n}{2} ,r}a_{\frac{n}{2} −1,r+1} \frac{1 + (−1)^{n}}{2} + a_{\frac{n−1}{2} ,r}a_{\frac{n−1}{2} ,r+1} \frac{1 − (−1)^{n}}{2} ,

and for r ≥ 0, we have

d_{n,2r} = a_{\frac{n}{2} ,r}a_{\frac{n}{2} −1,r+2}(−1)^{\frac{n}{2}} \frac{1 + (−1)^{n}}{2} .

We close this section by noting that the above number square is one of a one-parameter family of symmetric number squares that also contains the Pascal number square. This family is given by the generating function

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

The above number square is given by r = 1, while for r = 2 we obtain Pascal’s square \binom{n+k}{k}, since

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

The square for r = 3 is given by \underline{A026374} when considered as a number square, while that for r = 0 is \underline{A051159}.

Example 18. We reprise Example 1 of the Introduction, based on Section 5 of [10]. We use Riordan arrays as before to achieve our result. In this case, the appearance of the quadratic

1 − \sqrt{3}x + x^{2}

leads us to use two Riordan arrays with coefficients over the complex numbers. Thus we let

g(x) = \frac{(1 − (1 − 3\sqrt{3}x)^{\frac{1}{3}} )}{\sqrt{3}x}.

We recall that the reversion of xg(x) is given by x(1 − \sqrt{3}x + x^{2}). We therefore have

[\frac{xg(x) − yg(y)}{x − y}]_{n} = [(1, x(1 − \sqrt{3}x + x^{2})) . (1, y(1 − \sqrt{3}y + y^{2})) \frac{xg(x) − yg(y)}{x − y}]_{n}
= [\frac{x − y}{x(1 − \sqrt{3}x + x^{2}) − y(1 − \sqrt{3}y + y^{2})}]_{n} .

The generating function

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

expands to give a matrix that begins

( \begin{matrix}1 & \sqrt{3} & 2 & \sqrt{3} & 1 & 0 & −1 \\ \sqrt{3} & 5 & 5\sqrt{3} & 11 & 6\sqrt{3} & 6 & −\sqrt{3} \\ 2 & 5\sqrt{3} & 21 & 21\sqrt{3} & 48 & 27\sqrt{3} & 25 \\ \sqrt{3} & 11 & 21\sqrt{3} & 83 & 83\sqrt{3} & 193 & 109\sqrt{3} \\ 1 & 6\sqrt{3} & 48 & 83\sqrt{3} & 319 & 319\sqrt{3} & 747 \\ 0 & 6 & 27\sqrt{3} & 193 & 319\sqrt{3} & 1209 & 1209\sqrt{3} \\ −1 & −\sqrt{3} & 25 & 109\sqrt{3} & 747 & 1209\sqrt{3} & 4551 \end{matrix} ) .

We must now operate on this to get a form that is more familiar. Thus we form the generating function

(\frac{1}{(1 + ωx)^{2}} , \frac{−ix}{1 + ωx}) . (\frac{1}{(1 + ω^{2}y)^{2}} , \frac{iy}{1 + ω^{2}y} ) .f(x, y) = \frac{1}{(1 + ωx)^{2}} \frac{1}{(1 + ω^{2}y)^{2}} f (\frac{−ix}{1 + ωx}, \frac{iy}{1 + ω^{2}y} )
= \frac{1}{(1 − x − y)(1 − xy)}.

This new generating function g(x, y) produces the matrix that begins

( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 9 & 14 & 20 & 27 & 35 \\ 1 & 5 & 14 & 29 & 49 & 76 & 111 \\ 1 & 6 & 20 & 49 & 99 & 175 & 286 \\ 1 & 7 & 27 & 76 & 175 & 351 & 637 \\ 1 & 8 & 35 & 111 & 286 & 637 & 1275 \end{matrix} ) ,

with general element

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

Note that this matrix has diagonal sums with g.f.

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

which expands to the partial sums of the Jacobsthal numbers

∑_{k+0}^{n} J_{k+1}.

In order to transform this into a known matrix, with known principal minor sequence, we form the generating function

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

to obtain the generating function of the matrix

(\binom{n + k}{n − 1} + δ_{n,k}) ,

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 1 & 1 & 1 & 1 \\ 2 & 3 & 5 & 5 & 6 & 7 & 8 \\ 3 & 6 & 10 & 16 & 21 & 28 & 36 \\ 4 & 10 & 20 & 35 & 57 & 84 & 120 \\ 5 & 15 & 35 & 70 & 126 & 211 & 330 \\ 6 & 21 & 56 & 126 & 252 & 462 & 793 \end{matrix} ) .

Now it is known that the principal minor sequence of this matrix is A_{n} [6]. The diagonal sums d_{n} \underline{A051049} of this matrix have generating function

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

and they satisfy

\frac{d_{n+1} − d_{n}}{3} = J_{n}.

△

We close this section by finding a sequence with Hankel transform \underline{A005156}, or

1, 1, 3, 26, 646, ….

For this, we start with the sequence b_{n} = \frac{1}{n+1} \binom{3n+1}{n} \underline{A006013} that has Hankel transform

1, 3, 26, 646, ….

The sequence b_{n} has a generating function that can be expressed as a continued fraction b(x) as follows.

b(x) = \frac{1}{1 − 2x − \frac{3x^{2}}{1 − \frac{10}{3}x − \frac{\frac{26}{9}x^{2}}{1 − \frac{131}{92}x − \frac{\frac{969}{338}x^{2}}{1 − \frac{744}{221}x − \frac{\frac{282}{119}x^{2}}{1 − ⋯}}}}},

where

b(x) = \frac{4}{3x} sin (\frac{1}{3} sin^{−1} (\sqrt{\frac{27x}{4}}))^{2} .

Then the sequence with g.f. given by

b(x) = \frac{1}{1 − \frac{x^{2}}{1 − 2x − \frac{3x^{2}}{1 − \frac{10}{3}x − \frac{\frac{26}{9}x^{2}}{1 − \frac{131}{92}x − \frac{\frac{969}{338}x^{2}}{1 − \frac{744}{221}x − \frac{\frac{282}{119}x^{2}}{1 − ⋯}}}}}},

or

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

will then have a Hankel transform beginning

1, 1, 3, 26, 646, ….

This is the sequence d_{n} with g.f.

d(x) = \frac{3}{3 − 2x + 2x cos (\frac{1}{3} cos^{−1} (\frac{2−27x}{2}))}.

This sequence is given by the diagonal sums of the Riordan array

(1, x(1 − x)^{2})^{−1}.

It is given by \underline{A109972}. We have d_{0} = 1 and for n > 0,

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

The Riordan array (1, x(1 − x)^{2})^{−1} begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 7 & 4 & 1 & 0 & 0 & 0 \\ 0 & 30 & 18 & 6 & 1 & 0 & 0 \\ 0 & 143 & 88 & 33 & 8 & 1 & 0 \\ 0 & 728 & 455 & 182 & 52 & 10 & 1 \end{matrix} ) ,

and is equal to

(1, xb(x)).

10 Generalizations

It is interesting to investigate to what extent the above results are generalizable. There are a number of ways to approach this, some of which we indicate in the following examples. A first approach might be to look at the generating function

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

and to see what suitable variants of this yield.

Example 19. As an example we look at the generating function

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

which generates a matrix that begins

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

The sequence of principal minors for this matrix begins

1, 0, −1, −2, −7, −10, 212, 3136, 62284, 1084902, ….

The associated Riordan array is

(\frac{1}{1 − \frac{2x^{3}}{(1−x)^{2}} c (\frac{x^{3}}{(1−x)^{2}} )}, \frac{x}{1 − x}c (\frac{x^{3}}{(1 − x)^{2}} )) ,

or

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

This Riordan array begins

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

The generating function f(x) has a continued fraction expansion given by

\frac{x}{1 − x − \frac{x^{3}}{1 − x − \frac{x^{3}}{1 − x − \frac{x^{3}}{1 − ⋯}}}},

and expands to a sequence \underline{A023431} that counts peakless Motzkin paths of length n with no double rises. The generating function g(x) expands to give the sequence that begins

1, 0, 0, 2, 4, 6, 14, 34, 72, 154, 346, 774, …

with Hankel transform \underline{A120580} that begins

1, 0, −4, −8, 0, 32, 64, 0, −256, −512, 0, ….

Example 20. The matrix generated by

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

begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 2 & 3 & 1 & 0 & 0 & … \\ 0 & 0 & 3 & 6 & 8 & 5 & 1 & … \\ 0 & 0 & 1 & 8 & 18 & 23 & 7 & … \\ 0 & 0 & 0 & 5 & 23 & 52 & 69 & … \\ 0 & 0 & 0 & 1 & 18 & 69 & 150 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and is associated with the Riordan array

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

Here, the second member f(x) is the generating function of \underline{A091561} (see also \underline{A152225}, \underline{A025265} and \underline{A025247}), which counts Dyck paths of semi-length n with no peaks at height 0 mod 3 and no valleys at height 2 mod 3. The first member g(x) expands to give a sequence that begins

1, 2, 4, 10, 28, 80, 230, 668, 1960, 5796, …,

which has Hankel transform \underline{A120580} that begins

1, 0, −4, −8, 0, 32, 64, 0, −256, −512, 0, ….

Similarly the matrix generated by

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

begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 4 & 4 & 1 & 0 & 0 & … \\ 0 & 0 & 4 & 10 & 12 & 6 & 1 & … \\ 0 & 0 & 1 & 12 & 28 & 35 & 24 & … \\ 0 & 0 & 0 & 6 & 35 & 80 & 104 & … \\ 0 & 0 & 0 & 1 & 24 & 104 & 230 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and is associated with the Riordan array

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

Example 21. The matrix with generating function

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

begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & 3 & 0 & 1 & 0 & 1 & … \\ 0 & 1 & 0 & 3 & 0 & 6 & 0 & … \\ 0 & 0 & 1 & 0 & 11 & 0 & 6 & … \\ 0 & 0 & 0 & 6 & 0 & 11 & 0 & … \\ 0 & 0 & 1 & 0 & 6 & 0 & 45 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

where the diagonals are the doubles of the sequences

1, 3, 11, 45, 195, 873, …, with e.g.f e^{3x}I_{0}(2x),
0, 1, 6, 30, 144, 685, …, with e.g.f e^{3x}I_{1}(2x),
0, 0, 1, 9, 58, 330, …, with e.g.f e^{3x}I_{2}(2x), …

Example 22. We could also generalize the matrix Ã = (\binom{n+k}{2n−k}) to the matrix (\binom{n+k}{3n−2k}) which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 6 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & 1 & 20 & 7 & 0 & 0 & … \\ 0 & 0 & 0 & 7 & 70 & 36 & 1 & … \\ 0 & 0 & 0 & 0 & 36 & 252 & 165 & … \\ 0 & 0 & 0 & 0 & 1 & 165 & 924 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This has a principal minor sequence that begins

1, 2, 12, 238, 16072, 3741696, 3022534368, 8503710205536, ….

We do not know of a combinatorial interpretation for this sequence. The Riordan array associated with the matrix (\binom{n+k}{3n−2k}) is

(\frac{1}{\sqrt{1 − 4x}}, xc(x)^{5}) .

Example 23. A combinatorially significant example is given by the matrix with bivariate generating function

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

This matrix Ã begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 2 & 2 & 1 & 0 & 0 & … \\ 0 & 0 & 2 & 5 & 5 & 3 & 1 & … \\ 0 & 0 & 1 & 5 & 11 & 13 & 9 & … \\ 0 & 0 & 0 & 3 & 13 & 26 & 32 & … \\ 0 & 0 & 0 & 1 & 9 & 32 & 63 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

It is associated with the Riordan array

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

which begins

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

In this case g(x) is the g.f. of \underline{A051286}, the Whitney numbers of level n of the lattice of the ideals of the fence of order 2n. These numbers are associated with symmetric circular matchings and RNA foldings. The second column of this array is \underline{A110320}, the number of blocks in all RNA secondary structures with n nodes. The function f(x)/x is the g.f. of \underline{A004148}(n + 1), which counts peakless Motzkin paths of length n.

The determinants |Ã_{i,j}|_{n} and |Ã_{i+1,j+1}|_{n} both yield the all 1’s sequence

1, 1, 1, 1, …,

while the determinants |Ã_{i+2,j+2}|_{n} yield the sequence

2, 6, 31, 227, 1991, 19415, 203456, 2248356,

or \underline{A094639}(n+1), the partial sums of the squared Catalan numbers. The sequence |Ã_{i+3,j+3}|_{n} then gives the partial sums

5, 30, 226, 1990, 19414, 203455, 2248355, 25887399, …

\underline{A167892}(n + 1) of the squared once-shifted Catalan numbers.

Example 24. In a similar vein to the last example we can consider the matrix with bivariate g.f. given by

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

which begins

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

This matrix is associated with the Riordan array

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

which can also be expressed as

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

The expansion of f(x) is essentially \underline{A025250}. The Hankel transform of the expansion of \frac{f(x)}{x} is the Somos sequence \underline{A050512}, which is associated with rational points on the elliptic curve

y^{2} − 2xy − y = x^{3} − x.

△

We note that to each Riordan array (g(x), f(x)) with (n, k)-th term T_{n,k}, we may associate with it the matrix Ã with general (n, k)-th term

Ã_{n,k} = \begin{cases}T_{n,k−n} if k > n \\ T_{k,n−k} otherwise \end{cases}  (4)

Example 25. A simple example is given by the Riordan array

(\frac{1}{1 − rx}, x)

whose elements are given by

T_{n,k} = \begin{cases}0 if k > n \\ r^{n−k} otherwise \end{cases}  (5)

Then the matrix Ã begins

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

This matrix has generating function

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

which may be expressed as

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

We note that the diagonal sums of the above matrix Ã have generating function

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

Example 26. For the binomial matrix

B = (\frac{1}{1 − x}, \frac{x}{1 − x})

we find that the corresponding matrix Ã begins

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

This matrix has generating function

\frac{1 − 2xy + x^{2}y^{2} − x^{3}y^{3}}{(1 − xy − x^{2}y)(1 + xy(y + 2) + x^{2}y^{2}(y + 1))},

or

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

The diagonal sums of this matrix, which begin

1, 0, 1, 2, 1, 4, 3, 6, 7, 10, 13, …,

have g.f.

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

We draw from this example that even when the originating Riordan array is simple, the generating function of the corresponding matrix Ã can be quite complicated.

Example 27. In this example we look at a modification of the Narayana truncation that led to the main result. Thus we consider the expression

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

As before, we form g(x, y/x) or

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

We now form

f̃(x, y) = \frac{1}{1 + x}g̃ (\frac{x}{1 + x}, \frac{y}{1 + 2y} ) \frac{1}{1 + 2y}
= \frac{1 − 2xy}{1 − 2xy^{2} − 5xy + 2x^{2}y^{2} − x^{2}y} .

This generates the matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 3 & 2 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 13 & 16 & 4 & 0 & 0 & … \\ 0 & 0 & 8 & 63 & 102 & 52 & 8 & … \\ 0 & 0 & 1 & 51 & 321 & 608 & 456 & … \\ 0 & 0 & 0 & 13 & 304 & 1683 & 3530 & … \\ 0 & 0 & 0 & 1 & 114 & 1765 & 8989 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We recognize that the main diagonal elements are the central Delannoy numbers \underline{A001850}, with g.f. \frac{1}{\sqrt{1−6x+x^{2}}} . We find that this matrix is associated with the Riordan array

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

where we note that the g.f. ^{\frac{1−5x+2x^{2}−(1−2x)\sqrt{1−6x+x^{2}}}{4x^{2}}} is the generating function of bracketed decomposable averaging words of degree n \underline{A238112} [9]. We have

Ã_{n,k} = \begin{cases}2T_{n,k−n} if k > n \\ T_{k,n−k} otherwise, \end{cases}  (6)

where T_{n,k} is the general term of the Riordan array matrix. The corresponding determinant sequence in this case begins

1, 3, 37, 1947, 441549, 433380147, 1844924230885, 34108080418744875, ….

Example 28. Our final generalization example stems from the fact that

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

Thus the general element of the Riordan array

(\frac{1}{\sqrt{1 − 4x}}, xc(x)^{3})

can be expressed as

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

We now generalize this to

T_{n,k} = ∑_{j=0}^{n} \binom{n + 2k}{j}\binom{n − k}{n − k − j}r^{j}.

For instance, when r = 2, this yields the Riordan array

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

or

(\frac{1}{\sqrt{1 − 6x + x^{2}}} , xS(x)^{3}) ,

where

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

is the g.f. of the large Schröder numbers \underline{A006318}. This Riordan array begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 3 & 1 & 0 & 0 & 0 & 0 & … \\ 13 & 9 & 1 & 0 & 0 & 0 & … \\ 63 & 61 & 15 & 1 & 0 & 0 & … \\ 321 & 377 & 145 & 21 & 1 & 0 & … \\ 1683 & 2241 & 1159 & 265 & 27 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

where the first column elements are the central Delannoy numbers \underline{A001850}. This then gives rise to the matrix

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 3 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 13 & 9 & 1 & 0 & 0 & … \\ 0 & 0 & 9 & 63 & 61 & 15 & 1 & … \\ 0 & 0 & 1 & 61 & 321 & 377 & 145 & … \\ 0 & 0 & 0 & 15 & 377 & 1683 & 2241 & … \\ 0 & 0 & 0 & 1 & 145 & 2241 & 8989 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The diagonal sums of this matrix, which begin

1, 0, 3, 2, 13, 18, 65, …,

have g.f.

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

The principal minor sequence for this matrix begins

1, 3, 38, 2151, 552178, 646763430, ….

For r = 3, we obtain the Riordan array

(\frac{1}{\sqrt{1 − 8x + 4x^{2}}} , xR(x)^{3}) ,

where

R(x) = \frac{1 − 2x − \sqrt{1 − 8x + 4x^{2}}}{2x} .

We find in general that the matrix with general term

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

is the Riordan array

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

while the matrix with general term

T_{n,k} = ∑_{j=0}^{n} \binom{n + 2k}{j}\binom{n − k}{n − k − j}r^{j}

is the Riordan array

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

Here, we recognize in

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

the bi-variate generating function of the Narayana triangle with general element

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

that begins

( \begin{matrix}1 & 0 & 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 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

while

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

is the generating function of the central term of (1+(r +1)x+rx^{2})^{n}, which can be expressed as

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

We note that

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

generates the sequence with general element

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

The generalization of the Jacobsthal decomposition matrix Ã then begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & r + 1 & 1 & 0 & 0 & 0 & … \\ 0 & 1 & r^{2} + 4r + 1 & 4r + 1 & 1 & 0 & … \\ 0 & 0 & 4r + 1 & r^{3} + 9r^{2} + 9r + 1 & 10r^{2} + 10r + 1 & 7r + 1 & … \\ 0 & 0 & 1 & 10r^{2} + 10r + 1 & r^{4} + 16r^{3} + 36r^{2} + 16r + 1 & 20r^{3} + 45r^{2} + 18r + 1 & … \\ 0 & 0 & 0 & 7r + 1 & 20r^{3} + 45r^{2} + 18r + 1 & r^{5} + 25r^{4} + 100r^{3} + 100r^{2} + 25r + 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

with general element

Ã_{n,k} = \begin{cases}∑_{j=0}^{n} \binom{n}{j}\binom{2n−k}{2n−k−j}r^{j} if k > n \\ ∑_{j=0}^{k} \binom{k}{j}\binom{2k−n}{2k−n−j}r^{j} otherwise. \end{cases}  (7)

The diagonal sums of this matrix begin 1, 0, r + 1, 2, r^{2} + 4r + 1, 8r + 2, r^{3} + 9r^{2} + 9r + 3, 20r^{2} + 20r + 2, r^{4} + 16r^{3} + 36r^{2} + 30r + 3, …, while the principal minor sequence begins

1, r+1, r^{3}+5r^{2}+5r, r^{6}+14r^{5}+59r^{4}+75r^{3}+26r^{2}−4r−1, r(r^{9}+30r^{8}+319r^{7}+1439r^{6}+2875r^{5}+2450r^{4}+589r^{3}−200r^{2}−69r−5), …

For r = 1, this is

1, 2, 11, 170, 7429, 920460, 323801820, …,

as anticipated.

References

[1] P. Barry, Embedding structures associated with Riordan arrays and moment matrices, Int. J. Comb., 2014 (2014), Article ID 301394.

[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, On integer sequences associated with the cyclic and complete graphs, J. Integer Seq., 10 (2007), Article 07.4.8.

[4] P. Barry, Triangle geometry and Jacobsthal numbers, Irish Math. Soc. Bulletin, 51 (2003), 45–57.

[5] S. Bilotta, D. Merlini, E. Pergola, and R. Pinzani, Binary words avoiding a pattern and marked succession rule. In Lattice Path Combinatorics and Applications, Siena, July

4-7, 2010. Available online at http://arxiv.org/abs/1103.5689.

[6] D. M. Bressoud, Proofs and Confirmations, Cambridge University Press, 1999.

[7] F. Colomo and A. G. Pronko, Square ice, alternating sign matrices, and classical orthogonal polynomials, J. Stat. Mech. Theory Exp., 2005, (2005). Available online at

http://arxiv.org/abs/math-ph/0411076.

[8] D. D. Frey and J. A. Sellers, Jacobsthal numbers and alternating sign matrices, J. Integer Seq., 3 (2000), Article 00.2.3.

[9] L. Guo and J. Pei, Averaging algebras, Schröder numbers and rooted trees, preprint,

2014. Available at http://arxiv.org/abs/1401.7386v1.

[10] I. M. Gessel and Guoce Xin, The generating function of ternary trees and continued fractions, Electron. J. Combin. 13 (2006), #R53.

[11] I. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1995.

[12] F. K. Hwang and C. L. Mallows, Enumerating nested and consecutive partitions, J. Combin. Theory A, 70 (1995), 323–333.

[13] R. Koekoek and R. F. Swarttouw, The Askey-scheme of hypergeometric orthogonal polynomials and its q-analoque, Report no. 98-17, Delft University of Technology, 1998.

[14] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin., 42 (1999), Article B42q, available electronically at

http://www.emis.de/journals/SLC/wpapers/s42kratt.html.

[15] J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq., 4 (2001), Article 01.1.5.

[16] A. Luzon, D. Merlini, M. A. Moron, and R. Sprugnoli, Complementary Riordan arrays, Disc. Appl. Math., 172 (2014), 75–87.

[17] D. Merlini, R. Sprugnoli, and M. C. Verri, Some statistics on Dyck paths, J. Statist. Plann. Inference 101 (2002), 211–227.

[18] D. Merlini, R. Sprugnoli, and M. C. Verri, The method of coefficients, Amer. Math. Monthly 114 (2007), 40–57.

[19] D. Merlini and R. Sprugnoli, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Theoret. Comput. Sci. 412 (2011), 2988–3001.

[20] R. L. Ollerton and A. G. Shannon, Some properties of generalized Pascal squares and triangles, Fibonacci Quart. 36 (1998)

[21] P. Pyatov, Raise and peel models of fluctuating interfaces and combinatorics of Pascal’s hexagon, J. Stat. Mech. (2004) P09003.

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

[23] L. Shapiro, A survey of the Riordan group, Center for Combinatorics, Nankai University, 2005.

[24] N. J. A. Sloane, The on-line encyclopedia of integer sequences. Published electronically

    at http://oeis.org, 2016.

[25] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

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

[27] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 1967.

2010 Mathematics Subject Classification: Primary 11C20; Secondary 11B83, 15B35, 15B36. Keywords: Jacobsthal number, Pascal’s triangle, binomial matrix, Riordan array, alternating sign matrix, ternary tree, plane partition.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001006}, \underline{A001045}, \underline{A001263}, \underline{A001850}, \underline{A002426}, \underline{A004148}, \underline{A005130}, \underline{A005156}, \underline{A005161}, \underline{A006013}, \underline{A006134}, \underline{A006318}, \underline{A007318}, \underline{A023431}, \underline{A025247}, \underline{A025250}, \underline{A025265}, \underline{A026374}, \underline{A047749}, \underline{A050512}, \underline{A051049}, \underline{A051159}, \underline{A051255}, \underline{A051286}, \underline{A053088}, \underline{A056241}, \underline{A059332}, \underline{A059475}, \underline{A059477}, \underline{A059489}, \underline{A078008}, \underline{A080635}, \underline{A091561}, \underline{A092392}, \underline{A094639}, \underline{A100100}, \underline{A109972}, \underline{A110320}, \underline{A120580}, \underline{A152225}, \underline{A159965}, \underline{A167892}, \underline{A169623}, \underline{A173102}, \underline{A187306}, and \underline{A238112}.)

Received July 15 2014; revised version received February 24 2016. Published in Journal of Integer Sequences, April 6 2016.

Return to Journal of Integer Sequences home page.