Pseudo-Involutions in the Riordan Group

Alexander Burstein and Louis W. Shapiro Department of Mathematics Howard University Washington, DC 20059 USA

                 aburstein@howard.edu
                  lshapiro@howard.edu

Abstract

We consider pseudo-involutions in the Riordan group where the generating function g for the first column of a Riordan array satisfies a palindromic or near-palindromic functional equation. For those types of equations, we find, for very little work, the pseudo-involutory companion of g and have a pseudo-involution in a k-Bell subgroup. There are only slight differences in the ordinary and exponential cases. In many cases, we also develop a general method for finding B-functions of Riordan pseudo-involutions in k-Bell subgroups, and show that these B-functions involve Chebyshev polynomials. We apply our method for many families of Riordan arrays, both new and already known.

We also have some duality and reciprocity results. Since many of the examples we discuss have combinatorial significance, we conclude with a few remarks on the general framework for a combinatorial interpretation of some of the generating function results we obtain.

1 Preface

This paper is concerned with the Riordan group, first defined by Shapiro et al. [28], a group of infinite lower triangular matrices with properties generalizing those of the Pascal triangle. Before starting systematically in Section 2, we will assume some familiarity with the Riordan group and pseudo-involutions (see [4, 29] for an introductory book and lecture) and make a few remarks to add some perspective.

Riordan arrays are useful in enumerating unlabeled or labeled combinatorial structures consisting of a sequence of nonempty structures of the same type connected to a root structure, possibly empty and possibly of a different type. Examples of unlabeled structures include compositions, lattice paths, rooted unlabeled trees, secondary RNA structures, and directed animals, while examples of labeled structures include sets, set partitions, necklaces of set partitions, and rooted labeled trees. As we mentioned before, the basic example of a Riordan array is the Pascal triangle matrix, given by (\frac{1}{1−z}, \frac{z}{1−z}) as an ordinary Riordan array, and by [e^{z}, z] as an exponential Riordan array. Other well-known examples of ordinary Riordan arrays include the RNA matrix (R, zR) (Example 12) and the directed animal matrix (m̃(z), zm̃(z)) (Example 8). Well-known examples of exponential Riordan arrays are triangles of the Stirling numbers of the first and second kind.

Desirable properties of Riordan arrays include not only combinatorial meaning, but also recognizable A- and Z-sequences [21, 23, 27], or B-sequences for pseudo-involutions [5, 6, 10, 12, 13, 14, 20]. Those sequences let us construct Riordan arrays along their rows or antidiagonals, respectively, since the definition of Riordan arrays implies a column-by-column construction.

In this paper, we are primarily interested in Riordan arrays with certain special properties and other arrays closely related to those. One such property is that the Riordan array be an element of finite order in the Riordan group. It is straightforward to see that the only real-valued non-identity Riordan arrays of finite order are elements of order 2, i.e., involutions. It turns out, however, that the closely related pseudo-involutions are often more “combinatorial” as they are more likely to contain only nonnegative entries. The second property of interest is that the Riordan array be contained in a k-Bell subgroup, i.e., be of the form (g, f) or [g, f] with f(z) = zg(z)^{k} for some integer k. Some well-known examples of pseudo-involutions in k-Bell subgroups for various k include the Pascal triangle, the RNA matrix, and the directed animal matrix mentioned above, as well as arrays (C, zC^{3}) and (r, zr^{2}), where C = C(z) and r = r(z) are the generating functions for the Catalan and large Schröder numbers, respectively.

In this article we greatly increase the number of families of “desirable” pseudo-involutions. We begin in Section 2 by defining a Riordan array, ordinary and exponential, and its associated A- and Z-sequence and function, as well the B-sequence and B-function if the array is a pseudo-involution. This includes the interpretation of the B-sequence of an exponential Riordan array in terms of a recursive relation on a related array that we call the associated reduced exponential Riordan array.

In Section 3, we show that, for functions g of Riordan arrays (g, f) or [g, f], defined by certain functional relations common in combinatorial contexts (e.g., C = 1 + zC^{2}), we can easily produce the pseudo-involutory companion f. Furthermore, we show that for many classic combinatorial examples, where those functional equations involve palindromic polynomials, the resulting Riordan pseudo-involution is in the k-Bell subgroup for some k.

In Section 4, we develop a general method for finding B-functions of k-Bell Riordan pseudo-involutions and apply it to determine B-functions for several families of Riordan arrays, both new and already known. An interesting feature of those B-functions is that they all involve Chebyshev polynomials. We also find the relation between the B-function of a k-Bell Riordan pseudo-involution and the B-function of its aerated version in the 1-Bell subgroup (simply called the Bell subgroup).

For example, consider walks from (0, 0) to (3n, 0) on or above the x-axis with steps (2, 1), (1, 2) and (1, −1), a class also considered in Drake [17, Example 1.6.9]. It can be shown that the ordinary generating function r_{3} = r_{3}(z) for the counting sequence \underline{A027307} of such walks satisfies the recurrence relation r_{3} = 1 + z(r_{3}^{2} + r_{3}^{3}), from which we can infer that (r_{3}, zr_{3}^{4}) is a pseudo-involution that begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 10 & 10 & 1 & 0 & 0 \\ 66 & 90 & 18 & 1 & 0 \\ 498 & 810 & 234 & 26 & 1 \end{matrix}] .

However, to find the B-function for zr_{3}^{4}, it is better to consider r_{3} not on its own but as part of a family of functions r_{k} = r_{k}(z), k ≥ 1, that satisfy the equation r_{k} = 1 + z(r_{k}^{k−1} + r_{k}^{k}). This family also includes the generating function r = r(z) for the large Schröder numbers as r = r_{2}. The functional relation for r_{k} lets us show that the Riordan array (r_{k}, zr_{k}^{2k−2}) is a pseudo-involution in the (2k − 2)-Bell subgroup, and its B-function is \frac{4}{1−z}U_{k−2} (\frac{1+z}{1−z}), where U_{n} is the n-th Chebyshev polynomial of the second kind. Thus, we obtain B_{zr_{3}^{4}} = \frac{8(1+z)}{(1−z)^{2}}.

In Section 5, we extend our results from the previous sections to new pseudo-involutions where the pseudo-involutory companion f in (g, f) or [g, f] is more difficult to find given the function g. For example, we show that the pseudo-involutory companion of the Fibonacci generating function F = F (z) = \frac{1}{1−z−z^{2}} is (F −1)C(F −1) = (zC)∘(F −1), where C = C(z) is the Catalan generating function, and the array (F, (F − 1)C(F − 1)) begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 7 & 1 & 0 & 0 \\ 5 & 50 & 35 & 10 & 1 & 0 \\ 8 & 190 & 160 & 65 & 13 & 1 \end{matrix}]

However, developing a general method that would simplify finding the B-function of this array remains an open problem. Nevertheless, we find by computing a few initial terms, comparing with existing OEIS sequences, and checking by substitution, that

B_{(F −1)C(F −1)}(z) = \frac{1 + z − \sqrt{1 − 10z + 5z^{2}}}{2z} .

Another example of such a function g is the generating function m = m(z) for the Motzkin numbers with the pseudo-involutory companion f = \frac{m−\sqrt{4m−3m^{2}}}{2} . We show (see Example 47) how the pseudo-involution (m, \frac{m−\sqrt{4m−3m^{2}}}{2} ) can be easily recovered from the Pascal triangle using an operation we call pseudo-conjugation. As in the previous example, a general approach to finding the B-function under such an operation remains an open problem.

Among the new pseudo-involutions we find is a family that includes partial noncrossing matchings and some types of secondary RNA structures. Another new family contains the pseudo-involution (1/C(−zC^{2}), z/C(−zC^{2})) in the Bell subgroup, where 1/C(−zC^{2}) is the generating function for the basketball walks [2, 3, 9]. Yet another new pseudo-involution we find in a closely related family is (C(zC), zC^{5}(zC)) in the 5-Bell subgroup, where C(zC) is the generating function for the number of permutations of length 3n, n ≥ 0, that avoid pattern 132 and decompose into n disjoint 3-cycles (a, b, c) with a > b > c (see Archer and Graves [1]). Alternatively, C(zC) is the generating function for the number of permutations that avoid the set of patterns {1342, 3142, 45132} and do not start with a descent.

Finally, we conclude with a few remarks on the general framework for a combinatorial interpretation of some of the generating function results we have obtained.

2 Introduction

Consider the set F = ℝ[[z]] of formal power series with real coefficients. We define the order of f(z) ∈ ℝ[[z]], where f = ∑_{n=0}^{∞} a_{n}z^{n}, as the smallest index n such that a_{n} ≠ 0, and let F_{r} be the set of all formal power series of order r. Whenever there is no confusion, we will omit the variable (which we will assume to be z) and simply write f instead of f(z). (Note that this setup readily generalizes to any field F in place of ℝ, but we restrict ourselves to ℝ since our interest is motivated by possible combinatorial interpretations of the coefficients of the formal power series f.)

A lower triangular matrix D = [d_{ij}]_{i,j≥0} is called a Riordan array (or sometimes, an ordinary Riordan array) if there exist g ∈ F_{0} and f ∈ F_{1} such that, for any k ≥ 0, the generating function ∑_{n=0}^{∞} d_{nk}z^{n} of the kth column of D is gf^{k}. We will denote this by writing D = (g, f).

Given a column vector h = [h_{k}]_{k≥0}^{T} and its generating function h(z) = ∑_{k=0}^{∞} h_{k}z^{k}, the generating function of the product Dh is given by

(g, f) ∗ h = ∑_{k=0}^{∞} h_{k}gf^{k} = g ∑_{k=0}^{∞} h_{k}f^{k} = g · (h ∘ f) = gh(f).  (1)

Equation (1) is called the Fundamental Theorem of Riordan Arrays [28] (abbreviated FTRA). From this identity, it is straightforward to see that the matrix multiplication induces the following multiplication law for Riordan arrays:

(g, f) ∗ (G, F) = (g · (G ∘ f), F ∘ f) = (gG(f), F (f)).  (2)

Given a function f ∈ F_{1}, let f̄ ∈ F_{1} denote its compositional inverse. Then we see that the set of Riordan arrays is closed under matrix multiplication, with (1, z), the identity matrix, as the identity element and

(g, f)^{−1} = (\frac{1}{g ∘ f̄} , f̄) = (\frac{1}{g(f̄)} , f̄)  (3)

for any Riordan array (g, f). This means that the Riordan arrays form a group, called the Riordan group [28].

Given any Riordan array (g, f), we can write

(g, f) = (G, F) ∗ (g(0), |f′(0)|z)

for some G ∈ F_{0}, F ∈ F_{1}, such that G(0) = 1 and F′(0) = ±1. Note that if both G, F ∈ ℤ[[z]], then both 1/G, F̄ ∈ ℤ[[z]] as well, and moreover, (1/G)(0) = 1 and F̄′(0) = ±1. Since our motivation for considering Riordan arrays is mostly combinatorial, we will assume from now on, with little loss of generality, that Riordan arrays (g, f) have g(0) = 1 and f′(0) = ±1.

For example, consider the Pascal triangle as a lower triangular matrix P = [\binom{i}{j}]_{i,j≥0}.

The generating function of the kth column of P is

∑_{i=0}^{∞} \binom{i}{k}z^{i} = \frac{z^{k}}{(1 − z)^{k+1}} = \frac{1}{1 − z} (\frac{z}{1 − z} )^{k} ,

so

P = (\frac{1}{1 − z} , \frac{z}{1 − z} ) .  (4)

The Riordan group contains several subgroups whose elements often occur in combinatorial contexts. Those include:

• the Lagrange subgroup of Riordan arrays of the form (1, f);

• the Appell subgroup of Riordan arrays of the form (g, z), which is normal in the Riordan group;

• the Bell subgroup of Riordan arrays of the form (g, zg);

• the k-Bell subgroup, for each k ≥ 0, of Riordan arrays of the form (g, zg^{k}), which yields the Appell subgroup for k = 0 and the Bell subgroup for k = 1;

• the checkerboard subgroup of Riordan arrays of the form (g, f), where g is even and f is odd, that is (g, f) = (u(z^{2}), zv(z^{2})) for some u, v ∈ F_{0};

• more generally, for each k ≥ 1, the k-checkerboard subgroup of Riordan arrays of the form (u(z^{k}), zv(z^{k})), where u, v ∈ F_{0}; • the derivative subgroup of Riordan arrays of the form (f′, f) (where the multiplication

law is just the chain rule);

• the hitting time subgroup of Riordan arrays of the form (zf′/f, f) (these are just derivative subgroup arrays propagated one column to the left).

Note also that for any Riordan array (g, f), we have

(g, f) = (g, z) ∗ (1, f) = (1, f) ∗ (g(f̄), z),

so that the Riordan group is a semidirect product of its Appell and Lagrange subgroups.

Considering the rows of Riordan arrays, Rogers [27] and Merlini et al. [23] defined the Asequence and Z-sequence, respectively, of a Riordan array (g, f), whose generating functions A_{f} and Z_{(g,f)} satisfy

f = z(A_{f} ∘ f),  g = \frac{g(0)}{1 − z(Z_{(g,f)} ∘ f)}  (5)

or, equivalently,

A_{f} = \frac{z}{f̄} ,  Z_{(g,f)} = \frac{g − g(0)}{zg} ∘ f̄.  (6)

Translating this into relations between the matrix entries of (g, f) = [d_{ij}]_{i,j≥0}, and the coefficients of A_{f}(z) = ∑_{j=0}^{∞} a_{j}z^{j} and Z_{(g,f)}(z) = ∑_{j=0}^{∞} ζ_{j}z^{j}, we obtain

\begin{aligned}d_{n+1,k+1} & = ∑_{j=0}^{∞} a_{j}d_{n,k+j}, n, k ≥ 0, \\ d_{n+1,0} & = ∑_{j=0}^{∞} ζ_{j}d_{n,j}, n ≥ 0. \end{aligned}  (7)

For more on properties of A- and Z-sequences of Riordan arrays, see, e.g., He and Sprugnoli [21].

In this paper, our particular interest will be in the Riordan group elements of finite order. With ℝ as the underlying coefficient field, the only formal power series of finite order with respect to composition are involutions, and thus, the only non-identity Riordan arrays of finite order are those of order 2. It is a straightforward exercise to show that if (g, f) is an involution, i.e., (g, f)^{2} = (1, z), then either f′(0) = −1 or f = z, and in the latter case (g, f) = (±1, z). Thus, non-identity involutions with g(0) = 1 always have f′(0) = −1. Note also that (g, f)^{2} = (1, z) is equivalent to

g · (g ∘ f) = 1, f ∘ f = z.  (8)

A Riordan array (g, f) is called a pseudo-involution if (g, −f) is an involution. Equivalently, (g, f) = [d_{ij}]_{i,j≥0} is a pseudo-involution if and only if (g, f)^{−1} = [(−1)^{i−j}d_{ij}]_{i,j≥0}. Since (g, −f) = (g, f) ∗ (1, −z), it follows that (g, f) is a pseudo-involution if and and only if

(g, f)^{−1} = (1, −z) ∗ (g, f) ∗ (1, −z) = (g(−z), −f(−z)),

or, equivalently,

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

If (g, f) is a pseudo-involution, we say that g and f are companions. A given g can have at most one companion f, but a given f has infinitely many companions g. In particular, it is easy to check [26] that (g^{k}, f) is also a pseudo-involution for any power k. When f̄ = −f(−z), we will call f pseudo-involutory (so as not use the same term for a function and a Riordan array).

If (g, f) is a pseudo-involution, then zf ∈ F_{2} and its coefficient at z^{2} is 1, thus \sqrt{zf} ∈ F_{1}. Furthermore, it is easy to check that (zf) ∘ (−f) = (−f) · (−z) = zf, and thus, zf is a fixed point of −f, which implies that if f ≠ −z then \sqrt{zf} ∘ (−f) = −\sqrt{zf}. Moreover, f − z ∈ F_{2} and (f − z) ∘ (−f) = −z − (−f) = f − z, i.e., f − z is also a fixed point of −f. Therefore, for a pseudo-involution (g, f) we can define a so-called B-function of f, B_{f} = B_{f}(z), such that

f − z = (zB_{f}) ∘ (zf) = zfB_{f}(zf).  (9)

If B_{f}(z) = ∑_{j=0}^{∞} b_{j}z^{j}, then this is equivalent to the fact that

d_{n+1,k+1} = d_{n,k} + ∑_{j=0}^{∞} b_{j}d_{n−j,k+j+1}, n, k ≥ 0,  (10)

and {b_{n}}_{n≥0} is called the B-sequence of f. The B-sequence and B-function of a Riordan array were first introduced in Cheon et al. [12] as the Δ-sequence and Δ-function, respectively, but were subsequently called the B-sequence and B-function in later papers [19, 20, 26].

Pseudo-involutions often have combinatorial interpretations as distributions of combinatorial statistics on combinatorial classes. For example, it is easy to check that Pascal triangle (4) is a pseudo-involution. Furthermore, for the Pascal triangle P, we have

f − z = \frac{z}{1 − z} − z = \frac{z^{2}}{1 − z} = zf,

so that B_{f} = 1. In this case, both the A- and B-sequences simply yield the binomial formula \binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}.

2.1 Exponential Riordan group

The preceding discussion assumed the use of ordinary generating functions. Some adjustments are needed in order to use the exponential generating functions as companions in a Riordan pair. Specifically, a lower triangular matrix M = [a_{n,k}]_{n,k≥0} is an exponential Riordan array [g, f] [16, 7], for exponential generating functions g ∈ F_{0} and f ∈ F_{1}, if the kth column of M (starting on the left with k = 0) is given by \frac{gf^{k}}{k!} . It follows that

a_{n,k} = [\frac{z^{n}}{n!} ] \frac{gf^{k}}{k!} = \frac{n!}{k!}[z^{n}](gf^{k}) = \frac{n!}{k!}d_{n,k} ,  0 ≤ k ≤ n,  (11)

where [d_{n,k}]_{n,k≥0} = (g, f). The FTRA (1) still holds for the exponential Riordan arrays, and the identity matrix is again given by [1, z].

For example, the Pascal triangle is the exponential Riordan array P = [e^{z}, z] since

