Continued Fractions and Transformations of Integer Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

We show how various transformations of integer sequences, normally realized by Riordan or generalized Riordan arrays, can be translated into continued fraction form. We also examine the Deleham number triangle construction using bi-variate continued fractions, giving examples from the field of associahedra.

1 Introduction

Many classical sequences have generating functions with well known representations as continued fractions. Many other important sequences arise from applying transformations to such sequences with known continued fraction representations. Thus if we can represent the result of the transformation in continued fraction form, we can infer the continued fraction representation of the new sequence.

The transformations that we shall discuss in this note will all be described by (ordinary) Riordan arrays, or generalized Riordan arrays. Thus we shall devote the next section to an overview of the Riordan group.

Sequences will be referred to by their Annnnnn number, as found in the On-Line Encyclopedia of Integer Sequences [10, 11].

The reader is referred to [13] for a general reference on continued fractions.

Example 1. The Catalan numbers. The Catalan numbers \underline{A000108}

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

have generating function

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

which can be represented as, for instance,

C(x) = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − ⋯}}},

or as

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

We shall use this notation of C(x) for the generating function of the Catalan numbers and c_{n} for the n-th Catalan number throughout. Similarly, the g.f. of the central binomial coefficients \binom{2n}{n} \underline{A000984}, \frac{1}{\sqrt{1−4x}}, may be represented as

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

or as

\frac{1}{\sqrt{1 − 4x}} = \frac{1}{1 − 2x − \frac{2x^{2}}{1 − 2x − \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − ⋯}}}}.

In the sequel we will have occasion to use the Iverson bracket notation [5], defined by [P] = 1 if the proposition P is true, and [P] = 0 if P is false. For instance, δ_{ij} = [i = j], while δ_{n} = [n = 0].

Note also that if we have a sequence a_{0}, a_{1}, a_{2}, … then the aeration of this sequence is the sequence a_{0}, 0, a_{1}, 0, a_{2}, 0, a_{3}, 0, … with interpolated zeros. If a_{n} has generating function g(x), then the aerated sequence has generating function g(x^{2}).

2 Riordan group

The Riordan group [9, 12], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + … and f(x) = f_{1}x + f_{2}x^{2} + … where f_{1} ≠ 0 [12]. The associated matrix is the matrix whose j-th column is generated by g(x)f(x)^{j} (the first column being indexed by 0). Thus the i-th element of the j-th column is given by

T_{i,j} = [x^{i}]g(x)f(x)^{j}

where the operator [x^{n}] [7] extracts the coefficient of x^{n} from the power series that it is applied to. The matrix corresponding to the pair g, f is denoted by (g, f) or R(g, f). The group law is then given by

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

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f. A Riordan array of the form (g(x), x), where g(x) = ∑_{k=0}^{n} a_{k}x^{k} is the generating function of the sequence a_{n}, is called the sequence array of the sequence a_{n}. Its general term is

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

Arrays of this form constitute a subgroup of the Riordan group, called the Appell group [6].

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)^{⊤} is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)). This follows since if M = (T_{n,k})_{n,k≥0}, we have

∑_{k=0}^{n} T_{n,k}a_{k} = ∑_{k=0}^{∞}[x^{n}]g(x)f(x)^{k}a_{k}

= [x^{n}]g(x) ∑_{k=0}^{∞} f(x)^{k}a_{k}
= [x^{n}]g(x)A(f(x)).

The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences Z^{N} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series Z[[x]] by

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

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

If f_{1} = 0 we call the matrix a “generalized” Riordan array. Such a matrix is not invertible.

3 The Binomial transform b_{n} = ∑_{k=0}^{n} \binom{n}{k}r^{n−k}a_{k}.

A common transformation on integer sequences is the so-called “binomial transform”, which maps the sequence with general term a_{n} to the sequence with general term b_{n} defined by

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

More generally, for r ∈ ℤ, we can define the “r-th binomial transform” of a_{n} to be the sequence with general term

b_{n} = ∑_{k=0}^{n} r^{n−k}\binom{n}{k}a_{k}.

The theory of Riordan arrays now tells us that this transformation can be represented by the matrix

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

We recall that if g(x) is the g.f. of the sequence a_{n}, then the g.f. of the sequence b_{n} will be given by

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

Applying this to the continued fraction representations above, we obtain the following expressions for the generating function of the r-th binomial transform of the Catalan numbers. Firstly

(\frac{1}{1 − rx}, \frac{x}{1 − rx}) · C(x) = \frac{1}{1 − rx} \frac{1}{1 − \frac{\frac{x}{1−rx}}{1 − \frac{\frac{x}{1−rx}}{1 − \frac{\frac{x}{1−rx}}{1 − ⋯}}}}

= \frac{1}{1 − rx − \frac{x}{1 − \frac{\frac{x}{1−rx}}{1 − \frac{\frac{x}{1−rx}}{1 − ⋯}}}}

