On Sums, Derivatives, and Flips of Riordan Arrays

Caroline Bang Iowa State University

411 Morrill Rd Ames, IA 50011

USA

cbang@iastate.edu

Matias von Bell Institute of Geometry Graz University of Technology Kopernikusgasse 24 A-8010 Graz Austria

                            matias.vonbell@gmail.com

Eric Culver Brigham Young University

Provo, UT 84602

USA

eric.culver@mathematics.byu.edu

Jessica Dickson Washington State University PO Box 643113 Pullman, WA 99164 USA

                               jmdickson@wsu.edu

Stoyan Dimitrov Rutgers University

Hill Center Piscataway, NJ 08854

USA

EmailToStoyan@gmail.com

Rachel Perrier Washington State University PO Box 643113 Pullman, WA 99164 USA

                             rachel.perrier@wsu.edu

Sheila Sundaram Pierrepont School One Sylvan Road North Westport, CT 06880 USA

          shsund@comcast.net

Abstract

We study three operations on Riordan arrays. First, we investigate when the sum of Riordan arrays yields another Riordan array. We characterize the A- and Z-sequences of these sums of Riordan arrays, and also identify an analog for A-sequences when the sum of Riordan arrays does not yield a Riordan array. In addition, we define the new operations ‘Der’ and ‘Flip’ on Riordan arrays. We fully characterize the Riordan arrays resulting from these operations applied to the Appell and Lagrange subgroups of the Riordan group. Finally, we study the application of these operations to various known Riordan arrays, generating many combinatorial identities in the process.

1 Introduction

Riordan arrays are lower triangular matrices, extending infinitely to the right and downward, whose columns encode generating functions. They were first introduced by Shapiro et al.

[16] as a generalization of Pascal’s triangle.

In general, a Riordan array R(d(t), h(t)) is characterized by a pair of formal power series d(t) and h(t), satisfying d(0) ≠ 0 and h′(0) ≠ 0. Riordan arrays form a group under matrix multiplication known as the Riordan group, which has been extensively studied [2, 15, 16]. However, Riordan arrays are not in general closed under matrix addition. In Section 3 we investigate the sums of Riordan arrays, and determine in Theorem 14 when the sum of two Riordan arrays is again a Riordan array, namely, when they share the same h(t). Riordan arrays can also be described in terms of a pair of sequences A and Z. When two Riordan arrays can be added to form another, we characterize the A- and Z-sequences of their sum in Theorem 16. Although the matrix sum of two Riordan arrays is not a Riordan array in general, we call the resulting arrays Riordan sumrays and show in Theorem 26 that they satisfy a second order recurrence.

In Section 4, we introduce two new operations on Riordan arrays which we call derivatives and flips. For a Riordan array R(d(t), h(t)), derivative and flip are the following two operations respectively.

1. Der: R(d(t), h(t)) ↦ R(h′(t), td(t));

2. Flip: R(d(t), h(t)) ↦ R(h(t)/t, td(t)).

An important observation is that Flip is an involution, and that Der maps the Appell subgroup of the Riordan group to the Lagrange subgroup, and vice versa. In the case of Appell and Lagrange subgroups, we fully characterize their derivatives in Theorem 37.

There is a large literature on Riordan arrays showing their use in obtaining combinatorial identities [9, 16, 17, 19]. In the spirit of the pioneering work of Shapiro, we highlight this feature of Riordan arrays throughout the article. The new operations Der and Flip have proved especially fruitful by revealing surprising connections with known sequences, as well as leading to the discovery of new identities. These identities arise primarily from viewing a Riordan array R as the transformation of a sequence (a_{i})_{i=0}^{∞} to a sequence (b_{i})_{i=0}^{∞} via the product R ·(a_{i})_{i=0}^{∞} = (b_{i})_{i=0}^{∞}. In Section 5, we apply our results about Der and Flip to various Riordan arrays including the Fibonacci array, Pascal array, Catalan array, and Shapiro array.

Name  Sequence  Generating Function
Fibonacci (F_{i})_{i=0}^{∞} = (1, 1, 2, 3, 5, 8, 13, …)  F (t) = \frac{1}{1 − t − t^{2}}
Catalan (C_{i})_{i=0}^{∞} = (1, 1, 2, 5, 14, 42, …)  C(t) = \frac{1 − \sqrt{1 − 4t}}{2t}
Motzkin (M_{i})_{i=0}^{∞} = (1, 1, 2, 4, 9, 21, …) M(t) = \frac{1 − t − \sqrt{1 − 2t − 3t^{2}}}{2t^{2}}
Riordan (R_{i})_{i=0}^{∞} = (1, 0, 1, 1, 3, 6, 15, …) R(t) = \frac{1 + t − \sqrt{1 − 2t − 3t^{2}}}{2t(1 + t)}

Table 1: The recurring sequences in this article and their generating functions.

These are respectively the Riordan arrays

Fib := R(1, t + t^{2}),  Pas := R (\frac{1}{1 − t}, \frac{t}{1 − t}) ,
Cat := R(C(t), tC(t)),  Sha := R(C(t), tC^{2}(t)),

where C(t) is the generating function for the Catalan numbers (see Table 1). As a consequence we obtain several known combinatorial identities in new ways, along with identities that we have not found in the literature (Identities 11, 13, 52, 53, 54, 56, 59, 60, and Theorem 55). For several of the identities obtained we also provide new combinatorial proofs (Identities 11,13, 53, 54, 60). Furthermore, for any Riordan array in the Appell subgroup, the operation Der can be interpreted as giving a Riordan array involving weighted integer compositions (see Theorem 40). A summary of the relationships between sequences obtained using various Riordan arrays is given in Table 2.

2 Background and examples

We begin by providing the necessary background on Riordan arrays.

Definition 1. A Riordan array D = R(d(t), h(t)) is an infinite, lower triangular array defined by a pair of formal power series (d(t), h(t)) where d(0) ≠ 0, h(0) = 0, and h′(0) ≠ 0. The (n, k)-entry of D is given by

d_{n,k} = [t^{n}] d(t)h(t)^{k}, n, k ≥ 0,  (1)

where [t^{n}] a(t) = a_{n} is notation to extract the coefficient a_{n} from an ordinary generating function a(t) = ∑_{n≥0} a_{n}t^{n}. In particular, note that d_{0,0} = d(0) and d_{0,k} = 0 for k ≥ 1.

Riordan array R  Sequence (a_{i})_{i=0}^{∞}  Product R · (a_{i})_{i=0}^{∞}
1 T := R(1 + t, t)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A040000}, (1, 2, 2, …)
2  \underline{A007598}, (F_{i}^{2})_{i=0}^{∞}  \underline{A001519}, (F_{2i})_{i=0}^{∞}
3 Fib := Der T = R(1, t + t^{2}) \underline{A000012}, (1)_{i=0}^{∞}  \underline{A000045}, (F_{i})_{i=0}^{∞}
4 Jac := Der^{3} T = R(1, t + 2t^{2}) \underline{A000012}, (1)_{i=0}^{∞}  (\underline{A001045}(i + 1))_{i=0}^{∞}
5 R (\frac{C(t)−1}{tF (t)}, t) \underline{A000045}, (F_{i})_{i=0}^{∞} \underline{A000108}, (C_{i})_{i=1}^{∞}
6  \underline{A000007}, (1, 0, 0, …) (1, 1, \underline{A067324}(i)_{i=0}^{∞})
7 R(tM(t) + 1, t)  \underline{A000012}, (1)_{i=0}^{∞}  (\underline{A086615}(i) + 1)_{i=−1}^{∞}
8  \underline{A005043}, (R_{i})_{i=0}^{∞}  \underline{A001006}, (M_{i})_{i=0}^{∞}
9 R := R (\frac{−1}{1−t^{2}} , \frac{t}{1−t^{2}} )  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A152163}, (−F_{i})_{i=0}^{∞}
10  \underline{A000027}, (i)_{i=0}^{∞}  (\underline{A029907}(i))_{i=1}^{∞}
11 S := R (\frac{2}{(t^{2}−1)^{2}} , \frac{t}{1−t^{2}} )  \underline{A000012}, (1)_{i=0}^{∞}  (\underline{A052952}(i))_{i=1}^{∞}
12  \underline{A000027}, (i + 1)_{i=0}^{∞} (2·\underline{A001629}(i))_{i=2}^{∞}
13 R + S  \underline{A000012}, (1)_{i=0}^{∞}  (\underline{A001350}(i))_{i=1}^{∞}
14  \underline{A000027}, (i + 1)_{i=0}^{∞}  \underline{A045925}
15 Flip Der(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A001519}, (F_{2i})_{i=0}^{∞}
16 Der^{2}(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A001906}, (F_{2i+1})_{i=0}^{∞}
17 Der^{3}(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A004146}
18 Der^{4}(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A033453}
19 Der^{6}(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A144109}
20 Der^{2}(Pas) + Der^{3}(Pas)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A027941}, (F_{2i+1} − 1)_{i=1}^{∞}
21 Der(Cat)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A001700}
22  \underline{A000027}, (2^{i})_{i=0}^{∞}  \underline{A000302}, (4^{i})_{i=1}^{∞}
23  \underline{A005408}, (2i + 1)_{i=0}^{∞} (\underline{A129869}(i))_{i=1}^{∞}
24 Flip Der(Cat)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A026737}
25 Der^{2}(Cat)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A026671}
26 Der(Sha)  \underline{A000012}, (1)_{i=0}^{∞}  \underline{A002054}
27  \underline{A000027}, (2^{i})_{i=0}^{∞}  \underline{A008549}

Table 2: A summary of the relationships between sequences appearing in this article.

For example, choosing d(t) = 1/(1 − t) and h(t) = t/(1 − t) gives the Pascal array

Pas = R (\frac{1}{1 − t}, \frac{t}{1 − t}) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & ⋯ \\ 1 & 3 & 3 & 1 & 0 & ⋯ \\ 1 & 4 & 6 & 4 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

We will encounter more examples in Section 2.2. First, however, we review the main theorems on Riordan arrays.

2.1 The main theorems

As mentioned in the introduction, Riordan arrays have been used in the literature to investigate combinatorial identities. These results often exploit the following theorem, often called the fundamental theorem of Riordan arrays or “FTRA” [2].

Theorem 2. (FTRA) [16, Eqn. (5)], [17, Thm. 1.1] Let D = R(d(t), h(t)) be a Riordan array, and let f(t) := ∑_{k≥0} f_{k}t^{k} be the generating function for the sequence (f_{k})_{k≥0}. If D maps the sequence (f_{k})_{k≥0}, to the sequence (g_{k})_{k≥0}, then the generating function g(t) = ∑_{k≥0} g_{k}t^{k} for the sequence (g_{k})_{k≥0} is

d(t)f(h(t)).

We will provide several examples of using the FTRA to obtain combinatorial identities in Section 2.2.

An important fact about Riordan arrays is that they form a group known as the Riordan group. This is encapsulated in the following theorem.

Theorem 3. [16] The Riordan arrays form a group with respect to matrix multiplication. If R_{1} = R(d_{1}(t), h_{1}(t)) and R_{2} = R(d_{2}(t), h_{2}(t)) are Riordan arrays, then

R_{1}R_{2} = R(d_{1}(t)d_{2}(h_{1}(t)), h_{2}(h_{1}(t))).

The inverse of R = R(d(t), h(t)) is

R^{−1} = R (\frac{1}{d(\overline{h}(t))}, \overline{h}(t)) ,

where \overline{h}(t) denotes the compositional inverse of h(t), i.e., h(\overline{h}(t)) = t = \overline{h}(h(t)). The identity of the group is R(1, t).

The following are well-known subgroups of the Riordan group.

• The Lagrange subgroup {R(1, h(t)) | h′(0) ≠ 0} (also called the Associated subgroup).

• The Appell subgroup {R(d(t), t) | d(0) ≠ 0} (also called the Toeplitz subgroup).