a_{n,k} = \frac{n!}{k!}[z^{n}](z^{k}e^{z}) = \frac{n!}{k!}[z^{n−k}]e^{z} = \frac{n!}{k!(n − k)!} = \binom{n}{k}.

Similarly, for any fixed integer k ≥ 0, the exponential generating function for the Stirling numbers of the second kind S(n, k) is \frac{(e^{z}−1)^{k}}{k!} , so the matrix [S(n, k)]_{n,k≥0} is the exponential Riordan array [1, e^{z} − 1]. Likewise, letting s(n, k), 0 ≤ k ≤ n, be the signed Stirling numbers of the first kind, we have

[s(n, k)]_{n,k≥0} = [S(n, k)]_{n,k≥0}^{−1} = [1, e^{z} − 1]^{−1} = [1, \overline{(e^{z} − 1)}] = [1, log(1 + z)].

Therefore, for the signless Stirling numbers of the first kind, c(n, k) = (−1)^{n−k}s(n, k), we obtain

[c(n, k)]_{n,k≥0} = [1, −z] ∗ [1, log(1 + z)] ∗ [1, −z] = [1, − log(1 − z)] = [1, log (\frac{1}{1 − z} )] .

The involutions and pseudo-involutions in the exponential Riordan group are defined just like those in the Riordan group: [g, f] is an involution if [g, f]^{2} = [1, z], and [g, f] is a pseudo-involution if [g, −f] is an involution.

The definition of the B-sequence for the exponential Riordan array also requires some adjustments so as to preserve the functional relation (9) for the B-function. Specifically, with a_{n,k} and b_{j} defined as in (11) and (10), respectively, let

α_{n,k} = \frac{a_{n,k}}{\binom{n}{k}} , n ≥ k ≥ 0;  α_{n,k} = 0, n < k;  β_{j} = (2j + 1)! b_{j} , j ≥ 0; (12)

so that α_{n,k} (n ≥ k ≥ 0) is the coefficient at \frac{z^{n−k}}{(n−k)!} of the power series expansion of g · (f/z)^{k}, with f/z ∈ F_{0}, and

B_{f}(z) = ∑_{j=0}^{∞} b_{j}z^{j} = ∑_{j=0}^{∞} β_{j} \frac{z^{j}}{(2j + 1)!}.  (13)

In other words, B_{f}(z) = ^{\frac{Y_{f}(\sqrt{z})}{\sqrt{z}}} for some odd exponential generating function Y_{f}(z). Then

α_{n+1,k+1} = α_{n,k} + ∑_{j=0}^{∞} \binom{n − k}{2j + 1}β_{j}α_{n−j,k+j+1}, n ≥ k ≥ 0.  (14)

For example, the Pascal triangle as the exponential Riordan array P = [e^{z}, z] has f = z,

so zfB_{f}(zf) = f − z = 0 and thus B_{f} = 0. Therefore, we have α_{n,k} = \begin{matrix}( & {n \atop k} & ) \\ ( & {n \atop k} & ) \end{matrix} = 1 for all

n ≥ k ≥ 0 and β_{j} = 0 for all j ≥ 0, and thus we see that Equation (14) holds for P.

Definition 1. Given an exponential Riordan array [g, f] = [a_{n,k}]_{n,k≥0}, define its reduction by red[g, f] = [α_{n,k}]_{n,k≥0}, where α_{n,k} is as in (12). We call red[g, f] the reduced exponential array associated with [g, f], and call the sequence {β_{j}}_{j=0}^{∞} in (12) the beta-sequence of [g, f].

Since α_{n,0} = a_{n,0}, the exponential generating function for the leftmost column of red[g, f] is simply g. Knowing the first column, we can use the sequence {β_{j}}_{j=0}^{∞} together with (14) to construct the rest of red[g, f] recursively. Finally, given any α_{n,k} in red[g, f], we find a_{n,k} = \binom{n}{k}α_{n,k} to construct the exponential Riordan array [g, f].

3 Generalized palindromes and the k-Bell subgroup

In this section, we will consider two special cases of a recursive formula for g, the first component of a Riordan array (g, f), that imply that f = zg^{k} for some k ∈ ℤ. In other words, all these Riordan arrays are pseudo-involutions in the k-Bell subgroup.

Consider a polynomial p(z) = ∑_{j=ℓ_{∗}}^{ℓ^{∗}} a_{j}z^{j}, where a_{ℓ_{∗}}, a_{ℓ^{∗}} ≠ 0. Then the reciprocal polynomial of p(z) is

p_{rec}(z) = ∑_{j=ℓ_{∗}}^{ℓ^{∗}} a_{ℓ_{∗}+ℓ^{∗}−j}z^{j} = z^{ℓ_{∗}+ℓ^{∗}}p (\frac{1}{z}) .

Moreover, a polynomial p is called palindromic, or a palindrome, if p_{rec} = p.

Finally, we call a function γ = γ(z) a generalized palindrome if

\frac{γ(z)}{γ (\frac{1}{z})} = z^{k}

for some k ∈ ℚ. In this case, we call k the darga of γ (stress on the second syllable), denoted k = dar(γ). For example, for a palindromic polynomial p as above, we have dar(p) = ℓ_{∗} + ℓ^{∗}.

Let P_{d} be the set of generalized palindromes of darga d, and let P = ⋃_{d∈ℚ} P_{d}. It is routine to check that generalized palindromes satisfy the following properties: if γ_{1} = γ_{1}(z) ∈ P_{d_{1}} and γ_{2} = γ_{2}(z) ∈ P_{d_{2}}, then

• γ_{1}γ_{2} ∈ P_{d_{1}+d_{2}},

• γ_{1}/γ_{2} ∈ P_{d_{1}−d_{2}},

• γ_{1}^{r} ∈ P_{rd_{1}} for r ∈ ℚ,

• γ_{1}(z^{r}) ∈ P_{rd_{1}} for r ∈ ℚ,

• if d_{1} = d_{2} = d and γ_{1} + γ_{2} ≠ 0, then γ_{1} + γ_{2} ∈ P_{d},

• if d_{1} = 0, then η ∘ γ_{1} ∈ P_{0} for any η = η(z) ≠ 0.

Most of the results in this paper stem from two simple observations, one more often useful in the case of ordinary generating functions, and the other more often useful in the case of exponential generating functions.

Theorem 2.

1. Let g = g(z) be a function that satisfies a functional relation

g = 1 + zγ(g) = 1 + z · (γ ∘ g),  (15)

for some function γ. Then (g, f) and [g, f] are pseudo-involutions if and only if

f = z \frac{γ(g)}{gγ (\frac{1}{g})}.  (16)

Moreover, if γ ∈ P_{d}, then f = zg^{d−1}, so (g, f) and [g, f] are in the (d − 1)-Bell subgroup.

2. Let g = g(z) be a function that satisfies a functional relation

g = e^{zγ(g)} = e^{z·(γ∘g)},  (17)

for some function γ. Then (g, f) and [g, f] are pseudo-involutions if and only if

f = z \frac{γ(g)}{γ (\frac{1}{g})}.  (18)

Moreover, if γ ∈ P_{d}, then f = zg^{d}, so (g, f) and [g, f] are in the d-Bell subgroup.

Proof. In the first case, we have

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

Recall that for a pseudo-involution (g, f), we have g(−f) = 1/g, so

−f = \frac{g(−f) − 1}{γ(g(−f))} = \frac{\frac{1}{g} − 1}{γ (\frac{1}{g})} = −\frac{g − 1}{gγ (\frac{1}{g})} = −\frac{zγ(g)}{gγ (\frac{1}{g})},

and hence,

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

In the second case, we have

z = \frac{log(g)}{γ(g)},

so

−f = \frac{log(g(−f))}{γ(g(−f))} = \frac{log (\frac{1}{g})}{γ (\frac{1}{g})} = −\frac{log(g)}{γ (\frac{1}{g})} = −\frac{zγ(g)}{γ (\frac{1}{g})},

and hence,

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

We begin with an example where γ is not necessarily a generalized palindrome.

Example 3. Suppose that g = g(z) satisfies the equation g = 1+z(bg−a) for some constants a, b such that a ≠ b (if a = b, then g = 1, so (g, f) is a pseudo-involution whenever f is pseudo-involutory). Then γ(z) = bz − a and

g = \frac{1 − az}{1 − bz} ,

and if (g, f) is a pseudo-involution, then

f = z \frac{bg − a}{g · (\frac{b}{g} − a)} = z \frac{bg − a}{b − ag} = \frac{z}{1 − (a + b)z} .

As an example, we take a = 1 and b = 2 to get

(\frac{1 − z}{1 − 2z} , \frac{z}{1 − 3z} ) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 2 & 4 & 1 & 0 & 0 & ⋯ \\ 4 & 14 & 7 & 1 & 0 & ⋯ \\ 8 & 46 & 35 & 10 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Note also that letting a = 0 and a = −b, respectively, leads to well-known examples (\frac{1}{1−bz} , \frac{z}{1−bz}) in the Bell subgroup and (\frac{1+bz}{1−bz} , z) in the Appell subgroup, respectively.

Any pseudo-involution (g, zg^{k}) can be expanded into a family of pseudo-involutions as follows.

Corollary 4. Let g = g(z) be as in Theorem 2, and let k = d − 1 (resp., k = d) if g satisfies the functional relation (15) (resp., (17)), where γ is a generalized palindrome. Let q ∈ ℕ, and let p = k/q. Then

(g(z^{q}), zg^{p}(z^{q}))^{−1} = (g(−z^{q}), zg^{p}(−z^{q})) .

In particular, this implies the following:

Special Case 1: for q = k and p = 1, we have (g(z^{k}), zg (z^{k}))^{−1} = (g(−z^{k}), zg (−z^{k})),

Special Case 2: if q is odd, then (g(z^{q}), zg^{p}(z^{q})) is a pseudo-involution,

Special Case 3: if k is odd, then (g(z^{k}), zg(z^{k})) is a pseudo-involution.

Proof. Let h = h(z) = zg^{p}(z^{q}), then

z^{q} ∘ h = h^{q} = z^{q}g^{pq}(z^{q}) = z^{q}g^{k}(z^{q}) = (zg^{k}) ∘ (z^{q}).

Moreover,

g(−z^{q}) ∘ h = g ∘ (−h^{q}) = g ∘ (−zg^{k}) ∘ z^{q} = \frac{1}{g} ∘ z^{q} = \frac{1}{g(z^{q})},

so

(zg^{p}(−z^{q})) ∘ h = h · (g^{p} ∘ (−h^{q})) = zg^{p}(z^{q}) · (\frac{1}{g(z^{q})})^{p} = z,

and therefore

(g(z^{q}), zg^{p}(z^{q})) (g(−z^{q}), zg^{p}(−z^{q})) = (1, z).

A similar manipulation shows that (g(−z^{q}), zg^{p}(−z^{q})) (g(z^{q}), zg^{p}(z^{q})) = (1, z) as well, and thus (g(z^{q}), zg^{p}(z^{q}))^{−1} = (g(−z^{q}), zg^{p}(−z^{q})).

When q is odd, we have z^{q} ∘ (−z) = (−z)^{q} = −z^{q} = (−z) ∘ z^{q}, so

g(z^{q}) ∘ (−h) = g ∘ (−h)^{q} = g ∘ (−h^{q}) = \frac{1}{g(z^{q})},

and hence (g(z^{q}), h) is a pseudo-involution.

In fact, note that for odd k in Corollary 4, (g, zg^{k}) is a pseudo-involution if and only if the array (g(z^{k}), zg(z^{k})) is also a pseudo-involution, a fact that we will use later in the paper. In this situation, if k = pq for some odd integer q ∈ ℕ and p ∈ ℚ, then we call (g(z^{q}), zg^{p}(z^{q})) a q-aeration of (g, zg^{k}), and in particular, if p = 1 and q = k, simply an aeration of (g, zg^{k}).

We will now discuss some examples where γ ∈ P_{d}, in particular, when γ is a palindromic polynomial.

Example 5. (Palindromic trees) Consider the class of vertex-colored rooted ordered trees with color set {κ_{i} | 0 ≤ ℓ_{∗} ≤ i ≤ ℓ^{∗}} where a vertex v of color κ_{i} has weight wt(v) = a_{i} and is the root of a subtree with i ordered, possibly empty subtrees. Then the weight of a tree T is defined as the product of weights of its vertices, wt(T) = ∏_{v∈T} wt(v). This allows the weights a_{j} to be negative as well. Then the generating function g = g(z) for the signed weighted enumeration of such trees is

g = 1 + ∑_{i=ℓ_{∗}}^{ℓ^{∗}} a_{i}zg^{i} = 1 + zγ(g),  (19)

where γ = γ(z) = ∑_{i=ℓ_{∗}}^{ℓ^{∗}} a_{i}z^{i}. We say that such a tree satisfies the palindromic condition, or is palindromic, if a_{i} = a_{d−i} for d = ℓ_{∗} + ℓ^{∗} and i ∈ [ℓ_{∗}, ℓ^{∗}]. Note that, for a palindromic class of trees as above, the polynomial γ is palindromic as well, and dar(γ) = d.

Alternatively, we can dispense with colors and leave only weights as follows. Consider a class of rooted ordered trees where a vertex of degree i ∈ [0, ℓ^{∗}] has weight ∑_{k=i}^{l^{∗}} \binom{k}{i}a_{k} (and we set a_{i} = 0 for i ∉ [ℓ_{∗}, ℓ^{∗}]). Note that ∑_{k=i}^{l^{∗}} \binom{k}{i}a_{k} = [z^{i}]γ(z + 1) for 0 ≤ i ≤ ℓ^{∗}. Let g be the ordinary generating function for the enumerating sequence of this class. Then G = g − 1 satisfies the equation G = z · (γ(z + 1) ∘ G) = zγ(G + 1), which is equivalent to (19).

Here are several examples (or families of examples) of palindromic trees.

Example 6. (k-ary trees) Consider the class of (incomplete) k-ary trees, where ℓ_{∗} = ℓ^{∗} = k (see Example 5) and all vertices have weight a ≠ 0. If g = g(z) is the generating function for this class, then g = 1 + azg^{k}, so g = T_{k}(az), where T_{k} = T_{k}(z) is the generating function for the uncolored k-ary trees, satisfying the equation T_{k} = 1 + zT_{k}^{k}. We also have γ(z) = az^{k}, so γ is palindromic with dar(γ) = k + k = 2k, and thus

(T_{k}(az), zT_{k}^{2k−1}(az))

is a pseudo-involution. For example, this yields pseudo-involutions (1 + z, \frac{z}{1+z}) when k = 0, (\frac{1}{1−z}, \frac{z}{1−z}) when k = 1, and (C, zC^{3}) when k = 2, where C = C(z) = \frac{1−\sqrt{1−4z}}{2z} is the Catalan generating function (see \underline{A000108}) and zC^{3} is the generating function of \underline{A000245}.

Example 7. (Schröder trees) If γ = γ(z) is palindromic and has only two nonzero terms, then γ = az^{k} + az^{ℓ} for some a ≠ 0, and dar(γ) = k + ℓ, so

(g, zg^{k+ℓ−1})

is a pseudo-involution. For example, setting k = 1 and ℓ = 2 yields g = r(az) and the pseudo-involution

(r(az), zr^{2}(az)) ,

where r = r(z) is the generating function for the large Schröder numbers \underline{A006318} that satisfies the functional equation r = 1 + zr + zr^{2}. Recall that the n-th large Schröder number counts the number of Schröder paths, i.e., lattice paths from (0, 0) to (2n, 0) with steps (1, 1), (1, −1), (2, 0) that stay on or above the x-axis. The related little Schröder numbers \underline{A001003}, whose generating function s = s(z) satisfies s = (r − 1)/2 = 1/(1 − zr), count the lattice paths with the same steps and no (2, 0) (“level”) steps on the x-axis.

Example 8. (Motzkin trees) Motzkin trees are ordered trees where each internal vertex has outdegree 1 or 2. Thus the generating function m for Motzkin trees satisfies the functional equation m = 1 + zm + z^{2}m^{2} (see \underline{A001006}). Let m̃ = 1 + zm be the generating function for the planted Motzkin trees (i.e., Motzkin trees with the root of degree at most 1), then m̃ = 1+z(1+(m̃−1)m̃) = 1+z(1−m̃+m̃^{2}), so in this case γ = 1−z+z^{2}, a palindrome with dar(γ) = 0 + 2 = 2, and hence (m̃, zm̃) is a pseudo-involution (see \underline{A086246}). We also note that m is the generating function for the number of Motzkin paths, i.e., paths from (0, 0) to (n, 0) with unit steps (1, 1), (1, 0), (1, −1) staying on or above the x-axis, as well as for the number of (partial) noncrossing matchings of points labeled 1, …, n (i.e., if a < b < c < d, then a matching cannot simultaneously include pairs ac and bd), and m̃ is the generating function for the number of (partial) noncrossing matchings where 1 is unmatched (or the matching is empty).

Example 9. (Doubling at the root) Consider a class of colored k-ary trees where the root of any nonempty tree has 2 possible colors and all other vertices have only one color. The generating function for such k-ary trees is t_{k} = 2T_{k} − 1, where T_{k} is as above. Then

t_{k} = 1 + 2(T_{k} − 1) = 1 + 2zT_{k}^{k} = 1 + 2z (\frac{1 + t_{k}}{2} )^{k} ,

so in this case γ = 2 (\frac{1+z}{2})^{k} is palindromic with dar(γ) = 0 + k = k, and therefore (t_{k}, zt_{k}^{k−1}) is a pseudo-involution. In particular, this yields (\frac{1+z}{1−z}, z) for k = 1, and (2C − 1, z(2C − 1)) for k = 2 (\underline{A068875}).

Similarly, it is easy to check that the functional equation g = 1 + z(1 + g)^{k} yields g = t_{k}(2^{k−1}z) and f = zg^{k−1} for a pseudo-involution (g, f).

Example 10. (Doubling at the leaves) Consider a class of colored k-ary trees where the leaves of any nonempty tree have 2 possible colors and all internal vertices have only one color. The generating function u_{k} for such trees satisfies the functional equation

u_{k} = 1 + z(1 + u_{k}^{k}),  (20)

so in this case γ = 1 + z^{k} is palindromic with dar(γ) = 0 + k = k, and therefore (u_{k}, zu_{k}^{k−1}) is a pseudo-involution. Since u_{k} = (1 + z) + zu_{k}^{k}, we obtain after some routine algebra that