= \frac{1}{1 − rx − \frac{x}{1 − \frac{x}{1 − rx − \frac{x}{1 − \frac{x}{1 − rx − \frac{x}{1 − ⋯}}}}}}

and secondly,

(\frac{1}{1 − rx}, \frac{x}{1 − rx}) · C(x) = \frac{1}{1 − rx} \frac{1}{1 − \frac{x}{1−rx} − \frac{\frac{x^{2}}{(1−rx)^{2}}}{1 − 2\frac{x}{1−rx} − \frac{\frac{x^{2}}{(1−rx)^{2}}}{1 − 2\frac{x}{1−rx} − \frac{\frac{x^{2}}{(1−rx)^{2}}}{1 − ⋯}}}}

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

= \frac{1}{1 − rx − x − \frac{x^{2}}{1 − rx − 2x − \frac{x^{2}}{1 − rx − 2x − \frac{x^{2}}{1 − ⋯}}}}.

Generalizing this example in an obvious way, we obtain the following two propositions. Proposition 3. Let a_{n} be a sequence with generating function g(x) expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the r-th binomial transform of a_{n} has generating function given by

\frac{1}{1 − rx − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − rx − \frac{α_{3}x}{1 − \frac{α_{4}x}{1 − rx − \frac{α_{5}x}{1 − ⋯}}}}}}.

Proposition 4. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the r-th binomial transform of a_{n} has generating function given by

\frac{1}{1 − rx − α_{1}x − \frac{β_{1}x^{2}}{1 − rx − α_{2}x − \frac{β_{2}x^{2}}{1 − rx − α_{3}x − \frac{β_{3}x^{2}}{1 − rx − ⋯}}}}.

We note that the last expression may be written as

\frac{1}{1 − (α_{1} + r)x − \frac{β_{1}x^{2}}{1 − (α_{2} + r)x − \frac{β_{2}x^{2}}{1 − (α_{3} + r)x − \frac{β_{3}x^{2}}{1 − rx − ⋯}}}}.

Thus the form of the continued fraction in this case does not change: only the coefficient of x in each case is incremented (or decremented). It can be shown that through the mechanism of series reversion, this translates the fact that

\begin{matrix}(\frac{1}{1 − αx − βx^{2}} , \frac{x}{1 − αx − βx^{2}} ) · (\frac{1}{1 − rx}, \frac{x}{1 − rx}) = \\ (\frac{1}{1 − (α + r)x − βx^{2}} , \frac{x}{1 − (α + r)x − βx^{2}} ) . \end{matrix}

Example 5. The central trinomial coefficients. The central binomial coefficients \binom{2n}{n} have g.f. expressible as

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

Thus the central trinomial coefficients \underline{A002426}, which are the (first) inverse binomial transform of \binom{2n}{n}, have g.f expressible as

\frac{1}{1 + x − \frac{2x}{1 − \frac{x}{1 + x − \frac{x}{1 − \frac{x}{1 + x − \frac{x}{1 − ⋯}}}}}}.

Example 6. The Motzkin numbers. The Motzkin numbers M_{n} \underline{A001006} are given by the binomial transform of the “aerated” Catalan numbers 1, 0, 1, 0, 2, 0, 5, …, which have g.f. C(x^{2}). Now

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

and so the Motzkin numbers have g.f. given by

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

Example 7. The central trinomial coefficients (revisited). The central trinomial coefficients may also be expressed as the binomial transform of the aerated central binomial coefficients. These latter have g.f. expressible as

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

and thus the central trinomial coefficients have g.f. expressible as

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

4 The transformation b_{n} = ∑_{k=0}^{⌊\frac{n}{2}⌋} \binom{n−k}{k}r^{n−2k}a_{k}.

The matrix that has general term

[k ≤ ⌊\frac{n}{2}⌋] \binom{n − k}{k}r^{n−2k}

can be represented by the generalized Riordan array

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

This follows since the general term of

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

is given by

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

We thus have Proposition 8. Let a_{n} be a sequence with generating function expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the sequence b_{n} with general term

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}r^{n−2k}a_{k}

has g.f. expressible as

\frac{1}{1 − rx − \frac{α_{1}x^{2}}{1 − \frac{α_{2}x^{2}}{1 − rx − \frac{α_{3}x^{2}}{1 − \frac{α_{4}x^{2}}{1 − ⋯}}}}}.

Proof. The g.f. of the transformed sequence is given by

(\frac{1}{1 − rx}, \frac{x^{2}}{1 − rx}) · g(x) = \frac{1}{1 − x} \frac{1}{1 − \frac{α_{1} \frac{x^{2}}{1−rx}}{1 − \frac{α_{2} \frac{x^{2}}{1−rx}}{1 − ⋯}}}

= \frac{1}{1 − rx − \frac{α_{1}x^{2}}{1 − \frac{α_{2} \frac{x^{2}}{1−rx}}{1 − ⋯}}}