• The Bell subgroup {R(d(t), t · d(t)) | d(0) ≠ 0} (these are also called Renewal arrays or Rogers arrays).

• The derivative subgroup {R(h′(t), h(t)) | h′(0) ≠ 0}.

• The hitting time subgroup {R(th′(t)/h(t), h(t)) | h′(0) ≠ 0}.

Associated with a Riordan array are two sequences, its A-sequence [14] and its Z-sequence [11]. The A-sequence A = (a_{0} ≠ 0, a_{1}, a_{2}, …) provides a way to recursively construct each row of the array from the previous row, via the generating function A(t) = ∑_{n≥0} a_{n}t^{n}, as follows.

d_{r+1,c+1} = a_{0}d_{r,c} + a_{1}d_{r,c+1} + a_{2}d_{r,c+2} + ⋯, r ≥ 0.  (2)

On the other hand, the Z-sequence, Z = (z_{0}, z_{1}, z_{2}, …), with generating function Z(t) = ∑_{n≥0} z_{n}t^{n}, allows the 0th column to be (uniquely) constructed using

d_{r+1,0} = z_{0}d_{r,0} + z_{1}d_{r,1} + z_{2}d_{r,2} + · · · .  (3)

Note that since Riordan arrays are lower triangular, the sums in equations (2) and (3) are finite. Results of Rogers [14], He and Sprugnoli [8, Thm. 2.1, Thm. 2.2], and Merlini et al. [11] imply that a Riordan array can be completely characterized by the triple (d_{0,0}, A(t), Z(t)). In the case of the Riordan array Pas, A = (1, 1, 0, 0, …) and thus A(t) = 1 + t, so that equation (2) reduces to the familiar Pascal recurrence d_{r+1,c+1} = d_{r,c} + d_{r,c+1}. Similarly, Z = (1, 0, 0, …) and Z(t) = 1 = d_{0,0} gives, using equation (3), d_{r+1,0} = 1.

Theorem 4. ([8, Thm. 2.1], [11, Thm. 2.2], [14])

If R = R(d(t), h(t)) is a Riordan array, then the A-sequence is determined by:

h(t) = tA(h(t)) ⟺ A(t) = \frac{t}{\overline{h}(t)}.

In particular, the A-sequence and the function h(t) determine each other. Furthermore,

A(t) = 1 ⟺ h(t) = t

and the Z-sequence is determined by:

d(t) = \frac{d(0)}{1 − tZ(h(t))}
⟺ d(t) − d(0) = td(t)Z(h(t))
⟺ Z(t) = \frac{d(\overline{h}(t)) − d(0)}{\overline{h}(t)d(\overline{h}(t))}

The A- and Z-sequences for a product of Riordan arrays have been completely determined as follows.

Theorem 5. [8, Thm. 3.3, Thm. 3.4] For the Riordan arrays R_{i} = R(d_{i}(t), h_{i}(t)), i = 1, 2 with respective A-sequences and Z-sequences A_{i}(t), Z_{i}(t), i = 1, 2, the A-sequence A(t) and the Z-sequence Z(t) of the product R = R_{1}R_{2} are given by

A(t) = A_{2}(t)A_{1} (\frac{t}{A_{2}(t)})

and

Z(t) = (1 − \frac{t}{A_{2}(t)}Z_{2}(t)) Z_{1} (\frac{t}{A_{2}(t)}) + A_{1} (\frac{t}{A_{2}(t)}) Z_{2}(t).

We will also need the following result, obtained by Lagrange inversion [21].

Theorem 6. [9, Thm. 2.2] Let R = R(d(t), h(t)) be a Riordan array. Then the inverse Riordan array R^{−1} has (n, k)-entry equal to

[t^{n−k}] \frac{h′(t)}{d(t) (\frac{h(t)}{t})^{n+1}} .

For more on Riordan arrays and the Riordan group we refer the reader to Shapiro et al. [16], as well as Sprugnoli [17].

2.2 Examples

Obtaining combinatorial identities using the FTRA is straightforward. Here, we give three examples, with combinatorial proofs. The first identity, Identity 8, and its proof, are well known. To the best of our knowledge, the other two examples and Identities 11 and 13 do not appear in the literature.

Example 7. Let F_{i} denote the ith Fibonacci number. Let (f_{n})_{n≥0} be the sequence of squares of Fibonacci numbers, i.e.,

(f_{n})_{n≥0} = (F_{n}^{2})_{n=0}^{∞} = (1, 1, 4, 9, 25, 64, 169, …),

and let (g_{n})_{n≥0} denote the even-indexed Fibonacci numbers, i.e.,

(g_{n})_{n≥0} = (F_{2n})_{n=0}^{∞} = (1, 2, 5, 13, 34, 89, 233, …).

The sequences (f_{n})_{n≥0} and (g_{n})_{n≥0} have generating functions

f(t) = \frac{t(1 − t)}{(1 + t)(1 − 3t + t^{2})} and g(t) = \frac{t(1 − t)}{(1 − 3t + t^{2})},

respectively. Observing that g(t) = (1+t)f(t), the FTRA gives that D = R(1+t, t)(f_{n})_{n≥0} = (g_{n})_{n≥0}, which yields the following well-known identity (see, for instance, Benjamin and Quinn [3, Sec. 1.5]).

Identity 8. For n ≥ 1,

F_{n}^{2} + F_{n+1}^{2} = F_{2n+2}.  (4)

A combinatorial proof (mentioned by Benjamin and Quinn [3]) is given below, for completeness.

Proof. We use the fact that the Fibonacci number F_{k} is the number of ways to tile a strip of length k with squares and dominoes [20]. Thus, the right-hand side of (4) is the number of ways to tile such a strip of length 2n + 2. If the middle two cells with numbers n + 1 and n + 2 are tiled with a domino, we can tile the rest of the board in F_{n}^{2} ways. If they are not, we have F_{n+1}^{2} ways to tile the entire board.

We record the following general proposition, obtained from the FTRA.

Proposition 9. Let (f_{n})_{n≥0} be a sequence with generating function f(t) of the form 1/p(t) where p(t) is a polynomial. Let (g_{n})_{n≥0} be a sequence with g_{0} ≠ 0 and generating function g(t). Then

∑_{i=0}^{n} f_{n−i} · ∑_{j=0}^{m} p_{j}g_{i−j} = g_{n},  (5)

with the understanding that g_{k} = 0 whenever k < 0.

Proof. Suppose we have a Riordan array R(d(t), t) which transforms (f_{n})_{n≥0} to (g_{n})_{n≥0}, i.e., R(d(t), t))(f_{i})_{i=0}^{∞} = (g_{i})_{i=0}^{∞}. Then FTRA tells us that

d(t) = g(t)/f(t) = g(t)p(t),

and the result follows.

As a specific example, we relate the Fibonacci numbers to the Catalan numbers.

Example 10. Let (C̄_{n})_{n=0}^{∞} denote the shifted Catalan sequence without the leading one. That is, the sequence (C̄_{n})_{n=0}^{∞} = (1, 2, 5, 14, …), with nth term given by C̄_{n} = C_{n+1}, n ≥ 0. The generating function for (C̄_{n})_{n=0}^{∞} is thus

C̄(t) := \frac{1 − 2t − \sqrt{1 − 4t}}{2t^{2}}.

Note that the generating function for (C_{n})_{n≥0} is tC̄(t) + 1 = (1 − \sqrt{1 − 4t})/(2t), see Section 5.3. Since the Fibonacci sequence has generating function F (t) = 1/p(t) with p(t) = 1 − t − t^{2}, the Riordan array transforming (F_{i})_{i=0}^{∞} to (C̄_{i})_{i=0}^{∞} is

R(C̄(t) · (1 − t − t^{2}), t) = R (\frac{C̄(t)}{F (t)}, t)

where the kth column has k zeros followed by the sequence (C̄_{i} − C̄_{i−1} − C̄_{i−2})_{i=0}^{∞}, with the understanding that C̄_{i} = 0 when i < 0. This is sequence \underline{A067324} with two initial ones.

Equation 5 simplifies to the following identity.

Identity 11. For n ≥ 3,

∑_{i=3}^{n} (C̄_{i} − C̄_{i−1} − C̄_{i−2}) F_{n+1−i} = C̄_{n} − F_{n} − F_{n−1}.  (6)

A combinatorial proof of Identity 11 follows.

Proof. It is well known that C̄_{n} counts the number of Dyck paths, that is, paths from (0, 0) to (2n, 0), consisting of steps U = (1, 1) and D = (1, −1), which never go below the x-axis. On the other hand, F_{n+1} is the number of Dyck paths from (0, 0) to (2n, 0) consisting only of UD and UUDD segments. Thus, the right-hand side, C̄_{n} − F_{n} − F_{n−1} = C̄_{n} − F_{n+1}, is the number of the remaining Dyck paths which contain at least one segment different from these two. To interpret the left-hand side, note that the number of Dyck paths of length 2i, which do not end in UD or UUDD, is precisely C̄_{i} − (C̄_{i−1} + C̄_{i−2}), since the number of paths ending in UD is C̄_{i−1} and the number of paths ending in UUDD is C̄_{i−2}. Thus, the ith term of the sum on the left is the number of Dyck paths from (0, 0) to (2n, 0), such that they have a prefix ending at (2i, 0), not finishing with UD or UUDD, but the rest of the path, from (2i, 0) to (2n, 0), is comprised of these two segments. It remains just to note that the possible values of i are from 3 to n.

Example 12. Consider the Motzkin numbers (M_{n})_{n=0}^{∞} = (1, 1, 2, 4, 9, 21, 51, …) and the Riordan numbers (R_{n})_{n=0}^{∞} = (1, 0, 1, 1, 3, 6, 15, 36, …), along with their respective generating functions M(t) and R(t) (see Table 1).

One can check that

\frac{M(t)}{R(t)} = tM(t) + 1,  (7)

and that the Riordan array R(tM(t) + 1, t) below maps the sequence of Riordan numbers to the sequence of Motzkin numbers.

Equation (7) is equivalent to

tM(t)R(t) = M(t) − R(t),

which gives the following identity.

Identity 13. For n ≥ 1,

∑_{i=0}^{n−1} R_{i−1}M_{n−i} = M_{n} − R_{n}.  (8)

A combinatorial proof follows.

Proof. Recall that a Motzkin path of length n is a lattice path in the plane from (0, 0) to (n, 0) never going below the x-axis, which consists of up steps U = (1, 1), down steps D = (1, −1), and horizontal steps H = (1, 0). The Motzkin number M_{n} counts the number of Motzkin paths of length n. On the other hand, the Riordan number R_{n} counts the Motzkin paths of length n with no horizontal steps of height 0 [6, Sec. 2]. Therefore, the right-hand side of (8) is the number of Motzkin paths of length n, which have at least one horizontal step of height 0. Let the first such step be step i. Before this step, we must have a path of length i − 1 without horizontal steps of height 0. The number of these paths is R_{i−1}. After this step, we can have any Motzkin path of length n − i and thus we have M_{n−i} such paths. Summing over the possible values of i gives the left-hand side.

3 Sums of Riordan arrays

Although Riordan arrays form a group under multiplication, the sum of Riordan arrays is not necessarily a Riordan array, as has already been observed in the literature [10, p. 172]. In this section we examine the summations of Riordan arrays more closely. We first determine when the sum of Riordan arrays yields a Riordan array (Theorem 14). We then consider the case of summing arbitrary Riordan arrays and show that it satisfies a recurrence (Theorem 26).

3.1 When addition of Riordan arrays is closed

The following theorem specifies exactly when the sum of Riordan arrays is again a Riordan array.