u_{k} = (1 + z)T_{k}(z(1 + z)^{k−1}).

In particular, this yields (\frac{1+z}{1−z}, z) for k = 1, and (u_{2}, zu_{2}) for k = 2, where u_{2}(z) = (1 + z)C(z(1 + z)), or equivalently, zu_{2} = (zC) ∘ (z + z^{2}), with the coefficient sequence given by \underline{A025227}.

Note the following curious duality between the pseudo-involutory functions zt_{k}^{k−1} and zu_{k}^{k−1} from Examples 9 and 10. Since zT_{k}^{k−1} = \overline{(z(1 − z)^{k−1})} and 1 + zT_{k}^{k−1} = (2T_{k} − 1)/T_{k}, we have

\begin{aligned}zt_{k}^{k−1} & = (z(1 + z)^{k−1}) ∘ \overline{(z(1 − z)^{k−1})}, \\ zu_{k}^{k−1} & = \overline{(z(1 − z)^{k−1})} ∘ (z(1 + z)^{k−1}), \end{aligned}

and z(1 + z)^{k−1} = (−z) ∘ (z(1 − z)^{k−1}) ∘ (−z). Likewise, for the aerations zt_{k}(z^{k−1}) and zu_{k}(z^{z−1}), we have

\begin{aligned}zt_{k}(z^{k−1}) & = (z + z^{k}) ∘ \overline{(z − z^{k})}, \\ zu_{k}(z^{k−1}) & = \overline{(z − z^{k})} ∘ (z + z^{k}). \end{aligned}

Furthermore, if k is odd, then z + z^{k} = (−z) ∘ (z − z^{k}) ∘ (−z), which implies that both zt_{k}(z^{k−1}) and zu_{k}(z^{k−1}) are pseudo-involutory.

Some well-known pseudo-involutions arise from functions γ that are not polynomials.

Example 11. (Central binomial coefficients) Consider γ(z) = \frac{4z^{2}}{1+z}, then γ is palindromic as a ratio of two palindromic polynomials. Moreover, dar(γ) = (2 + 2) − (0 + 1) = 3, and if

g = 1 + z \frac{4g^{2}}{1 + g} ,

then g = \frac{1}{\sqrt{1−4z}} = B(z) = B, the generating function for the central binomial coefficients. In this case, we obtain the pseudo-involution

(B, zB^{2}) = (\frac{1}{\sqrt{1 − 4z}} , \frac{z}{1 − 4z} ) .

Example 12. (Secondary RNA structures) A secondary RNA structure can be modeled as a noncrossing partial matching of points on a straight line where no two adjacent points can be in the same pair. Let g be the generating function of the counting sequence \underline{A004148} for the secondary RNA structures (see, e.g., Cameron and Nkwanta [10]), then g satisfies the functional equation

g = 1 + zg + z^{2}g(g − 1).

Then

g − 1 = \frac{zg}{1 − z^{2}g} = z \frac{g}{1 − z^{2}g} ,

so

\frac{(1 − z)^{2}}{z} ∘ g = \frac{(g − 1)^{2}}{g} = \frac{z^{2}g}{(1 − z^{2}g)^{2}} = \frac{z}{(1 − z)^{2}} ∘ (z^{2}g),

or, equivalently,

z^{2}g = \overline{(\frac{z}{(1 − z)^{2}} )} ∘ \frac{(1 − z)^{2}}{z} ∘ g = (zC^{2}(−z)) ∘ \frac{(1 − z)^{2}}{z} ∘ g.

Therefore,

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

and hence,

g = 1 + z · (\frac{z}{C (−\frac{(1−z)^{2}}{z} )} ∘ g).

To find the darga of

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

note that (1 − z)^{2}/z is a generalized palindrome of darga (0 + 2) − (1 + 1) = 0, and therefore C(−(1 − z)^{2}/z) also has darga 0. Thus, dar(γ) = dar(z) − 0 = 2, and hence (g, zg^{2−1}) = (g, zg) is a pseudo-involution in the Bell subgroup.

When γ is a quadratic polynomial, not necessarily a palindrome, we have the following general result.

Theorem 13. For constants a, b, c, where a ≠ 0, let f ∈ F_{1} satisfy the functional equation

f = z(a + bf + cf^{2}),  (21)

in other words, let f have A_{f} = a + bz + cz^{2}. Let t = 1 + (b/a)f = (a + bf)/a. Then h = zt is pseudo-involutory with B_{h} = bC(acz).

Note that for c = 0, C(0) = 1 is the constant term of the power series expansion of C(z), and indeed in that case h = \frac{z}{1−bz} and B_{h} = b.

The way we find the B-function in the proof that follows is somewhat ad hoc. We will develop a more general method for finding B-functions in Section 4.1, then apply it (see Example 28) to recover this B-function result.

Proof. When b = 0, we have t = 1, h = z, and B_{h} = B_{z} = 0. Assume b ≠ 0. Substituting f = (a/b)(t − 1) into (21), we obtain

\begin{aligned}t & = 1 + \frac{b}{a}f = 1 + \frac{b}{a}z(a + bf + cf^{2}) \\ & = 1 + \frac{b}{a}z (a + b\frac{a}{b}(t − 1) + c (\frac{a}{b}(t − 1))^{2}) \\ & = 1 + z (bt + \frac{ac}{b}(t − 1)^{2}) , \end{aligned}  (22)

and notice that the γ function for t is

γ(z) = bz + \frac{ac}{b}(z − 1)^{2} ∈ P_{2},  (23)

since both summands are palindromic of darga 2. Therefore h = zt^{2−1} = zt is pseudoinvolutory.

Finally, for the B-function of h = zt, we have zt = z + z^{2}tB_{zt}(z^{2}t), i.e., B_{zt}(z^{2}t) = \frac{t−1}{zt}. Let g = g(z) = \frac{1}{b}B_{zt}(z^{2}t), then

g = \frac{t − 1}{bzt} = \frac{(b/a)f}{bzt} = \frac{f}{azt} = \frac{f/z}{at} = \frac{a + bf + cf^{2}}{a + bf}

= 1 + \frac{cf^{2}}{a + bf} = 1 + \frac{cf^{2}}{at} = 1 + acz^{2}t (\frac{f}{azt})^{2}

= 1 + (aczh) g^{2},

and g = 1 + (aczh)g^{2} has a unique power series solution g = C(aczh), which implies that

B_{h}(z) = bC(acz).

Example 14. If f = zm, where m is the generating function for the Motzkin numbers, then a = b = c = 1, so h = z(1 + zm) = zm̃ and B_{h} = C.

Example 15. If f = C−1 = zC^{2}, then f = z(1+2f +f^{2}), so h = z(1+2f) = z(2C−1) = zt_{2} from Example 9 and B_{h} = 2C.

Example 16. If f = zm_{k}, where m_{k} = 1 + kzm_{k} + z^{2}m_{k}^{2} is the generating function for the k-Motzkin numbers counting Motzkin paths with horizontal steps of k colors. Then f = z(1 + kf + f^{2}), so h = z(1 + kf) = z(1 + kzm_{k}) = zm̃_{k} and B_{h} = kC. In particular, letting k = 1 and k = 2 yields Examples 14 and 15, respectively, while letting k = 3 yields the planted hex trees [15] (see \underline{A002212}).

Example 17. If f = u_{2}−1 = z(1+u_{2}^{2}), where u_{2} is as in Example 10, then f = z(2+2f +f^{2}), so h = z(2 + 2f)/2 = z(1 + f) = zu_{2} and B_{h} = 2C(2z).

Example 18. If f = r−1, where r is the generating function for the large Schröder numbers, then r−1 = z(r+r^{2}), i.e., f = z(2+3f +f^{2}), so h = z(2+3f)/2 = z(3r−1)/2 = z(r+s−1), where s is the generating function for the little Schröder numbers, and B_{h} = 3C(2z). The coefficient sequence of t (that we may call huge Schröder numbers) is given by \underline{A238113}.

Corollary 19. Let g = g(z) be the function defined by the functional relation

g = 1 + z(a + bg + cg^{2})

for some constants a, b, c such that a + b + c ≠ 0. Let

t = t(z) = \frac{(b + 2c)g + (a − c)}{a + b + c} = 1 + \frac{b + 2c}{a + b + c}(g − 1).

Then zt is a pseudo-involutory, and its B-function is

B_{zt}(z) = (b + 2c)C((a + b + c)cz).

Proof. Let f = r − 1 in Theorem 13.

Remark 20. In particular, as expected from the prior discussion, t = g when c = a in Corollary 19, and then zg is pseudo-involutory with B_{zg} = (b + 2c)C((b + 2c)cz). For example, when g = m̃, we have a = c = 1 and b = −1 in Corollary 19, so B_{zm̃} = C, as before.

Remark 21. Note also that when a = 0, we obtain a generalization of large and little Schröder number generating functions r = r(z) and s = s(z), respectively, where

\begin{aligned}r & = 1 + z(br + cr^{2}) = 1 + (b + c)zrs, \\ s & = \frac{b + cr}{b + c} = \frac{1}{1 − czr} = 1 + czrs, \\ t & = r + s − 1 = 1 + (b + 2c)zrs. \end{aligned}

The Schröder numbers correspond to b = c = 1, whereas the Catalan numbers correspond to b = 0, c = 1. In the latter case, r = s = C, so that t = 2r − 1 = 2C − 1, and we recover the pseudo-involutory function z(2C − 1). To interpret this combinatorially, notice that, given some classes of trees enumerated by the coefficient sequences of r and s, the corresponding structure for t is obtained by taking the combinatorial sum of the r- and s-structures and identifying the two empty objects. The “doubling” mentioned above for k-ary trees generalizes in this case to the disjoint sum of the nonempty “large” and “little” objects.

Another related combinatorial interpretation of r and s is (b, c)-Schröder paths, which are Schröder paths where level steps L = (2, 0) come in b colors, while up-steps U = (1, 1) and down-steps D = (1, −1) come in c colors. The large (b, c)-Schröder paths (corresponding to r) have no further restrictions, while the little (b, c)-Schröder paths (corresponding to s) additionally have no level steps at height 0.

Alternatively, t counts the (b, c)-Schröder paths, such that if the leftmost D comes before the leftmost L, then that leftmost D has 2c colors, i.e., twice as many as other downsteps. To see this, note that any nonempty (b, c)-Schröder path can be uniquely decomposed either as U^{k−1}LP_{1}DP_{2}d ⋯ DP_{k} or as U^{k}DP_{1}DP_{2}D ⋯ DP_{k} for some positive integer k and smaller (b, c)-Schröder paths P_{1}, …, P_{k}. In the latter case, the leftmost D (marked in bold) can be colored in 2c, rather than c, colors. Then the number of such paths has the generating function

1 + \frac{bzr}{1 − czr} + \frac{2czr}{1 − czr} = 1 + (b + 2c)zrs = t.

We conclude this section with two applications of Theorem 2 to exponential Riordan group. Both of these examples are related to labeled trees.

Example 22. (Rooted labeled trees) The set of labeled trees with vertices {0, 1, …, n}, n ≥ 0, rooted at 0 are counted by the sequence 1, 1, 3, 16, 125, 1296, …, (n + 1)^{n−1}, … (\underline{A000272} without the initial 1), whose exponential generating function T = T (z) satisfies the functional equation

T = e^{zT} ,  (24)

or, equivalently, zT = ze^{zT}, i.e., zT = \overline{(ze^{−z})}. From Equation (17), we have that γ = z, a palindrome with dar(γ) = 1+1 = 2. Therefore, from the second part of Theorem 2, it follows that [T, zT^{2}] is a pseudo-involution in the 2-Bell subgroup of the exponential Riordan group. An application of Lagrange inversion shows that the companion zT^{2} of T is the exponential generating function of the sequence

{2n(n + 1)^{n−2}}_{n≥0} = {0, 1, 4, 24, 200, 2160, 28812, … }

(a shifted version of \underline{A089946}). Similarly, the kth column of the matrix [T, zT^{2}] has exponential generating function T · (zT^{2})^{k}/k! = z^{k}T^{2k+1}/k!, which, after applying Lagrange inversion and some algebraic manipulations, yields

[T, zT^{2}] = [(2k + 1)\binom{n}{k}(n + k + 1)^{n−k−1}]_{n,k≥0} ,

which begins with

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 6 & 1 & 0 & 0 & 0 \\ 16 & 45 & 15 & 1 & 0 & 0 \\ 125 & 432 & 210 & 28 & 1 & 0 \\ 1296 & 5145 & 3200 & 630 & 45 & 1 \end{matrix}] .

Note that the associated Riordan array

[1, zT^{2}] = [2k\binom{n}{k}(n + k)^{n−k−1}]_{n,k≥0}

in the Lagrange subgroup begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 0 & 0 & 0 \\ 0 & 24 & 12 & 1 & 0 & 0 \\ 0 & 200 & 144 & 24 & 1 & 0 \\ 0 & 2160 & 1960 & 480 & 40 & 1 \end{matrix}] .

Example 23. (Rooted labeled trees with 2-colored leaves) Consider a function S = S(z) that satisfies a functional equation similar to (24):

S = e^{z(1+S)}.  (25)

Then zS = ze^{z}e^{zS}, or, in other words, zS = (zT) ∘ (ze^{z}), where T is from Example 22. Here, the function γ from Equation (17) is γ = 1 + z, a palindrome with dar(γ) = 0 + 1 = 1, and thus [S, zS] is a pseudo-involution in the Bell subgroup of the exponential Riordan group. It is easy to check directly that zS is pseudo-involutory: note that

zS = (zT) ∘ (ze^{z}) = \overline{(ze^{−z})} ∘ (ze^{z}) = (−z) ∘ \overline{(ze^{z})} ∘ (−z) ∘ (ze^{z}),  (26)

and thus

\overline{(zS)} = \overline{(ze^{z})} ∘ (−z) ∘ (ze^{z}) ∘ (−z) = (−z) ∘ (zS) ∘ (−z).

The coefficient sequence of S begins 1, 2, 8, 56, 576, 7872, … (\underline{A349562}) and counts rooted labeled forests with 2-colored leaves. Equivalently, the sequence \underline{A349562} counts rooted labeled trees on vertices 0, 1, …, n rooted at 0 with 2-colored leaves (except the singleton tree 0 is 1-colored). The coefficient sequence of zS begins 0, 1, 4, 24, 224, 2880, 47232, … (see \underline{A216857} and \underline{A038049}) and counts, e.g., rooted labeled trees on vertices 1, 2, …, n with 2-colored leaves (with the exception that the singleton tree is 1-colored). Moreover, Lagrange inversion for zT and the identity zS = (zT) ∘ (ze^{z}) yield [\frac{z^{n}}{n!} ] zS = ∑_{j=1}^{n} \binom{n}{j}j^{n−1} and [\frac{z^{n}}{n!} ] S = ∑_{j=0}^{n} \binom{n}{j}(j + 1)^{n−1}, and similarly,

[\frac{z^{n}}{n!} ] \frac{S(zS)^{k}}{k!} = \binom{n}{k}(k + 1) ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k + 1)^{n−k−1}.

Thus, the array

[S, zS] = [\binom{n}{k}(k + 1) ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k + 1)^{n−k−1}]_{n,k≥0}

begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 8 & 8 & 1 & 0 & 0 & 0 \\ 56 & 72 & 18 & 1 & 0 & 0 \\ 576 & 832 & 288 & 32 & 1 & 0 \\ 7872 & 12160 & 5040 & 800 & 50 & 1 \end{matrix}] ,

and the associated array

[1, zS] = [\binom{n}{k}k ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k)^{n−k−1}]_{n,k≥0}

in the Lagrange subgroup begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 0 & 0 & 0 \\ 0 & 24 & 12 & 1 & 0 & 0 \\ 0 & 224 & 144 & 24 & 1 & 0 \\ 0 & 2880 & 2080 & 480 & 40 & 1 \end{matrix}] .

4 B-sequence and B-function

As we mentioned earlier (see Equation (9) on page 7), given a pseudo-involution (g, f), its B-sequence {b_{n}}_{n≥0} and B-function B_{f}(z) = ∑_{n=0}^{∞} b_{n}z^{n} are defined so that the pseudoinvolutory function f satisfies

f − z = (zB_{f}) ∘ (zf) = zfB_{f}(zf) = ∑_{n=0}^{∞} b_{n}(zf)^{n+1}.  (27)

Note that the B_{f} depends only on f. In fact, the B-sequence of f, together with the leftmost column of (g, f), gives us enough information to determine f and the entire matrix (g, f). For example, the B-function of f = zC^{3} is B_{zC^{3}} = 3 + z, a fact that we shall re-establish later in this section, so its B-sequence is 3, 1, 0, 0, 0, . . .. Looking at the matrix (C, zC^{3}), whose first few rows and columns are given by

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 4 & 1 & 0 & 0 & 0 \\ 5 & 14 & 7 & 1 & 0 & 0 \\ 14 & 48 & 35 & 10 & 1 & 0 \\ 42 & 165 & 154 & 65 & 13 & 1 \end{matrix}] ,

we see that, for instance, 154 = 48 + 3 · 35 + 1 · 1. Every entry other than those in the leftmost column can be computed from this simple 3,1-rule.

4.1 B-functions for ordinary Riordan arrays with palindromic γ

Recall from Theorem 2, that if g = g(z) satisfies the functional equation (15), where γ = γ(z) is a generalized palindrome of darga d, then (g, zg^{d−1}) is a pseudo-involution. Then

dar (\frac{γ(z)}{z^{d/2}}) = d − 2 · \frac{d}{2} = 0,

so \frac{γ(z)}{z^{d/2}} is a function of z + \frac{1}{z}, or, equivalently, a function of z + \frac{1}{z} − 2 = \frac{(z−1)^{2}}{z}. Define a function δ = δ(z) so that

δ (\frac{(z − 1)^{2}}{z} ) = \frac{γ(z)}{z^{d/2}} ,  (28)

and suppose that δ(0) ≠ 0. Then let the function D = D(z) be defined by

zD^{2} = \overline{(\frac{z}{δ^{2}} )}.  (29)

In other words, from Equation (6), we have D^{2} = 1/A_{z/δ^{2}} and δ^{2} = A_{zD^{2}}.