= \frac{1}{1 − rx\frac{α_{1}x^{2}}{1 − \frac{α_{2}x^{2}}{1 − rx − \frac{α_{3}x^{2}}{1 − \frac{α_{4}x^{2}}{1 − rx − ⋯}}}}}.

Example 9. Number of Motzkin paths of length n with no level steps at odd level. The sequence \underline{A090344} with general term

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

has generating function given by

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

Proposition 10. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the g.f. of the sequence

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}r^{n−2k}a_{k}

is given by

\frac{1}{1 − rx − α_{1}x^{2} − \frac{β_{1}x^{4}}{1 − rx − α_{2}x^{2} − \frac{β_{2}x^{4}}{1 − ⋯}}}.

Proof. We have

(\frac{1}{1 − rx}, \frac{x^{2}}{1 − rx}) · g(x) = \frac{1}{1 − rx} \frac{1}{1 − α_{1} \frac{x^{2}}{1−rx} − \frac{β_{1} \frac{x^{4}}{(1−rx)^{2}}}{1 − α_{2} \frac{x^{2}}{1−rx} − \frac{β_{2} \frac{x^{4}}{(1−rx)^{2}}}{1 − ⋯}}}

= \frac{1}{1 − rx − α_{1}x^{2} − \frac{β_{1} \frac{x^{4}}{1−rx}}{1 − α_{2} \frac{x^{2}}{1−rx} − \frac{β_{2} \frac{x^{4}}{(1−rx)^{2}}}{1 − ⋯}}}

= \frac{1}{1 − rx − α_{1}x^{2} − \frac{β_{1}x^{4}}{1 − rx − α_{2}x^{2} − \frac{β_{2}x^{4}}{1 − ⋯}}}.

Example 11. Number of ordered trees with n edges and having no branches of length 1. This is given by \underline{A026418}, which begins 1, 0, 1, 1, 2, 3, 6, 11, 22, … Now the sequence which begins 1, 1, 2, 3, 6, … has general term

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

and therefore has g.f. given by

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

5 The transformation b_{n} = ∑_{k=0}^{n} \binom{n+k}{2k}a_{k}.

The transformation which maps the sequence with general term a_{n} to the sequence with general term

b_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}a_{k}

can be represented by the Riordan array

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

We then have the following proposition. Proposition 12. Let a_{n} be a sequence with generating function g(x) expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the sequence with general term b_{n} given by

b_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}a_{k}

has g.f. expressible as

(\frac{1}{1 − x}, \frac{x}{(1 − x)^{2}} ) · g(x) = \frac{1}{1 − x − \frac{α_{1}x}{1 − x − \frac{α_{2}x}{1 − x − ⋯}}}.

Proof. We have

(\frac{1}{1 − x}, \frac{x}{(1 − x)^{2}} ) · g(x) = \frac{1}{1 − x} \frac{1}{1 − \frac{α_{1} \frac{x}{(1−x)^{2}}}{1 − \frac{α_{2} \frac{x}{(1−x)^{2}}}{1 − ⋯}}}

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

= \frac{1}{1 − x − \frac{α_{1}x}{1 − x − \frac{α_{2}x}{1 − x − ⋯}}}.

Example 13. The large Schröder numbers. The large Schröder numbers S_{n} \underline{A006318} can be defined by

S_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}c_{k}.

Thus they have g.f. expressible as

S(x) = \frac{1}{1 − x − \frac{x}{1 − x − \frac{x}{1 − x − \frac{x}{1 − x − ⋯}}}}.

Example 14. The central Delannoy numbers. The central Delannoy numbers d_{n} \underline{A001850} can be defined by

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

Thus they have g.f. expressible as

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

More generally, we can consider the action of the Riordan array

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

for r ∈ ℤ. We obtain

Proposition 15. Let a_{n} be a sequence with generating function g(x) expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the sequence b_{n} with g.f. given by

\frac{1}{1 − rx}g (\frac{x}{(1 − rx)^{2}} )

is the expansion of

\frac{1}{1 − rx − \frac{α_{1}x}{1 − rx − \frac{α_{2}x}{1 − rx − \frac{α_{3}x}{1 − rx − ⋯}}}}.

In this case,

b_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}r^{n−k}a_{k}

is the general element of the transformed sequence. Example 16. The case r = −1. This case corresponds to the Riordan array

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

Now we have, for instance,

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

where 0^{n} is the sequence 1, 0, 0, 0, … with g.f. equal to 1. Thus we obtain the identity

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

Similarly the identity

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

yields the identity

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

Proposition 17. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the generating function of the sequence

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

obtained by applying the transformation represented by

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

to a_{n} has g.f. given by

\frac{1 − rx}{(1 − rx)^{2} − α_{1}x − \frac{β_{1}x^{2}}{(1 − rx)^{2} − α_{2}x − \frac{β_{2}x^{2}}{(1 − rx)^{2} − ⋯}}}.

Proof. The result follows by considering the expression

