On Some (Pseudo) Involutions in the Riordan Group

Naiomi T. Cameron Department of Mathematics Occidental College Los Angeles, CA 90041 USA

                   ncameron@oxy.edu

Asamoah Nkwanta Department of Mathematics Morgan State University Baltimore, MD 21251 USA

               nkwanta@jewel.morgan.edu

Abstract

In this paper, we address a question posed by L. Shapiro regarding algebraic and/or combinatorial characterizations of the elements of order 2 in the Riordan group. We present two classes of combinatorial matrices having pseudo-order 2. In one class, we find generalizations of Pascal’s triangle and use some special cases to discover and prove interesting identities. In the other class, we find generalizations of Nkwanta’s RNA triangle and show that they are pseudo-involutions.

1 Introduction

Briefly, let us describe the Riordan group [14, 15], denoted (R, ∗). An element R ∈ R is an infinite lower triangular array whose k-th column has generating function g(z)f^{k}(z), where k = 0, 1, 2, … and g(z), f(z) are generating functions with g(0) = 1, f(0) = 0. We say R is a Riordan matrix, write R = (g(z), f(z)) and note that g(z) and f(z) are elements of ℂ[[z]].

Multiplication in the Riordan group is matrix multiplication. Since a Riordan group element is determined by a pair of generating functions, it makes sense that the product of Riordan matrices can be described in terms of generating functions. In particular,

(g(z), f(z)) ∗ (h(z), l(z)) = (g(z)h(f(z)), l(f(z)))

It is also not hard to see that the identity element of the Riordan group is (1, z) and that

(g(z), f(z))^{−1} := (\frac{1}{g(f̄(z))}, f̄(z))  (1)

where f̄ is the compositional inverse of f.

One can identify a Riordan matrix by its generating functions or by its dot diagram. A dot diagram is a symbolic representation of the recursions which define the matrix. Rogers and Merlini et. al. [5, 10] showed that every element of a Riordan matrix can be expressed as a linear combination of the elements in the preceding row. Suppose r_{n,k} is the (n, k) entry of R ∈ R. We say that [a_{1}, a_{2}, a_{3}, …; b_{0}, b_{1}, b_{2}, …] is the dot diagram for R if r_{0,0} = g(0) = 1,

r_{n,0} = a_{1} · r_{n−1,0} + a_{2} · r_{n−1,1} + a_{3} · r_{n−1,2} + ⋯ for n ≥ 1

and

r_{n,k} = b_{0} · r_{n−1,k−1} + b_{1} · r_{n−1,k} + b_{2} · r_{n−1,k+1} + ⋯ for n, k ≥ 1.

See [6, 7, 8, 15, 16] for more information regarding the connection between dot diagrams and defining generating functions for Riordan matrices.

When studying any group, it is quite natural to want to classify the elements of finite order. As it turns out, in the case of the Riordan group, any element with integer entries having finite order must have order 1 or 2 [12]. Our goal in this paper is to study the combinatorics of some involutions in the Riordan group. For combinatorial considerations in the Riordan group, it is common to focus on elements with nonnegative integer entries. Since involutions with integer entries necessarily contain negative entries, we direct our attention to pseudo-involutions [3, 12] in order to keep the focus on Riordan matrices with nonnegative entries.

Definition 1. An element R of the Riordan group has pseudo-order 2 if RM has order 2, where M = (1, −z).

A Riordan group element with pseudo-order 2 will be known as a pseudo-involution. Pascal’s triangle P = (\frac{1}{1−z}, \frac{z}{1−z}) \underline{A007318} is an example of a pseudo-involution, since right multiplying P by M = (1, −z) (i.e., the element with alternating 1’s and -1’s on the diagonal and zeros elsewhere) produces a signed version of Pascal’s triangle (\frac{1}{1−z}, \frac{z}{1−z}) ∗ (1, −z) = (\frac{1}{1−z}, \frac{−z}{1−z}) which is an involution. We can see this using Riordan group multiplication

(\frac{1}{1 − z} , \frac{−z}{1 − z} ) ∗ (\frac{1}{1 − z} , \frac{−z}{1 − z} ) = (\frac{1}{1 − z} · \frac{1}{1 − \frac{−z}{1−z}} , \frac{−\frac{−z}{1−z}}{1 − \frac{−z}{1−z}} )

= (\frac{1}{1 − z} · \frac{1 − z}{1 − z + z} , \frac{−(−z)}{1 − z + z} )
= (1, z)

or by looking at the entries of the matrices, where we see that

[\begin{matrix}1 \\ 1 & −1 \\ 1 & −2 & 1 \\ 1 & −3 & 3 & −1 \\ 1 & −4 & 6 & −4 & 1 \\ 1 & −5 & 10 & −10 & 5 & −1 \\ & & & … \end{matrix} ] [\begin{matrix}1 \\ 1 & −1 \\ 1 & −2 & 1 \\ 1 & −3 & 3 & −1 \\ 1 & −4 & 6 & −4 & 1 \\ 1 & −5 & 10 & −10 & 5 & −1 \\ & & & … \end{matrix} ] = [\begin{matrix}1 \\ 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ & & & … \end{matrix} ] .