Theorem 14. Let R = R(d_{R}(t), h_{R}(t)) and S = R(d_{S}(t), h_{S}(t)) be two Riordan arrays. Then R+S is a Riordan array if and only if h_{R}(t) = h_{S}(t) = h(t), say, and d_{R}(0)+d_{S}(0) ≠ 0. In that case R + S is the Riordan array R(d_{R}(t) + d_{S}(t), h(t)).

Proof. Suppose h_{R}(t) = h_{S}(t) = h(t) and d_{R}(0) + d_{S}(0) ≠ 0. By definition,

R_{n,c} = [t^{n}] d_{R}(t)h(t)^{c}

and

S_{n,c} = [t^{n}] d_{S}(t)h(t)^{c}.

Hence

R_{n,c} + S_{n,c} = [t^{n}] d_{R}(t)h(t)^{c} + d_{S}(t)h(t)^{c}
= [t^{n}] (d_{R}(t) + d_{S}(t))h(t)^{c}.

Since d_{R}(0) + d_{S}(0) ≠ 0, this gives that R + S is a Riordan array.

Conversely, suppose R+S is a Riordan array. Hence there are series d_{R+S}(t), h_{R+S}(t) such that R+S = R(d_{R+S}(t), h_{R+S}(t)). From Equation (1) it is clear that d_{R+S}(t) = d_{R}(t)+d_{S}(t). By Theorem 2 we thus obtain

d_{R+S}(t)f(h_{R+S}(t)) = d_{R}(t)f(h_{R}(t)) + d_{S}(t)f(h_{S}(t)).

Equivalently, since Equation (1) implies that d_{R+S}(t) = d_{R}(t) + d_{S}(t), we have

f(h_{R+S}(t)) = \frac{d_{R}(t)f(h_{R}(t)) + d_{S}(t)f(h_{S}(t))}{d_{R}(t) + d_{S}(t)}.

Applying this to the polynomial f(t) = t^{k}, k = 1, 2, and suppressing the t’s for clarity, gives

h_{R+S} = \frac{d_{R}h_{R} + d_{S}h_{S}}{d_{R} + d_{S}} , h_{R+S}^{2} = \frac{d_{R}h_{R}^{2} + d_{S}h_{S}^{2}}{d_{R} + d_{S}} .

This in turn implies that (h_{R} − h_{S})^{2} = 0, thereby finishing the proof.

Remark 15. Let G_{h(t)} denote a subgroup of Riordan group consisting of the Riordan arrays R(d(t), h(t)) for a fixed h(t). Although the array of zeroes R(0, h(t)) is not a Riordan array, the set G_{h(t)} ∪{R(0, h(t))} admits a ring structure under matrix addition and multiplication.

We can now give an analogue of Theorem 5, characterizing the A- and Z-sequences formed by the sum of Riordan arrays with a common h(t).

Theorem 16. Let R = R(d_{R}(t), h(t)) and S = R(d_{S}(t), h(t)) be two Riordan arrays with the same h(t), such that d_{R}(0)+d_{S}(0) ≠ 0. Then R, S, and R+S have the same A-sequence

A(t) = \frac{t}{\overline{h}(t)}. The Z-sequence of R + S is given by

Z_{R+S}(t) = \frac{d_{R}(0)Z_{R}(t) + d_{S}(0)Z_{S}(t) − d_{R+S}(0)\overline{h}(t)Z_{R}(t)Z_{S}(t)}{d_{R+S}(0) − \overline{h}(t)d_{R}(0)Z_{S}(t) − \overline{h}(t)d_{S}(0)Z_{R}(t)};  (9)

This expression can also be written in several equivalent ways as follows. We have

Z_{R+S}(t) = \frac{[d_{R}(0)Z_{R}(t) + d_{S}(0)Z_{S}(t)]A(t) − td_{R+S}(0)Z_{R}(t)Z_{S}(t)}{d_{R+S}(0)A(t) − t[d_{R}(0)Z_{S}(t) + d_{S}(0)Z_{R}(t)]};  (10)

Z_{R+S}(h(t)) = \frac{d_{R}(t) + d_{S}(t) − d_{R}(0) − d_{S}(0)}{t(d_{R}(t) + d_{S}(t))};  (11)

and finally a symmetric expression as a weighted average of the individual Z-sequences:

Z_{R+S}(t) = \frac{d_{R}(\overline{h}(t))Z_{R}(t) + d_{S}(\overline{h}(t))Z_{S}(t)}{d_{R}(\overline{h}(t)) + d_{S}(\overline{h}(t))}  (12)

Proof. By Theorem 4 and Theorem 14, since R, S, and R + S have the same h(t), it follows

that R, S, and R + S have the same A-sequence. By Theorem 4, this is A(t) = \frac{t}{\overline{h}(t)}.

From Theorem 4 we also know that

d_{R}(\overline{h}(t)) = \frac{d_{R}(0)}{1 − \overline{h}(t)Z_{R}(t)}, d_{S}(\overline{h}(t)) = \frac{d_{S}(0)}{1 − \overline{h}(t)Z_{S}(t)},

and

d_{R+S}(\overline{h}(t)) = \frac{d_{R+S}(0)}{1 − \overline{h}(t)Z_{R+S}(t)}.  (13)

Since d_{R+S} = d_{R} + d_{S} by Theorem 14, we have (suppressing the t’s for clarity) that

\frac{d_{R+S}(0)}{1 − \overline{h}Z_{R+S}} = \frac{d_{R}(0)}{1 − \overline{h}Z_{R}} + \frac{d_{S}(0)}{1 − \overline{h}Z_{S}}

= \frac{d_{R+S}(0) − \overline{h} d_{R}(0)Z_{S} − \overline{h} d_{S}(0)Z_{R}}{(1 − \overline{h}Z_{R})(1 − \overline{h}Z_{S})} .

Hence we have

d_{R+S}(0)(1 − \overline{h}Z_{R})(1 − \overline{h}Z_{S}) = [d_{R+S}(0) − \overline{h}(d_{R}(0)Z_{S} + d_{S}(0)Z_{R})] (1 − \overline{h}Z_{R+S}).

The left-hand side equals

d_{R+S}(0) − \overline{h} [d_{R+S}(0) (Z_{R} + Z_{S}) − d_{R+S}(0)\overline{h}Z_{R}Z_{S}] .

The right-hand side equals

d_{R+S}(0) − \overline{h}(d_{R}(0)Z_{S} + d_{S}(0)Z_{R}) + [d_{R+S}(0) − \overline{h}(d_{R}(0)Z_{S} + d_{S}(0)Z_{R})](−\overline{h}Z_{R+S}).

It follows that

−\overline{h} [d_{R}(0)Z_{R} + d_{S}(0)Z_{S} − d_{R+S}(0)\overline{h}Z_{R}Z_{S}] = [d_{R+S}(0) − \overline{h}(d_{R}(0)Z_{S} + d_{S}(0)Z_{R})](−\overline{h}Z_{R+S})

again using d_{R+S} = d_{R} + d_{S}, and hence

d_{R}(0)Z_{R} + d_{S}(0)Z_{S} − d_{R+S}(0)\overline{h}Z_{R}Z_{S} = [d_{R+S}(0) − \overline{h} (d_{R}(0)Z_{S} + d_{S}(0)Z_{R})] Z_{R+S}.

This gives (9). Now using h̄(t) = t/A(t) gives (10).

Replacing t with h(t) in (13) and rearranging gives the expression (11) for the composition Z_{R+S} ∘ h in terms of only the d(t)’s. Finally, since d(t) − d(0) = td(t)Z(h(t)) by Theorem 4, we can also write the composition Z_{R+S} ∘ h as a symmetric expression in d(t) and Z(t):

Z_{R+S}(h(t)) = \frac{d_{R}(t)Z_{R}(h(t)) + d_{S}(t)Z_{S}(h(t))}{d_{R}(t) + d_{S}(t)},

from which Equation (12) follows.

In the next example, we demonstrate how the summation of Riordan arrays can be used to obtain combinatorial identities.

Example 17. Let R = R (\frac{−1}{1−t^{2}} , \frac{t}{1−t^{2}} ) and S = R (\frac{2}{(t^{2}−1)^{2}} , \frac{t}{1−t^{2}} ). We have that

R = R (\frac{−1}{1 − t^{2}} , \frac{t}{1 − t^{2}} ) ,

with general term given by

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

We also have that

S = R (\frac{2}{(1 − t^{2})^{2}} , \frac{t}{1 − t^{2}} ) ,

with general term given by

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

The sum R + S is then computed to be

R + S = R (\frac{t^{2} + 1}{(t^{2} − 1)^{2}} , \frac{t}{1 − t^{2}} ) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & ⋯ \\ 3 & 0 & 1 & 0 & 0 & ⋯ \\ 0 & 4 & 0 & 1 & 0 & ⋯ \\ 5 & 0 & 5 & 0 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

with general term given by

(R + S)_{n,k} = \frac{1 + (−1)^{n−k}}{2} · \frac{n + 1}{k + 1}\binom{(n + k)/2}{k}

The row sums of R are the negative Fibonacci numbers (−F_{i})_{i=0}^{∞} = (−1, −1, −2, −3, −5, …), while the row sums of S are given by 2(a_{i})_{i=0}^{∞} = 2F_{i+1} − 1 − (−1)^{i+1}, where (a_{i}) is the sequence \underline{A052952}. The row sums of R + S give the associated Mersenne numbers 1, 1, 4, 5, 11, 16, 29, … \underline{A001350}, with the ith term given by L_{i+1} − 1 − (−1)^{i+1}.

As a consequence, we have

−F_{i} + 2F_{i+1} − 1 − (−1)^{i+1} = L_{i+1} − 1 − (−1)^{i+1},

from which we obtain the following identity \underline{A000032}.

Identity 18.

2F_{i−1} + F_{i} = L_{i+1}

We observe that R · (1, 2, 3, 4, 5, …)^{t} = (−1, −2, −4, −8, −15, −28, −51, …)^{t}. This is the negative of a shift of the sequence \underline{A029907}, and its nth term is given by −\frac{1}{5}((n + 5)F_{n} + 2(n+1)F_{n−1}). Using the FTRA, its generating function can be verified to be d_{R}(t)f(h_{R}(t)) = (1 − t^{2})/(1 − t − t^{2})^{2} with f(t) = 1/(1 − t)^{2}.

Similarly, we observe that S·(1, 2, 3, 4, 5, …)^{t} = 2(1, 2, 5, 10, 20, 38, 71, …)^{t}, which is twice the convolution of the Fibonacci sequence with itself, i.e., 2 ∑_{k=0}^{n} F_{k}F_{n−k}. Furthermore, it is easy to check that (R + S) transforms the sequence (1, 2, 3, 4, 5, …) to the sequence ((n + 1)F_{n})_{n=0}^{∞}, which is \underline{A045925}.

Thus we have that

−\frac{1}{5}((n + 5)F_{n} + 2(n + 1)F_{n−1}) + 2 ∑_{k=0}^{n} F_{k}F_{n−k} = (n + 1)F_{n},

which simplifies to the following expression for the convolution of Fibonacci numbers with themselves.

Identity 19. For n ≥ 0,

∑_{k=0}^{n} F_{k}F_{n−k} = \frac{(3n + 5)F_{n} + (n + 1)F_{n−1}}{5} .

This identity is closely related to an identity given in \underline{A001629}.

3.2 Sums of arbitrary Riordan arrays

Let R = R(d_{R}(t), h_{R}(t)) and S = R(d_{S}(t), h_{S}(t)) be two Riordan arrays where h_{R}(t) may not equal h_{S}(t). The matrix sum R + S is not necessarily a Riordan array but does have some interesting properties in its own right. We call such an array a Riordan sumray and use the notation

R + S = RS(d_{R}(t), d_{S}(t), h_{R}(t), h_{S}(t))

to specify it. Note that the (n, k)-element of R(d_{R}(t), d_{S}(t), h_{R}(t), h_{S}(t)) is the coefficient of t^{n} in d_{R}(t)(h_{R}(t))^{k} + d_{S}(t)(h_{S}(t))^{k}.