\frac{1 − rx}{(1 − rx)^{2}} \frac{1}{1 − α_{1} \frac{x}{(1−rx)^{2}} − \frac{β_{1} \frac{x^{2}}{(1−rx)^{4}}}{1 − α_{2} \frac{x}{(1−rx)^{2}} − \frac{β_{2} \frac{x^{2}}{(1−rx)^{4}}}{1 − ⋯}}} .

Example 18. Large Schröder numbers (revisited). Since the large Schröder numbers are given by

S_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}c_{k}

we obtain the following expression for their generating function :

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

or

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

Note that the above example shows that the partial sums of the large Schröder numbers, which have g.f. given by \frac{1}{1−x}S(x), can be obtained from the expansion of

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

This can be put in a more general context by observing that the general term of the matrix

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

is given by

\binom{n + k + 1}{n − k}r^{n−k} = \binom{n + k + 1}{2k + 1}r^{n−k}.

Thus we have the proposition

Proposition 19. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the generating function of the sequence

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

obtained by applying the transformation represented by

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

to a_{n} has g.f. given by

\frac{1}{(1 − rx)^{2} − α_{1}x − \frac{β_{1}x^{2}}{(1 − rx)^{2} − α_{2}x − \frac{β_{2}x^{2}}{(1 − rx)^{2} − ⋯}}}.

For instance, the g.f. of the partial sums of the large Schröder numbers, which have general term

∑_{k=0}^{n} \binom{n + k + 1}{2k + 1}c_{k},

can be represented as above in Eq. (3). This sequence is \underline{A086616}.

In a similar fashion, we have the result.

Proposition 20. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the generating function of the sequence

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

obtained by applying the transformation represented by

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

to a_{n} has g.f. given by

\frac{(1 − rx)^{2}}{(1 − rx)^{2} − α_{1}x − \frac{β_{1}x^{2}}{(1 − rx)^{2} − α_{2}x − \frac{β_{2}x^{2}}{(1 − rx)^{2} − ⋯}}}.

Example 21. Royal paths in a lattice \underline{A006319}. This is the sequence 1, 1, 4, 16, 68, 304, 1412, …, which also gives the number of peaks at level 1 in all Schröder paths of semi-length n, (n ≥ 1). It has general element

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

and g.f.

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

We note similarly that the sequence with g.f. given by

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

is the transformation of the Motzkin numbers M_{n} with general element

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

Finally, the sequence with g.f.

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

is the transformation of the shifted Catalan numbers c_{n+1} with general term

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

6 The transformation b_{n} = ∑_{k=0}^{n} \binom{n}{2k}a_{k}.

The matrix with general element \binom{n}{2k} is the generalized Riordan array

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

Proposition 22. Let a_{n} be a sequence with generating function expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the sequence with general term

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}a_{k}

has g.f. expressible in the form

\frac{1}{1 − x − \frac{α_{1}x^{2}}{1 − x − \frac{α_{2}x^{2}}{1 − x − ⋯}}}.

Proof. We have

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

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

= \frac{1}{1 − x − \frac{α_{1}x^{2}}{1 − x − \frac{α_{2}x^{2}}{1 − x − ⋯}}}.

In similar fashion, we can show that for a_{n} as above, the sequence

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}r^{n−2k}a_{k}

has g.f. expressible in continued fraction form as

\frac{1}{1 − rx − \frac{α_{1}x^{2}}{1 − rx − \frac{α_{2}x^{2}}{1 − rx − ⋯}}}.

We also have the following : Proposition 23. Let a_{n} be a sequence with generating function g(x) expressible in the form

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

Then the generating function of the sequence

b_{n} = ∑_{k=0}^{n} \binom{n}{2k}a_{k}

is expressible in the form

\frac{1 − x}{(1 − x)^{2} − α_{1}x^{2} − \frac{β_{1}x^{4}}{(1 − x)^{2} − α_{2}x^{2} − \frac{β_{2}x^{4}}{(1 − x)^{2} − α_{3}x^{2} − ⋯}}}.

Example 24. The Motzkin numbers M_{n}. We have

M_{n} = ∑_{k=0}^{n} \binom{n}{2k}c_{k}.

Hence the Motzkin numbers have g.f. expressible as

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

= \frac{1 − x}{1 − 2x − \frac{x^{4}}{1 − 2x − x^{2} − \frac{x^{4}}{1 − 2x − x^{2} − \frac{x^{4}}{1 − ⋯}}}}.

A simple consequence of this is the fact that the partial sums of the Motzkin numbers, \underline{A086615}, have generating function expressible as

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

7 The transformation b_{n} = ∑_{k=0}^{n} \binom{n−k}{2k}a_{k}.

We consider the generalized Riordan array

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

The general term of this matrix is given by

T_{n,k} = [x^{n}]\frac{x^{3k}}{(1 − x)^{2k+1}}
= [x^{n−3k}] ∑_{i=0} \binom{−2k − 1}{i}(−1)^{i}x^{i}
= [x^{n−3k}] ∑_{i=0} \binom{2k + 1 + i − 1}{i}x^{i}
= \binom{2k + n − 3k}{n − 3k}
= \binom{n − k}{2k}.