Notice that we can express this product of matrices as the following identity:

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

where δ_{n,m} = 1 if n = m and 0 otherwise.

In 2001, Shapiro [12] discussed several examples of nonnegative integer Riordan matrices that have pseudo-order 2, including Pascal’s triangle P = (\frac{1}{1−z}, \frac{z}{1−z}), Nkwanta’s RNA triangle (g(z), zg(z)), where g(z) is defined as in (15), and Aigner’s directed animal matrix (1 + zm, z(1 + zm)), where m(z) is defined as in (3). He also posed the following question: is it the case that any pseudo-order 2 element can be written as RMR^{−1}M, for some R? In Section 2, we will show that for at least one class of pseudo-order 2 elements, the answer is yes. One advantage of this knowledge is that one can verify that an element has pseudoorder 2 by simply verifying that it belongs to this certain class of matrices (without having to compose generating functions through Riordan multiplication). This verification can be done with the generating functions or with the dot diagram of R. Another advantage of this knowledge is that we can obtain a number of interesting identities with (almost) immediate combinatorial proofs. In Section 3, we present some results regarding a certain class of pseudo-order 2 elements for which Shapiro’s question is not answered. Certain elements of this class of Riordan matrices can be interpreted combinatorially as lattice paths, and have connections to the Fibonacci numbers and RNA secondary structures from molecular biology.

Characteristics of Pseudo-Involutions

Here, we make some basic observations about elements of pseudo-order 2. If R = (g(z), f(z)) has pseudo-order 2, then

g(z) = \frac{1}{g(−f(z))} and f(−f(z)) = −z.

This statement follows directly from (1) and Definition 1. While pseudo-order 2 elements do not form a subgroup, there are some pseudo-order 2 elements that can be easily recognized by the subgroup to which they belong. Many of the pseudo-involutions presented in this paper, including Pascal’s triangle P = (\frac{1}{1−z}, \frac{z}{1−z}), are elements of the Bell subgroup which is the set of all Riordan elements of the form (g(z), zg(z)) [13]. However, there are pseudoinvolutions which are not in the Bell subgroup, such as the matrix D_{1} described in Section 3.

The associated subgroup is the set of all Riordan group elements of the form (1, f(z)). This set forms a subgroup since (1, f(z)) ∗ (1, g(z)) = (1, g(f(z))) and (1, f(z))^{−1} = (1, f̄(z)) are elements of the set. In the case of an associated subgroup member (1, f(z)), we have a test to determine whether it is a pseudo-involution. We leave it to the reader to check that when f = f̄, it follows that (1, f(z)) is an involution in the Riordan group.

Proposition 1. An element R = (1, f(z)) of the associated subgroup has pseudo-order 2 if f = f̄ and f is odd.

Proof. This follows from the fact that (RM)^{2} = (1, f(z)) ∗ (1, −z) ∗ (1, f(z)) ∗ (1, −z) = (1, −f(z)) ∗ (1, −f(z)) = (1, −f(−f(z))). If f is odd then −f(−f(z)) = −f(f(−z)) and if f is its own compositional inverse, then −f(f(−z)) = −(−z) = z. Hence, (RM)^{2} is in fact the identity and R has pseudo-order 2.

Note that, as a consequence of this proposition, M = (1, −z) has pseudo-order 2. Since M^{2} is the identity, any element of the form RMR^{−1}M will have pseudo-order 2 (because (RMR^{−1}M)M(RMR^{−1}M)M = RMR^{−1}(MM)RMR^{−1}(MM) is also the identity). In the next section, we explore the converse of this statement for a specific class of Riordan matrices.

The following is an equivalent characterization of pseudo-order 2 elements. In fact, it is merely the equivalent definition with left multiplication by M [8].

Proposition 2. A Riordan group element R = (g (z) , f (z)) has pseudo-order 2 if and only if the element R_{−z} = (g (−z) , f (−z)) has order 2.

Proof. (⟹) Suppose R has order pseudo-order 2. Then for M = (1, −z) we know by the definition of pseudo-order 2

RM = (g (z) , f (z)) (1, −z) = (g (z) , −f (z))

has order 2 in the Riordan group. Therefore,

(RM)^{2} = (g (z) , −f (z))^{2}
= (g (z) g (−f (z)) , −f (−f (z)))
= (1, z) .

Equating components in the last two expressions g (z) g (−f (z)) = 1 and −f (−f (z)) = z, and replacing z with −z gives g (−z) g (−f (−z)) = 1 and f (−f (−z)) = z. By these last two equations

(1, z) = (g (−z) g (−f (−z)) , f (−f (−z)))
= (g (−z) , f (−z)) (g (−z) , f (−z))
= R_{−z}R_{−z}.

Hence R_{−z} has order 2.

It is trivial to prove the opposite direction. Assume R_{−z} has order 2, then reverse the above arguments. This leads to R has pseudo-order 2. This completes the proof of the proposition.

2 A Class of Generalized Pascal’s Triangles

In this section, we refer to some common combinatorial sequences. We note here that C(z) is the generating function for the famous Catalan numbers \underline{A000108},

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