Lemma 24. Let g = g(z) satisfy the functional equation g = 1 + zγ(g), where γ = γ(z) is a generalized palindrome of darga d, and let the functions δ and D be as in (28) and (29). Then

\frac{(g − 1)^{2}}{g} = (zD^{2}) ∘ (z^{2}g^{d−1}).  (30)

Proof. We have

\frac{(g − 1)^{2}}{g} = \frac{(zγ(g))^{2}}{g} = z^{2}g^{d−1} · (\frac{γ(g)}{g^{d/2}})^{2} = z^{2}g^{d−1} · δ^{2} (\frac{(g − 1)^{2}}{g} ) ,

or, equivalently,

z^{2}g^{d−1} = (\frac{z}{δ^{2}} ) ∘ (\frac{(g − 1)^{2}}{g} ) ,

which implies (30), as claimed.

On the other hand, note that for h = h(z) = zg^{d−1}, we have h − z = zhB_{h}(zh), and thus

(zB_{h}^{2}) ∘ (zh) = (zB_{h}^{2}) ∘ (z^{2}g^{d−1}) = \frac{(h − z)^{2}}{zh} = \frac{(g^{d−1} − 1)^{2}}{g^{d−1}} = g^{d−1} + \frac{1}{g^{d−1}} − 2,  (31)

so the final piece we need to find B_{h} is the family of polynomials p_{k} = p_{k}(z), k ≥ 0, such that

(zp_{k}) ∘ (\frac{(g − 1)^{2}}{g} ) = \frac{(g^{k+1} − 1)^{2}}{g^{k+1}} ,  (32)

or, equivalently,

(zp_{k}) ∘ (g + \frac{1}{g} − 2) = g^{k+1} + \frac{1}{g^{k+1}} − 2.

In addition, consistent with the above definition, we let p_{−1}(z) = 0. Recall that for Chebyshev polynomials of the first kind T_{k}(z), k ≥ 0, defined by T_{k}(cos θ) = cos(kθ), we have the identity

T_{k} (\frac{z + \frac{1}{z}}{2} ) = \frac{z^{k} + \frac{1}{z^{k}}}{2} .

Therefore,

p_{k}(z) = \frac{1}{z} (2T_{k+1} (\frac{z + 2}{2}) − 2) = (\frac{T_{k+1} − 1}{z − 1}) ∘ (\frac{z + 2}{2}) .  (33)

Consider the Riordan array \underline{A156308},

[d_{n,k}]_{n,k≥0} = (\frac{1 + z}{(1 − z)^{3}} , \frac{z}{(1 − z)^{2}} ) ,

where

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

Its first few rows are given by

[\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 9 & 6 & 1 & 0 & 0 \\ 16 & 20 & 8 & 1 & 0 \\ 25 & 50 & 35 & 10 & 1 \end{matrix}] .

Lemma 25. The array [d_{n,k}]_{n,k≥0} satisfies the identity

[d_{n,k}]_{n,k≥0} [(\frac{(g − 1)^{2}}{g} )^{k+1}]_{k≥0}^{T} = [\frac{(g^{n+1} − 1)^{2}}{g^{n+1}} ]_{n≥0}^{T}  (34)

(where the superscript ^{T} denotes the transpose). Proof. The proof of this identity follows from the fundamental theorem of Riordan arrays (1), since

(\frac{1 + z}{(1 − z)^{3}} , \frac{z}{(1 − z)^{2}} ) ∗ \frac{\frac{(g−1)^{2}}{g}}{1 − \frac{(g−1)^{2}}{g} z} = \frac{g}{1 − zg} + \frac{1/g}{1 − z/g} − \frac{2}{1 − z} .

Thus, the polynomials p_{k}(z) of (32) are given by

p_{k}(z) = ∑_{j=0}^{k} d_{k,j}z^{j}.  (35)

Moreover, letting z = cos θ and applying routine trigonometric identities shows that

\begin{aligned}\frac{T_{2l+1}(z) − 1}{z − 1} & = (U_{l}(z) + U_{l−1}(z))^{2}, \\ \frac{T_{2l+2}(z) − 1}{z − 1} & = 2(1 + z)U_{l}(z)^{2}, \end{aligned}

where U_{l}(z), l ≥ 0, defined by U_{l}(cos θ) = \frac{sin((l+1)θ)}{sin θ}, are the Chebyshev polynomials of the second kind. Therefore, polynomials p_{k} can be also expressed in terms of the polynomials U_{l} as follows (see also the notes for \underline{A156308}):

\begin{aligned}p_{2l}(z) & = (U_{l} (\frac{z + 2}{2}) + U_{l−1} (\frac{z + 2}{2}))^{2} , \\ p_{2l+1}(z) & = (z + 4) (U_{l} (\frac{z + 2}{2}))^{2} , \end{aligned}  (36)

where we note that U_{−1}(z) = 0. A Riordan array [c_{k,n}]_{k,n≥0} where the generating function for row k ≥ 0 is U_{k}(\frac{z}{2}) is given by \underline{A049310}, in other words,

[c_{k,n}]_{k,n≥0} = (\frac{1}{1 + y^{2}} , \frac{y}{1 + y^{2}} ) ,

and

c_{k,n} = \begin{cases}(−1)^{\frac{k+n}{2}} \binom{\frac{k+n}{2}}{n}, & if k − n ≥ 0 is even; \\ 0, & otherwise. \end{cases}  (37)

The preceding discussion, including Lemmas 24 and 25, implies the following theorem.

Theorem 26. Let g = g(z) satisfy the functional equation g = 1 + zγ(g), where γ = γ(z) is a generalized palindrome of darga d, and let the functions δ and D be as in (28) and (29). Then

B_{h} = D\sqrt{p_{|d−1|−1}(zD^{2})} = \begin{cases}D\sqrt{p_{d−2}(zD^{2})}, & if d ≥ 2; \\ 0, & if d = 1; \\ D\sqrt{p_{−d}(zD^{2})}, & if d ≤ 0. \end{cases}  (38)

Proof. Indeed, if d ≥ 2, then from Lemma 24 and Equations (31) and (32) we have

zB_{h}^{2} = (zp_{(d−1)−1}) ∘ (zD^{2}) = (zp_{d−2}) ∘ (zD^{2}).

If d = 1, then it is easy to see that h = f = z and thus B_{h} = 0. If d ≤ 0, then we note that

g^{d−1} + \frac{1}{g^{d−1}} − 2 = g^{1−d} + \frac{1}{g^{1−d}} − 2,

so, for d ≤ 0, we have

B_{h} = D\sqrt{p_{(1−d)−1}(zD^{2})} = D\sqrt{p_{−d}(zD^{2})}.

Remark 27. We can combine the steps involved in finding, successively, δ, D, p_{k}, and zB_{h}^{2} into explicit formulas for zD^{2} and zB_{h}^{2} that involve only γ(z), namely,

\begin{aligned}zD^{2} & = \frac{(z − 1)^{2}}{z} ∘ \overline{(\frac{z^{d−1}(z − 1)^{2}}{γ^{2}(z)} )}, \\ zB_{h}^{2} & = \frac{(z^{d−1} − 1)^{2}}{z^{d−1}} ∘ \overline{(\frac{z^{d−1}(z − 1)^{2}}{γ^{2}(z)} )}. \end{aligned}  (39)

However, we believe that for practical calculations, breaking down the procedure into steps as described above is more effective.

Example 28. Let us apply Theorem 26 to re-establish Theorem 13. The function t in Theorem 13 satisfies the equation t = 1 + zγ(t), where γ(z) = bz + \frac{ac}{b}(z − 1)^{2} (see (23)) is

palindromic of darga d = 2. Thus, δ (\frac{(z−1)^{2}}{z} ) = \frac{γ(z)}{z} = b + \frac{ac}{b} \frac{(z−1)^{2}}{z}, and hence, δ = δ(z) = b + \frac{ac}{b}z. Therefore,

\frac{z}{δ^{2}} = \frac{z}{(b + \frac{ac}{b}z)^{2}} = \frac{\frac{z}{b^{2}}}{(1 + ac\frac{z}{b^{2}} )^{2}} = \frac{z}{ac} ∘ \frac{z}{(1 + z)^{2}} ∘ \frac{acz}{b^{2}} ,

so

zD^{2} = \overline{(\frac{z}{δ^{2}} )} = \frac{b^{2}z}{ac} ∘ (zC^{2}) ∘ (acz) = b^{2}zC^{2}(acz),

and thus D = bC(acz), so B_{zt} = D\sqrt{p_{0}(zD^{2})} = D = bC(acz).

4.2 B-functions for exponential Riordan arrays with palindromic γ

Recall from Theorem 2, that if g = g(z) satisfies the functional equation (17), where γ = γ(z) is a generalized palindrome of darga d, then the exponential Riordan array [g, zg^{d}] is a pseudo-involution (as is the ordinary Riordan array (g, zg^{d})). As in Section 4.1, we have

dar (\frac{γ(z)}{z^{d/2}}) = d − 2 · \frac{d}{2} = 0.

Define a function ε = ε(z) so that

ε (log(z)) = \frac{γ(z)}{z^{d/2}} ,  i.e. ε(z) = \frac{γ(e^{z})}{e^{dz/2}} ,  (40)

and suppose that ε(0) = γ(1) ≠ 0. Then let the function E = E(z) be defined by

zE = \overline{(z/ε)} = \overline{(\frac{ze^{dz/2}}{γ(e^{z})} )}.  (41)

In other words, from Equation (6), we have E = 1/A_{z/ε} and ε = A_{zE}. Then we have the following lemma.

Lemma 29. Let g = g(z) satisfy the functional equation g = e^{zγ(g)}, where γ = γ(z) is a generalized palindrome of darga d, and let the functions δ and D be as in (40) and (41). Then

log g = (zE) ∘ \sqrt{z} ∘ (z^{2}g^{d}).  (42)

Proof. This follows immediately from the fact that

\frac{z}{ε} ∘ log g = \frac{log g}{ε(log g))} = \frac{zγ(g)}{γ(g)/g^{\frac{d}{2}}} = zg^{d/2} = \sqrt{z^{2}g^{d}}.

This lets us find the B-function of the pseudo-involutory companion h = zg^{d} of g.

Theorem 30. Let g = g(z) satisfy the functional equation g = e^{zγ(g)}, where γ = γ(z) is a generalized palindrome of darga d, let h = zg^{d}, and let the functions ε and E be as in (40) and (41). Then

B_{h} = (\frac{2 sinh (\frac{d}{2}zE)}{z}) ∘ \sqrt{z}.  (43)

In other words, B_{h}(z) = ∑_{j=0}^{∞} β_{j} \frac{z^{j}}{(2j+1)!}, where β_{j} is the coefficient at \frac{z^{2n+1}}{(2n+1)!} in the power series expansion of 2 sinh(dzE/2).

Proof. As before, we have

(zB_{h}^{2}) ∘ (z^{2}g^{d}) = \frac{(h − z)^{2}}{zh} = \frac{(g^{d} − 1)^{2}}{g^{d}} = \frac{(e^{dz} − 1)^{2}}{e^{dz}} ∘ (log g) = 4 sinh^{2}(dz/2) ∘ (log g).

Therefore, from Lemma 29, we obtain

zB_{h}^{2} = 4 sinh^{2}(dz/2) ∘ (zE) ∘ \sqrt{z},

or, equivalently,

B_{h} = \frac{(2 sinh(dz/2)) ∘ (zE) ∘ \sqrt{z}}{\sqrt{z}} = (\frac{2 sinh (\frac{d}{2}zE)}{z}) ∘ \sqrt{z}.

Example 31. Consider the set of labeled trees of Example 22 with vertices {0, 1, …, n}, n ≥ 0 and rooted at 0. The number of such trees on n + 1 vertices is (n + 1)^{n−1}, and their exponential generating function T = T (z) is given by the equation T = e^{zT}. Thus, in this case, we have γ(z) = z of darga d = 1 + 1 = 2, so the pseudo-involutory companion of T is h = zT^{2}, and

ε(z) = \frac{e^{z}}{e^{z}} = 1, zE = \overline{(z/ε)} = z,

so

B_{h} = \frac{2 sinh(z)}{z} ∘ \sqrt{z} = \frac{2 sinh(\sqrt{z})}{\sqrt{z}} = 2 ∑_{j=0}^{∞} \frac{z^{j}}{(2j + 1)!} ,

and thus β_{j} = 2 for all j ≥ 0. We saw in Example 22 that the exponential Riordan arrays [T, zT^{2}] and [1, zT^{2}] are given by

\begin{aligned}[T, zT^{2}] & = [(2k + 1)\binom{n}{k}(n + k + 1)^{n−k−1}]_{n,k≥0} , \\ [1, zT^{2}] & = [2k\binom{n}{k}(n + k)^{n−k−1}]_{n,k≥0} , \end{aligned}

so their reductions (as in Definition 1) are

\begin{aligned}red[T, zT^{2}] & = [(2k + 1)(n + k + 1)^{n−k−1}]_{n≥k≥0} , \\ red[1, zT^{2}] & = [2k(n + k)^{n−k−1}]_{n≥k≥0} , \end{aligned}

with all entries above the main diagonal equal to 0. (Here we evaluate the entry at (n, k) = (0, 0) of [1, zT^{2}] and red[1, zT^{2}] as 1, similarly to other entries on the main diagonal where n = k > 0.) Substituting these values into the recurrence relation (14), we obtain the following respective identities for n ≥ k ≥ 0:

(2k + 3)(n + k + 3)^{n−k−1}

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

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

where we canceled the factor of 2 in the second identity. It would be interesting to see a combinatorial interpretation of the above identities.

Example 32. Consider the function S of Example 23 defined by S = e^{z(1+S)}. Then γ(z) = 1 + z is palindromic with darga d = 0 + 1 = 1, so the pseudo-involutory companion of S is h = zS. Moreover,

ε = \frac{ze^{z/2}}{1 + e^{z}} = \frac{2z}{2 cosh(z/2)} = (z/2) sech(z/2) = (z sech(z)) ∘ (z/2),

so

zE = \overline{(z sech(z)) ∘ (z/2)} = 2 \overline{(z sech(z))}

and

B_{h} = \frac{2 sinh(zE/2)}{z} ∘ \sqrt{z} = \frac{2 sinh(z) ∘ \overline{(z sech(z))}}{z} ∘ \sqrt{z}

As in the previous example, we want

β_{j} = [\frac{z^{j}}{(2j + 1)!}] B_{h} = [\frac{z^{2j+1}}{(2j + 1)!}] (2 sinh(z) ∘ \overline{(z sech(z))}) .

This can be found using Lagrange inversion, as we need the odd-power coefficients of 2 sinh(u(z)) where u = u(z) satisfies the equation u = z cosh(u). After some routine manipulations, we obtain

β_{j} = \begin{cases}2, & if j = 0; \\ ∑_{i=0}^{j} \binom{2j+2}{i}(j + 1 − i)^{2j}, & if j ≥ 1. \end{cases}

In other words, β_{j} = 2 · \underline{A007106}(j + 1), that is twice the number of labeled trees on 2j + 2 vertices with all degrees odd.

We also saw in Example 23 that the exponential Riordan arrays [S, zS] and [1, zS] are given by

\begin{aligned}[S, zS] & = [\binom{n}{k}(k + 1) ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k + 1)^{n−k−1}]_{n,k≥0} , \\ [1, zS] & = [\binom{n}{k}k ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k)^{n−k−1}]_{n,k≥0} , \end{aligned}

so their reductions (as in Definition 1) are

\begin{aligned}red[S, zS] & = [(k + 1) ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k + 1)^{n−k−1}]_{n≥k≥0} , \\ red[1, zS] & = [k ∑_{j=0}^{n−k} \binom{n − k}{j}(j + k)^{n−k−1}]_{n≥k≥0} , \end{aligned}

with all entries above the main diagonal equal to 0. The matrix red[S, zS] begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 8 & 4 & 1 & 0 & 0 & 0 \\ 56 & 24 & 6 & 1 & 0 & 0 \\ 576 & 208 & 48 & 8 & 1 & 0 \\ 7872 & 2432 & 504 & 80 & 10 & 1 \end{matrix}] ,

and the matrix red[1, zS] is simply red[S, zS] shifted 1 row down and 1 column to the right, with the new first column [1, 0, 0, 0, …]^{T} prepended.

As in the Example 31, it would be interesting to find a combinatorial interpretation of the recurrence (14) for the exponential Riordan arrays [S, zS] and [1, zS].

4.3 B-sequence and aeration

Even though Theorem 26 and Theorem 30 give general solutions for B-functions, that general solution can be simplified for some special families, such as when g satisfies (15) and d is even, or when g satisfies (17) and d is odd. Then we see from Corollary 4 that (g(z^{d−1}), zg(z^{d−1})), or, respectively, (g(z^{d}), zg(z^{d})), is also a pseudo-involution. The same applies to the corresponding exponential Riordan arrays. We shall see now how the B-functions of these un-aerated and aerated Riordan arrays (both ordinary and exponential) are related.

Theorem 33 (“The Twin Powers Theorem”). Let g = g(z) be a power series with g(0) ≠ 0, and suppose that, for some integer l ≥ 0,

f = zg(z^{2l+1}) or h = zg^{2l+1}(z)  (44)

is pseudo-involutory. Then both functions f and h are pseudo-involutory, and

(zB_{h}^{2}) ∘ (z^{2l+1}) = (zP_{l}^{2}) ∘ (zB_{f}^{2}),  (45)

where

P_{l} = P_{l}(z) = ∑_{j=0}^{l} a_{lj}z^{j}  (46)

and

a_{lj} = \frac{2l + 1}{2j + 1}\binom{l + j}{2j}, j, l ≥ 0.  (47)

Note that we only need to know that one of f or h is a pseudo-involution, then so is the other one. Note also that a_{lj} = 0 if j > l, so [a_{lj}]_{l,j≥0} is a lower triangular matrix. In fact, it is straightforward to see that

[a_{lj}]_{l,j≥0} = (\frac{1 + z}{(1 − z)^{2}} , \frac{z}{(1 − z)^{2}} )

is the array \underline{A111125} that starts with

[\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 \\ 5 & 5 & 1 & 0 & 0 \\ 7 & 14 & 7 & 1 & 0 \\ 9 & 30 & 27 & 9 & 1 \end{matrix}] .