We then have Proposition 25. Let a_{n} be a sequence with generating function g(x) expressible in the form

g(x) = \frac{1}{1 − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − ⋯}}}.

Then the sequence

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

has g.f. expressible as

\frac{1}{1 − x − \frac{α_{1}x^{3}}{1 − x − \frac{α_{2}x^{3}}{1 − x − ⋯}}}.

Proof. We have

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

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

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

Example 26. Generalized Catalan numbers. We take a_{n} = C_{n} and form the sequence

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

with g.f.

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

Then we can express this g.f. as

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

These are the generalized Catalan numbers \underline{A023431}. Similarly, the sequence with g.f.

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

has general term

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

This is \underline{A098479}.

In general, we can show that the sequence with g.f. given by

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

is the image of the power sequence r^{n} by the product of Riordan arrays

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

Thus the g.f. of the image sequence is given by

\frac{1}{1 − x} \frac{1}{1 − r\frac{x^{3}}{1−x^{3}} C (\frac{x^{3}}{1−x^{3}} )}.

8 The transformation b_{n} = ∑_{k=0}^{n} \binom{n+k}{3k}a_{k}.

The general term of the generalized Riordan array

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

is given by

T_{n,k} = \binom{n + k}{3k}.

Thus if the sequence a_{n} has g.f. expressible in the form

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

then the sequence

b_{n} = ∑_{k=0}^{n} \binom{n + k}{3k}a_{k}

will have g.f.

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

which is equal to

\frac{1}{1 − x} \frac{1}{1 − \frac{α_{1} \frac{x^{2}}{(1−x)^{3}}}{1 − \frac{α_{2} \frac{x^{2}}{(1−x)^{3}}}{1 − \frac{α_{3} \frac{x^{2}}{(1−x)^{3}}}{1 − ⋯}}}}

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

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

= \frac{1}{1 − x − \frac{α_{1}x^{2}}{(1 − x)^{2} − \frac{α_{2}x^{2}}{1 − x − \frac{α_{3} \frac{x^{2}}{(1−x)^{2}}}{1 − ⋯}}}} .

Thus we arrive at the Proposition 27. In the circumstances above, the sequence

b_{n} = ∑_{k=0}^{n} \binom{n + k}{3k}a_{k}

has g.f. expressible in the form

\frac{1}{1 − x − \frac{α_{1}x^{2}}{(1 − x)^{2} − \frac{α_{2}x^{2}}{1 − x − \frac{α_{3}x^{2}}{(1 − x)^{2} − ⋯}}}}.

Example 28. Number of Dyck paths of semi-length n with no UUDD. We let a_{n} = c_{n}. Then the sequence with general term

b_{n} = ∑_{k=0}^{n} \binom{n + k}{3k}c_{k}

has g.f. \frac{1}{1−x}C (\frac{x^{2}}{(1−x)^{3}} ) expressible as

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

This is \underline{A086581} (number of Dyck paths of semi-length n with no UUDD).

9 Bi-variate continued fractions and number triangles

We have seen that

(\frac{1}{1 − rx}, \frac{x}{1 − rx}) · C(x) = \frac{1}{1 − rx − \frac{x}{1 − \frac{x}{1 − rx − \frac{x}{1 − \frac{x}{1 − rx − \frac{x}{1 − ⋯}}}}}}.

Now treating r as an independent variable (and writing it as y), we consider the bi-variate expression

g(x, y) = \frac{1}{1 − xy − \frac{x}{1 − \frac{x}{1 − xy − \frac{x}{1 − \frac{x}{1 − xy − \frac{x}{1 − ⋯}}}}}}.  (4)

This is the bi-variate generating function of the number triangle with general term

[k ≤ n]\binom{n}{k}c_{n−k},

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 2 & 1 & 0 & 0 & 0 & … \\ 5 & 6 & 3 & 1 & 0 & 0 & … \\ 14 & 20 & 12 & 4 & 1 & 0 & … \\ 42 & 70 & 50 & 20 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

This is \underline{A124644}. The image of the sequence r^{n} by this matrix is given by

b_{n} = ∑_{k=0}^{n} \binom{n}{k}c_{n−k}r^{k} = ∑_{k=0} \binom{n}{k}c_{k}r^{n−k},

using \binom{n}{k} = \binom{n}{n−k}. Thus applying the matrix with bi-variate generating function given by Eq. (4) to the sequence r^{n} is equivalent to calculating the r-th binomial transformation of the Catalan numbers C_{n}.

This example may be generalized in many ways.

10 The transformation b_{n} = ∑_{k=0}^{⌊\frac{n}{2}⌋} \binom{n−k}{k}r^{n−2k}a_{n−2k}.

Setting y = x in Eq. (4) of the last section gives us the generating function of the diagonal sums of the matrix. Thus the sequence with general term

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

has generating function expressible as

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