while m(z) is the generating function for the Motzkin numbers \underline{A001006},

m(z) = \frac{1 − z − \sqrt{1 − 2z − 3z^{2}}}{2z^{2}} ,  (3)

and S(z) is the generating function for the little Schröder numbers \underline{A001003},

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

Consider Pascal’s triangle as the Riordan matrix P = (\frac{1}{1−z}, \frac{z}{1−z}) with dot diagram [1; 1, 1]. We saw in the preceding section that P is an element of pseudo-order 2 and P = P_{−1}MP_{−1}M. In fact, it is the case that any generalized Pascal array of the form P_{b} = (\frac{1}{1−bz}, \frac{z}{1−bz}) , where b ≥ 0, is a pseudo-involution. A natural question arises. Can we write any pseudoinvolution as RMR^{−1}M for some R? If so, how do we classify the R? The next theorem provides an answer to these questions for a select class of Riordan matrices. One of the consequences of the theorem is that we can always factor these Pascal-like triangles of the form (\frac{1}{1−bz}, \frac{z}{1−bz}). In the examples following the theorem, we use this fact to provide some interesting decompositions of sequences associated with the triangles and a combinatorial interpretation of those decompositions.

The proof of the following theorem relies on a result known as the Triple Factorization theorem, due to Peart and Woodson [9], which says that if R has dot diagram [b + ϵ, λ + δ; 1, b, λ], then R = P_{b}C_{λ}F_{ϵ,δ}, where P_{b} = (\frac{1}{1−bz}, \frac{z}{1−bz}), C_{λ} = (C(λz^{2}), zC(λz^{2})), and F_{ϵ,δ} = (\frac{1}{1−ϵz−δz^{2}} , z) .

Theorem 1. Let b ∈ ℤ and δ, ϵ, λ ∈ ℝ. The Riordan matrix

R^{∗} = (\frac{1 + \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )}{1 − \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )} · \frac{1}{1 − 2bz} , \frac{z}{1 − 2bz} )  (5)

has pseudo-order 2. Furthermore, R^{∗} = RMR^{−1}M, where R = P_{b}C_{λ}F_{ϵ,δ} has dot diagram [b + ϵ, λ + δ; 1, b, λ].

Proof. It suffices to verify that R^{∗} = RMR^{−1}M. By the Triple Factorization Theorem [9], if R has dot diagram [b + ϵ, λ + δ; 1, b, λ], then R = P_{b}C_{λ}F_{ϵ,δ}.

First, let us note that

C_{λ}F_{ϵ,δ} = (\frac{C(λz^{2})}{1 − ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}, zC(λz^{2}))

and by (1),

(C_{λ}F_{ϵ,δ})^{−1} = F_{ϵ,δ}^{−1}C_{λ}^{−1} = (\frac{1 − \frac{ϵz}{1+λz^{2}} C (\frac{λz^{2}}{(1+λz^{2})^{2}} ) − \frac{δz^{2}}{(1+λz^{2})^{2}} C^{2} (\frac{λz^{2}}{(1+λz^{2})^{2}} )}{C (\frac{λz^{2}}{(1+λz^{2})^{2}} )}, \frac{z}{1 + λz^{2}} , )

So,

RMR^{−1}M = (P_{b}C_{λ}F_{ϵ,δ})M(F_{ϵ,δ}^{−1}C_{λ}^{−1}P_{b}^{−1})M
= P_{b}(C_{λ}F_{ϵ,δ}MF_{ϵ,δ}^{−1}C_{λ}^{−1})P_{b}^{−1}M
= P_{b} (\frac{C(λz^{2})}{1 − ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}, −zC(λz^{2}))

(\frac{1 − \frac{ϵz}{1+λz^{2}} C (\frac{λz^{2}}{(1+λz^{2})^{2}} ) − \frac{δz^{2}}{(1+λz^{2})^{2}} C^{2} (\frac{λz^{2}}{(1+λz^{2})^{2}} )}{C (\frac{λz^{2}}{(1+λz)^{2}} )}, \frac{z}{1 + λz^{2}} ) P_{b}^{−1}M

= P_{b} (\frac{C(λz^{2})}{1 − ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})} · \frac{1 + ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}{C(λz^{2})}, −z) P_{b}^{−1}M
= P_{b} (\frac{1 + ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}{1 − ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}, −z) P_{b}^{−1}M
= (\frac{1}{1 − bz} , \frac{z}{1 − bz} ) (\frac{1 + ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}{1 − ϵzC(λz^{2}) − δz^{2}C^{2}(λz^{2})}, −z) (\frac{1}{1 + bz} , \frac{−z}{1 + bz} )

= (\frac{1}{1 − bz} · \frac{1 + \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )}{1 − \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )}, \frac{−z}{1 − bz} ) (\frac{1}{1 + bz} , \frac{−z}{1 + bz} )

= (\frac{1 + \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )}{1 − \frac{ϵz}{1−bz}C (\frac{λz^{2}}{(1−bz)^{2}} ) − \frac{δz^{2}}{(1−bz)^{2}} C^{2} (\frac{λz^{2}}{(1−bz)^{2}} )} · \frac{1}{1 − 2bz} , \frac{z}{1 − 2bz} )