Example 20. From the Riordan arrays R = R (\frac{1}{1−t}, \frac{t}{1−t}) and S = R (\frac{1}{1−t}, \frac{2t}{1−t}) we have the Riordan sumray:

RS (\frac{1}{1 − t}, \frac{1}{1 − t}, \frac{t}{1 − t}, \frac{2t}{1 − t}) = [\begin{matrix}2 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 6 & 5 & 0 & 0 & 0 & ⋯ \\ 2 & 9 & 15 & 9 & 0 & 0 & ⋯ \\ 2 & 12 & 30 & 36 & 17 & 0 & ⋯ \\ 2 & 15 & 50 & 90 & 85 & 33 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

Our goal in this subsection is to derive an interesting second order recurrence for an arbitrary sum R + S. We begin with some notation and preliminary lemmas.

Definition 21. Let A := (a_{n})_{n≥0} be any sequence. We define Ã to be the infinite matrix whose (i, j)-entry is

\begin{cases}a_{i−j}, & i ≥ j, \\ 0, & otherwise. \end{cases}

In particular, Ã is a Toeplitz array; it is lower triangular with constant entries along the main diagonal and its parallel subdiagonals, where the nth term of the sequence fills the subdiagonal formed by {(i, j) : i − j = n}. Note that the jth column of Ã is simply the sequence (a_{n})_{n≥0} shifted down by j spaces.

Remark 22. Note that if the sequence from Definition 21 is an A-sequence A := (a_{0} ≠ 0, a_{1}, a_{2}, …), one has Ã = R(A(t), t).

Lemma 23. Let A := (a_{n})_{n≥0} and B := (b_{n})_{n≥0} be any two sequences. Then the matrices Ã and B̃ commute.

Proof. The (i, j)-entry of the product ÃB̃ is the convolution

∑_{k≥0} a_{i−k}b_{k−j}.

This is nonzero if and only if i ≥ k ≥ j, and then it equals

∑_{k=j}^{i} a_{i−k}b_{k−j} = a_{i−j}b_{0} + a_{i−j−1}b_{1} + ⋯ + a_{0}b_{i−j} = ∑_{p+q=i−j^{p,q≥0}} a_{p}b_{q}.

Clearly the latter convolution is symmetric in A and B.

Lemma 24. Let R = R(d_{R}(t), h_{R}(t)) be a Riordan array, and let A_{R} be its A-sequence. Let R^{σ} denote the array obtained from R by deleting the first row and the first column. Then

1. R^{σ} is the Riordan array R(d_{R}(t)h_{R}(t)/t, h_{R}(t)), and hence has the same A-sequence A_{R};

2. the matrix equation R^{σ} = R Ã_{R} holds.

Proof. Note that the coefficient of t^{n} in (d_{R}(t)h_{R}(t)/t) · h_{R}(t)^{k} equals the coefficient of t^{n+1} in d_{R}(t)h_{R}(t)^{k+1}, which is precisely the (n + 1, k + 1)-entry of the Riordan array R = R(d_{R}(t), h_{R}(t)), from Equation (1). But this is also the (n, k)-entry of R^{σ} for n, k ≥ 0, and the first part of the first statement follows. The A-sequence is preserved since it depends only on h_{R}(t) by Theorem 4.

Let d_{n,k} denote the (n, k)-entry of the Riordan array R. For the second statement, the definition of the A-sequence gives (Equation (2)) for n, k ≥ 0,

d_{n+1,k+1} = ∑_{i≥0} d_{n,k+i}a_{i} = ∑_{j≥0} d_{n,j}a_{j−k}.

But the right-hand side is the (n, k)-entry of the matrix product R Ã_{R}, by Definition 21, while d_{n+1,k+1} is the (n, k)-entry of R^{σ}. The claim follows.

Remark 25. Part (1) of Lemma 24 also follows from Theorem 3 and Theorem 4 since

R (d_{R}(t), h_{R}(t)) R (A(t), t) = R (d_{R}(t), h_{R}(t)) R (\frac{t}{\overline{h}_{R}(t)}, t)

= R (d_{R}(t)\frac{h_{R}(t)}{\overline{h}_{R}(h_{R}(t))}, h_{R}(t))

= R (d_{R}(t)\frac{h_{R}(t)}{t}, h_{R}(t)) .

A similar argument appears in Sprugnoli [18, Proof of Theorem 5.3.1].

We can now establish a recurrence relating the sum of any two arbitrary Riordan arrays. This recurrence for Riordan sumrays is an analog of the typical A-sequence.

Theorem 26. Let R = R(d_{R}(t), h_{R}(t)) and S = R(d_{S}(t), h_{S}(t)) be two Riordan arrays with respective A-sequences A_{R}, A_{S}. Then the Riordan sumray R + S satisfies the following recurrence.

(R + S)^{σσ} = (R + S)^{σ}(Ã_{R} + Ã_{S}) − (R + S)Ã_{R}Ã_{S}.

Equivalently, the entries d_{n,k} of the sum R + S satisfy the following recurrence:

d_{n+2,k+2} = ∑_{j=0}^{∞} d_{n+1,j+1}B_{j,k} + ∑_{j=0}^{∞} d_{n,k+j}C_{j,k},

where B = Ã_{R} + Ã_{S}, and C = −Ã_{R}Ã_{S}, and thus B_{j,k} = (A_{R})_{j−k} + (A_{S})_{j−k} and C_{j,k} =

− ∑_{p+q=j−k^{p,q≥0}}(A_{R})_{p}(A_{S})_{q}.

Proof. Note that, by using Part (2) followed by Part (1) of Lemma 24,

R^{σσ} = R^{σ}Ã_{R^{σ}} = R^{σ}Ã_{R}.

Similarly,

S^{σσ} = S^{σ}Ã_{S^{σ}} = S^{σ}Ã_{S}.

Since (R + S)^{σ} = R^{σ} + S^{σ}, we have:

(R + S)^{σσ} = R^{σσ} + S^{σσ}
= R^{σ}Ã_{R} + S^{σ}Ã_{S}
= (R^{σ} + S^{σ})(Ã_{R} + Ã_{S}) − R^{σ}Ã_{S} − S^{σ}Ã_{R}
= (R^{σ} + S^{σ})(Ã_{R} + Ã_{S}) − RÃ_{R}Ã_{S} − SÃ_{S}Ã_{R}
= (R + S)^{σ}(Ã_{R} + Ã_{S}) − (R + S)Ã_{R}Ã_{S},

since Ã_{R} and Ã_{S} commute by Lemma 23.

Let d_{n,k}, n, k ≥ 0, denote the (n, k)-entry of the sum R + S. Then the (n, k)-entries of (R + S)^{σ} and (R + S)^{σσ} are respectively

d_{n+1,k+1} and d_{n+2,k+2}

for n, k ≥ 0. Writing out the corresponding equation for the matrix entries gives, for n, k ≥ 0,

d_{n+2,k+2} = ∑_{j=0}^{∞} d_{n+1,j+1}B_{j,k} + ∑_{j=0}^{∞} d_{n,k+j}C_{j,k},

where B = Ã_{R} + Ã_{S}, and C = −Ã_{R}Ã_{S}.

Example 27. Consider Example 20 within the context of this theorem. The A-sequences for the Riordan arrays whose sum produces this Riordan sumray are (1, 1, 0, 0, …) and (2, 1, 0, 0, …). Therefore, the matrices B and C are:

B = [\begin{matrix}3 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 3 & 0 & 0 & ⋯ \\ 0 & 0 & 2 & 3 & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] C = [\begin{matrix}−2 & 0 & 0 & 0 & 0 & ⋯ \\ −3 & −2 & 0 & 0 & 0 & ⋯ \\ −1 & −3 & −2 & 0 & 0 & ⋯ \\ 0 & −1 & −3 & −2 & 0 & ⋯ \\ 0 & 0 & −1 & −3 & −2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

The Riordan sumray R = RS (\frac{1}{1−t}, \frac{1}{1−t}, \frac{t}{1−t}, \frac{2t}{1−t}) then satisfies the second-order recurrence:

R^{σσ} = R^{σ}B + RC

The previous example illustrates the recurrence in terms of array multiplication. We can also use this recurrence to calculate specific entries d_{n,k}, as shown in the next example.

Example 28. Consider the Pascal array Pas = R (\frac{1}{1−t}, \frac{t}{1−t}) and the Shapiro array Sha =

R (\frac{1−\sqrt{1−4t}}{2t}, \frac{1−2t−\sqrt{1−4t}}{2t}).

Pas = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & ⋯ \\ 1 & 3 & 3 & 1 & 0 & ⋯ \\ 1 & 4 & 6 & 4 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] , Sha = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 1 & 0 & 0 & ⋯ \\ 5 & 9 & 5 & 1 & 0 & ⋯ \\ 14 & 28 & 20 & 7 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

and

Pas + Sha = [\begin{matrix}2 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 2 & 0 & 0 & 0 & ⋯ \\ 3 & 5 & 2 & 0 & 0 & ⋯ \\ 6 & 11 & 8 & 2 & 0 & ⋯ \\ 15 & 32 & 26 & 11 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... . \end{matrix}]

The A-sequences for Pas and Sha are A_{Pas} = (1, 1, 0, 0, …) and A_{Sha} = (1, 2, 1, 0, 0, …). We check that the entries d_{n+2,k+2} for n, k ≥ 0 of Pas + Sha satisfy the formula given by Theorem 26. For instance, the following calculation gives us the d_{3,2} entry:

8 = d_{3,2} = ∑_{j=0}^{∞} d_{2,j+1}B_{j,0} + ∑_{j=0}^{∞} d_{1,j}C_{j,0}
= d_{2,1}B_{0,0} + d_{2,2}B_{1,0} + d_{1,0}C_{0,0} + d_{1,1}C_{1,0}
= 5(2) + 2(3) + 2(−1) + 2(−3),

where

B_{0,0} = (Ã_{Pas})_{0,0} + (Ã_{Sha})_{0,0}  C_{0,0} = − ((Ã_{Pas})_{0,0}(Ã_{Sha})_{0,0})
B_{1,0} = (Ã_{Pas})_{1,0} + (Ã_{Sha})_{1,0}  C_{1,0} = − ((Ã_{Pas})_{1,0}(Ã_{Sha})_{0,0} + (Ã_{Pas})_{1,1}(Ã_{Sha})_{1,0}) .

When h_{R}(t) = h_{S}(t), R + S is itself a Riordan array with Ã_{R} = Ã_{S} = Ã, and the recurrence from Theorem 26 specializes to

(R + S)^{σσ} = 2(R + S)^{σ}(Ã) − (R + S)Ã^{2}
= 2(R + S)(Ã)(Ã) − (R + S)Ã^{2}
= (R + S)Ã^{2},

as expected.

Example 29. Consider the Riordan arrays Pas = R (\frac{1}{1−t}, \frac{t}{1−t}) and S = R (\frac{1}{1−2t}, \frac{t}{1−t}). We have that

Pas +S = R (\frac{2 − 3t}{1 − 3t + 2t^{2}} , \frac{t}{1 − t}) = [\begin{matrix}2 & 0 & 0 & 0 & 0 & ⋯ \\ 3 & 2 & 0 & 0 & 0 & ⋯ \\ 5 & 5 & 2 & 0 & 0 & ⋯ \\ 9 & 10 & 7 & 2 & 0 & ⋯ \\ 17 & 19 & 17 & 9 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Under the Riordan sumray definition, Pas +S = RS (\frac{1}{1−t}, \frac{1}{1−2t}, \frac{t}{1−t}, \frac{t}{1−t}). These have shared A-sequence (1, 1, 0, 0, …). Then

Ã^{2} = [\begin{matrix}1 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & ⋯ \\ 0 & 1 & 2 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Thus

(Pas +S)Ã^{2} = [\begin{matrix}2 & 0 & 0 & 0 & ⋯ \\ 7 & 2 & 0 & 0 & ⋯ \\ 17 & 9 & 2 & 0 & ⋯ \\ 36 & 26 & 11 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] = (Pas +S)^{σσ}.

4 The operations Der and Flip

In this section we present two new operations on Riordan arrays. These are the derivative and the flip, which we define as follows. Definition 30. Let R(d(t), h(t)) be a Riordan array. The derivative and flip are the following two operations respectively.

1. Der: R(d(t), h(t)) ↦ R(h′(t), td(t));

2. Flip: R(d(t), h(t)) ↦ R(h(t)/t, td(t)).

The following observations are immediate. Lemma 31. The operations Der and Flip satisfy the following.

• Flip is an involution.

• Flip(Der(R)) = R(d(t), th′(t)).

• Der(Flip(R)) = R(d(t) + td′(t), h(t)).

• Both Der and Flip map the Appell subgroup to the Lagrange subgroup, since

R(d(t), t) ⟶^{Der,Flip} R(1, td(t)).

• Both Der and Flip map the Lagrange subgroup to the Appell subgroup, since Der(R(1, h(t))) = R(h′(t), t), Flip(R(1, h(t))) = R(h(t)/t, t).

• Der maps the Derivative subgroup to the Bell subgroup, since

R(h′(t), h(t)) ⟶^{Der} R(h′(t), th′(t)).

• Flip fixes an array R(d(t), h(t)) if and only if it is in the Bell subgroup (when h(t) =

td(t)), and here Der is the map

R(d(t), td(t)) ⟶^{Der} R(d(t) + td′(t), td(t)).

• Der fixes an array R(d(t), h(t)) if and only if h′(t) = d(t) = h(t)/t, i.e., if and only if h(t) = ct for some nonzero constant c.

• Der(R) = Flip(R) if and only if h(t) = ct for some nonzero constant c, in which case both operations fix R, and R = R(c, ct).

From the definitions of Der and Flip, we have Proposition 32. Let R = R(d(t), h(t)) be any Riordan array. The (n, k)-entries of Der and Flip are

Der(R)_{n,k} = [t^{n−k}] h′(t)d(t)^{k}, Flip(R)_{n,k} = [t^{n−k+1}] h(t)d(t)^{k}.

For an array d_{n,k}, the row sum of the nth row is the sum ∑_{k≥0} d_{n,k}, while the alternating row sum of the nth row is the signed sum ∑_{≥0}(−1)^{k}d_{n,k}. Lemma 33. Let R = R(d(t), h(t)) be a Riordan array. The generating function for the row sums (respectively, alternating row sums) of

1. Der(R) is \frac{h′(t)}{1 − td(t)} (respectively, \frac{h′(t)}{1 + td(t)});

2. Flip(R) is \frac{h(t)}{t(1 − td(t))} (respectively, \frac{h(t)}{t(1 + td(t))}).

Proof. This follows from the fact that the generating function for the row sums (respectively, alternating row sums) of any Riordan array R = R(d(t), h(t)) is d(t)/(1−h(t)) (respectively, d(t)/(1 + h(t))), a consequence of Theorem 2 using the generating functions f(t) = 1/(1 − t) (respectively, f(t) = 1/(1 + t)).

The next two lemmas are simply applications of Theorem 4. As before, the bar denotes compositional inverse.

Lemma 34. If R = R(d(t), h(t)) is a Riordan array, then the A-sequences of Der(R) and Flip(R) are given by

A(t) = \frac{t}{\overline{td(t)}},

and the A sequence of Der^{2}(R) is

A(t) = \frac{t}{\overline{th′(t)}}.

Lemma 35. If R = R(d(t), h(t)) is a Riordan array, then the Z-sequences of Der(R) and Flip(R) are given by

Z(t) = \frac{h′(\overline{td(t)}) − h′(0)}{\overline{td(t)} · h′(\overline{td(t)})}.

The following gives the connection between sums, derivatives, and flips of Riordan arrays. Let Der^{k} (respectively, Flip^{k}) denote the operation Der (respectively, Flip) iterated k times.

Proposition 36. Let R_{1} = R(d_{1}(t), h(t)) and R_{2} = R(d_{2}(t), h(t)) be Riordan arrays. Then the following hold:

1. Der^{2m}(R_{1} + R_{2}) = Der^{2m}(R_{1}) + Der^{2m}(R_{2}), m ≥ 1,

2. Flip^{2m}(R_{1} + R_{2}) = Flip^{2m}(R_{1}) + Flip^{2m}(R_{2}), m ≥ 1,

3. Der(Flip(R_{1} + R_{2})) = Der(Flip(R_{1})) + Der(Flip(R_{2})), and

4. Flip(Der(R_{1} + R_{2})) = Flip(Der(R_{1})) + Flip(Der(R_{1})).

Proof. These are easily checked. Note that for the first two items it suffices to check the case n = 1.

As noted before, Der maps the Appell subgroup to the Lagrange subgroup and vice versa. Therefore Der^{2m} maps the Appell subgroup to itself for any m. We have the following.

Theorem 37. For a Riordan array R(d(t), t) in the Appell subgroup where d(t) = d_{0} +d_{1}t+ d_{2}t^{2} + ⋯ and m ≥ 0 we have

Der^{2m}(R) = R (∑_{i=0}^{m} S_{m+1,i+1}t^{i}d^{(i)}(t), t) = R (∑_{i≥0} d_{i}(i + 1)^{m}t^{i}, t) ,

Der^{2m+1}(R) = R (1, ∑_{i=0}^{m} S_{m+1,i+1}t^{i+1}d^{(i)}(t)) = R (1, t ∑_{i≥0} d_{i}(i + 1)^{m}t^{i}) ,

where S_{m+1,i+1} is the Stirling number of the second kind, and d^{(i)}(t) denotes the ith derivative of d(t).

Proof. For each m ≥ 0, the Der^{2m+1}(R) case follows immediately from Der^{2m}(R), so it suffices to show the latter. We begin by showing the first equality. Observe that when m = 0, we have Der^{2m}(R(d(t), t)) = R(d(t), t). We then proceed by induction, assuming that

Der^{2(m−1)}(R) = R (∑_{i≥0}^{m−1} S_{m,i+1}t^{i}d^{(i)}(t), t) .

Note that by the definition of Der, we have

Der^{2m}(R) = R ((t · ∑_{i≥0}^{m−1} S_{m,i+1}t^{i}d^{(i)}(t))^{(1)} , t) .

It remains to simplify as follows.

(t · ∑_{i=0}^{m−1} S_{m,i+1}t^{i}d^{(i)}(t))^{(1)} = ∑_{i=0}^{m−1}[S_{m,i+1}(i + 1)t^{i}d^{(i)}(t) + S_{m,i+1}t^{i+1}d^{(i+1)}(t)]

= ∑_{i=0}^{m−1} S_{m,i+1}(i + 1)t^{i}d^{(i)}(t) + ∑_{i=1}^{m} S_{m,i}t^{i}d^{(i)}(t)

= S_{m,1}d(t) + S_{m,m}d^{(m)}(t) + ∑_{i=1}^{m−1}[S_{m,i+1}(i + 1) + S_{m,i}]t^{i}d^{(i)}(t)

= ∑_{i=0}^{m} S_{m+1,i+1}t^{i}d^{(i)}(t)

The last equality uses the Stirling recurrence S_{m+1,i+1} = (i + 1)S_{m,i+1} + S_{m,i}, and the fact that S_{m,1} = S_{m+1,1} = S_{m,m} = S_{m+1,m+1} = 1.

The second equality follows from the observation that

∑_{j=0}^{m} S_{m+1,j+1}t^{j}d^{(j)}(t) = ∑_{j=0}^{m} S_{m+1,j+1} ∑_{i≥0} d_{i} \frac{i!}{(i − j)!}t^{i}

= ∑_{i≥0} d_{i} (∑_{j=0}^{m} S_{m+1,j+1} \frac{i!}{(i − j)!}) t^{i}

= ∑_{i≥0} d_{i}(i + 1)^{m}t^{i}.

For the final equality above, take the well-known identity [20, Eqn. (1.94d)] which counts functions from a set of size (m + 1) to a set of size (i + 1) according to the size (j + 1) of the image, namely

(i + 1)^{m+1} = ∑_{j=0}^{m}(j + 1)!\binom{i + 1}{j + 1}S_{m+1,j+1} = ∑_{j=0}^{m} \frac{(i + 1)!}{(i − j)!}S_{m+1,j+1},

and divide throughout by (i + 1).

Corollary 38. For any Riordan array R = R(d(t), t) in the Appell subgroup and m ≥ 0, we have

Der^{2m}(R)_{n,k} = d_{n−k}(n − k + 1)^{m}.

Corollary 39. If Der^{2m}(R(d(t), t)) maps the sequence (a_{n})_{n≥0} to the sequence (b_{n})_{n≥0}, then

b_{n} = ∑_{k≥0} a_{k}d_{n−k}(n − k + 1)^{m}.

The operation Der can be given a combinatorial interpretation when applied to an element in the Appell subgroup.

Theorem 40. Let d(t) = d_{0} + d_{1}t + d_{2}t^{2} + · · ·. Then Der(R(d(t), t))_{n,k} is the number of weighted compositions of n with k parts, where part i has weight d_{i−1}.

Proof. The following computation yields the result.

Der(R(d(t), t))_{n,k} = R(1, td(t))_{n,k}

= [t^{n}] t^{k}d(t)^{k}

= [t^{n}] (d_{0}t + d_{1}t^{2} + d_{2}t^{3} + ⋯)^{k}

= [t^{n}] ∑_{m≥0} ∑_{\begin{matrix}c_{1}+c_{2}+···+c_{k}=m \\ c_{1},c_{2},...,c_{k}∈ℤ_{+} \end{matrix}} d_{c_{1}−1}d_{c_{2}−1} ⋯ d_{c_{k}−1}t^{c_{1}}t^{c_{2}} ⋯ t^{c_{k}}

= ∑_{\begin{matrix}c_{1}+c_{2}+···+c_{k}=n \\ c_{1},c_{2},...,c_{k}∈ℤ_{+} \end{matrix}} d_{c_{1}−1}d_{c_{2}−1} ⋯ d_{c_{k}−1}.

5 Applications

In this section we investigate applications of the results in Section 4 to well-known Riordan arrays. In particular, we apply Der and Flip to the Fibonacci array, Pascal array, Catalan array, and Shapiro array. In the process, we obtain various combinatorial identities.

5.1 The Fibonacci array

We begin with a case in the Appell subgroup. Let T = R(1 + t, t), and define Fib := Der(T) = R(1, t + t^{2}). The Riordan array Fib is known as the Fibonacci array, as its row sums give the Fibonacci sequence. Indeed, using Lemma 33, we see that the row sums of Fib have generating function 1/(1 − t − t^{2}), which is the generating function for the Fibonacci sequence. The (n, k)-entry in Fib is given by

Fib_{n,k} = [t^{n−k}](1 + t)^{k} = \binom{k}{n − k}, n ≥ k ≥ 0.  (14)

T = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 1 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 1 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 1 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] , Fib = R(1, t + t^{2}) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 2 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 1 & 3 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 3 & 4 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

Furthermore, Der^{2}(T) = R(1 + 2t, t) and Der^{3}(T) = R(1, t + 2t^{2}) are the following Riordan arrays.

Der^{2}(T)=[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 2 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 2 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 2 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}], Jac := Der^{3}(T)=[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 4 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 4 & 6 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 12 & 8 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Note that by Theorem 2, Der^{2}(T) has row sums (1, 3, 3, …) with generating function (1 + 2t)/(1 − t), while the row sums of Der^{3}(T) have generating function 1/(1 − t − 2t^{2}). The latter is the generating function for the Jacobsthal numbers \underline{A001045} (without the leading zero), which are recursively defined by a_{n} = a_{n−1} + 2a_{n−2} with initial values a_{0} = a_{1} = 1. For this reason we define Jac := Der^{3}(T) to be the Jacobsthal array.

We also observe that • Flip(Der(T))) = Flip(Fib) = Flip(R(1, t + t^{2})) = T, and

• Flip(Der^{3}(T)) = Flip(Jac) = Flip(R(1, t + 2t^{2})) = Der^{2}(T).

Since Jac = R(1, t(1 + 2t)), we have that Jac_{n,k} = [t^{n−k}](1 + 2t)^{k} = 2^{n−k}\binom{k}{n−k}. The (n + 1)-st Jacobsthal number is thus ∑_{k=0}^{n} 2^{n−k}\binom{k}{n−k}. On the other hand, the generating function 1/(1 − t − 2t^{2}) = 1/((1 + t)(1 − 2t)) gives the explicit formula J_{n} = \frac{1}{3}(2^{n+1} + (−1)^{n}) for the nth Jacobsthal number. These identities can be found under sequence \underline{A001045}.

We give a bijective proof of the following combinatorial interpretation of the Jacobsthal numbers in terms of pattern avoidance.

Theorem 41. Let D_{n}(231, 132) be the set of derangements of length n avoiding the patterns 231 and 132. If J_{n} denotes the nth Jacobsthal number, then

J_{n+1} = ∑_{k=0}^{n} 2^{n−k}\binom{k}{n − k} = |D_{n+2}(231, 132)|.

Proof. (Combinatorial) First, note that every π ∈ D_{n+2}(231, 132) must begin with n+2 since if we have elements both before and after n + 2, then a forbidden pattern will be formed. Furthermore, n + 2 cannot be at the last position, as π is a derangement. In addition, to avoid 231 and 132, all the numbers preceding 1 in π must be in decreasing order and all the numbers following 1 in π must be in increasing order. For example, 53124 ∈ D_{5}(231, 132). This implies that there is a unique index i ≥ 2, such that π_{i} < i and π_{j} > j for j = 1, …, i−1. For a fixed i, we have that the numbers π_{2}, …, π_{i−1} are i − 2 numbers in decreasing order among i, i+1, …, n+1. Thus, we can select these i−2 numbers and determine the segment π_{2} ⋯ π_{i−1} in \binom{(n+1)−(i−1)}{i−2} = \binom{n+2−i}{i−2} ways. The non-selected numbers in \{i, i + 1, …, n + 1\} must be in increasing order at the end of π. What remains is to determine the positions of i − 1, …, 2, 1. Note that if we do this sequentially for each of the listed numbers, every time we will have exactly two choices for that position - the leftmost or the rightmost unoccupied position in the permutation. The only exception is the position of 1 for which we will have only one possible choice at the end. Hence we shall multiply by 2^{i−2}. For instance, when n = 3 and i = 3, we will have \binom{5−3}{1}2^{1} such permutations in D_{5}(231, 132): 54123, 54213, 53124, 53214. The number at position 2, i.e., π_{2} is determined in \binom{5−3}{1} = 2 ways since it can be 3 or 4. If, for example, π_{2} = 3, then the number 4 must be at the last position, i.e., π_{5} = 4. Then, we have 2 choices for the position of the number 2 - either after 3 or before 4. The number 1 must be at the last unoccupied position. Note that by following this simple algorithm for construction of π, we always obtain a derangement. Summing over the possible values of i, we get

|D_{n+2}(231, 132)| = ∑_{i=2}^{n+2} \binom{n + 2 − i}{i − 2}2^{i−2} = ∑_{j=0}^{n} \binom{n − j}{j}2^{j} = ∑_{k=0}^{n} 2^{n−k}\binom{k}{n − k},

as claimed.

Applying Theorem 40 to R(1 + ct, t) shows that the previous identity is a special case of the following.

Identity 42. Let a_{n} denote the number of compositions of n using parts 1 and 2, with c available colors for the 2’s. Then

a_{n} = ∑_{k≥0} c^{n−k}\binom{k}{n − k}.

Proof. There are \binom{k}{n−k} compositions of n with k parts from \{1, 2\} of which n − k are 2’s. We have c^{n−k} ways to color these 2’s. Summing over the possible number of parts gives the result.

5.2 The Pascal array

The Pascal array Pas and its inverse Pas^{−1} are the Riordan arrays

Pas = R (\frac{1}{1 − t}, \frac{t}{1 − t})  and  Pas^{−1} = R (\frac{1}{1 + t}, \frac{t}{1 + t}) .

Their general terms are given by Pas_{n,k} = \binom{n}{k} and Pas_{n,k}^{−1} = (−1)^{n−k}\binom{n}{k} respectively.

Recall [12, Sec. 1.3] that the Eulerian number A(n, k) counts the number of permutations on n letters with exactly k descents, where i is a descent of a permutation σ on n letters if and only if σ(i) > σ(i + 1), 1 ≤ i ≤ n − 1. Let des(σ) denote the number of descents of the permutation σ. The generating function for the Eulerian numbers {A(n, k)}_{k=0}^{n−1} is the Eulerian polynomial A_{n}(t) := ∑_{σ∈S_{n}} t^{des(σ)} = ∑_{k=0}^{n−1} A(n, k)t^{k}, n ≥ 1. We define A_{0}(t) := 1. Thus A_{1}(t) = 1, A_{2}(t) = 1 + t, A_{3}(t) = 1 + 4t + t^{2}, A_{4}(t) = 1 + 11t + 11t^{2} + t^{3}. ^{1}

We have the following recurrence [12, Thm. 1.4] for the Eulerian polynomials:

A_{n+1}(t) = (1 + nt)A_{n}(t) + t(1 − t)A′_{n}(t).  (15)

Theorem 43. Let A_{i}(t) denote the ith Eulerian polynomial. For each i ≥ 0, we have

Der^{2i}(Pas) = R (\frac{A_{i}(t)}{(1 − t)^{i+1}} , \frac{tA_{i}(t)}{(1 − t)^{i+1}} ) ,
Der^{2i+1}(Pas) = R (\frac{A_{i+1}(t)}{(1 − t)^{i+2}} , \frac{tA_{i}(t)}{(1 − t)^{i+1}} ) ,
Der^{2i}(Pas^{−1}) = R (\frac{A_{i}(−t)}{(1 + t)^{i+1}} , \frac{tA_{i}(−t)}{(1 + t)^{i+1}} ) ,
Der^{2i+1}(Pas^{−1}) = R (\frac{A_{i+1}(−t)}{(1 + t)^{i+2}} , \frac{tA_{i}(−t)}{(1 + t)^{i+1}} ) .

1Note: Stanley [20, Sec. 1.4] and others define the Eulerian polynomial to be ∑_{σ∈S_{n}} t^{1+des(σ)} = t · A_{n}(t).

Proof. Using the well-known generating function [12, Cor. 1.1]

∑_{k=0}^{∞} k^{i}t^{k} = \frac{tA_{i}(t)}{(1 − t)^{i+1}}  (16)

we observe that

\frac{d}{dt} (\frac{tA_{i}(t)}{(1 − t)^{i+1}} ) = ∑_{k=1}^{∞} k^{i+1}t^{k−1} = \frac{A_{i+1}(t)}{(1 − t)^{i+2}} .

The equations for the derivatives of Pas and Pas^{−1} then follow readily by induction on i. Example 44.

Der(Pas) = R (\frac{1}{(1 − t)^{2}} , \frac{t}{1 − t}) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & ⋯ \\ 3 & 3 & 1 & 0 & 0 & ⋯ \\ 4 & 6 & 4 & 1 & 0 & ⋯ \\ 5 & 10 & 10 & 5 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

Der^{2}(Pas) = R (\frac{1}{(1 − t)^{2}} , \frac{t}{(1 − t)^{2}} ) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & ⋯ \\ 3 & 4 & 1 & 0 & 0 & ⋯ \\ 4 & 10 & 6 & 1 & 0 & ⋯ \\ 5 & 20 & 21 & 8 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

Flip(Der(Pas)) = R (\frac{1}{1 − t}, \frac{t}{(1 − t)^{2}} ) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 3 & 1 & 0 & 0 & ⋯ \\ 1 & 6 & 5 & 1 & 0 & ⋯ \\ 1 & 10 & 15 & 7 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

We can compute the general terms of these Riordan arrays to be

Der(Pas)_{n,k} = \binom{n + 1}{k + 1}, Der^{2}(Pas)_{n,k} = \binom{n + k + 1}{n − k}, Flip(Der(Pas))_{n,k} = \binom{n + k}{2k}.

Using Lemma 33, the row sums of Der^{2}(Pas) and Flip(Der(Pas)) have the generating functions

\frac{1}{1 − 3t + t^{2}} and \frac{1 − t}{1 − 3t + t^{2}} ,

respectively. These are well known to be the generating functions for the two bisections of the Fibonacci sequence, ∑_{n≥0} F_{2n+1}t^{n}, i.e., (1, 3, 8, 21, …), and ∑_{n≥0} F_{2n}t^{n}, i.e., (1, 2, 5, 13, …). See also Example 7.

Similarly, the alternating row sums have generating functions as follows.

For Pas itself, the alternating row sum generating function is 1, reflecting the fact that the alternating sum of the binomial coefficients in the nth row of Pascal’s triangle is 0 for n ≥ 1. Note that the alternating row sums of Pas are the row sums of Pas^{−1}.

For Der(Pas), it is 1/(1 − t), i.e., the alternating sum in each row is 1.

For Der^{2}(Pas), it is (1 + t)/(1 + t^{3}), and hence the alternating sum along the nth row is ∑_{n≥0}(t^{3n} + t^{3n+1}), i.e., it equals

\begin{cases}(−1)^{⌊m/3⌋}, & if m ≡ 0, 1 (mod 3), \\ 0, & otherwise. \end{cases}

For Flip Der(Pas)), it is (1 − t^{2})/(1 + t^{3}), and hence the alternating sum along the nth row equals