Then P_{l} is the polynomial whose coefficient sequence forms the l-th row of [a_{lj}]_{l,j≥0}. For our proof, we will need a generalized version of this array, [a_{ij}(uv)^{i−j}]_{i,j≥0}.

Lemma 34. The array [a_{ij}(uv)^{i−j}]_{i,j≥0} satisfies the identity

[a_{lj}(uv)^{l−j}]_{l,j≥0} [(u − v)^{2j+1}]_{j≥0}^{T} = [u^{2l+1} − v^{2l+1}]_{l≥0}^{T}  (48)

(where the superscript ^{T} denotes the transpose).

This identity has a long history going back to Albert Girard (1629) and Edward Waring (1762). The article of Gould [18], where it appears as [18, Equation (1)] (up to a simple change of variables), discusses this history and generalizations to more variables.

The first few rows of (48) are

[\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 3uv & 1 & 0 & 0 & 0 \\ 5u^{2}v^{2} & 5uv & 1 & 0 & 0 \\ 7u^{3}v^{3} & 14u^{2}v^{2} & 7uv & 1 & 0 \\ 9u^{4}v^{4} & 30u^{3}v^{3} & 27u^{2}v^{2} & 9uv & 1 \end{matrix}] [\begin{matrix}u − v \\ (u − v) & 3 \\ (u − v) & 5 \\ (u − v) & 7 \\ (u − v) & 9 \end{matrix}] = [\begin{matrix}u − v \\ u^{3} − v^{3} \\ u^{5} − v^{5} \\ u^{7} − v^{7} \\ u^{9} − v^{9} \end{matrix}] .

Proof. The proof of this matrix identity follows from the fundamental theorem of Riordan arrays (1), since

(\frac{1 + uvy}{(1 − uvy)^{2}} , \frac{y}{(1 − uvy)^{2}} ) ∗ \frac{u − v}{1 − (u − v)^{2}y} = \frac{u}{1 − u^{2}y} − \frac{v}{1 − v^{2}y}

(we use y instead of z as the main variable here due to substitutions that we will make later).

Proof of Theorem 33. Note that

z^{2l+1} ∘ f = f^{2l+1} = z^{2l+1}g^{2l+1}(z^{2l+1}) = h(z^{2l+1}) = h ∘ z^{2l+1},

and therefore h − z = zhB_{h}(zh) = (zB_{h}) ∘ (zh) implies that

\begin{aligned}f^{2l+1} − z^{2l+1} & = h(z^{2l+1}) − z^{2l+1} \\ & = (zB_{h}) ∘ (z^{2l+1}h(z^{2l+1})) = (zB_{h}) ∘ (z^{2l+1}f^{2l+1}) = (zB_{h}) ∘ ((zf)^{2l+1}) . \end{aligned}

Note also that f − z = (zB_{f}) ∘ (zf) = zfB_{f}(zf). Then, from equation (48) with u = f and v = z, we have

(zf)^{2l+1}B_{h} ((zf)^{2l+1})) = f^{2l+1} − z^{2l+1}

= ∑_{j=0}^{l} a_{lj}(zf)^{l−j}(f − z)^{2j+1}

= ∑_{j=0}^{l} a_{lj}(zf)^{l−j}(zf)^{2j+1}(B_{f}(zf))^{2j+1}

= (zf)^{l+1} ∑_{j=0}^{l} a_{lj}(zf)^{j}(B_{f}(zf))^{2j+1}.

Cancelling (zf)^{l+1} on both sides and replacing zf with z, we obtain

z^{l}B_{h}(z^{2l+1}) = ∑_{j=0}^{l} a_{lj}z^{j}B_{f}(z)^{2j+1}.

Now, multiplying both sides by \sqrt{z}, we obtain the following compositions of functions on the respective sides of the equation:

(\sqrt{z}B_{h}) ∘ (z^{2l+1}) = (\sqrt{z} ∑_{j=0}^{l} a_{lj}z^{j}) ∘ (zB_{f}^{2}) = (\sqrt{z}P_{l}) ∘ (zB_{f}^{2}).  (49)

Finally, squaring both sides of (49), we obtain

(zB_{h}^{2}) ∘ (z^{2l+1}) = (zP_{l}^{2}) ∘ (zB_{f}^{2}).

Example 35. (k-ary trees) Let g = T_{k} from Example 6, then d = 2k, so 2l + 1 = d − 1 = 2k − 1, i.e., l = k − 1. Then f = zT_{k}(z^{2k−1}), h = zT_{k}^{2k−1}, and

f − z = zT_{k}(z^{2k−1}) − z = z(T_{k}(z^{2k−1}) − 1) =

= z · z^{2k−1}T_{k}^{k}(z^{2k−1}) = (z^{2}T_{k}(z^{2k−1}))^{k} = (zf)^{k} = (zB_{f}) ∘ (zf),

so zB_{f} = z^{k}, and thus, B_{f} = z^{k−1} and zB_{f}^{2} = z^{2k−1}. Therefore, from Theorem 33,

(zB_{h}^{2}) ∘ (z^{2k−1}) = (zP_{k−1}^{2}) ∘ (z^{2k−1}),

and thus, B_{h} = P_{k−1}. For example, k = 2 yields d = 4, l = 1, g = C, f = zC(z^{3}), h = zC^{3}, B_{f} = z, and B_{h} = 3 + z. Likewise, for k = 3, we have B_{zT_{3}(z^{5})} = z^{2} and B_{zT_{3}^{5}} = 5 + 5z + z^{2}.

We conclude this section with a few remarks relating the results of Theorems 26 and 33. Remark 36. Notice that the Riordan arrays [α_{nk}]_{n,k≥0} and [a_{nk}]_{n,k≥0} only differ by a factor of \frac{1}{1−z} in the first component. This implies that

p_{k}(z) = ∑_{l=0}^{k} P_{l}(z), i.e. P_{k}(z) = p_{k}(z) − p_{k−1}(z).  (50)

Moreover, it is easy to verify, using the fact that T_{k}(cos θ) = cos(kθ) and Equation (33), that

P_{l}(z) = U_{l} (\frac{z + 2}{2}) + U_{l−1} (\frac{z + 2}{2}) = \sqrt{p_{2l}(z)}, l ≥ 0.  (51)

Corollary 37. Let g, f, h, l be as in Theorem 33, and let δ and D be as in (28) and (29). Then

B_{h} = DP_{l}(zD^{2}) and B_{f} = z^{l}D(z^{2l+1}).

Proof. Equation (51) implies that for even darga d = 2l + 2, l ≥ 0, in Theorem 26, we have

B_{h} = D\sqrt{p_{2l}(zD^{2})} = DP_{l}(zD^{2}),

or, equivalently,

zB_{h}^{2} = (zP_{l}^{2}) ∘ (zD^{2}).

Therefore, from Equation (45) we obtain

zB_{f}^{2} = (zD^{2}) ∘ (z^{2l+1}),

and thus,

B_{f} = z^{l}D(z^{2l+1}).

4.4 B-functions for doubled k-ary trees

Consider the family t_{k} = t_{k}(z), k ≥ 1, from Example 9. Recall that t_{k} = 2T_{k} − 1, where T_{k} = 1 + zT_{k}^{k} is the generating function for k-ary trees, and

t_{k} = 1 + 2z (\frac{1 + t_{k}}{2} )^{k} .

In this case, γ = 2 (\frac{1+z}{2})^{k} from Equation (15) has darga d = k, so (t_{k}, zt_{k}^{k−1}) is a pseudoinvolution in the (k − 1)-Bell subgroup. Moreover, if k is even (i.e., k − 1 is odd), then by Corollary 4, (t_{k}(z^{k−1}), zt_{k}(z^{k−1})) is a pseudo-involution in the Bell subgroup.

Consider the δ and D functions for t_{k}. From Equations (28) and (29), we have

δ^{2} (\frac{(z − 1)^{2}}{z} ) = \frac{γ^{2}(z)}{z^{d}} = \frac{4(1 + z)^{2k}}{2^{2k}z^{k}} = 4 (\frac{(1 + z)^{2}}{4z} )^{k} = 4 (1 + \frac{(z − 1)^{2}}{4z} )^{k} ,

so

δ^{2}(z) = 4 (1 + \frac{z}{4})^{k} ,

and hence,

\frac{z}{δ^{2}(z)} = \frac{z}{4 (1 + \frac{z}{4})^{k}} = \frac{z}{(1 + z)^{k}} ∘ \frac{z}{4}.

Therefore,

zD^{2} = \overline{(\frac{z}{δ^{2}} )} = (4z) ∘ \overline{(\frac{z}{(1 + z)^{k}} )} = (4z) ∘ (zT_{k}^{k}) = 4zT_{k}^{k},

and thus

D = 2T_{k}^{k/2}.  (52)

From the discussion above, we see that for even k = 2l, the B-function for f = zt_{2l}(z^{2l−1}) is quite simple.

Theorem 38. For f = zt_{2l}(z^{2l−1}), we have B_{f} = 2z^{l−1}T_{2l}^{l}(z^{2l−1}).

Proof. We have B_{f} = z^{l−1}D(z^{2l−1}) from Corollary 37, and D = 2T_{2l}^{2l/2} = 2T_{2l}^{l} from (52).

For example, when k = 2, i.e., l = 1, we get 2l−1 = 1, f = zt_{2}, and B_{f} = 2T_{2} = 2C, as in Example 15. Similarly, for k = 4, we have l = 2, 2l − 1 = 3, f = zt_{4}(z^{3}), and B_{f} = 2zT_{4}^{2}(z^{3}).

Note that it is possible to use Corollary 37 to find B_{h} for h = zt_{2l}^{2l−1}. For the remaining half of the family, where h = zt_{2l+1}^{2l}, l ≥ 0, we find the B-functions directly from Theorem 26.

Lemma 39. For h = zt_{2l}^{2l−1}, we have

B_{h} = 2T_{2l}^{l}P_{l−1} (4zT_{2l}^{2l}) = 2T_{2l}^{l} · (U_{l−1} + U_{l−2}) ∘ (t_{2l}).

For h = zt_{2l+1}^{2l}, we have

B_{h} = 2T_{2l+1}^{l+1} U_{l−1}(t_{2l+1}).

Proof. Note that zD^{2} = 4zT_{k}^{k} for D = T_{k}^{k/2}. We will make use of the following facts:

\begin{aligned}\frac{z + 2}{2} ∘ (4zT_{k}^{k}) & = \frac{4zT_{k}^{k} + 2}{2} = 1 + 2zT_{k}^{k} = 2T_{k} − 1 = t_{k} , \\ (z + 4) ∘ (4zT_{k}^{k}) & = 4 + 4zT_{k}^{k} = 4T_{k} . \end{aligned}

For k = 2l and h = zt_{2l}^{2l−1}, Corollary 37 implies that

B_{h} = DP_{l−1}(zD^{2}) = 2T_{2l}^{l}P_{l−1}(4zT_{2l}^{2l}) = 2T_{2l}^{l} · (U_{l−1} + U_{l−2}) ∘ (t_{2l}).

For k = 2l + 1 and h = zt_{2l+1}^{2l}, Theorem 26 implies that

\begin{aligned}B_{h} & = D\sqrt{p_{d−2}(zD^{2})} = 2T_{2l+1}^{l+ \frac{1}{2}}\sqrt{p_{2l−1}(4zT_{2l+1}^{2l+1})} = 2T_{2l+1}^{l+ \frac{1}{2}}\sqrt{4 + 4zT_{2l+1}^{2l+1}} U_{l−1}(t_{2l+1}) \\ & = 2T_{2l+1}^{l+ \frac{1}{2}} · 2T2l+1^{\frac{1}{2}}U_{l−1}(t_{2l+1}) = 4T_{2l+1}^{l+1}U_{l−1}(t_{2l+1}). \end{aligned}

We can express B_{h} for h = zt_{k}^{k−1} as a polynomial in T_{k} even more simply.

Theorem 40. For h = zt_{k}^{k−1}, k ≥ 1, and [c_{k,n}]_{k,n≥0} as in (37), we have

B_{h} = 2T_{k}^{k/2} U_{k−2}(\sqrt{T_{k}}) = ∑_{n=0}^{k−2} 2^{n+1}c_{k−2,n}Tk^{\frac{k+n}{2}} .  (53)

Proof. We have B_{h} = ϕ_{k}(T_{k}), where

ϕ_{k}(z) = \begin{cases}2z^{l} · ((U_{l−1} + U_{l−2}) ∘ (2z − 1)) = 2z^{l}(U_{l−1}^{∗} + U_{l−2}^{∗}) , & if k = 2l; \\ 4z^{l+1}U_{l−1}(2z − 1) = 4z^{l+1}U_{l−1}^{∗} , & if k = 2l + 1. \end{cases}

The polynomial U_{l}^{∗}(z) = U_{l}(2z − 1) is called the shifted Chebyshev polynomial of the second kind and has the following properties (derivable from the definition of U_{k} by replacing θ with 2θ and using applicable trigonometric identities):

\begin{aligned}U_{l}^{∗}(z^{2}) & = \frac{U_{2l+1}(z)}{2z} , \\ U_{l}^{∗}(z^{2}) + U_{l−1}^{∗}(z^{2}) & = \frac{U_{2l+1}(z) + U_{2l−1}(z)}{2z} = U_{2l}(z). \end{aligned}

This implies that, for both k = 2l and k = 2l + 1, we have

ϕ_{k}(z^{2}) = 2z^{k}U_{k−2}(z),

or, equivalently, ϕ_{k}(z) = 2z^{k/2}U_{k−2}(\sqrt{z}). Applying Lemma 39 now yields the theorem.

Note that \frac{k+n}{2} = \frac{(k−2)+n}{2} + 1 in Equation (53), so all nonzero summands in the above sum contain only integer powers of T_{k}. Note also that for k = 1, we have t_{1} = \frac{1+z}{1−z}, whose Riordan companion is zt_{1}^{0} = z with B_{z} = 0, which agrees with Theorem 40, since the sum in the theorem statement is empty for k = 1.

Example 41. The matrix [c_{k,n}]_{k,n≥0} begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ −1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & −2 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & −3 & 0 & 1 & 0 & 0 \\ 0 & 3 & 0 & −4 & 0 & 1 & 0 \\ −1 & 0 & 6 & 0 & −5 & 0 & 1 \end{matrix}] ,

so the matrix [2^{n+1}c_{k,n}]_{k,n≥0} begins

[\begin{matrix}2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 & 0 & 0 \\ −2 & 0 & 8 & 0 & 0 & 0 & 0 \\ 0 & −8 & 0 & 16 & 0 & 0 & 0 \\ 2 & 0 & −24 & 0 & 32 & 0 & 0 \\ 0 & 12 & 0 & −64 & 0 & 64 & 0 \\ −2 & 0 & 48 & 0 & −160 & 0 & 128 \end{matrix}] .

Hence, for the first few values of k, we have

\begin{aligned}B_{zt_{2}} & = 2T_{2} = 2C, \\ B_{zt_{3}^{2}} & = 4T_{3}^{2}, \\ B_{zt_{4}^{3}} & = −2T_{4}^{2} + 8T_{4}^{3} = 2T_{4}^{2} · (2t_{4} + 1), \\ B_{zt_{5}^{4}} & = −8T_{5}^{3} + 16T_{5}^{4} = 4T_{5}^{3} · 2t_{5}, \\ B_{zt_{6}^{5}} & = 2T_{6}^{3} − 24T_{6}^{4} + 32T_{6}^{5} = 2T_{6}^{3} · (4t_{6}^{2} + 2t_{6} − 1). \end{aligned}

4.5 Generalized Schröder trees

Another family we can analyze similarly to the k-ary trees and double k-ary trees is a special case of Example 7: a family r_{k} = r_{k}(z), k ≥ 1, that satisfies the equation

r_{k} = 1 + z(r_{k}^{k−1} + r_{k}^{k}).

Then r_{1} = \frac{1+z}{1−z} = t_{1} and r_{2} = r, the generating function for the large Schröder numbers. Note that in this case, γ = z^{k−1} + z^{k} in Equation (15), so d = dar(γ) = (k − 1) + k = 2k − 1, and thus the companion of r_{k} is zr_{k}^{2k−2}, i.e., (r_{k}, zr_{k}^{2k−2}) is a pseudo-involution in the (2k−2)-Bell subgroup.

Consider the δ and D functions for r_{k}. From Equations (28) and (29), we have

δ^{2} (\frac{(z − 1)^{2}}{z} ) = \frac{γ^{2}(z)}{z^{d}} = \frac{(1 + z)^{2}z^{2k−2}}{z^{2k−1}} = \frac{(1 + z)^{2}}{z} = 4 + \frac{(z − 1)^{2}}{z} ,

so δ^{2}(z) = z + 4, and thus

zD^{2} = \overline{(\frac{z}{z + 4})} = \frac{4z}{1 − z} and D = \frac{2}{\sqrt{1 − z}} .

Therefore, applying Corollary 37 to h = zr_{k}^{2k−2} and d = 2k − 1, we get

\begin{aligned}B_{h} & = D\sqrt{p_{2k−3}(zD^{2})} = D\sqrt{zD^{2} + 4} U_{k−2}(\frac{zD^{2} + 2}{2}) \\ & = \frac{2}{\sqrt{1 − z}} · \frac{2}{\sqrt{1 − z}} · U_{k−2}(\frac{1 + z}{1 − z} ) = \frac{4}{1 − z} U_{k−2}(\frac{1 + z}{1 − z} ) \end{aligned}

For example, since U_{0}(z) = 1, U_{1}(z) = 2z, and U_{2}(z) = 4z^{2} − 1, it follows that

\begin{aligned}B_{zr^{2}} = B_{zr_{2}^{2}} & = \frac{4}{1 − z} , \\ B_{zr_{3}^{4}} & = \frac{4}{1 − z} U_{1} (\frac{1 + z}{1 − z} ) = \frac{8(1 + z)}{(1 − z)^{2}} , \\ B_{zr_{4}^{6}} & = \frac{4}{1 − z} U_{2} (\frac{1 + z}{1 − z} ) = \frac{4(3 + z)(1 + 3z)}{(1 − z)^{3}} , \end{aligned}

and so on. Note that, just like for the previous family, we have r_{1} = \frac{1+z}{1−z} for k = 1, with the Riordan companion of h = zr_{1}^{0} = z and B_{h} = B_{z} = 0.

4.6 Increasing trees of even arity