The fourth equality follows from the fact that 1 + λz^{2}C^{2}(λz^{2}) = C(λz^{2}).

In the case when ϵ = δ = 0, the matrix in (5) represents a “Pascal-like” Riordan matrix. Theorem 1 asserts that these Pascal-like matrices can be factored into two Riordan matrices, R and MR^{−1}M, where R can be interpreted combinatorially. Notice that in this case the dot diagram of R is [b, λ; 1, b, λ]. This means that if r_{n,k} is the (n, k) entry of R, then

r_{n,0} = b · r_{n−1,0} + λ · r_{n−1,1} for n ≥ 0

and

r_{n,k} = r_{n−1,k−1} + b · r_{n−1,k} + λ · r_{n−1,k+1} for n, k ≥ 1

We can interpret R in terms of paths. Note that we will use the term restricted for paths which never go below the x-axis. It follows from the recursions above that r_{n,k} as the number of restricted paths from (0, 0) to (n, k) using b types of (1, 0) level steps, λ types of (1, −1) down steps, and one type of (1, 1) up step. As we will see in the following examples, this observation will expose a nice vehicle for obtaining and proving combinatorial identities.

Example 1: Let

R^{∗} = (\frac{1}{1 − 4z} , \frac{z}{1 − 4z} )

Notice that R^{∗} has the form (5) with ϵ = δ = 0, b = 2 and λ = 1. Hence, by Theorem 1, R^{∗} has pseudo-order 2 and R^{∗} = RMR^{−1}M, where R has dot diagram [2, 1; 1, 2, 1]. Solving the recurrence relation given by the dot diagram of R, we find that R = (C^{2}(z), zC^{2}(z)) \underline{A039598}, where C(z) is the Catalan generating function (2). Using (1) and the fact that C(z) = 1 + zC^{2}(z), we can determine that R^{−1} = (\frac{1}{(1+z)^{2}} , \frac{z}{(1+z)^{2}} ). That is, R^{∗} = R · (MR^{−1}M) \underline{A038231} is given by

[\begin{matrix}1 \\ 4 & 1 \\ 16 & 8 & 1 \\ 64 & 48 & 12 & 1 \\ 256 & 256 & 96 & 16 & 1 \\ & & … \end{matrix} ] = (C^{2}(z), zC^{2}(z)) · ((1, −z) · (\frac{1}{(1 + z)^{2}} , \frac{z}{(1 + z)^{2}} ) · (1, −z))

= (C^{2}(z), zC^{2}(z)) · (\frac{1}{(1 − z)^{2}} , \frac{z}{(1 − z)^{2}} )

= [\begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ & & … \end{matrix} ] [\begin{matrix}1 \\ 2 & 1 \\ 3 & 4 & 1 \\ 4 & 10 & 6 & 1 \\ 5 & 20 & 21 & 8 & 1 \\ & & … \end{matrix} ] ,  (6)

where MR^{−1}M is \underline{A053122}.

Notice that the entries of R represent restricted bicolored Motzkin paths [4]. A bicolored Motzkin path is a path from (0, 0) to (n, k) using U(1, 1), D(1, −1), L(1, 0), or \overline{L}(1, 0). Let M_{n,k} denote the set of all bicolored Motzkin paths of length n and terminal height k. (Terminal height is the y-coordinate of the final step in the path.) The (n, k)-th entry of R is |M_{n,k}|. Using the Lagrange Inversion formula (see p. 38, [17]), we find that for n, k ≥ 0,

|M_{n,k}| = [z^{n+1}]z^{k+1}C^{2(k+1)}
= \frac{k + 1}{n + 1}[z^{n−k}](1 + z)^{2(n+1)}
= \frac{k + 1}{n + 1}\binom{2n + 2}{n − k}

We can see clearly from (6) that the (dot) product of the first column of (\frac{1}{(1−z)^{2}} , \frac{z}{(1−z)^{2}} ) with the n-th row of R produces the quantity 4^{n}. We can write this more formally as the following identity found in [2].

Identity 1.

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

Now, we present another combinatorial proof of this identity.

Proof. To prove the identity, we will combinatorially extend the set of restricted bicolored Motzkin paths of length n to the set of all paths of length n using U, D, L, \overline{L} (and no other restrictions). Clearly, the total number of the latter paths is 4^{n}, giving us the left hand side of (1). We will present a set of maps ϕ_{i}, i = 0, 1, 2, … k so that the right hand side of (1) is the cardinality of the set

⋃_{k=0}^{n} ⋃_{Q∈M_{n,k}}{ϕ_{i}(Q) : 0 ≤ i ≤ k}.

Suppose Q ∈ M_{n,k}. The last ascent to height i of Q is the last up step (in order from left to right) which starts at height i − 1 and ends at height i. Notice that if we change the last ascent to height i of Q to a down step, we obtain a new path with terminal height k − 2. Let ϕ_{i}(Q) denote the path obtained by changing each of the last ascents to heights 1, 2, …, i to down steps. See Figures 1 and 2 for an illustration of this map.