This is \underline{A105864}. By the construction above, it is the result of applying the Riordan array

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

to the Catalan numbers. In fact, we have the following proposition :

Proposition 29. Let a_{n} be a sequence with generating function expressible as

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

Then the sequence b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n−k}{k}a_{n−2k} which results from applying the Riordan array

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

to a_{n} will have g.f. of the form

\frac{1}{1 − rx^{2} − \frac{α_{1}x}{1 − \frac{α_{2}x}{1 − rx^{2} − \frac{α_{3}x}{1 − \frac{α_{4}x}{1 − rx^{2} − \frac{α_{5}x}{1 − ⋯}}}}}}.

Example 30. A transform of the large Schröder numbers. The large Schröder numbers have g.f. expressible as

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

Thus the sequence with general term

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

has g.f. given by

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

This is equal to

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

The special case r = −1 which corresponds to the Riordan array (\frac{1}{1+x^{2}} , \frac{x}{1+x^{2}} ) corresponds to the so-called “Chebyshev transform”. Thus the transform of c_{k} for this matrix has general term

b_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k}\binom{n − k}{k}c_{n−2k},

reminiscent of the formula for the Chebyshev polynomials of the second kind. This sequence is \underline{A101499}. By the above, it has generating function

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

11 The Deleham construction

The Deleham construction is a means of using bi-variate continued fraction generating functions, based on two base sequences, to construct number triangles. Many triangles of classical importance may be so constructed. Numerous examples are to be found in [10]. For the purposes of this note, we can define the Deleham construction as follows. Given two sequences r_{n} and s_{n},we use the notation

r Δ s = [r_{0}, r_{1}, r_{2}, …] Δ [s_{0}, s_{1}, s_{2}, …]

to denote the number triangle whose bi-variate generating function is given by

\frac{1}{1 − \frac{(r_{0}x + s_{0}xy)}{1 − \frac{(r_{1}x + s_{1}xy)}{1 − \frac{(r_{2}x + s_{2}xy)}{1 − ⋯}}}}.

We furthermore define

r Δ^{(1)} s = [r_{0}, r_{1}, r_{2}, …] Δ^{(1)} [s_{0}, s_{1}, s_{2}, …]

to denote the number triangle whose bi-variate generating function is given by

\frac{1}{1 − (r_{0}x + s_{0}xy) − \frac{(r_{1}x + s_{1}xy)}{1 − \frac{(r_{2}x + s_{2}xy)}{1 − ⋯}}}.

See \underline{A084938} for the original definition.

Example 31. The Narayana triangles. Three common versions of the Narayana triangle can be expressed as follows :

[1, 0, 1, 0, 1, 0, 1, …] Δ [0, 1, 0, 1, 0, 1, …]

which is \underline{A131198},

[0, 1, 0, 1, 0, 1, …] Δ [1, 0, 1, 0, 1, 0, 1, …],

which is the reverse of that matrix, and

[0, 1, 0, 1, 0, 1, …] Δ^{(1)} [1, 0, 1, 0, 1, 0, 1, …]

which is \underline{A090181}. We have the following result: Theorem 32. The first column of the Deleham array

[r_{0}, r_{1}, r_{2}, r_{3}, …] Δ [s_{0}, s_{1}, s_{2}, s_{3}, …]

has g.f.

\frac{1}{1 − \frac{r_{0}x}{1 − \frac{r_{1}x}{1 − \frac{r_{2}x}{1 − ⋯}}}}.

The row sums of the array have g.f.

\frac{1}{1 − \frac{(r_{0} + s_{0})x}{1 − \frac{(r_{1} + s_{1})x}{1 − \frac{(r_{2} + s_{2})x}{1 − ⋯}}}}.

The diagonal sums of the array have g.f.

\frac{1}{1 − \frac{(r_{0}x + s_{0}x^{2})}{1 − \frac{(r_{1}x + s_{1}x^{2})}{1 − \frac{(r_{2}x + s_{2}x^{2})}{1 − ⋯}}}}.

The product of the array with B has generating function

\frac{1}{1 − \frac{((r_{0} + s_{0})x + s_{0}xy)}{1 − \frac{((r_{1} + s_{1})x + s_{1}xy)}{1 − \frac{((r_{2} + s_{2})x + s_{2}xy)}{1 − ⋯}}}} = \frac{1}{1 − \frac{r_{0}x + s_{0}x(1 + y)}{1 − \frac{r_{1}x + s_{1}x(1 + y)}{1 − \frac{r_{2}x + s_{2}x(1 + y)}{1 − ⋯}}}},

and is thus the Deleham array

(r + s) Δ s.

The product of B and the array has generating function

\frac{1}{1 − x − \frac{(r_{0}x + s_{0}xy)}{1 − \frac{(r_{1}x + s_{1}xy)}{1 − x − \frac{(r_{2}x + s_{2}xy)}{1 − ⋯}}}}.