To conclude this section, we want to give an example of functions f(z) and h(z) as in (44), where B_{h} is easier to find, which in turn allows us to find B_{f} using Equation (45) of Theorem 33.

A (d + 1)-ary increasing tree is a rooted, partially labeled tree in which each internal vertex has outdegree (arity) d + 1, leaves are unlabeled, internal vertices are labeled with consecutive integers starting with 1, and labels increase along any path away from the root. A (d + 1)-ary tree with n internal vertices has dn + 1 leaves and (d + 1)n + 1 vertices in total. For an extensive treatment of various types of increasing trees, see, e.g., Bergeron et al. [8]. We also mention that (d + 1)-ary increasing trees are in bijection with d-Stirling permutations [22], i.e., permutations of {1^{d}, 2^{d}, …, n^{d}} where any subsequence a ⋯ b ⋯ a satisfies b ≥ a. From [8, Table 1], we see that the exponential generating function for the number of such trees with n internal vertices (including the singleton tree when n = 0) is given by

\frac{1}{(1 − dz)^{\frac{1}{d}}} .

We will instead consider these trees according to the number of leaves, i.e., the weight of a tree with n internal vertices will be z^{dn+1}. This yields the exponential generating function

\frac{z}{(1 − dz^{d})^{\frac{1}{d}}} .

To generalize the class of functions under consideration slightly, we let

f = f(z) = \frac{z}{(1 − cz^{d})^{\frac{1}{d}}} ,

where c is an arbitrary constant. For a nonnegative integer c, this corresponds to allowing c possible colors for each internal vertex, while leaves remain uncolored. Note that this implies that

z^{d} ∘ f = f^{d} = \frac{z^{d}}{1 − cz^{d}} = \frac{z}{1 − cz} ∘ z^{d},

and since z/(1 − cz) is pseudo-involutory, it follows that so is f when d is odd (i.e., when the outdegree d + 1 is even). In that case, let l = (d − 1)/2, so that d = 2l + 1.

Note that

f(z) = \frac{z}{(1 − cz^{d})^{\frac{1}{d}}} = ∑_{n=0}^{∞} ((\frac{c}{d})^{n} ∏_{j=0}^{n}(jd + 1)) \frac{x^{n}}{n!} ,

so the coefficient at x^{n}/n! is an integer if d | c, and the coefficient at x^{n} is an integer if d^{2} | c. When d = 1, this yields the coefficient n! at x^{n}/n!, corresponding to the well-known fact that binary increasing trees are in bijection with permutations. The expression ∏_{j=0}^{n}(jd+1) is sometimes denoted (dn + 1)(!^{d}), i.e., n!, (2n + 1)!!, (3n + 1)!!!, etc.

Let g = g(z) = 1/(1 − cz)^{1/d}, then f(z) = zg(z^{d}) as in (45), while the corresponding function h from (45) is h = zg^{d} = z/(1−cz). Therefore, B_{h}(z) = c is constant, so zB_{h}^{2} = c^{2}z, and thus (45) implies that

(zP_{l}^{2}) ∘ (zB_{f}^{2}) = (zB_{h}^{2}) ∘ (z^{2l+1}) = (c^{2}z) ∘ (z^{2l+1}) = c^{2}z^{2l+1},

or, equivalently,

zB_{f}^{2} = \overline{(zP_{l}^{2})} ∘ (c^{2}z^{2l+1}),

where P_{l} = P_{l}(z) is as in (46).

Example 42. Letting d = 1 (i.e., considering binary increasing trees) yields l = 0 and P_{l} = 1, so that B_{f} = cz^{l} = c. Letting d = 3 (i.e., considering quaternary increasing trees) yields l = 1 and P_{l} = 3 + z, so for the corresponding function f = f(z) = z/(1 − cz^{3})^{1/3} (see \underline{A007559} for c = 3), we have

zB_{f}^{2} = \overline{(z(3 + z)^{2})} ∘ (c^{2}z^{3}).

Note that

\overline{z(3 + z)^{2}} = \overline{(27z) ∘ (z(1 + z)^{2}) ∘ (\frac{z}{3})} = (3z) ∘ (zT_{3}^{2}(−z)) ∘ (\frac{z}{27}) = \frac{z}{9} T_{3}^{2} (−\frac{z}{27}) ,

and therefore

zB_{f}^{2} = \frac{c^{2}z^{3}}{9} T_{3}^{2} (−\frac{c^{2}z^{3}}{27} ) ,

or, equivalently,

B_{f} = \frac{cz}{3} T_{3} (−\frac{c^{2}z^{3}}{27} ) .

In particular, this yields B_{f} = zT_{3}(−z^{3}/3) for c = 3 and B_{f} = 3zT_{3}(−3z^{3}) for c = 9.

5 Pseudo-conjugation of pseudo-involutions

In this section, we will give a simple general result useful in obtaining new pseudo-involutions from the existing ones by compositions with invertible functions. This will be followed by several applications of that general result. Furthermore, we will find the B-functions for some of the families of pseudo-involutions in our examples.

Definition 43. Let h be an invertible formal power series, and define the pseudo-inverse ĥ of h to be ĥ = (−z) ∘ \overline{h} ∘ (−z).

Note that ĥ = h if and only if \overline{h} = (−z)∘h∘(−z), i.e., if and only if h is pseudo-involutory. Note also that, for an arbitrary invertible h, we have \overline{ĥ} = ˆ \overline{h} = (−z) ∘ h ∘ (−z).

Theorem 44. Let h be an invertible formal power series. Then (g, f) is a pseudo-involution if and only if (g ∘ h, ĥ ∘ f ∘ h) is a pseudo-involution.

Note that (g ∘ h, ĥ ∘ f ∘ h) = (1, h)(g, f)(1, ĥ), with the order of h and ĥ reversed. We call ĥ ∘ f ∘ h the pseudo-conjugate of f by h. Likewise, (g ∘ h, ĥ ∘ f ∘ h) is the pseudo-conjugate of (g, f) by (1, h). In each case, we call the corresponding operation pseudo-conjugation.

Corollary 45. Let h be pseudo-involutory. Then (g, f) is a pseudo-involution if and only if (g ∘ h, h ∘ f ∘ h) is a pseudo-involution.

The same statements also hold for the exponential pseudo-involutions [g, f] and [g ∘h, ĥ∘ f ∘ h].

We note that Theorem 44 and Corollary 45 have already appeared in He and Shapiro [20] as Theorem 5.1 and Corollary 5.2, as part of the “very helpful comments” by the first author of this paper, referred to in [20, Acknowledgments].

Proof of Theorem 44. (g, f) is a pseudo-involution if and only if g(−f) = 1/g, i.e.

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

But then

\begin{aligned}(g ∘ h) ∘ (−z) ∘ (ĥ ∘ f ∘ h) & = g ∘ h ∘ (−z) ∘ (−z) ∘ \overline{h} ∘ (−z) ∘ f ∘ h \\ & = g ∘ (−z) ∘ f ∘ h = \frac{1}{g} ∘ h = \frac{1}{g ∘ h}, \end{aligned}

i.e., (g ∘ h, ĥ ∘ f ∘ h) is a pseudo-involution.

The converse follows easily from the above and the facts that g = (g∘h)∘\overline{h} and \overline{ĥ} = ˆ \overline{h}.

We note, following He and Shapiro [20], that when h is pseudo-involutory, the Riordan array

(g ∘ h, h ∘ f ∘ h) = (1, h)(g, f)(1, h)

is a pseudo-involution as a palindromic product of pseudo-involutions.

We will first give a few examples of Corollary 45, where h is pseudo-involutory.

Example 46. Let h = \frac{z}{1 − z} and g = m̃ of Example 8. Then f = zm̃, so g ∘ h = C, and

h ∘ f ∘ h = \frac{z}{1 − z} ∘ (zm̃) ∘ \frac{z}{1 − z} = \frac{z}{1 − z} ∘ \frac{zC}{1 − z} = \frac{zC}{1 − z − zC} = zC^{3}.

This uses the identity m̃ (\frac{z}{1−z}) = C, or equivalently, m̃ = C (\frac{z}{1+z}). The last of the chain of equalities is obtained by multiplying through by C and using the identity C − zC^{2} = 1 twice. Thus, we (re-)obtain pseudo-involution (C, zC^{3}) from (m̃, zm̃).

Example 47. Let h = zm̃ and g = \frac{1}{1 − z}. Then f = \frac{z}{1 − z}, so g ∘ h = \frac{1}{1 − zm̃} = m, and

\begin{aligned}h ∘ f ∘ h & = (zm̃) ∘ \frac{z}{1 − z} ∘ (zm̃) = \frac{zC}{1 − z} ∘ (zm̃) \\ & = \frac{zm̃}{1 − zm̃}C(zm̃) = zm̃mC(zm̃) = (m − 1)C(zm̃). \end{aligned}

Thus, we (re-)obtain the pseudo-involution (m, (m − 1)C(zm̃)) and see that the pseudoinvolutory companion to the Motzkin generating function m is

(m − 1)C(zm̃) = m · ((zC) ∘ (zm̃)).

Example 48. Let h = zm̃ and g = \frac{1+z}{1−z}. Then f = z, so g ∘ h = \frac{1+zm̃}{1−zm̃} = m(1 + zm̃) = m + (m − 1) = 2m − 1, and h ∘ f ∘ h = (zm̃) ∘ (zm̃). This yields the pseudo-involution

(2m − 1, (zm̃) ∘ (zm̃)) .

Similarly, we can see that (\frac{1+h}{1−h} , ĥ ∘ h) is a pseudo-involution for any invertible function h.

Note that the coefficient sequence \underline{A348197} of (zm̃) ∘ (zm̃) begins

0, 1, 2, 4, 10, 28, 84, 264, 860, 2880, 9862, 34392, …,

and, curiously, its first 8 terms coincide with those of z(2C − 1). From the 9th term on, it appears that ((zm̃) ∘ (zm̃))−z(2C −1) = 2z^{8} +20z^{9} +138z^{10} +800z^{11} +⋯ has only positive coefficients. It would be interesting to see a combinatorial interpretation of that fact.

Example 49. Let h = \frac{z}{1 + z} and g = 2C−1. Then f = z(2C−1), so g∘h = (2C−1)∘\frac{z}{1 + z} = 2m̃ − 1, and

\begin{aligned}h ∘ f ∘ h & = \frac{z}{1 + z} ∘ (z(2C − 1)) ∘ \frac{z}{1 + z} \\ & = \frac{z}{1 + z} ∘ \frac{z(2m̃ − 1)}{1 + z} = \frac{z(2m̃ − 1)}{1 + z + z(2m̃ − 1)} = \frac{z(2m̃ − 1)}{1 + 2zm̃}. \end{aligned}

Thus,

(2m̃ − 1, \frac{z(2m̃ − 1)}{1 + 2zm̃})

is a pseudo-involution. The pseudo-involutory companion

\frac{z(2m̃ − 1)}{1 + 2zm̃} = \frac{1 − \sqrt{1 − 2z − 3z^{2}}}{2 + z − \sqrt{1 − 2z − 3z^{2}}}

of 2m̃ − 1 corresponds to the coefficient sequence \underline{A348189} that begins

0, 1, 0, 0, 2, 0, 6, 8, 24, 60, 148, 396, 1026, 2744, 7350, 19872, 54102, 148104, 407682, ….

It would be interesting to see a natural combinatorial interpretation of this sequence.

Now we give some examples of the application of Theorem 44, where h is not necessarily pseudo-involutory. An easy example involves the Fibonacci generating function.

Example 50. Let g = \frac{1}{1−z} and h = z + z^{2}, then f = \frac{z}{1−z} , ĥ = \overline{(z − z^{2})} = zC, F = g ∘ h = \frac{1}{1−z−z^{2}} is the generating function for the Fibonacci numbers, and

ĥ ∘ f ∘ h = (zC) ∘ \frac{z}{1 − z} ∘ (z + z^{2}) = (zC) ∘ (F − 1) = (F − 1) · C(F − 1).

Thus, (F, (zC) ∘ (F − 1)) is a pseudo-involution. It begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 7 & 1 & 0 & 0 \\ 5 & 50 & 35 & 10 & 1 & 0 \\ 8 & 190 & 160 & 65 & 13 & 1 \end{matrix}] .

We note that the pseudo-involutory companion

(zC) ∘ (F − 1) = \frac{1}{2} (1 − \sqrt{\frac{1 − 5z − 5z^{2}}{1 − z − z^{2}}} )

is the generating function for the sequence \underline{A344623}. The methods for finding B-functions discussed in this paper do not appear to apply in this case, but comparing a few initial terms of this pseudo-involution’s B-sequence with existing OEIS sequences allows us to conjecture and verify the entire B-sequence: it is, in fact, \underline{A200031} with the initial 1 replaced by 3. Thus, y = B_{(zC)∘(F −1)} satisfies the functional equation

y = 3 − z − zy + zy^{2}

and is given explicitly by

B_{(zC)∘(F −1)} = \frac{1 + z − \sqrt{1 − 10z + 5z^{2}}}{2z} .

The next pair of examples involves two related families of functions (so related that we will see that it is, in fact, a single family of functions), with both aerated and non-aerated versions of those families. These examples rely on the following identity satisfied by the Catalan generating function C = 1 + zC^{2}:

1 + zC^{3} = 1 + (C − 1)C = 1 − C + C^{2} = C^{2} − zC^{2} = (1 − z)C^{2},  (54)

or, equivalently,

1 − z = \frac{1 − C + C^{2}}{C^{2}} = \frac{1 − z + z^{2}}{z^{2}} ∘ C = \frac{1 + z + z^{2}}{(1 + z)^{2}} ∘ (zC^{2}).  (55)

Example 51. Let T_{n} = T_{n}(z) be the generating function for the n-ary trees from Example 6, i.e., T_{n} = 1 + zT_{n}^{n}. Let g = C and h = zT_{n}^{n−1}, then f = zC^{3} and \overline{h} = z(1 − z)^{n−1}, so ĥ = z(1 + z)^{n−1}, and hence

ĥ ∘ f ∘ h = (z(1 + z)^{n−1}) ∘ (zC^{3}) ∘ (zT_{n}^{n−1}).

However, from Equation (54),

(z(1 + z)^{n−1}) ∘ (zC^{3}) = zC^{3}(1 + zC^{3})^{n−1} = zC^{3} ((1 − z)C^{2})^{n−1} = z(1 − z)^{n−1}C^{2n+1},

so, recalling that z(1 − z)^{n−1} = \overline{zT_{n}^{n−1}}, we have

ĥ ∘ f ∘ h = (z(1 − z)^{n−1}C^{2n+1}) ∘ (zT_{n}^{n−1}) = zC^{2n+1}(zT_{n}^{n−1}).

Thus, (C(zT_{n}^{n−1}), zC^{2n+1}(zT_{n}^{n−1})) is a pseudo-involution in the (2n + 1)-Bell subgroup. Note also that T_{n} = 1/(1 − zT_{n}^{n−1}), and C = m̃ (\frac{z}{1−z}), so

C(zT_{n}^{n−1}) = m̃ (\frac{zT_{n}^{n−1}}{1 − zT_{n}^{n−1}} ) = m̃(zT_{n}^{n}),

and thus

(C(zT_{n}^{n−1}), zC^{2n+1}(zT_{n}^{n−1})) = (m̃(zT_{n}^{n}), zm̃^{2n+1}(zT_{n}^{n})).

Thus, letting n = 0, we recover the pseudo-involution (m̃, zm̃); letting n = 1, we recover the pseudo-involution (C, zC^{3}).

Letting n = 2 in this example yields the pseudo-involution (C(zC), zC^{5}(zC)). The function C(zC) is the generating function for the sequence \underline{A127632}, which is the counting sequence e.g., for permutations that avoid the set of patterns (1342, 3142, 45132) and do not start with a descent. Alternatively, as shown by Archer and Graves [1], C(zC) is the generating function for the number of 132-avoiding permutations of length 3n, n ≥ 0, whose disjoint cycle decomposition contains only 3-cycles (a, b, c) with a > b > c.

Likewise, letting n = 3 and n = 4, we obtain pseudo-involutions (C(zT_{3}^{2}), zC^{7}(zT_{3}^{2})) and (C(zT_{4}^{3}), zC^{9}(zT_{4}^{3})), where the first components are the generating functions for sequences \underline{A153295} and \underline{A153396}, respectively.

Finally, for comparison, note that, for n ≥ 2, we have T_{n} = 1 + (zT_{n}^{n−2})T_{n}^{2}, so T_{n} = C(zT_{n}^{n−2}), and thus (C(zT_{n}^{n−2}), zC^{2n−1}(zT_{n}^{n−2})) = (T_{n}, zT_{n}^{2n−1}) is also a pseudo-involution (see Example 6).

Example 52. The following family is complementary to the one in Example 51. With T_{n} as before, let g = 1/C = 1 − zC and h = −zT_{n}^{n}, then f = zC^{3} and \overline{h} = −z/(1 − z)^{n}, so ĥ = −z/(1 + z)^{n}, and hence

ĥ ∘ f ∘ h = (−z/(1 + z)^{n}) ∘ (zC^{3}) ∘ (−zT_{n}^{n}).

However,

(−\frac{z}{(1 + z)^{n}} ) ∘ (zC^{3}) = −\frac{zC^{3}}{(1 + zC^{3})^{n}} = −\frac{zC^{3}}{((1 − z)C^{2})^{n}} = −\frac{z}{(1 − z)^{n}C^{2n−3}} ,

so, recalling that −z/(1 − z)^{n} = \overline{(−zT_{n}^{n})}, we have

ĥ ∘ f ∘ h = (−\frac{z}{(1 − z)^{n}C^{2n−3}} ) ∘ (−zT_{n}^{n}) = \frac{z}{C^{2n−3}(−zT_{n}^{n})}.

Thus,

(\frac{1}{C(−zT_{n}^{n})}, \frac{z}{C^{2n−3}(−zT_{n}^{n})})

is a pseudo-involution in the (2n − 3)-Bell subgroup. In particular, for n = 2, the pseudoinvolution

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

is in the Bell subgroup.

Note that, despite the negative signs and division in the generating function 1/C(−zT_{n}^{n}), its sequence of coefficients consists of positive integers only. For example, for n = 2, the coefficient sequence \underline{A166135} of 1/C(−zC^{2}) begins