(−1)^{\frac{m}{3}} , if m is divisible by 3,
(−1)^{\frac{m+1}{3}} , if m + 1 is divisible by 3,
0,  otherwise.

Definition 45. [4] Define the INVERT transform of the sequence (a_{n})_{n≥1} to be the sequence (b_{n})_{n≥1} where

1 + ∑_{n≥1} b_{n}t^{n} = (1 − ∑_{n≥1} a_{n}t^{n})^{−1}.

We have the following interesting relationship between the even derivatives of the Riordan array Pas and the INVERT transform of the sequence of nth powers of the positive integers for fixed n.

Proposition 46. Let n be a fixed positive integer. Suppose the sequence (b_{k})_{k≥1} is the INVERT transform of the sequence (k^{n})_{k≥1}. Then the generating function for the row sums of Der^{2n}(Pas) is

∑_{k≥0} b_{k+1}t^{k}.

Proof. By definition, we have

\frac{1}{1 − ∑_{k≥1} k^{n}t^{k}} = 1 + ∑_{k≥1} b_{k}t^{k}.

From Theorem 43, we have

Der^{2n}(Pas) = R (\frac{A_{n}(t)}{(1 − t)^{n+1}} , \frac{tA_{n}(t)}{(1 − t)^{n+1}} ) = R (∑_{k≥1} k^{n}t^{k−1}, ∑_{k≥1} k^{n}t^{k}) .