Proof. The g.f. of the first column is obtained by setting y = 0 in the bivariate g.f. Similarly, the g.f. of the row sums is obtained by setting y = 1, while that of the diagonal sums is found by setting y = x.

The product of the array r Δ s and B has g.f. given by

(1, x, x^{2}, …) (r Δ s) · B (1, y, y^{2}, …)^{⊤}.

But this is

(1, x, x^{2}, …) (r Δ s) (1, 1 + y, (1 + y)^{2}, …)^{⊤}

which by assumption is

\frac{1}{1 − \frac{r_{0}x + s_{0}x(1 + y)}{1 − \frac{r_{1}x + s_{1}x(1 + y)}{1 − \frac{r_{2}x + s_{2}x(1 + y)}{1 − ⋯}}}}.

The g.f. of the binomial transform of the array (that is, of the product of B and r Δ s) will be given by

\frac{1}{1 − x} \frac{1}{1 − \frac{(r_{0} + s_{0}y)\frac{x}{1−x}}{1 − \frac{(r_{1} + s_{1}y)\frac{x}{1−x}}{1 − \frac{(r_{2} + s_{2}y)\frac{x}{1−x}}{1 − ⋯}}}},

which simplifies to

\frac{1}{1 − x − \frac{(r_{0}x + s_{0}xy)}{1 − \frac{(r_{1}x + s_{1}xy)}{1 − x − \frac{(r_{2}x + s_{2}xy)}{1 − ⋯}}}}.

Example 33. \underline{A088874}. The number triangle

[0, 2, 6, 12, 20, 30, …] Δ [1, 2, 3, 4, 5, 6, …]

with g.f.

\frac{1}{1 − \frac{xy}{1 − \frac{(2x + 2xy)}{1 − \frac{(6x + 3xy)}{1 − \frac{(10x + 4xy)}{1 − ⋯}}}}}

is studied in [4].

The Deleham construction leads to many interesting triangular arrays of numbers. The field of associahedra [1, 2, 3, 8] is rich in such triangles, including the Narayana triangle. We finish with some examples from this area. An associahedron is a special type of polytope. The f-vector is a vector (f_{−1}, f_{0}, …, f_{n−1}) where f_{i} denotes the number of i-dimensional faces. The unique “(−1)-dimensional” face is the empty face. The h-vector (h_{0}, h_{1}, …, h_{n}) is determined from the f-vector by a process equivalent to that described below. In the sequel, A_{n} and B_{n} refer to standard root systems connected to rotation groups [3].

Example 34. The coefficient array for the f-vector for B_{n}. The triangle with general term

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

which is \underline{A063007}, is the coefficient array for the f-vector of B_{n} [2]. In other words, the fvector for B_{n} is given by ∑_{k=0}^{n} \binom{n}{k}\binom{n+k}{k}x^{k}. By our previous results, the bi-variate generating function of this triangle is given by

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

This may also be expressed as

\frac{1}{1 − x − \frac{2xy}{1 − \frac{x + xy}{1 − \frac{xy}{1 − \frac{x + xy}{1 − ⋯}}}}},

which is

[1, 0, 1, 0, 1, 0, …] Δ^{(1)} [0, 2, 1, 1, 1, 1, …].

Example 35. The h-vector array for B_{n}. Reversing the above array to get the array

[0, 2, 1, 1, 1, 1, …] Δ^{(1)} [1, 0, 1, 0, 1, 0, …],

we see that this array, which has general term \binom{n}{k}\binom{2n−k}{n}, has generating function

\frac{1}{1 − xy − \frac{2x}{1 − \frac{x + xy}{1 − \frac{x}{1 − \frac{x + xy}{1 − \frac{x}{1 − ⋯}}}}}},

or equivalently,

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

Taking the product of this matrix with B^{−1} we obtain the matrix with general term \binom{n}{k}^{2}. This is the h-vector array for B_{n}. Its generating function is thus expressible as

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

or

\frac{1}{1 − xy + x − \frac{2x}{1 − \frac{xy}{1 − \frac{x}{1 − \frac{xy}{1 − \frac{x}{1 − ⋯}}}}}}.

It may also be expressed as

\frac{1}{1 − xy + x − \frac{2x}{1 − xy + x − \frac{x}{1 − xy + x − \frac{x}{1 − xy + x − \frac{x}{1 − xy + x − ⋯}}}}}.

This is thus the Deleham array

[−1, 2, 0, 1, 0, 1, …] Δ^{(1)} [1, 0, 1, 0, 1, 0, …].

Example 36. The f- and h-vectors for A_{n}. The triangle with general term

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

is given by

[1, 0, 1, 0, 1, …] Δ^{(1)} [1, 1, 1, 1, …].

This is the coefficient array for the f-vector for A_{n} [1, 2]. We recall that

[1, 0, 1, 0, 1, …] Δ [1, 1, 1, 1, …]

has generating function

\frac{1}{1 − \frac{x + xy}{1 − \frac{xy}{1 − \frac{x + xy}{1 − ⋯}}}},