1, 1, 1, 3, 7, 22, 65, 213, 693, 2352, 8034, …,

and for n = 3, the coefficient sequence \underline{A347953} of 1/C(−zT_{3}^{3}) begins

1, 1, 2, 8, 35, 171, 882, 4744, 26286, 149045, 860596, ….

The pseudo-involution (\frac{1}{C(−zC^{2})}, \frac{z}{C(−zC^{2})}) begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 7 & 8 & 6 & 4 & 1 & 0 & 0 & 0 & 0 \\ 22 & 21 & 16 & 10 & 5 & 1 & 0 & 0 & 0 \\ 65 & 64 & 45 & 28 & 15 & 6 & 1 & 0 & 0 \\ 213 & 197 & 138 & 83 & 45 & 21 & 7 & 1 & 0 \\ 693 & 642 & 436 & 260 & 140 & 68 & 28 & 8 & 1 \end{matrix}] .

The sequence 1/C(−zC^{2}) is the generating function for the basketball walks defined in Ayyer and Zeilberger [2] and considered using the kernel method in Banderier et al. [3] and bijectively in Bettinelli et al. [9], i.e., lattice paths starting at (0, 0) that either consist of a single point, or have only steps from among (1, 1), (1, −1), (1, 2), (1, −2), stay at positive height except at (0, 0), and end at height 1.

Unfortunately, we were unable to construct a lattice path generalization of basketball walks whose counting sequence would have 1/C(−zT_{n}^{n}) as its generating function. Such a generalization or another natural combinatorial interpretation of the coefficients of 1/C(−zT_{n}^{n}) would be interesting to see.

Finally, notice that T_{n} = 1 + zT_{n}^{n} and C = m̃ (\frac{z}{1−z}) imply that

C(−zT_{n}^{n}) = m̃ (\frac{−zT_{n}^{n}}{1 + zT_{n}^{n}} ) = m̃(−zT_{n}^{n−1}),

and thus

(\frac{1}{C(−zT_{n}^{n})}, \frac{z}{C^{2n−3}(−zT_{n}^{n})}) = (\frac{1}{m̃(−zT_{n}^{n−1})}, \frac{z}{m̃^{2n−3}(−zT_{n}^{n−1})}) .

The two families of functions in Examples 51 and 52 are complementary in the following way. We can extend the family of n-ary tree generating functions T_{n} from n ≥ 1 to all n ∈ ℤ using the functional equation T_{n} = 1 + zT_{n}^{n}. Then, for n ≥ 0, we have T_{−n} = 1 + zT_{−n}^{−n}. Dividing this through by T_{−n} and rearranging terms, we obtain

\frac{1}{T_{−n}} = 1 − z (\frac{1}{T_{−n}} )^{n+1} ,

i.e.

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

or, equivalently,

T_{−n} = \frac{1}{T_{n+1}(−z)}.  (56)

Now denote the pseudo-involutory companions in Examples 51 and 52 by

h_{1,n} = zC^{2n+1}(zT_{n}^{n−1}),  h_{2,n} = \frac{z}{C^{2n−3}(−zT_{n}^{n})} .  (57)

Then

\frac{z}{C^{2(−n)−3}(−zT_{−n}^{−n})} = \frac{z}{C^{−2n−3}(−zT_{n+1}^{n}(−z))} = (−z) ∘ (zC^{2n+3}(zT_{n+1}^{n})) ∘ (−z),

or, in other words,

h_{2,−n} = (−z) ∘ h_{1,n+1} ∘ (−z) = \overline{h_{1,n+1}},

and therefore, similarly,

h_{1,−n} = (−z) ∘ h_{2,n+1} ∘ (−z) = \overline{h_{2,n+1}}.

As an alternative way to show that functions h_{1,n} and h_{2,n} are pseudo-involutory and yield pseudo-involutions in the k-Bell subgroups for k = 2n + 1 and k = 2n − 3, respectively, we can produce the corresponding generalized palindromes γ satisfying (15) for g = C(zT_{n}^{n−1}) and g = 1/C(−zT_{n}^{n}), respectively.

For g = C(zT_{n}^{n−1}), we have

g − 1 = C(zT_{n}^{n−1}) − 1 = (zC^{2}) ∘ (zT_{n}^{n−1}),

which implies

\begin{aligned}z & = \overline{(zT_{n}^{n−1})} ∘ \overline{(zC^{2})} ∘ (g − 1) = (z(1 − z)^{n−1}) ∘ (\frac{z}{(1 + z)^{2}} ) ∘ (g − 1) \\ & = \frac{z(1 + z + z^{2})^{n−1}}{(1 + z)^{2n}} ∘ (g − 1) = \frac{(g − 1)(1 − g + g^{2})^{n−1}}{g^{2n}} , \end{aligned}

and therefore,

g = 1 + z \frac{g^{2n}}{(1 − g + g^{2})^{n−1}} ,

so

γ(z) = \frac{z^{2n}}{(1 − z + z^{2})^{n−1}} ,  (58)

which is palindromic with dar(γ) = (2n + 2n) − (0 + 2) · (n − 1) = 2n + 2, and thus, by Theorem 2, (g, zg^{2n+1}) is a pseudo-involution.

Similarly, for g = 1/C(−zT_{n}^{n}), we have

g − 1 = \frac{1}{C(−zT_{n}^{n})} − 1 = (−zC) ∘ (−zT_{n}^{n}) = (−z) ∘ (zC) ∘ (−z) ∘ (zT_{n}^{n}),

and therefore

\begin{aligned}z & = \overline{(zT_{n}^{n})} ∘ (−z) ∘ \overline{(zC)} ∘ (−z) ∘ (g − 1) = \frac{z}{(1 + z)^{n}} ∘ (−z) ∘ (z − z^{2}) ∘ (−z) ∘ (g − 1) \\ & = \frac{z}{(1 + z)^{n}} ∘ (z + z^{2}) ∘ (g − 1) = \frac{z(1 + z)}{(1 + z + z^{2})^{n}} ∘ (g − 1) = \frac{(g − 1)g}{(1 − g + g^{2})^{n}} , \end{aligned}

which implies

g = 1 + z \frac{(1 − g + g^{2})^{n}}{g} ,

so

γ(z) = \frac{(1 − z + z^{2})^{n}}{z} ,  (59)

which is palindromic with dar(γ) = (0 + 2) · n − (1 + 1) = 2n − 2, and thus, by Theorem 2, (g, zg^{2n−3}) is a pseudo-involution.

Since both powers 2n + 1 and 2n − 3 are odd, it follows that the aerations