[figure: ↑; ↑; ↑]

Figure 1: Q = UDL̄ULUDUUL̄DUUDDUUDUDL, a restricted bicolored Motzkin path of length n = 21 and terminal height k = 3. Last ascents are indicated with a bold U and marked above with an up arrow.

[figure: ↓; ↓]

Figure 2: ϕ_{2}(Q) = UDL̄DLUDDUL̄DUUDDUUDUDL, the unrestricted bicolored Motzkin path of length n = 21 and terminal height j = k − 2i = 3 − 2(2) = 1 which is obtained by changing the last ascents to heights 1 and 2 to D’s. Premier descents are indicated with a bold D and marked above with a down arrow.

Since Q has terminal height k, it contains exactly k last ascents and therefore ϕ_{i} is welldefined as long as i ≤ k. By replacing the first i last ascents in Q with D’s, we ensure that, at some point, the number of D’s exceeds the number of preceding U’s, so that ϕ_{i}(Q) necessarily goes below the x-axis (called unrestricted), eventually ending at height k − 2i.

Notice also that ϕ_{i} is one-to-one. If Q and Q′ are restricted paths ending at the same height, then they differ at some step which is not a last ascent, and ϕ_{i} will preserve that difference so that ϕ_{i}(Q) ≠ ϕ_{i}(Q′). On the other hand, if Q and Q′ end at different heights, then ϕ_{i}(Q) and ϕ_{i}(Q′) will also end at different heights, so that ϕ_{i}(Q) ≠ ϕ_{i}(Q′). Because ϕ_{i} is one-to-one, we may conclude that for every bicolored Motzkin path, the collection {Q, ϕ_{1}(Q), ..., ϕ_{k}(Q)} contains k + 1 distinct unrestricted paths and for Q ≠ Q′, the sets {Q, ϕ_{1}(Q), ..., ϕ_{k}(Q)} and {Q′, ϕ_{1}(Q′), ..., ϕ_{k}(Q′)} are disjoint. Hence, the set of all such collections is certainly contained in the set of all paths of length n using U, D, L, \overline{L}.

To show that the set {Q, ϕ_{1}(Q), ..., ϕ_{k}(Q) : Q ∈ M_{n,k}, 0 ≤ k ≤ n} is indeed equal to the set of all paths of length n using U, D, L, \overline{L}, we need only show that it is possible to take an unrestricted bicolored Motzkin path P and recover its unique preimage Q under ϕ_{i} for some i.

Let P be an unrestricted bicolored Motzkin path with terminal height j. Since P goes below the x-axis, it has a set of premier descents below the x-axis, i.e. the first (from left to right) down steps from height m to m − 1 for m = 0, −1, … Suppose P has i > 0 premier descents below the x-axis. Then changing each of the i premier descents to up steps will create a new path Q which stays above the x-axis and ends at height k = j + 2i. What was a premier descent to height m − 1 below the x-axis in P becomes not just an up step located above the x-axis, but in fact, it becomes an up step for which the previous number of U’s is equal to −m plus the previous number of D’s. This is the same as a last ascent to height −m + 1. It follows then that ϕ_{i}(Q) = P.

Now there was certainly nothing special about multiplication by the first column of (\frac{1}{(1−z)^{2}} , \frac{z}{(1−z)^{2}} ). It is not hard to show that the m-th column of (\frac{1}{(1−z)^{2}} , \frac{z}{(1−z)^{2}} ) is the

sequence \binom{n}{m}4^{n−m}. So one can generalize Identity 1 by taking the product of the m-th

column of (\frac{1}{(1−z)^{2}} , \frac{z}{(1−z)^{2}} ) with R. Hence, we obtain the following.

Identity 2.

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

While the accuracy of Identity 2 is guaranteed by Theorem 1, the authors would like to see a purely combinatorial proof, perhaps by extending the proof of Identity 1.

Example 2: Let

S^{∗} = (\frac{1}{1 − 6z} , \frac{z}{1 − 6z} )

Notice that the Riordan matrix S^{∗} (\underline{A038255}) has the form (5) with ϵ = δ = 0, b = 3 and λ = 2. Hence, by Theorem 1, S^{∗} has pseudo-order 2 and S^{∗} = SMS^{−1}M, where S has dot diagram [3, 2; 1, 3, 2]. Solving the recurrence relation given by the dot diagram of S, we find that S = (S(z), zS(z)) \underline{A110440}, where S(z) is the little Schröder generating function (4). Moreover, S^{−1} = (\frac{1}{1+3z+2z^{2}} , \frac{z}{1+3z+2z^{2}} ) and we note that \frac{1}{1−3z+2z^{2}} is the generating function for the Mersenne number sequence 2^{n} − 1, n ≥ 1, \underline{A000225}. More expressly, we have

S^{∗} = [\begin{matrix}1 \\ 6 & 1 \\ 36 & 12 & 1 \\ 216 & 108 & 18 & 1 \\ 1296 & 864 & 216 & 24 & 1 \\ & & … \end{matrix} ]  (8)