and thus the triangle

[1, 0, 1, 0, 1, …] Δ^{(1)} [1, 1, 1, 1, …]

has generating function

\frac{1}{1 − (x + xy) − \frac{xy}{1 − \frac{x + xy}{1 − \frac{xy}{1 − ⋯}}}}.

This is the array \underline{A033282} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 0 & 0 & 0 & 0 & … \\ 1 & 5 & 5 & 0 & 0 & 0 & … \\ 1 & 9 & 21 & 14 & 0 & 0 & … \\ 1 & 14 & 56 & 84 & 42 & 0 & … \\ 1 & 20 & 120 & 1300 & 330 & 132 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Reversing this triangle to get the triangle with general element

[k ≤ n]\frac{1}{n − k + 1}\binom{n}{k}\binom{2n − k + 2}{n − k},

and then forming the product of this matrix and B^{−1}, we obtain the coefficient array of the h-vector for A_{n} [3]. This turns out to be the version of the triangle of Narayana numbers 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 & 20 & 10 & 1 & 0 & … \\ 1 & 15 & 50 & 50 & 15 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and has generating function

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

Example 37. The Narayana numbers \underline{A090181}. In this example, we start with the number array with general element

\binom{n + k}{2k}c_{k} = \frac{1}{k + 1}\binom{n}{k}\binom{n + k}{k}.

This is \underline{A088617}, whose terms count the number of Schröder paths from (0, 0) to (2n, 0) with k up-steps. It has generating function

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

This may also be expressed as

\frac{1}{1 − x − \frac{xy}{1 − \frac{x + xy}{1 − \frac{xy}{1 − \frac{x + xy}{1 − ⋯}}}}},

which is

[1, 0, 1, 0, 1, 0, …] Δ^{(1)} [0, 1, 1, 1, 1, 1, …].

Reversing the above array to get the array

[0, 1, 1, 1, 1, 1, …] Δ^{(1)} [1, 0, 1, 0, 1, 0, …],

we see that this array, which has general term

[k ≤ n]\binom{2n − k}{k}c_{n−k} = [k ≤ n]\frac{1}{n − k + 1}\binom{n}{k}\binom{2n − k}{n − k},

has generating function

\frac{1}{1 − xy − \frac{x}{1 − \frac{x + xy}{1 − \frac{x}{1 − \frac{x + xy}{1 − \frac{x}{1 − ⋯}}}}}},

or equivalently,

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

Taking the product of this matrix with B^{−1} we obtain the matrix of the Narayana numbers 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} )

which is the Narayana triangle \underline{A090181}. Its generating function is thus expressible as

\frac{1}{1 − x(y − 1) − \frac{x}{1 − \frac{x + x(y − 1)}{1 − \frac{x}{1 − \frac{x + x(y − 1)}{1 − \frac{x}{1 − ⋯}}}}}},

or

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

It may also be expressed as

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

This is thus the Deleham array

[−1, 1, 0, 1, 0, 1, …] Δ^{(1)} [1, 0, 1, 0, 1, 0, …].

In fact, it is also expressible as the Deleham array

[0, 1, 0, 1, 0, 1, …] Δ [1, 0, 1, 0, 1, 0, …]

with generating function

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

12 Acknowledgements

The author is happy to acknowledge the input of an anonymous referee, whose careful reading of the original text and cogent comments have hopefully led to a clearer paper.

References

[1] A. Burgiel, V. Reiner, Two signed associahedra, New York J. Math., 4 (1998), 83–95.

[2] F. Chapoton, Enumerative properties of generalized associahedra, Séminaire Lotharingien de Combinatoire, 51 (2004), Article B51b.

[3] S. Fomin, N. Reading, Root systems and generalized associahedra, Preprint, http://arxiv.org/abs/math/0505518.

[4] G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, J. Integer Sequences, 9 (2006) Article 06.4.1, published electronically at

   http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Franssens/franssens13.html

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

[6] C. Kimberling, Matrix transformations of integer sequences, J. Integer Sequences, 6 (2003) Article 03.3.3.

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

[8] A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, Documenta Math. 13 (2008) 207–273.

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

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

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

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

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

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

2000 Mathematics Subject Classification: Primary 11B83; Secondary 15A36, 30B70, 15A04. Keywords: Integer sequence, Riordan array, continued fraction, generating function, linear transformation, Deleham construction.

(Concerned with sequences \underline{A000108}, \underline{A000984}, \underline{A001850}, \underline{A006318}, \underline{A006319}, \underline{A023431}, \underline{A026418}, \underline{A063007}, \underline{A084938}, \underline{A086581}, \underline{A086615}, \underline{A088617}, \underline{A090181}, \underline{A090344}, \underline{A098479}, \underline{A101499}, \underline{A105864}, \underline{A124644}, and \underline{A131198}.)

Received July 7 2009; revised version received November 2 2009. Published in Journal of Integer Sequences, November 4 2009.

Return to Journal of Integer Sequences home page.