Write f_{n}(t) = ∑_{k≥1} k^{n}t^{k}. The generating function for row sums is thus

\frac{t^{−1}f_{n}(t)}{1 − f_{n}(t)} = t^{−1} (\frac{1}{1 − f_{n}(t)} − 1) = t^{−1} (∑_{k≥1} b_{k}t^{k}) ,

which equals ∑_{j≥0} b_{j+1}t^{j}, as claimed.

Example 47. The generating functions of the first few row sums of Der^{m}(Pas) for even values of m, together with the relevant sequences in OEIS, are as follows.

Der^{2}(Pas) : row sum generating function \frac{1}{1 − 3t + 2t^{2}} . (\underline{A000225})

Der^{4}(Pas) : row sum generating function \frac{1 + t}{1 − 4t + 2t^{2} − t^{3}} . (\underline{A033453})

Der^{6}(Pas) : row sum generating function \frac{1 + 4t + t^{2}}{1 − 5t + 2t^{2} − 5t^{3} + t^{4}} . (\underline{A144109})

Many other connections appear to hold. For instance, the generating function for the row sums of Der^{3}(Pas) is

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

which is two less than the bisection of Lucas numbers \underline{A004146}.

The row sums of Der^{2}(Pas) + Der^{3}(Pas) have generating function 2/(1 − 4t + 4t^{2} − t^{3}), and are twice the sequence \underline{A027941} of the odd Fibonacci minus one: (F_{2n+1} − 1)_{n=0}^{∞}.