= (S(z), zS(z)) · (1, −z) · (\frac{1}{1 + 3z + 2z^{2}} , \frac{z}{1 + 3z + 2z^{2}} ) · (1, −z)
= (S(z), zS(z)) · (\frac{1}{1 − 3z + 2z^{2}} , \frac{z}{1 − 3z + 2z^{2}} )

= [\begin{matrix}1 \\ 3 & 1 \\ 11 & 6 & 1 \\ 45 & 31 & 9 & 1 \\ 197 & 156 & 60 & 12 & 1 \\ & & … \end{matrix} ] [\begin{matrix}1 \\ 3 & 1 \\ 7 & 6 & 1 \\ 15 & 23 & 9 & 1 \\ 31 & 72 & 48 & 12 & 1 \\ & & … \end{matrix} ]  (9)

The (n, k) entry of S, call it s_{n,k}, is the number of restricted paths from (0, 0) to (n − 1, k − 1) using U, L, L̄, ¯ L̄, D and D̄ (that is, 3 types of level steps and 2 types of down steps). Let us refer to these paths as Schröder paths.

Remark. An interesting observation about the Mersenne array MS^{−1}M \underline{A110441} is that the diagonal slices are the even indexed (or numbered) Fibonacci numbers \underline{A001906} {1, 3, 8, 21, …}.

Left multiplying the matrix S by the first column of MS^{−1}M, we obtain the following statement.

6^{n−1} = ∑_{k=1}^{n} (2^{k} − 1)s_{n,k}  (10)

To prove this statement, we will use the same method from Example 1 to extend the set of Schröder paths of length n to the set of unrestricted paths of length n having the same step set. Clearly the cardinality of the latter is 6^{n}.

Let Q be a Schröder path of length n and terminal height k. As before, for all i between 0 and k, we will change the first i last ascents to D’s. Now, since we have 2 types of D’s in this case, we will say that ϕ_{i,j}(Q) is the path obtained by changing j of the first i last ascents to D’s and the remaining i − j to D̄’s. There are \binom{i}{j} ways to do this. Hence, the set of distinct paths generated by Q, that is, {ϕ_{i,j}(Q) : 0 ≤ j ≤ i ≤ k}, has cardinality

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

Although we know that statement (10) is true, it would be nice to be able to express it explicitly. Fortunately, this can be achieved by first producing a closed formula for s_{n,k}. Applying the Lagrange Inversion Formula, we have:

s_{n,k} = [z^{n}]z^{k}S^{k}(z)  (11)
= \frac{k}{n}[z^{n−k}] (1 + 3z + 2z^{2})^{n}  (12)
= \frac{k}{n} ∑_{j=0}^{n−k} \binom{n}{j}\binom{n − j}{n − k − 2j}2^{j}3^{n−k−2j}  (13)

Combining equations (10) and (13), we obtain the following explicit form of the identity:

Identity 3.

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

We close this section by remarking that an application of Theorem 1 with ϵ = δ = 0, any nonzero value for b and the same method used in the above examples will produce an identity for (2b)^{n}.

3 A Class of Generalized RNA Triangles

In this section we define another class of pseudo order 2 elements of the Riordan group. Consider, for n ≥ 1, the matrix D_{n} = (g (z) (\frac{1−z}{1−zg(z)})^{n} , zg (z)) , where

g (z) = \frac{(1 − z + z^{2}) − \sqrt{1 − 2z − z^{2} − 2z^{3} + z^{4}}}{2z^{2}} .  (15)

Note that D_{n} = A^{−n}D_{0}A^{n}, where D_{0} = (g (z) , zg (z)) , A^{n} = (\frac{1}{(1−z)^{n}} , z), and A^{−n} = ((1 − z)^{n} , z).

The matrix D_{n} is of combinatorial interest and the first few cases are explicitly given in Figure 3.

The matrix D_{0} = (C_{0})^{−1} P C_{0} where P is the Pascal matrix P = (\frac{1}{1−z}, \frac{z}{1−z}), C_{0} is the aerated Catalan matrix defined by

C_{0} = (C (z^{2}) , zC (z^{2})) = (\frac{1 − \sqrt{1 − 4z^{2}}}{2z^{2}} , \frac{1 − \sqrt{1 − 4z^{2}}}{2z} ) ,

and (C_{0})^{−1} = (\frac{1}{1+z^{2}} , \frac{z}{1+z^{2}} ) . D_{0} \underline{A097724} has a lattice path interpretation and arises in connection with counting RNA secondary structures from molecular biology. The entries in the leftmost column of D_{0} are the RNA numbers \{1, 1, 1, 2, 4, 8, 17, …\}, \underline{A004148}, which have a lattice path interpretation [7]. Consider counting paths which start at the origin (0, 0) and

D_{0} = [ \begin{matrix}1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 2 & 3 & 3 & 1 \\ 4 & 6 & 6 & 4 & 1 \\ 8 & 13 & 13 & 10 & 5 & 1 \\ & & ⋯ \end{matrix} ] D_{1} = [ \begin{matrix}1 \\ 1 & 1 \\ 2 & 2 & 1 \\ 5 & 4 & 3 & 1 \\ 12 & 10 & 7 & 4 & 1 \\ 29 & 25 & 18 & 11 & 5 & 1 \\ & & ⋯ \end{matrix} ]