(C(z^{2n+1}T_{n}^{n−1}(z^{2n+1}), zC(z^{2n+1}T_{n}^{n−1}(z^{2n+1}))

and

(\frac{1}{C(−z^{2n−3}T_{n}^{n}(−z^{2n−3}))}, \frac{z}{C(−z^{2n−3}T_{n}^{n}(−z^{2n−3}))})

are also pseudo-involutions in the Bell subgroup. We will denote the pseudo-involutory companions in those pseudo-involutions as

f_{1,n} = zC(z^{2n+1}T_{n}^{n−1}(z^{2n+1})),  f_{2,n} = \frac{z}{C(−z^{2n−3}T_{n}^{n}(−z^{2n−3}))} .  (60)

As we have seen in Example 35 and Theorem 38, it is often the case that the B-function for a k-Bell pseudo-involution (g, zg^{k}) is difficult to find directly, whereas the B-function for the associated aerated pseudo-involution (g(z^{k}), zg(z^{k})) in the Bell subgroup is somewhat easier to obtain. Such is the case with the families in Examples 51 and 52.

Theorem 53. The B-functions for the pseudo-involutory functions f_{1,n} and f_{2,n} defined in (60) and h_{1,n} and h_{2,n} defined in (57) are as follows:

• for f_{1,n} = zC(z^{2n+1}T_{n}^{n−1}(z^{2n+1})) and h_{1,n} = zC^{2n+1}(zT_{n}^{n−1}), we have

B_{f_{1,n}} = z^{n}T_{2n−1}^{n−1}(−z^{2n+1})  and  B_{h_{1,n}} = T_{2n−1}^{n−1}(−z) P_{n}(zT_{2n−1}^{2n−2}(−z)) ,

• for f_{2,n} = \frac{z}{C(−z^{2n−3}T_{n}^{n}(z^{2n−3}))} and h_{2,n} = \frac{z}{C^{2n−3}(−zT_{n}^{n})} , we have

B_{f_{2,n}} = z^{n−2}T_{2n}^{n}(z^{2n−3})  and  B_{h_{2,n}} = T_{2n}^{n} P_{n−2}(zT_{2n}^{2n}) .

Proof. Let functions δ and D be defined as in (28) and (29), respectively. From Corollary 37, it follows that we only need to find the function D in each case.

For the first family, with γ as in (58) and d = dar(γ) = 2n + 2, we have

δ^{2} (\frac{(z − 1)^{2}}{z} ) = \frac{γ(z)^{2}}{z^{d}} = \frac{1}{z^{2n+2}} · \frac{z^{4n}}{(1 − z + z^{2})^{2n−2}} = (\frac{z}{1 − z + z^{2}} )^{2n−2} = \frac{1}{(1 + \frac{(z−1)^{2}}{z} )^{2n−2}} ,

so δ^{2}(z) = 1/(1 + z)^{2n−2} and therefore z/δ^{2} = z(1 + z)^{2n−2}. This implies

zD^{2} = \overline{z(1 + z)^{2n−2}} = zT_{2n−1}^{2n−2}(−z),

and therefore,

D = T_{2n−1}^{n−1}(−z).

Likewise, for the second family, with γ as in (59) and d = dar(γ) = 2n − 2, we have

δ^{2} (\frac{(z − 1)^{2}}{z} ) = \frac{γ(z)^{2}}{z^{d}} = \frac{1}{z^{2n−2}} · \frac{(1 − z + z^{2})^{2n}}{z^{2}} = (\frac{1 − z + z^{2}}{z} )^{2n} = (1 + \frac{(z − 1)^{2}}{z} )^{2n} ,

so δ^{2}(z) = (1 + z)^{2n} and therefore z/δ^{2} = z/(1 + z)^{2n}. This implies

zD^{2} = \overline{(\frac{z}{(1 + z)^{2n}} )} = zT_{2n}^{2n},

and therefore,

D = T_{2n}^{n}.

Since in each case, the darga d is even, and hence d − 1 is odd, the theorem now follows from Theorem 2, Theorem 33, and Corollary 37.

Example 54. We will give a few initial examples of the results of Theorem 53.

In the first family, letting n = 0 yields T_{0} = 1 + z, f = zC (\frac{z}{1+z}) = zm̃, and B_{f} = T_{−1}^{−1}(−z) = T_{2} = C (see (56) for T_{n} with n < 0). Similarly, letting n = 1 yields f = zC(z^{3}) and B_{f} = z; and letting n = 2 yields f = zC(z^{5}C(z^{5})) and B_{f} = z^{2}T_{3}(−z^{5}).

In the second family, letting n = 2 yields f = z/C(−zC^{2}) and B_{f} = T_{4}^{2} (\underline{A069271}). Likewise, letting n = 3 yields f = z/C(−z^{3}T_{3}^{3}(z^{3})) and B_{f} = zT_{6}^{3}(z^{3}) (\underline{A212072} with 0 prepended).

Example 55. We have P_{0} = 1, P_{1} = 3 + z, P_{2} = 5 + 5z + z^{2}, which yields, for the first family,

B_{zm̃} = B_{h_{1,0}} = T_{−1}^{−1}(−z) = C,
B_{zC^{3}} = B_{h_{1,1}} = P_{1}(z) = 3 + z,
B_{zC^{5}(zC)} = B_{h_{1,2}} = T_{3}(−z)P_{2}(zT_{3}^{2}(−z))

= T_{3}(−z)(5 + 5zT_{3}^{2}(−z) + (zT_{3}^{2}(−z))^{2})

= (5T_{3} − 5zT_{3}^{3} + z^{2}T_{3}^{5}) ∘ (−z) = 5 + z^{2}T_{3}^{5}(−z)

= 5 + ∑_{n=2}^{∞} (−1)^{n} \frac{5}{2n + 1}\binom{3n − 2}{n − 2}z^{n}

= 5 + z^{2} − 5z^{3} + 25z^{4} − 130z^{5} + …,

and, similarly, for the second family,

B_{z/C(−zC^{2})} = B_{h_{2,2}} = T_{4}^{2}

= ∑_{n=0}^{∞} \frac{2}{3n + 2}\binom{4n + 1}{n}z^{n} = 1 + 2z + 9z^{2} + 52z^{3} + 340z^{4} + ⋯,

B_{z/C^{3}(−zT_{3}^{3})} = B_{h_{2,3}} = T_{6}^{3} P_{1}(zT_{6}^{6}) = T_{6}^{3}(3 + zT_{6}^{6}) = T_{6}^{3}(2 + T_{6}) = 2T_{6}^{3} + T_{6}^{4}

= ∑_{n=0}^{∞} \frac{3}{2n + 1}\binom{6n + 4}{n}z^{n} = 3 + 10z + 72z^{2} + 660z^{3} + 6825z^{4} + · · · .

Example 56. The form of the functions γ in (58) and (59) corresponding to Examples 51 and 52, respectively, leads us to the following generalization containing both of the above families:

γ(z) = z^{k}(1 − z + z^{2})^{n}.  (61)

Indeed, suppose the function a function g = g(z) satisfies the functional equation

g = 1 + zγ(g) = 1 + zg^{k}(1 − g + g^{2})^{n}.

Note that γ(z) is palindromic with dar(γ) = (k + k) + (0 + 2) · n = 2k + 2n. Therefore, the function h = h(z) = zg^{2k+2n−1} is pseudo-involutory by Theorem 2, and thus, f = f(z) = zg(z^{2k+2n−1}) is also pseudo-involutory by Theorem 33. Moreover,

δ^{2} (\frac{(z − 1)^{2}}{z} ) = \frac{γ(z)^{2}}{z^{d}} = \frac{z^{2k}(1 − z + z^{2})^{2n}}{z^{2n+2k}} = (\frac{1 − z + z^{2}}{z} )^{2n} = (1 + \frac{(z − 1)^{2}}{z} )^{2n} ,

so δ^{2}(z) = (1 + z)^{2n} and D = T_{2n}^{n}, as in the proof of Theorem 53.

For negative indices n = −p < 0, recall from (56) that T_{−n}(z) = 1/T_{n+1}(−z), and therefore,

D = T_{2n}^{n} = T_{−2p}^{−p} = \frac{1}{T_{2p+1}^{−p}(−z)} = T_{2p+1}^{p}(−z) = T_{−2n+1}^{−n}(−z).

Note that the darga d = 2k+2n is even, so d−1 is odd. Therefore, both f = zg(z^{2k+2n−1}) and h = zg^{2k+2n−1} are pseudo-involutory by Theorem 33, and

B_{f} = B_{f}(z) = z^{k+n−1}T_{2n}^{n}(z^{2k+2n−1}) and B_{h} = B_{h}(z) = T_{2n}^{n}P_{k+n−1}(zT_{2n}^{2n}) (62)

by Corollary 37.

Example 57. (Modulo-k-matched noncrossing matchings) Replacing k with k−1 and letting n = 1 in Example 56, we get

g = 1 + zg^{k−1}(1 − g + g^{2}),  f = zg(z^{2k−1}),  h = zg^{2k−1},

and since T_{2n}^{n} = T_{2} = C, it follows that

B_{f} = z^{k−1}C(z^{2k−1}), B_{h} = CP_{k−1}(zC^{2}).

For k = 1, we recover g = m̃, f = h = zm̃, B_{f} = B_{h} = C, as in Examples 8 and 14. For k = 2, we find that g is the generating function for the sequence \underline{A106228}, and

B_{f} = zC(z^{3}), B_{h} = CP_{1}(zC^{2}) = C(3 + zC^{2}) = C(2 + C) = C^{2} + 2C,

where the latter is the generating function for the sequence \underline{A038629}.

This example arises combinatorially in several different contexts (see \underline{A106228}), and we give another one here. Consider partial noncrossing matchings (see Example 8) on p points labeled 1 through p from left to right where only points with labels congruent modulo k can be matched. For k > 1, no pair of points with consecutive labels can be matched, so these noncrossing matchings are also secondary RNA structures of Example 12.

Let a_{p} be the number of such structures on p points, and consider the functions

G_{i} = G_{i}(z) = ∑_{j=0}^{∞} a_{kj+i}z^{j}, i = 0, 1, …, k − 1.

The point 1 is either unmatched or matched to some point kℓ + 1, where ℓ ≥ 0 and 2ℓ + 1 < p. Matching the point 1 to point kℓ + 1 separates the noncrossing matching into two submatchings: on the kℓ−1 points labeled 2 through kℓ, and on the p−kℓ−1 points labeled kℓ + 2 through p. The former submatching is necessarily of length k − 1 mod k, whereas p − kℓ − 1 ≡ p − 1 mod k. This yields the following generating function equations:

\begin{aligned}G_{0}(z^{k}) & = 1 + z(z^{k−1}G_{k−1}(z^{k})) + z^{2}(z^{k−1}G_{k−1}(z^{k}))(z^{k−1}G_{k−1}(z^{k})), \\ z^{i}G_{i}(z^{k}) & = z(z^{i−1}G_{i−1}(z^{k})) + z^{2}(z^{k−1}G_{k−1}(z^{k}))(z^{i−1}G_{i−1}(z^{k})), i = 1, 2, …, k − 1, \end{aligned}

where the summands from left to right correspond to the empty string, point 1 unmatched, and point 1 matched, respectively. Therefore,

\begin{aligned}G_{0} & = 1 + zG_{k−1} + (zG_{k−1})^{2}, \\ G_{i} & = G_{i−1} + zG_{k−1}G_{i−1} = (1 + zG_{k−1})G_{i−1}, i = 1, 2, …, k − 1, \end{aligned}

which implies that

G_{k−1} = (1 + zG_{k−1})^{k−1} (1 + zG_{k−1} + (zG_{k−1})^{2}) .

Now let g(z) = 1+zG_{k−1}(z). Then g satisfies the functional equation g = 1+zg^{k−1}(1−g+g^{2}) and corresponds to the counting sequence for the noncrossing matchings of length kℓ (ℓ ≥ 0), where the point 1 is unmatched if the structure is nonempty, and only points with labels congruent modulo k can be matched.

As noted above, for k = 2, g(z) = 1 + zG_{1}(z) is the generating function for the sequence \underline{A106228}. We also note that G_{0}(z) is the generating function for \underline{A109081}, whereas G_{0}(z^{2}) + zG_{1}(z^{2}) = ∑_{j=0}^{∞} a_{j}z^{j} is the generating function for \underline{A215067}.

Example 58. The identity (54) is one of many that can be used to produce pseudoinvolutions in k-Bell subgroups involving compositions of functions. Here we find a twoparameter family of pseudo-involutions similar to those in Examples 51 and 52 using an identity similar to (54).

Consider a family of functions v_{k} = v_{k}(z), k ∈ ℤ, defined implicitly by the equation

v_{k} = 1 + z(v_{k} + v_{k}^{k}).  (63)

The function

v_{k} = \frac{1}{1 − z} T_{k} (\frac{z}{(1 − z)^{k}} )  (64)

is the generating function, when k ≥ 1, for the number of lattice paths from (0, 0) to (kn, 0) on or above the x-axis with steps U = (1, k−1), D = (1, −1), and L = (k, 0), a generalization of Schröder paths. Furthermore, v_{k} is closely related to functions in several other families considered earlier in this paper. For example, v_{0} = \frac{1+z}{1−z} = r_{1} = t_{1} = u_{1} , v_{1} = \frac{1}{1−2z} , v_{2} = r = r_{2} (see Section 4.5). Moreover, rewriting (63) as v_{k} = 1 + zv_{k}(1 + v_{k}^{k−1}), we obtain v_{k} = u_{k−1}(zv_{k}), i.e., u_{k−1} = A_{zv_{k}} and zv_{k} = \overline{(z/u_{k−1})}, where u_{k} is a function from the family in Example 10. For nonpositive index values, i.e., for v_{−k}, k ≥ 0, dividing equation (63) through by v_{−k} and rearranging terms, we obtain

\frac{1}{v_{−k}} = 1 − z (1 + (\frac{1}{v_{−k}} )^{k+1}) ,

which implies that

v_{−k}(z) = \frac{1}{u_{k+1}(−z)}.

It is easy to see that, for the function v_{k}, we have γ = z + z^{k}, a palindrome of darga k + 1, so (v_{k}, zv^{k}) is a pseudo-involution. Moreover, similarly to the identity (54), we have

1 + zv_{k}^{k} = (1 − z)v_{k} .  (65)

As in Example 51, let g = v_{k} and h = zT_{n}^{n−1}, then g ∘ h = v_{k}(zT_{n}^{n−1}) and f = zv_{k}^{k}, so

ĥ ∘ f ∘ h = (z(1 + z)^{n−1}) ∘ (zv_{k}^{k}) ∘ (zT_{n}^{n−1}).

However, from Equation (65),

(z(1 + z)^{n−1}) ∘ (zv_{k}^{k}) = zv^{k} (1 + zv_{k}^{k})^{n−1} = zv_{k}^{k} ((1 − z)v_{k})^{n−1} = z(1 − z)^{n−1}v_{k}^{n+k−1},

so, recalling that z(1 − z)^{n−1} = \overline{zT_{n}^{n−1}}, we have

ĥ ∘ f ∘ h = (z(1 − z)^{n−1}v_{k}^{n+k−1}) ∘ (zT_{n}^{n−1}) = zv_{k}^{n+k−1}(zT_{n}^{n−1}).

Thus,

(v_{k}(zT_{n}^{n−1}), zv_{k}^{n+k−1}(zT_{n}^{n−1}))  (66)

is a pseudo-involution in the (n + k − 1)-Bell subgroup.

Similarly, as in Example 52, let g = 1/v_{k} and h = −zT_{n}^{n}, then g ∘ h = 1/v_{k}(−zT_{n}^{n}) and f = zv_{k}^{k}, so

ĥ ∘ f ∘ h = (−z/(1 + z)^{n}) ∘ (zv_{k}^{k}) ∘ (−zT_{n}^{n}).

However, from Equation (65),

(−\frac{z}{(1 + z)^{n}} ) ∘ (zv_{k}^{k}) = −\frac{zv_{k}^{k}}{(1 + zv_{k}^{k})^{n}} = −\frac{zv_{k}^{k}}{((1 − z)v_{k})^{n}} = −\frac{z}{(1 − z)^{n}v_{k}^{n−k}} ,

so, recalling that −z/(1 − z)^{n} = \overline{(−zT_{n}^{n})}, we have

ĥ ∘ f ∘ h = (−\frac{z}{(1 − z)^{n}v_{k}^{n−k}} ) ∘ (−zT_{n}^{n}) = \frac{z}{v_{k}^{n−k}(−zT_{n}^{n})}.

Thus,

(\frac{1}{v_{k}(−zT_{n}^{n})}, \frac{z}{v_{k}^{n−k}(−zT_{n}^{n})})  (67)

is a pseudo-involution in the (n − k)-Bell subgroup. Furthermore, since 1/(1 − zT_{n}^{n−1}) = 1 − (−zT_{n}^{n}) = T_{n}, we have

\begin{aligned}(v_{k}(zT_{n}^{n−1}), zv_{k}^{n+k−1}(zT_{n}^{n−1})) & = (T_{n} T_{k}(zT_{n}^{n+k−1}) , zT_{n}^{n+k−1}T_{k}^{n+k−1}(zT_{n}^{n+k−1})) \\ & = (T_{n} T_{k}(zT_{n}^{n+k−1}) , (zT_{k}^{n+k−1}) ∘ (zT_{n}^{n+k−1})) \end{aligned}

and

\begin{aligned}(\frac{1}{v_{k}(−zT_{n}^{n})}, \frac{z}{v_{k}^{n−k}(−zT_{n}^{n})}) & = (\frac{T_{n}}{T_{k}(−zT_{n}^{n−k})} , \frac{zT_{n}^{n−k}}{T_{k}^{n−k}(−zT_{n}^{n−k})}) \\ & = (\frac{T_{n}}{T_{k}(−zT_{n}^{n−k})} , (−zT_{k}^{k−n}) ∘ (−zT_{n}^{n−k})) . \end{aligned}

Note also that, for the first components of these pseudo-involutions, we have

\begin{aligned}T_{n} T_{k}(zT_{n}^{n+k−1}) & = \frac{T_{k}(z)}{T_{k}(−z)} ∘ (zT_{n}^{n+k−1}), \\ \frac{T_{n}}{T_{k}(−zT_{n}^{n−k})} & = \frac{T_{k}(z)}{T_{k}(−z)} ∘ (zT_{n}^{n−k}). \end{aligned}

We leave it as an exercise for the reader to produce the B-functions for the pseudoinvolutions (66) and (67) following the example of Theorem 53. A natural combinatorial interpretation of these pseudo-involutions would also be of interest.

Example 59. Finally, Examples 51, 52, and 58 are all part of a three-parameter family of involutions in p-Bell subgroups (for various powers p) involving composition with either zT_{n}^{n−1} or −zT_{n}^{n}. Given d, k, n ∈ ℤ, k > 0, consider a power series w_{k} with w_{k}(0) = 1 that satisfies an equation similar to (54) and (65):

1 + zw_{k}^{d−1} = (1 − z)w_{k}^{k}.  (68)

Solving for z, we obtain

z = \frac{w_{k}^{k} − 1}{w_{k}^{d−1} + w_{k}^{k}} = \frac{(w_{k} − 1) ∑_{j=0}^{k−1} w_{k}^{j}}{w_{k}^{d−1} + w_{k}^{k}} ,

or, equivalently,

w_{k} = 1 + z \frac{w_{k}^{d−1} + w_{k}^{k}}{∑_{j=0}^{k−1} w_{k}^{j}} .

Since the function γ(z) = (z^{d−1} + z^{k})/(∑_{j=0}^{k−1} z^{j}) is a generalized palindrome (having a palindromic numerator and denominator) of darga dar(γ) = (d − 1 + k) − (0 + k − 1) = d, Theorem 2 implies that (w_{k}, zw_{k}^{d−1}) is a pseudo-involution.

Now, as in Examples 51, 52, and 58, applying Theorem 44 to (g, f) = (w_{k}, zw_{k}^{d−1}) and h = zT_{n}^{n−1} yields the pseudo-involution

(w_{k}(zT_{n}^{n−1}), zw_{k}^{k(n−1)+(d−1)}(zT_{n}^{n−1})) ,  (69)

while applying Theorem 44 to (g, f) = (1/w_{k}, zw_{k}^{d−1}) and h = −zT_{n}^{n} yields the pseudoinvolution

(\frac{1}{w_{k}(−zT_{n}^{n})}, \frac{z}{w_{k}^{kn−(d−1)}(−zT_{n}^{n})}) .  (70)

For example, letting k = 2 and d = 4 yields Examples 51 and 52, whereas letting k = 1 yields Example 58 for v_{d−1}. As an exercise, the reader is invited to make the necessary minor adjustments needed to adapt formulas (69) and (70) to the case when k < 0.

5.1 Pseudo-conjugation of exponential pseudo-involutions

All the pseudo-conjugation results stated in Section 5 for ordinary Riordan arrays (g, f) also apply to exponential Riordan arrays [g, f]. In this section we give several examples of pseudo-conjugation of exponential pseudo-involutions. In all of these examples, we start with the exponential pseudo-involution [e^{z}, z], the Pascal triangle.

Example 60. (Involutions) Let [g, f] = [e^{z}, z] and h = z + z^{2}/2. Then g ∘ h = e^{z+z^{2}/2} is the exponential generating function for the number \underline{A000085} of involutions on an n-element set. Moreover, h = z + z^{2}/2 = (2z) ∘ (z + z^{2}) ∘ (z/2), so \overline{h} = (2z) ∘ \overline{(z + z^{2})} ∘ (z/2) = (2z) ∘ (zC(−z)) ∘ (z/2) = zC(−z/2), and thus ĥ = (−z) ∘ (zC(−z/2)) ∘ (−z) = zC(z/2) = 1 − \sqrt{1 − 2z}. Therefore,

ĥ ∘ f ∘ h = (zC (\frac{z}{2})) ∘ (z + \frac{z^{2}}{2} ) = 1 − \sqrt{1 − 2z − z^{2}},

the exponential generating function of \underline{A182037}, and thus [e^{z+z^{2}/2}, 1 − \sqrt{1 − 2z − z^{2}}] is a pseudo-involution.

Example 61. (Set partitions and necklaces of partitions) Let [g, f] = [e^{z}, z] and h = e^{z} − 1. Then g ∘ h = e^{e^{z}−1} is the exponential generating function for the Bell numbers \underline{A000110}. We also have ĥ = (−z) ∘ \overline{h} ∘ (−z) = (−z) ∘ log(1 + z) ∘ (−z) = log(1/(1 − z)). Therefore, the exponential pseudo-involutory companion of the Bell numbers is

ĥ ∘ f ∘ h = log (\frac{1}{1 − z} ) ∘ z ∘ (e^{z} − 1) = log (\frac{1}{2 − e^{z}} ) ,

the exponential generating function of the sequence \underline{A000629} prepended by 0, which counts necklaces of set partitions. This yields the exponential pseudo-involution

[e^{e^{z}−1}, log (\frac{1}{2 − e^{z}} )]

that begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 4 & 1 & 0 & 0 & 0 \\ 5 & 18 & 9 & 1 & 0 & 0 \\ 15 & 94 & 72 & 16 & 1 & 0 \\ 52 & 575 & 600 & 200 & 25 & 1 \end{matrix}] .

Example 62. (Set partitions with marked elements and rooted labeled trees) Let [g, f] = [e^{z}, z] and h = ze^{z}. Then g ∘ h = e^{ze^{z}} is the exponential generating function for \underline{A000248} that counts set partitions with one marked element per part. Then

ĥ ∘ f ∘ h = (−z) ∘ \overline{(ze^{z})} ∘ (−z) ∘ (ze^{z}) = zS

by (26), where S and zS are from Example 23, and zS is the exponential generating function of \underline{A216857}, i.e., the coefficients of zS count rooted trees labeled with parts of a partition with one marked element per part. This yields the exponential pseudo-involution [e^{ze^{z}}, zS] that begins

[\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 3 & 6 & 1 & 0 & 0 \\ 10 & 45 & 15 & 1 & 0 \\ 41 & 432 & 210 & 28 & 1 \end{matrix}] .

6 Conclusion

In this paper, we have developed some general methods for finding ordinary and exponential pseudo-involutions and their B-sequences, including, in particular, those in a k-Bell subgroup for some k. We also found several new families of pseudo-involutions of combinatorial significance. Many of the generating function identities involved, however, still await their combinatorial interpretation. Those, in particular, include combinatorial interpretations of several new integer sequences in our paper, as well as of the fact that the pseudo-involutory functions we have considered are indeed pseudo-involutory. We intend to develop such interpretations in subsequent papers and will only note here that many of those stem from the generalizations of the Carlitz-Scoville-Vaughn Theorem [11] given by Parker [25] for ordinary generating functions and by Drake [17] for exponential generating functions.

References

[1] K. Archer and C. Graves, Pattern-restricted permutations composed of 3-cycles, preprint, April 26 2021. Available at https://arxiv.org/abs/2104.12664.

[2] A. Ayyer and D. Zeilberger. The number of [old-time] basketball games with final score n : n where the home team was never losing but also never ahead by more than w points, Electron. J. Combin. 14 (1) (2007), Research Paper 19.

[3] C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method. In G. Andrews, C. Krattenthaler, and A. Krinik, eds., Lattice Path Combinatorics and Applications. Developments in Mathematics, Vol. 58, Springer, 2019. Preprint available electronically at https://arxiv.org/abs/1609.06473.

[4] P. Barry, The Riordan Group, a Primer, Logic Press, 2016.

[5] P. Barry, Chebyshev moments and Riordan involutions, preprint, December 26 2019.

    Available at https://arxiv.org/abs/1912.11845.

[6] P. Barry, Riordan pseudo-involutions, continued fractions, and Somos-4 sequences, J. Integer Sequences 22 (2019), Article 19.6.1.

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

[8] F. Bergeron, P. Flajolet, and B. Salvy, Varieties of increasing trees, in Proceedings of CAAP ’92 (Rennes, 1992) Lecture Notes in Comput. Sci., Vol. 581, Springer, 1992, pp. 24–48.

[9] J. Bettinelli, E. Fusy, C. Mailler, L. Randazzo, A bijective study of basketball walks, Sém. Lothar. Combin. 77 (2016), Article B77a, 1–24.

[10] N. T. Cameron and A. Nkwanta, On some (pseudo) involutions in the Riordan group, J. Integer Sequences 8 (2005), Article 05.3.7.

[11] L. Carlitz, R. Scoville, and T. Vaughn, Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math. 19 (1976), 211–243.

[12] G.-S. Cheon, S.-T. Jin, H. Kim, and L. W. Shapiro, Riordan group involutions and the Δ-sequence, Disc. Appl. Math. 157 (2009), 1696–1701.

[13] G.-S. Cheon and H. Kim, Simple proofs of open problems about the structure of involutions in the Riordan group, Lin. Alg. Appl. 428 (2008), 930–940.

[14] G.-S. Cheon, H. Kim and L. W. Shapiro, Riordan group involutions, Lin. Alg. Appl. 428 (2007), 941–952.

[15] E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (2010), 2191–2203.

[16] E. Deutsch and L. Shapiro, Exponential Riordan arrays, Lecture Notes, Nankai

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

[17] B. Drake, An Inversion Theorem for Labeled Trees and Some Limits of Areas under Lattice Paths, Ph.D. thesis, Brandeis University, 2008, http://people.brandeis.edu/

~gessel/homepage/students/drakethesis.pdf.

[18] H. W. Gould, The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences, Fibonacci Quart. 37 (1999), 135–140.

[19] T.-X. He, A-sequences, Z-sequence, and B-sequences of Riordan matrices, Discrete Math. 343 (2020), 111718.

[20] T.-X. He and L. Shapiro, Palindromes and pseudo-involution multiplication, Lin. Alg. Appl. 593 (2020), 1–17.

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

[22] S. Janson, M. Kuba, and A. Panholzer, Generalized Stirling permutations of increasing trees and urn models, J. Combin. Theory Ser. A 118 (2011), 94–114.

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

[24] OEIS, The Online Encyclopedia of Integer Sequences, 2022. Available at https://

    oeis.org.

[25] S. F. Parker, The Combinatorics of Functional Composition and Inversion, Ph. D. thesis, Brandeis University, 1993. Available at http://people.brandeis.edu/~gessel/

    homepage/students/parkerthesis.pdf.

[26] D. Phulara and L. Shapiro, Constructing pseudo-involutions in the Riordan group, J. Integer Sequences 20 (2017), Article 17.4.7.

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

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

[29] M. Zeleke, Riordan Arrays and their applications in Combinatorics, parts 1 and 2,

    YouTube, http://youtu.be/hdR24ApU_EM and http://youtu.be/coLIavPaW60.

2020 Mathematics Subject Classification: Primary 05A15. Secondary 05A05, 05A19, 11B83. Keywords: Riordan group, Riordan array, pseudo-involution.

(Concerned with sequences \underline{A000085}, \underline{A000108}, \underline{A000110}, \underline{A000245}, \underline{A000248}, \underline{A000272}, \underline{A000629}, \underline{A001003}, \underline{A001006}, \underline{A002212}, \underline{A004148}, \underline{A006318}, \underline{A007106}, \underline{A007559}, \underline{A025227}, \underline{A027307}, \underline{A038049}, \underline{A038629}, \underline{A049310}, \underline{A068875}, \underline{A069271}, \underline{A086246}, \underline{A089946}, \underline{A106228}, \underline{A109081}, \underline{A111125}, \underline{A127632}, \underline{A153295}, \underline{A153396}, \underline{A156308}, \underline{A166135}, \underline{A182037}, \underline{A200031}, \underline{A212072}, \underline{A215067}, \underline{A216857}, \underline{A238113}, \underline{A344623}, \underline{A347953}, \underline{A348189}, \underline{A348197}, and \underline{A349562}.)

Received December 29 2021; revised version received March 14 2022. Published in Journal of Integer Sequences, March 24 2022.

Return to Journal of Integer Sequences home page.