More generally, one can add the (2i)th and (2i + 1)th derivatives, since they have the same h(t). The sum is the Riordan array R(∑_{ℓ≥0}((ℓ + 1)^{i} + ℓ^{i+1})t^{ℓ}, ∑_{ℓ≥1} ℓ^{i}t^{ℓ}), and the row sum generating function in terms of the Eulerian polynomials is

\frac{(1 − t)A_{i}(t) + A_{i+1}(t)}{(1 − t)^{i+2} − tA_{i}(t)}.

A similar formula can be computed for the row sum generating function of the sum

Flip(Der^{2n−1}(Pas)) + Der^{2n}(Pas).

5.3 The Catalan array

Let C(t) denote the generating function ∑_{n≥0} C_{n}t^{n} for the Catalan numbers. The defining equation for C(t) is

tC^{2}(t) − C(t) + 1 = 0,

giving the well-known [22] formula

C(t) = \frac{1 − \sqrt{1 − 4t}}{2t}, and hence also C(t) − 1 = \frac{1 − 2t − \sqrt{1 − 4t}}{2t}.

Recall that the Catalan array Cat is the Riordan array defined by

Cat := R(C(t), tC(t)).  (17)

Its inverse Cat^{−1} is [9, Thm. 5.2]

Cat^{−1} = R(1 − t, t − t^{2}).  (18)

From Luzón et al. [9, Thm. 5.2 and 5.3], we have Cat_{n,k}^{−1} = (−1)^{n−k}\binom{k+1}{n−k} and hence

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

Theorem 48. For the Catalan array Cat = R(C(t), tC(t)) we have

Der(Cat) = R (\frac{1}{\sqrt{1 − 4t}}, \frac{1 − \sqrt{1 − 4t}}{2}) and (Der(Cat))^{−1} = R (1 − 2t, t − t^{2}) ,

and hence

Der(Cat)_{n,k} = \binom{2n − k}{n − k}.

Proof. We mimic the ingenious method of Merlini and Sprugnoli [10]. Using Theorem 3, we first calculate the inverse array R = (Der(Cat))^{−1} of Der(Cat). Then we apply Theorem 6 to compute the (n, k)-entry of the inverse of R, which is of course precisely the (n, k)-entry of Der(Cat).

This scheme exploits the fact that the inverse of Der(Cat) involves only simple polynomials, and hence its entries are easier to compute.

From the defining recurrence tC^{2}(t) = C(t) − 1, we observe that

(0) t C(t) = \frac{1−\sqrt{1−4t}}{2} = \frac{2t}{1+\sqrt{1−4t}};

1. \frac{d}{dt}(t C(t)) = \frac{1}{\sqrt{1−4t}};

2. the compositional inverse of t C(t) is t − t^{2}, and

3. \frac{d}{dt}(t C^{2}(t)) = C′(t).

Hence we have Der(Cat) = R(d^{∗}(t), h^{∗}(t)), where d^{∗}(t) = (\sqrt{1 − 4t})^{−1} and h^{∗}(t) = tC(t), and therefore \overline{h}^{∗}(t) = t − t^{2}. Clearly

\frac{1}{d^{∗}(t − t^{2})} = 1 − 2t = \overline{h}^{∗}′(t),

and hence the inverse of Der(Cat) is R(d(t), h(t)) where d(t) = 1 − 2t and h(t) = t − t^{2} = \overline{h}^{∗}(t). Now apply Theorem 6, noting that h(t)/t = 1 − t and d(t) = h′(t) in this case. Extracting the (n, k)-entry of Der(Cat) can now be done using Definition 1.

Example 49. The compositional inverse of tC(t) is t − t^{2} from above, and hence by Theorem 4, the generating function for the A-sequence of both Der(Cat) and Flip(Cat) is t/(t − t^{2}) = 1/(1 − t).

Recall [20] that a weak composition of a nonnegative integer m is a finite sequence of nonnegative integers whose sum is m.

Corollary 50. For each fixed k ≥ 0,

C^{k}(t) = \sqrt{1 − 4t} ∑_{n≥k} \binom{2n − k}{n}t^{n−k},  (19)

or equivalently

C^{k}(t) ∑_{n≥0} \binom{2n}{n}t^{n} = ∑_{n≥k} \binom{2n − k}{n}t^{n−k}.  (20)

See Stanley [22, Exercise A.32 (a), (b)] for (19) and also for the power series for C^{k}(t). This gives the following identity.

Identity 51.

∑_{I} \binom{2i_{0}}{i_{0}}C_{i_{1}}C_{i_{2}} … C_{i_{k}} = \binom{2n − k}{n},

where the sum on the left runs over all weak compositions I = (i_{0}, i_{1}, … i_{k}) of n − k, for fixed k ≥ 0.

From Theorem 48 we know that Der(Cat)_{n,k} = \binom{2n−k}{n−k}. Lemma 33 gives, for the row sums, the generating function

\frac{1 − \sqrt{1 − 4t}}{2t\sqrt{1 − 4t}} = \frac{1}{2} ∑_{n≥0} \binom{2(n + 1)}{n + 1}t^{n}.

In particular, the nth row sum of Der(Cat) is \frac{1}{2} \binom{2(n+1)}{n+1} = \frac{n+2}{2} · C_{n+1}.

Another Riordan array related to the Catalan numbers is the Shapiro array [10] Sha = R(C(t), tC^{2}(t)) = R(C(t), C(t) − 1). We will consider the Shapiro array in more detail in Section 5.4, but for now we recall [10, 13] the following property of the Shapiro array:

Sha ·(1, 3, 5, 7, …)^{t} = (1, 4, 4^{2}, 4^{3}, …)^{t}.

See Merlini and Sprugnoli [10, Thm. 2.1] for a combinatorial proof. We obtain an analogous result for Der(Cat), as Theorem 2 now tells us that Der(Cat) transforms powers of 2 into powers of 4:

Der(Cat) · (1, 2, 2^{2}, 2^{3}, …)^{t} = (1, 4, 4^{2}, 4^{3}, …)^{t}.

Hence we have the following.

Identity 52.

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

Proof. (Combinatorial) We can rewrite the first equation as

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

Then we can proceed as in the proof of Identity 60.

Similarly, since the sequence (n+1)_{n=0}^{∞} has generating function (1−t)^{−2}, Theorem 2 tells us that the generating function for Der(Cat) · (1, 2, 3, 4, 5, …)^{t} is

\frac{1}{\sqrt{1 − 4t}} (1 − \frac{1 − \sqrt{1 − 4t}}{2})^{−2} = \frac{(1 − 2t) + \sqrt{1 − 4t}}{2t^{2}\sqrt{1 − 4t}} = \frac{1}{2t^{2}} ((1 − 2t) ∑_{n≥0} \binom{2n}{n}t^{n} − 1) ,

and hence the coefficient of t^{n}, n ≥ 0, is \binom{2n+2}{n}. We therefore obtain:

Identity 53.

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

Proof. (Combinatorial) Rewrite the identity as

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

The right-hand side counts all of the subsets of [2n + 2] with exactly n + 2 elements, which do not contain both 2n + 1 and 2n + 2. Thus, each such subset A contains at least n + 1 numbers in [2n]. Let the (n+1)th largest number in A be 2n−k +1, where k can be between 1 and n. The smallest n numbers in A can be chosen in \binom{2n−k}{n} ways and the largest number in A can be chosen in (k + 1) ways.

Combining the expression for the row sums of Der(Cat) with the preceding sum (simply using 2k +1 = 2(k +1)−1) we can conclude that the nth term of Der(Cat)·(1, 3, 5, 7, 9, …)^{t} equals \frac{3n+2}{n+2} \binom{2n+1}{n+1}, which counts the number of positive clusters of Type D_{n+2} [7]. Thus we obtain the following.

Identity 54.

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

Proof. (Combinatorial)

Subtracting the previous Identity 53 and using \binom{2n+2}{n+2} = \frac{2n+2}{n+2} \binom{2n+1}{n+1}, we see that it suffices to prove the following:

∑_{k≥1} k\binom{2n − k}{n} = ∑_{k≥1} k\binom{2n − k}{n − k} = \frac{n}{n + 2}\binom{2n + 1}{n + 1} = \binom{2n + 1}{n + 2}.

Now consider a choice of n + 2 numbers out of 2n + 1 numbers labeled with 1, 2, …, 2n + 1 and let 2n − k + 1 be the second largest label of a selected number. Note that k ≥ 1. Out of the numbers with labels 1, 2, … 2n − k, exactly n must be selected and this can happen in \binom{2n−k}{n} ways. The selected number with the largest label can be chosen in k different ways since its label can be each of 2n − k + 2, 2n − k + 3, … 2n + 1.

The right-hand side is the sequence \underline{A129869}. Note that this is also the total number of all pure descents [1] whereas the right-hand side of Identity 60 equals the total number of inversions in all 321-avoiding permutations of length n.

Next we apply Der again to Der(Cat), obtaining

Der^{2}(Cat) = R (\frac{1}{\sqrt{1 − 4t}}, \frac{t}{\sqrt{1 − 4t}}) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 6 & 4 & 1 & 0 & 0 & 0 & ⋯ \\ 20 & 16 & 6 & 1 & 0 & 0 & ⋯ \\ 70 & 64 & 30 & 8 & 1 & 0 & ⋯ \\ 252 & 256 & 140 & 48 & 10 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The Riordan array Der^{2}(Cat) is also of combinatorial interest, as its (n, k)-entries count certain lattice paths as described by the following theorem. The number of such paths is given by \underline{A026671}.

Theorem 55. Let a_{n} denote the number of lattice paths from (0, 0) to (n, n) with steps (0, 1), (1, 0) and, when on the diagonal, (1, 1). If a_{n,k} denotes the number of such paths with exactly k diagonal steps, then

Der^{2}(Cat)_{n,k} = a_{n,k} = 4^{n−k}\binom{n − \frac{k+1}{2}}{n − k}

and

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

Proof. First note that by definition, we have

Der^{2}(Cat)_{n,k} = [t^{n−k}] (\frac{1}{\sqrt{1 − 4t}} · (\frac{1}{\sqrt{1 − 4t}})^{k}) = [t^{n−k}](1 − 4t)^{− \frac{k+1}{2}} ,

and hence

Der^{2}(Cat)_{n,k} = (−4)^{n−k}\binom{−\frac{k+1}{2}}{n − k}

which is as claimed, using the well-known formula \binom{−m}{j} = (−1)^{j}\binom{m+j−1}{j}.

Now we observe that the first column of Der^{2}(Cat) consists of the central binomial coefficients, as it has generating function 1/\sqrt{1 − 4t}. The central binomial coefficients count the number of lattice paths from (0, 0) to (n, n) using no diagonal steps, so Der^{2}(Cat)_{n,0} = a_{n,0}. We fix n and proceed by induction on k. Assume Der^{2}(Cat)_{n,k−1} = a_{n,k−1}. Then we have, for k ≥ 1,