D_{2} = [ \begin{matrix}1 \\ 1 & 1 \\ 3 & 2 & 1 \\ 8 & 5 & 3 & 1 \\ 21 & 14 & 8 & 4 & 1 \\ 55 & 38 & 23 & 12 & 5 & 1 \\ & & ⋯ \end{matrix} ]

Figure 3: RNA arrays

take unit steps, N (0, 1), S (0, −1), and E (1, 0) with the following restrictions: 1) no paths pass below the x-axis and 2) no S step immediately follows an N step, i.e there are no NS steps. We call this class of paths NES paths. A typical example is denoted by the path NNESSE. If l_{n,k} denotes the number of NES paths of length n and terminal height k, then the (n, k) entry of D_{0} is l_{n,k}. Note that the paths that have terminal height k = 0 are counted by the RNA numbers. There is a one-to-one correspondence between these particular paths and RNA secondary structures of length n [7].

The matrix D_{1} \underline{A110438} also has a lattice path interpretation. Consider counting paths which start at the origin (0, 0) and take unit steps, N (0, 1), S (0, −1), E (1, 0), and W (−1, 0) with the following restrictions: 1) no paths pass below the x-axis, 2) no paths begin with a W step, 3) all W steps remain on the x-axis, and 4) no S step immediately follows an N step, i.e there are no NS steps. We call this class of paths NESW paths. A typical example is denoted by the path EWEEWNESWN. If d_{n,k} denotes the number of NESW paths of length n and terminal height k, then the (n, k) entry of D_{1} is d_{n,k}.

Computing the first few paths gives the first few entries of D_{1}. By convention d_{0,0} = 1 and it is obvious d_{n,n} = 1 since the only way to be at height n after n steps is to always go north. By Riordan group methods, it is easy to show the formation rule of D_{1} is given by the following recurrence relations d_{0,0} = 1, d_{1,0} = 1, and for n ≥ 1

d_{n+1,0} = 2d_{n,0} + ∑_{j≥1} d_{n−j,j},  (16)

for the leftmost column, and for n > j, n ≥ 2, and k ≥ 1 we have

d_{n+1,k} = d_{n,k−1} + d_{n,k} + ∑_{j≥1} d_{n−j,k+j},  (17)

for the other columns.

Note that equation (17) is valid for entries in D_{0}, D_{1}, D_{2}, …, not including the leftmost columns.

We want to find the total number of NESW paths of length n and connect D_{1} to the paths by showing the paths satisfy (16) and (17). To do this we consider the following combinatorial arguments. Since d_{n,k} denotes the number of NESW paths of length n with terminal height k, we consider the following cases to form a d_{n+1,k} path. First, if the last step is N, then there are d_{n,k−1} possibilities to move up to height k. If the last step is E, then there are d_{n,k} possibilities to remain at height k. If the last step is S, then there are d_{n−j,k+j} possibilities to move down to height k by considering ES^{j} steps. Summing over the cases gives (17). Note for k > 0 there are no paths with last step W since the W steps remain on the x-axis. For the leftmost column, if the last step is E , then there are d_{n,0} possibilities. Also if the last step is W, there are d_{n,0} possibilities. If the last step is S then there are d_{n−j,j} possibilities considering ES^{j} steps. Combining these cases gives (16). There are no paths with last step N for height k = 0. The boundary condition d_{n,k} = 0 (k > n) is trivial since there are no paths of this form. This proves the formation rule and gives D_{1} a NESW lattice path interpretation.

To find the total number of NESW paths of length n, we multiply by (1, 1, …)^{T} which has 1/ (1 − z) as its generating function. Then by Riordan matrix multiplication and simplifying, the generating function for the total number of all NESW paths is

D_{1} ∗ (1/ (1 − z)) = ((\begin{matrix}√ & \overline{1 + z + z^{2}} \\ √ & \overline{1 − 3z + z^{2}} \end{matrix} − 1) \frac{1 − z}{2z} , zg (z)) ∗ (1/ (1 − z))
= ((1 − z) / (1 − 3z + z^{2}))
= 1 + 2z + 5z^{2} + 13z^{3} + 34z^{4} + ⋯ = ∑_{n≥0} F_{2n+1}z^{n}.

Thus the NESW paths are counted by the odd indexed Fibonacci numbers {F_{2n+1}} = \{1, 2, 5, 13, 34, …\} \underline{A001519}.

Notice also that the matrix D_{2} \underline{A110439} is related to the Fibonacci numbers. The generating function of the leftmost column of D_{2} gives the even indexed Fibonacci numbers \underline{A001906} (plus one), \{1, 1, 3, 8, 21, …\}.

We now show D_{0} is pseudo order 2 and generalize that D_{n} also has pseudo-order 2.

Lemma 2. The matrix D_{0} has pseudo order 2.

Proof. Let D_{(0,−z)} = ((C_{0})^{−1} P C_{0})_{−z} = (g (−z) , −zg (−z)) . Now using the definitions of Riordan matrix multiplication and pseudo order 2, and the fact P has pseudo-order 2 we obtain the following:

D_{(0,−z)}D_{(0,−z)} = ((C_{0})^{−1} P C_{0})_{−z} ((C_{0})^{−1} P C_{0})_{−z}
= ((C_{0})^{−1} P )_{−z} (C_{0} (C_{0})^{−1})_{−z} (P C_{0})_{−z}
= ((C_{0})^{−1})_{−z} (P P)_{−z} (C_{0})_{−z}
= ((C_{0})^{−1} (C_{0}))_{−z}
= (1, z) .

Hence, D_{(0,−z)} has order 2 which proves the lemma.

Theorem 3. The matrix D_{n} is pseudo order 2.

Proof. Let D_{(n,−z)} = (A^{−n} D_{0} A^{n})_{−z} = (g (−z) (\frac{1+z}{1+zg(−z)})^{n} , −zg (−z)) . Now using the definitions of Riordan matrix multiplication and pseudo order 2, and the fact D_{0} has pseudoorder 2 we obtain the following:

D_{(n,−z)} D_{(n,−z)} = (A^{−n} D_{0} A^{n})_{−z} (A^{−n} D_{0} A^{n})_{−z}
= (A^{−n} D_{0})_{−z} (A^{n} A^{−n})_{−z} (D_{0} A^{n})_{−z}
= (A^{−n})_{−z} (D_{0} D_{0})_{−z} (A^{n})_{−z}
= (A^{−n} A^{n})_{−z}
= (1, z) .

Hence, D_{(n,−z)} has order 2 which proves the theorem.

While it is true that D_{n} has pseudo-order 2 for all n ∈ ℤ and, moreover, certain cases of D_{n} have a nice lattice path interpretations, these matrices are distinct from the matrices discussed in Section 2 in that it is not known whether D_{n} has the form RMR^{−1}M for some R ∈ R. Nonetheless, D_{n} is in good company, as there are certainly other interesting combinatorial triangles, such as Aigner’s directed animal matrix (1 + zm, z(1 + zm)), where m(z) is defined as in (3), for which this question is yet unanswered. We close this section by noting that a definitive conclusion for D_{n} is desirable. If, for example, it were true that D_{0} = RMR^{−1}M for some R, then there would exist some combinatorial decomposition of the RNA numbers \underline{A004148}, and similarly for D_{2}, it would be interesting to see what decomposition of the odd Fibonacci numbers were possible by factoring D_{2} into R and MR^{−1}M. If it is not possible to write D_{n} as RMR^{−1}M, one would expect to be able to combinatorially explain why this is the case and reasonably connect D_{n} with other combinatorial matrices with the same property.

Finally, we note that this paper is only concerned with Riordan matrices generated by ordinary generating functions. Considering pseudo-involutions of Riordan matrices generated by exponential generating functions and their factorizations as RMR^{−1}M as well as finding connections to the umbral calculus [1, 11] would be of interest as well.

4 Acknowledgements

The authors wish to thank the referee for valuable comments that improved the presentation of the paper.

References

[1] M. Barnabei, A. Brini, and G. Nicoletti, Recursive matrices and umbral calculus, J. Algebra 75 (1982) 546-573.

[2] D. Callan, A combinatorial interpretation of a Catalan numbers identity, Math. Mag. 72 (1999), 295–298.

[3] N. Cameron, Random walks, trees and extensions of Riordan group techniques, Ph. D. diss., Howard University, Washington, DC, 2002.

[4] C. Mallows, L. Shapiro, Balls on the lawn, J. Integer Seq. 2 (1999), Article 99.1.5.

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

[6] A. Nkwanta, A Riordan matrix approach to unifying a selected class of combinatorial arrays, Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 160 (2003), 33–45.

[7] A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 34 (1997), 137–147.

[8] A. Nkwanta, Lattice paths, generating functions, and the Riordan group, Ph. D. diss., Howard University, Washington, DC, 1997.

[9] P. Peart, L. Woodson, Triple factorization of some Riordan matrices, Fibonacci Quart. 31 (1993), 121–128.

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

[11] S. Roman, The Umbral Calculus, Academic Press, New York, 1984.

[12] L. Shapiro, Some open questions about random walks, involutions, limiting distributions, and generating functions, Adv. in Appl. Math. 27 (2001), 585–596.

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

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

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

[16] R. Sprugnoli, Riordan arrays and the Abel-Gould identity, Discrete Math. 142 (1995), 213–233.

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

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Riordan arrays, Catalan numbers, lattice paths, combinatorial identity.

Concerned with sequences \underline{A000108}, \underline{A000225}, \underline{A001003}, \underline{A001006}, \underline{A001519}, \underline{A001906}, \underline{A004148}, \underline{A007318}, \underline{A038231}, \underline{A038255}, \underline{A039598}, \underline{A053122}, \underline{A097724}, \underline{A110438}, \underline{A110439}, \underline{A110440}, and \underline{A110441}.

Received June 17 2005; revised version received August 18 2005. Published in Journal of Integer Sequences, August 23 2005.

Return to Journal of Integer Sequences home page.