Der^{2}(Cat)_{n,k} = [t^{n}] (\frac{1}{\sqrt{1 − 4t}} · (\frac{t}{\sqrt{1 − 4t}})^{k})

= [t^{n−1}] (\frac{1}{\sqrt{1 − 4t}} · \frac{1}{\sqrt{1 − 4t}} · (\frac{t}{\sqrt{1 − 4t}})^{k−1})

= ∑_{i=0}^{n−1} a_{i,0} Der^{2}(Cat)_{n−1−i,k−1}

= ∑_{i=0}^{n−1} a_{i,0}a_{n−i−1,k−1}.

The set of lattice paths with k steps of the form (1, 1) on the diagonal can be partitioned according to where their final diagonal step lies. Let L_{i} denote the set of lattice paths whose first diagonal step is the step from (i, i) to (i + 1, i + 1). The lattice paths in L_{i} then consist of the paths of the form P_{1}DP_{2}, where P_{1} is a path to (i, i) with no diagonal steps, D is the first diagonal step in the path, and P_{2} is a path of length n − i − 1 with k − 1 steps on the diagonal. The paths in L_{i} are thus counted by a_{i,0}a_{n−i−1,k−1}. Summing over all i gives a_{n,k}, as desired.

Applying Flip to Der(Cat) yields

Flip(Der(Cat)) = R (\frac{1 − \sqrt{1 − 4t}}{2t}, \frac{t}{\sqrt{1 − 4t}}) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 5 & 10 & 5 & 1 & 0 & 0 & ⋯ \\ 14 & 35 & 22 & 7 & 1 & 0 & ⋯ \\ 42 & 126 & 93 & 38 & 9 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The row sums of Flip(Der(Cat)) are given by the generating function

\frac{1 − 4t − \sqrt{1 − 4t}}{2t(t − \sqrt{1 − 4t})} = \frac{1 − 5t + 4t^{2} − (1 − 5t)\sqrt{1 − 4t}}{2t(1 − 4t − t^{2})}.

This is the generating function for \underline{A026737}, which is the number of permutations avoiding the patterns {3241, 3421, 4321}.

Noting that

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

we can use Theorem 55 to obtain the following identity.

Identity 56. Let b_{n} denote the number of permutations of length n+1 avoiding the patterns {3241, 3421, 4321}. Then

b_{n} = 2 ∑_{k=0}^{n} 4^{n−k}\binom{n − \frac{k+1}{2}}{n − k} − ∑_{i=0}^{n} (C_{n−i} · ∑_{j=0}^{i} 4^{i−j}\binom{i − \frac{j+1}{2}}{i − j}) .

5.4 The Shapiro array

The Shapiro array is the Riordan array Sha defined as follows.

Sha := R(C(t), tC^{2}(t)) = R(C(t), C(t) − 1) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 2 & 3 & 1 & 0 & 0 & ⋯ \\ 5 & 9 & 5 & 1 & 0 & ⋯ \\ 14 & 28 & 20 & 7 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Its inverse Sha^{−1} is [10, Thm. 3.1]

Sha^{−1} = R (\frac{1}{1 + t}, \frac{t}{(1 + t)^{2}} ) .

Now Sha_{n,k}^{−1} = (−1)^{n−k}\binom{n+k}{n−k} [10, Eqn. 3.8] and hence

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

Sha ·(1, 1, 2, 5, 14, …)^{t} is known (see \underline{A007852}) to give the sequence (a_{n})_{n≥0} := (1, 2, 7, 29, 131, 625, 3099, …), where a_{n} is the number of antichains in a rooted plane tree on n nodes.

We obtain the following known expression for a_{n}.

Identity 57.

a_{n} = ∑_{k≥0} \frac{2k + 1}{n + k + 1}\binom{2n}{n − k} · C_{k} = ∑_{k≥0} \frac{1}{2n + 1}\binom{2n + 1}{n − k}\binom{2k + 1}{k}

Let us now consider

Der(Sha) = R(C′(t), tC(t)) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 4 & 1 & 0 & 0 & 0 & ⋯ \\ 15 & 5 & 1 & 0 & 0 & ⋯ \\ 56 & 21 & 6 & 1 & 0 & ⋯ \\ 210 & 84 & 28 & 7 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Theorem 58. For the Shapiro array Sha = R(C(t), tC^{2}(t)):

Der(Sha) = R(C′(t), tC(t)) and (Der(Sha))^{−1} = R((1 − t)^{2}(1 − 2t), t − t^{2}),

and hence

Der(Sha)_{n,k} = \binom{2n − k + 2}{n − k}.

Proof. The proof follows along the lines of Theorem 48. The derivation for the (n, k)th entry of Der(Sha) is as follows. Let Der(Sha) = R(d^{∗}(t), h^{∗}(t)) where

d^{∗}(t) = C′(t) = \frac{1 − 2t − \sqrt{1 − 4t}}{2t^{2}\sqrt{1 − 4t}}, h^{∗}(t) = t C(t).

Now we compute

\frac{1}{d^{∗}(t − t^{2})} = \frac{1}{C′(t − t^{2})} = (1 − t)^{2}(1 − 2t),

and the claims follow as before from Theorem 6. Once more, Equation (21) follows using Definition 1.

This implies that, for each fixed k ≥ 0,

C^{k+2}(t) = 2\sqrt{1 − 4t} ∑_{n≥k} \binom{2n − k + 2}{n + 2}t^{n−k+1},  (21)

or equivalently

C^{k+2}(t) ∑_{n≥0} \binom{2n}{n}t^{n} = 2 ∑_{n≥k} \binom{2n − k + 2}{n + 2}t^{n−k+1}.  (22)

From (21) and the power series for C^{k}(t) we then obtain the following.

Identity 59.

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

where the sum on the left runs over all weak compositions I = (i_{0}, i_{1}, … i_{k+2}) of n − k + 1, for fixed k ≥ 0.

Using Theorem 2, we see that the product Der(Sha) · (2^{i})_{i≥0}^{t} gives a sequence whose generating function is

C′(t)\frac{1}{1 − (1 − \sqrt{1 − 4t})} = \frac{1 − 2t − \sqrt{1 − 4t}}{2t^{2}(1 − 4t)} = \frac{C(t) − 1}{t(1 − 4t)}.

Note this is the generating function for the convolution of the Catalan numbers shifted by one, and the powers of 4, i.e., for the sequence whose nth term is ∑_{k=1}^{n} C_{k+1}4^{n−k}. Using Theorem 58 we obtain the identity

Identity 60.

∑_{k≥0} 2^{k} Der(Sha)_{n,k} = 4^{n+1} − \binom{2n + 3}{n + 1}

or

∑_{k≥0} 2^{k}\binom{2n − k + 2}{n − k} = 4^{n+1} − \binom{2n + 3}{n + 1}

Proof. (Combinatorial) Rewrite the identity in the form

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

The right-hand side counts all of the subsets of [2n + 2], which do not have n, n + 1 or n + 2 elements. We let A denote this set of subsets. We will show that the subsets in A are counted by the left-hand side. First, note that for each subset in A, either n + 3 or more of the all 2n + 2 elements are selected or n + 3 or more of these elements are not selected. The number of subsets in these two groups is equal, so it suffices to count the subsets Q ∈ A with at least n + 3 elements and multiply their number by 2.

Let k be the largest number such that [2n + 3 − k] contains n + 3 of the elements in Q. The possible values of k are between 1 and n. Obviously, the element 2n + 3 − k ∈ Q since k is the largest with this property. Thus, to determine Q, we shall select the n + 2 elements in [2n + 2 − k], which are elements of Q. This can be done in \binom{2n−k+2}{n+2} ways. In addition, Q can contain any of the 2^{k−1} subsets of {2n + 4 − k, 2n + 5 − k, …, 2n + 2}.

Note that the right-hand side of Identity 60 equals the total number of inversions in all 321-avoiding permutations of length n, as well as the sum of the areas of all Dyck paths of semilength n [5].

6 Future directions

In this article, we introduced and explored sums, derivatives, and flips of Riordan arrays. Using these operations, we obtained several combinatorial identities. We only studied the effects of these operations on a small subset of Riordan arrays, thereby merely scratching the surface of possible identities obtainable using these operations. Furthermore, we considered only ordinary generating functions. A natural future direction is therefore to extend our results to the setting of exponential generating functions. It would also be interesting to know if the second order recurrence of Theorem 26 gives rise to combinatorially meaningful identities.

7 Acknowledgments

This project was carried out as part of the 2021 Graduate Research Workshop in Combinatorics. We thank the organizers for their generous support of a valuable collaborative research experience. We also thank Matt Hudelson for completing the proof of Theorem 14.

Caroline Bang thanks the National Science Foundation for support through grant DMS-1839918.

References

[1] J. L. Baril and S. Kirgizov, The pure descent statistic on permutations, Discrete Math. 340 (2017), 2550–2558.

[2] P. Barry, Riordan Arrays: A Primer, Logic Press, 2017

[3] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art Of Combinatorial Proof, American Mathematical Society, 2022.

[4] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226 (1995), 57–72.

[5] W. Y. Chen, E. Y. Deng, and L. L. Yang, Riordan paths and derangements, Discrete Math. 308 (2008), 2222–2227.

[6] S. E. Cheng, S. P. Eu, and T. S. Fu, Area of Catalan paths on a checkerboard, European J. Combin. 28 (2007), 1331–1344.

[7] S. Fomin and A. Zelevinsky, Y -systems and generalized associahedra, Ann. of Math. 158 (2003), 977–1018.

[8] T. X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), 3962–3974.

[9] A. Luzón, D. Merlini, M. A. Morón, and R. Sprugnoli, Identities induced by Riordan arrays, Linear Algebra Appl. 436 (2012), 631–647.

[10] D. Merlini and R. Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, Discrete Math. 340 (2017), 160–174.

[11] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (1997), 301–320.

[12] T. K. Petersen, Eulerian Numbers, Springer, 2015.

[13] C. Radoux, Addition formulas for polynomials built on classical combinatorial sequences, J. Comput. Appl. Math. 115 (2000), 471–477.

[14] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

[15] L. W. Shapiro, Bijections and the Riordan group, Theoret. Comput. Sci. 307 (2003), 403–413.

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

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

[18] R. Sprugnoli, An Introduction to Mathematical Methods in Combinatorics, CreateSpace Independent Publishing Platform, 2014.

[19] R. Sprugnoli, Combinatorial sums through Riordan arrays, J. Geom. 101 (2011), 195– 210.

[20] R. P. Stanley, Enumerative Combinatorics, Vol. 1, second edition, Cambridge University Press, 2011.

[21] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[22] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2020 Mathematics Subject Classification: Primary 05A10. Secondary 05A15, 05A19. Keywords: Riordan array, Catalan number, Dyck path, Fibonacci number, Eulerian polynomial, Stirling number of the second kind, INVERT transform.

(Concerned with sequences \underline{A000007}, \underline{A000012}, \underline{A000027}, \underline{A000032}, \underline{A000045}, \underline{A000108}, \underline{A000225}, \underline{A000302}, \underline{A001006}, \underline{A001045}, \underline{A001070}, \underline{A001350}, \underline{A001519}, \underline{A001629}, \underline{A001700}, \underline{A001906}, \underline{A002054}, \underline{A004146}, \underline{A005043}, \underline{A005408}, \underline{A007598}, \underline{A007852}, \underline{A008549}, \underline{A026671}, \underline{A026737}, \underline{A027941}, \underline{A029907}, \underline{A033453}, \underline{A040000}, \underline{A045925}, \underline{A052952}, \underline{A067324}, \underline{A086615}, \underline{A129869}, \underline{A144109}, and \underline{A152163}.)

Received November 9 2022; revised versions received February 15 2023; February 27 2023. Published in Journal of Integer Sequences, February 28 2023.

Return to Journal of Integer Sequences home page.