Constructing Pseudo-Involutions in the Riordan Group

Dev Phulara National Security Agency Fort Meade, MD 20755 USA

                    drphula@nsa.gov
                  phulara@comcast.net

Louis Shapiro Howard University Washington, DC 20059 USA

                  lshapiro@howard.edu

Abstract

Involutions and pseudo-involutions in the Riordan group are interesting because of their numerous applications. In this paper we study involutions using sequence characterizations of the Riordan arrays. For a given B-sequence we find the unique function f(z) such that the array (g(z), f(z)) is a pseudo-involution. As a combinatorial application, we find the interpretation of each entry in the Bell array (g(z), f(z)) with a given B-sequence.

1 Introduction

A Riordan array originally introduced by Shapiro et al. [13] is defined in terms of generating functions of its columns. Let g(z) = g_{0} + g_{1}z + g_{2}z^{2} + ⋯, g_{0} ≠ 0 and f(z) = f_{1}z + f_{2}z^{2} + f_{3}z^{3} + ⋯, f_{1} ≠ 0 be two formal power series. The Riordan array generated by g(z) and f(z) is an infinite lower triangular array D whose kth column has the generating function g(z)(f(z))^{k} for all k ≥ 0. We denote D by (g(z), f(z)). In other words D = (d_{n,k})_{n,k≥0} is Riordan if and only if there exist two generating functions g(z) and f(z) such that d_{n,k} is the coefficient of z^{n} in the expansion of g(z)(f(z))^{k}.

The set R of all Riordan arrays forms a group under the matrix multiplication operation. In terms of generating functions, the product of two arrays (g(z), f(z)) and (α(z), β(z)) can be written as

(g(z), f(z)) · (α(z), β(z)) = (g(z)α(f(z)), β(f(z))).

The usual identity matrix (1, z) serves as the group identity and for any (g(z), f(z)) ∈ R, (\frac{1}{g(\overline{f}(z))}, \overline{f}(z)) is its inverse, where \overline{f} represents the compositional inverse of f.

Note that the original definitions of Riordan array are based on column construction. Merlini et al. [11] and Sprugnoli [14] characterized Riordan arrays using two sequences called the A-sequence and the Z-sequence which enables us to construct the Riordan array horizontally. That is each entry in the Riordan array can be written as a linear combination of entries in the previous row. More precisely we have

Theorem 1. An array D = (d_{n,k})_{n,k≥0} is Riordan if and only if there exist unique sequences A = (a_{0}, a_{1}, a_{2}, …) and Z = (z_{0}, z_{1}, z_{2}, …) such that

1. d_{n+1,k+1} = ∑_{i=0}^{∞} a_{i}d_{n,k+i} and

2. d_{n+1,0} = ∑_{i=0}^{∞} z_{i}d_{n,i}.

The sequences A and Z in this theorem are called the A-sequence and Z-sequence respectively. See also [8]. See [6] for another characterization of Riordan arrays (in terms of Stieltjes transform matrix). See also [7].

A nontrivial element D = (g(z), f(z)) ∈ R is an involution if and only if D^{2} = I. Let M = (1, −z), that is M is a diagonal matrix with (1, −1, 1, −1, …) along the diagonal. An element D = (g(z), f(z)) is a pseudo-involution if and only if DM is an involution or equivalently MD is an involution or D^{−1} = MDM. See [1, 2, 3, 4, 5] for more information. In this paper we study pseudo-involutions via B-sequences. It is an important fact that the A-sequence uniquely determines the generating function f. One version is f(z) = zA(f(z)) or equivalently z = \overline{f}(z)A(z). This could be called the second fundamental theorem of the Riordan group. A “dot” diagram of this is

\begin{matrix}a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \\ a_{4} \\ ⋯ \\ × \end{matrix}

However there are many situations where it is useful to expand to an A-matrix [11]

\begin{matrix}⋯ \\ ⋯ \\ ⋯ \\ ⋯ \\ ⋯ \\ × \\ a_{0,2} \\ a_{0,3} \\ a_{1,0} \\ a_{1,1} \\ a_{1,2} \\ a_{1,3} \\ a_{2,0} \\ a_{2,1} \\ a_{2,2} \\ a_{2,3} \end{matrix}

A modest example is given by

\begin{matrix}× \\ 1 \\ 1 \\ 1 \end{matrix}

This produces the large Schröder numbers.

Recently Merlini and Sprugnoli [10] studied binary words avoiding certain patterns using A-matrices such as

\begin{matrix}1 \\ c_{2} \\ c_{4} \\ c_{q} \\ −c_{2} \\ −c_{4} \\ −c_{6} \\ −c_{q−2} \\ 1 \\ c_{2} \\ c_{4} \\ c_{6} \\ c_{q−2} \end{matrix}

Here is a picture of the A-matrix that produces the B-sequence.

\begin{matrix}· \\ · \\ · \\ × \\ b_{0} \\ b_{1} \\ 1 \\ b_{2} \end{matrix}

See also [12] for several online software tools for exploring Riordan arrays.

This paper is organized as follows. In Section 2 we present some ways of constructing pseudo-involutions. In Section 3 we discuss those pseudo-involutions via B-sequences, we present a list of 24 examples, and we also present an explicit formula to compute the Asequence of a pseudo-involution with a given B-sequence. Finally in Section 4 we present combinatorial interpretations for all involutions in the Bell subgroup.

2 (Pseudo)-involutions

Given a formal power series g(z) = 1+∑_{n≥1} g_{n}z^{n}, we want to find a generating function f(z) such that (g(z), f(z))^{2} = I = (1, z). For such f(z), we must have g(z)g(f(z)) = 1. That is g(f(z)) = \frac{1}{g(z)}. We first study a special case in which g(z) can be expressed as g = 1 + zg^{k}, for some k ∈ ℕ.

Theorem 2. Let g(z) = 1+∑_{n≥1} g_{n}z^{n} be a power series where g = 1+zg^{k}, for some k ∈ ℕ. Then (g(z), −z(g(z))^{2k−1})^{2} = I.

Proof. Since g(z) = 1 + zg^{k}, we can write g as

g(z) = \frac{1}{1 − zg^{k−1}}
= (1 − zg^{k−1})^{−1}.

So zg^{k−1} = z(1 − zg^{k−1})^{−(k−1)}. Now set

F = F (z) = zg^{k−1}.  (1)

Then F = z(1 − F)^{−(k−1)}. Apply \overline{F} to this equation to get

z = \overline{F} (1 − z)^{−(k−1)}.

Then

\overline{F} = z(1 − z)^{k−1}.  (2)

Starting with Eq. 1, we get

F (f(z)) = f(z)g(f(z))^{k−1} = f · (g(f))^{k−1} = f(\frac{1}{g})^{k−1} = \frac{f}{g^{k−1}} .

Now apply \overline{F} to get

f(z) = \overline{F} (\frac{f}{g^{k−1}} ) = \frac{f}{g^{k−1}} (1 − \frac{f}{g^{k−1}} )^{k−1}.

This implies

g^{k−1} = (1 − \frac{f}{g^{k−1}} )^{k−1}

⇒g = 1 − \frac{f}{g^{k−1}}
⇒f = g^{k−1} − g^{k}
⇒f = g^{k−1}(1 − g).

But 1 − g = −zg^{k} so f = g^{k−1}(−zg^{k}) = −zg^{2k−1}.

The following important examples which are some special cases of this theorem go back at least to 1976 in a paper of Hoggatt and Bicknell in the Fibonacci Quarterly [9]. These occur again in Section 3 as examples 1, 10, 18, and 20. Here the generating functions C, T and Q refer to the Catalan, ternary, and quaternary numbers respectively while P = \frac{1}{1−z}.

\begin{matrix}k & g = 1 + zg^{k} & f = −zg^{2k−1} & (g, −zg^{2k−1})^{2} = I \\ k = 1 & P = 1 + zP & f = −zP & (P, −zP)^{2} = I \\ k = 2 & C = 1 + zC^{2} & f = −zC^{3} & (C, −zC^{3})^{2} = I \\ k = 3 & T = 1 + zT^{3} & f = −zT^{5} & (T, −zT^{5})^{2} = I \\ k = 4 & Q = 1 + zQ^{4} & f = −zQ^{7} & (Q, −zQ^{7})^{2} = I \end{matrix}

Table 1: Some special cases of Theorem 2

Another interesting relationship among these examples will be presented in Section 3 after presenting the notion of B-sequences.

For g(z) = 1 + ∑_{n≥1} g_{n}z^{n} and f(z) = z + ∑_{n≥2} f_{n}z^{n}, we know that if (g(z), f(z)) is a pseudo-involution then (g(z), −f(z)) is an involution so f(−f(−z)) = z. Then we use [15, Exercise 168, p. 134] to specify the even indexed coefficients (f_{2}, f_{4}, …) arbitrarily which then determine the odd indexed coefficients (f_{3}, f_{5}, …) uniquely. So there are many generating functions f(z) which generate pseudo-involutions. It is easy to show that if f(−f(−z)) = z, then (f(z)/z, f(z)) is a pseudo-involution. Moreover it has been established [2, Thm. 2.3] that if (g(z), f(z)) is an involution, then g(z) = ± exp(Φ(z, zf(z))) for some antisymmetric function Φ. However we do not know the answer of the following question.

Question 3. Given f(z) such that f(−f(−z)) = z or \overline{f}(z) = −f(−z), what are the possibilities for g(z) so that (g(z), f(z)) is an involution, particularly in combinatorial situations?

Another way to find more involutions and thus pseudo-involutions comes from basic group theory. If α and β are two noncommuting involutions then ⟨α, β⟩ is a dihedral group and (αβ)^{n}β is an involution for all integers n, where αβ plays the role of a rotation. In the Riordan group if M_{1} and M_{2} are noncommuting involutions then ⟨M_{1}, M_{2}⟩ is a dihedral group.

Proposition 4. Let D_{1} and D_{2} be two pseudo-involutions. Then both (D_{1}D_{2}^{−1})^{n}D_{2} and D_{1}(D_{1}^{−1}D_{2})^{n} are pseudo-involutions for all integers n.

Proof. Let H_{1} = D_{1}M and H_{2} = D_{2}M. Then H_{1} and H_{2} are involutions and so for all integer n, (H_{1}H_{2})^{n}H_{2} is an involution and

(H_{1}H_{2})^{n}H_{2} = (D_{1}MD_{2}M)^{n}D_{2}M
= (D_{1}D_{2}^{−1})^{n}D_{2}M.

Hence (D_{1}D_{2}^{−1})^{n}D_{2} is a pseudo-involution. On the other hand if we let J_{1} = MD_{1} and J_{2} = MD_{2}, then

J_{1}(J_{1}J_{2})^{n} = MD_{1}(MD_{1}MD_{2})^{n}
= MD_{1}(D_{1}^{−1}D_{2})^{n}.

Since J_{1}(J_{1}J_{2})^{n} is an involution, D_{1}(D_{1}^{−1}D_{2})^{n} is also a pseudo-involution.

The following result was first proved [4] using induction on n but it follows more quickly from the proposition we just proved.

Corollary 5. Let D = (g(z), f(z)) be a pseudo involution. Then so is D^{n}, for all n ∈ ℤ.

Proof. Let D_{1} = D and D_{2} = (1, z). Then D_{1} and D_{2} are pseudo-involutions and thus Proposition 4 applies.

3 Relationship with B-sequences

Let A(z) be the generating function of the A sequence of a Riordan array (g(z), f(z)). We can write f(z) in terms of A as follows

f(z) = zA(f(z)).

Replace z by \overline{f}(z) to get z = \overline{f}(z)A(z). So A(z) = \frac{z}{\overline{f}(z)}.

In case of pseudo-involutions, we have \overline{f}(z) = −f(−z). Thus we also have Lemma 6. Let A(z) be the generating function of the A-sequence of the pseudo-involution Riordan array (g(z), f(z)). Then

A(z) = \frac{−z}{f(−z)} = \frac{z}{−f(−z)}.

The following concept was discussed by Cheon et al. [4]. There the term “Δ-sequence” was used instead of B-sequence.

Definition 7. For a Riordan array D = (d_{n,k})_{n,k≥0}, a sequence (b_{0}, b_{1}, b_{2}, …) is said to be a B-sequence if and only if

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

Note that d_{n,k} = 0 for all n < k. So the sum on the right side is finite. In other words, we must have n − j ≥ k + j. That is 2j ≤ n − k.

In the following theorem we link the A-sequence with the B-sequence. It also follows from a notion of A-matrix [11].

Theorem 8. Let B(z) = b_{0} + b_{1}z + b_{2}z^{2} + ⋯ = ∑_{k≥0} b_{k}z^{k} be the B-sequence of a pseudo involution D = (g(z), f(z)). Then the A-sequence of D is given by

A(z) = 1 + zB( − zf(−z)) = 1 + zB(\frac{z^{2}}{A(z)}).

Proof. Since A(z) = \frac{−z}{f(−z)} = \frac{z}{\overline{f}(z)}, we have \overline{f}(z) = −f(−z). We also have f(z) = z + zf(z)B(zf(z)) = zA(f(z)). So A(f(z)) = 1 + f(z)B(zf(z)). Therefore A(f(z)) = 1 + f(z)[b_{0} + b_{1}zf(z) + b_{2}z^{2}(f(z))^{2} + ⋯]. Replace z by \overline{f}(z). Then

A(z) = 1 + z ∑_{k≥0} b_{k}(z\overline{f}(z))^{k}

= 1 + z ∑_{k≥0} b_{k}( − zf(−z))^{k}

= 1 + zB(\frac{z^{2}}{A(z)}).

Corollary 9. If (g(z), f(z)) is in the Bell subgroup, then

A(z) = 1 + ∑_{k≥0} b_{k}z^{2k+1}(g(−z))^{k}.

Proof. We have f(z) = zg(z). So f(−z) = −zg(−z). Therefore

A(z) = 1 + z ∑_{k≥0} b_{k}(z^{2}g(−z))^{k} = 1 + ∑_{k≥0} b_{k}z^{2k+1}(g(−z))^{k}.

In Corollary 5, we showed that any power of a pseudo-involution is a pseudo-involution. But we do not know how to easily combine the various B-sequences. The question remains open even in the case of the same pseudo-involution. More precisely,

Question 10. Let D = (g(z), f(z)) be a pseudo-involution with the B-sequence b_{0}, b_{1}, b_{2}, . . .. what is the B-sequence for D^{2}?

We present a list of some of the examples in the following tables. All these examples are in the Bell subgroup where f(z) = zg(z). One can apply Theorem 11 to construct many examples which are not in the Bell subgroup. Six out of these 24 examples can also be found [4]. We cluster them in families of B-sequences. One can use Theorem 8 to compute the A-sequence in each case. In these examples m, C, T, and r represent the Motzkin, Catalan, ternary, and large Schröder generating functions respectively.

Geometric B-sequences: One can compute the unique f(z) such that (g(z), f(z)) is a pseudo-involution with the B-sequence b, bk, bk^{2}, … as follows

f(z) = \begin{cases}\frac{z}{1−bz}, & if k = 0; \\ ^{\frac{1−bz+kz^{2}−\sqrt{(1−bz+kz^{2})^{2}−4kz^{2}}}{2kz}} , & if k ≠ 0. \end{cases}

We include some examples in the following table.

g  B-sequence  Comments
1 1, 1, 1, 1, 1, 1, 1, 1, …  1, 0, 0, …  Pascal
2 1, 1, 1, 2, 4, 8, 17, 37, 82, 185, …  1, 1, 1, …  RNA (\underline{A004148})
3 1, 2, 4, 10, 28, 82, 248, 770, …  2, 2, 2, …  \underline{A187256}
4 1, 4, 16, 68, 304, 1412, 6752, …  4, 4, 4, …  r^{2}

Table 2: Examples with geometric B-sequences

Linear B-sequences: If the B-sequence is a, b, 0, 0, 0, …, then the unique f(z) is

f(z) = \frac{1 − az − \sqrt{(1 − az)^{2} − 4bz^{3}}}{2bz^{2}} .

Others:

g  B-sequence  Comments
5 1, 1, 1, 2, 4, 7, 13, 26, 52, 104, 212, …  1, 1, 0, …  \underline{A023431}
6 1, 1, 1, 3, 7, 13, 29, 71, …  1, 2, 0, …  \underline{A091565}
7 1, 1, 1, 4, 10, 19, 49, 136, 334, 850, …  1, 3, 0, …
8 1, 2, 4, 9, 22, 56, 146, 388, 1048, …  2, 1, 0, …  \underline{A091561}
9 1, 2, 4, 10, 28, 80, 232, 688, 2080, …  2, 2, 0, …
10 1, 3, 9, 28, 90, 297, 1001, 3432, …  3, 1, 0, …  C^{3} (\underline{A000245})
11 1, 1, 1, 5, 13, 25, 73, 221, 565, 1553, …  1, 4, 0, …
12 1, 4, 16, 65, 268, 1120, 4738, 20264, …  4, 1, 0, …

Table 3: Examples with linear B-sequences

g  B-sequence  Comments
13 1, 1, 1, 2, 4, 9, 21, 50, 122, … 1, 1, 2, 4, 9, 21, 51, 127, …
14 1, 1, 1, 2, 4, 9, 21, 51, 127, … 1, 1, 2, 5, 14, 42, 132, 429, … 1 + zm
15 1, 1, 1, 2, 4, 10, 28, 85, …  1, 3, 9, 28, 90, 297, 1001, …
16 1, 2, 4, 9, 22, 57, 154, 429, … 2, 1, 1, 1, 1, 1, …  \underline{A105633}
17 1, 4, 16, 68, 304, 1409, …  4, 4, 1, 0, 0, …
18 1, 5, 25, 130, 700, 3876, …  5, 5, 1, 0, 0, …  Ternary(\underline{A102893})
19 1, 2, 4, 12, 40, 129, 424, …  2, 4, 1, 0, 0 …
20 1, 7, 49, 357, 2695, …  7, 14, 7, 1, …  Quaternary(\underline{A233658})
21 1, 4, 16, 64, 256, 1024, …  4, 0, 0, …  (B, zB^{2})
22 1, 0, 0, 2, 0, 0, 5, 0, 0, 14, … 0, 1, 0, 0, …  (C(z^{3}), zC(z^{3}))
23 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 12, … 0, 0, 1, 0, 0, …  (T (z^{5}), zT (z^{5}))
24 1, 1, 1, 2, 4, 9, 21, 50, 122, … 1, 1, 2, 4, 8, …

Table 4: Examples with other B-sequences

For each generating function g(z) and for each B-sequence, there exists a generating function f(z) such that the Riordan array (g(z), f(z)) is a pseudo-involution. In fact we see from Eq. 8 that for every B-sequence there exists a unique function f(z) such that (g(z), f(z)) is a pseudo-involution. Furthermore in the Bell subgroup such an array is unique because g(z) = \frac{f(z)}{z}. But the function g(z) is far from being unique. The following result shows that there are infinitely many functions g(z) for given f(z) such that the array (g(z), f(z)) is pseudo-involution with same B-sequence.

Theorem 11. Let (g(z), f(z)) be a pseudo-involution Riordan array and let B(z) = b_{0} + b_{1}z + b_{2}z^{2} + ⋯ be the generating function of its B-sequence. Then ((g(z))^{n}, f(z)) is also a pseudo-involution with the same B-sequence, for all n ∈ ℕ.

Proof. Let (g(z), f(z)) be a pseudo-involution. Then

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

That is (g(z)g(−f(z)), −f(−f(z))) = (1, z), so g(z)g(−f(z)) = 1 and −f(−f(z)) = z. Thus for any n,

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

Also if B_{1} and B_{2} are the B-sequences of (g(z), f(z)) and ((g(z))^{n}, f(z)) respectively, then f(z) = z + zf(z)B_{1}(zf(z)) = z + zf(z)B_{2}(zf(z)). Hence B_{1} = B_{2}.

Now we present a relationship among some of the pseudo-involutions presented in Section 1. The matrices (P, zP), (C, zC), (T, zT), and (Q, zQ) are linked with the g function for one being the A-sequence for the next. For instance using the Catalan numbers as Asequence one can produce the ternary Bell matrix. See [3] for more detail.

If we look at the B-sequences of the pseudo-involutions (P, zP), (C, zC^{3}), (T, zT^{5}) and (Q, zQ^{7}) (see Examples 1 in Table 2, 10 in Table 3, and 18 and 20 in Table 4) we obtain the following matrix

(\begin{matrix}1 & 0 & 0 & 0 & ⋯ \\ 3 & 1 & 0 & 0 & ⋯ \\ 5 & 5 & 1 & 0 & ⋯ \\ 7 & 14 & 7 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

This is a Riordan array (\frac{1+z}{(1−z)^{2}} , \frac{z}{(1−z)^{2}} ). Each row of this array is the B-sequence of a pseudo-involution in this family.

We also have the following results of independent interest.

Lemma 12.

(\begin{matrix}1 \\ −3x & 1 \\ 5x^{2} & −5x & 1 \\ −7x^{3} & 14x^{2} & −7x & 1 \\ 9x^{4} & −30x^{3} & 27x^{2} & −9x & 1 \end{matrix}) · (\begin{matrix}1 + x \\ (1 + x)^{3} \\ (1 + x)^{5} \\ (1 + x)^{7} \end{matrix}) = (\begin{matrix}1 + x \\ 1 + x^{3} \\ 1 + x^{5} \\ 1 + x^{7} \end{matrix})

Proof. We apply the Fundamental Theorem of Riordan Arrays which states that if

(g(z), f(z)) [α_{0} ; α_{1} ; α_{2} ; ⋮] = [β_{0} ; β_{1} ; β_{2} ; ⋮]

then β(z) = g(z)α(f(z)), where α(z) = ∑ α_{n}z^{n} and β(z) = ∑ β_{n}z^{n}. We have

g(z) = \frac{1 − xz}{(1 + xz)^{2}} ,
f(z) = \frac{z}{(1 + xz)^{2}} , and
α(z) = \frac{1 + x}{1 − (1 + x)^{2}z} .

Therefore

g(z)α(f(z)) = \frac{1 − xz}{(1 + xz)^{2}} · \frac{1 + x}{1 − (1 + x)^{2}f(z)}

= \frac{1 − xz}{(1 + xz)^{2}} · \frac{1 + x}{1 − (1 + x)^{2} \frac{z}{(1+xz)^{2}}}

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

= \frac{1 + x − xz − x^{2}z}{1 + 2xz + x^{2}z^{2} − z − 2xz − x^{2}z}

= \frac{1 − x^{2}z + x − xz}{1 + x^{2}z^{2} − z − x^{2}z}

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

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

An analogous result for the even powers of 1 + x is as follows. Lemma 13.

(\begin{matrix}1 \\ −2x & 1 \\ 2x^{2} & −4x & 1 \\ −2x^{3} & 9x^{2} & −6x & 1 \\ 2x^{4} & −16x^{3} & 20x^{2} & −8x & 1 \end{matrix}) · (\begin{matrix}1 \\ (1 + x)^{2} \\ (1 + x)^{4} \\ (1 + x)^{6} \end{matrix}) = (\begin{matrix}1 \\ 1 + x^{2} \\ 1 + x^{4} \\ 1 + x^{6} \end{matrix})

That is (\frac{1−xz}{1+xz}, \frac{z}{(1+xz)^{2}} ) · \frac{1}{1−(1+x)^{2}z} = \frac{1}{1−z} + \frac{x^{2}z}{1−x^{2}z}.

4 Applications

In this section we present an interpretation for each entry in the first column of the Bell array (\frac{f(z)}{z}, f(z)) with a given B-sequence b_{0}, b_{1}, b_{2}, . . .. For that we define a PI (pseudo-involution) tree. A PI tree is built from subtrees which if nontrivial, consist of a root and 2n + 1 edges, n + 1 of which are active and n of which are sterile with no descendants. The weight b_{i} is assigned to the building block subtree with 2i + 1 edges. We draw these where the sterile edges are drawn as dotted lines and alternate with the active edges. Some examples are as follows.

\{  ^{\begin{matrix}× \\ 1, \end{matrix}} \begin{matrix}· \\ ∘ \\ b_{0}z, \end{matrix}^{· ∘ ∘ •b_{1}z^{3},}^{·b_{2}z^{5}, ∘ • ∘ • ∘⋯}  \}

For instance if b_{0} = 1, b_{1} = 2, and b_{k} = 0, k ≥ 2, we have the building blocks in which the term 2z^{3} could represent one red and one green block.

\{  \}  ^{\begin{matrix}× \\ 1, \end{matrix}} \begin{matrix}· \\ ∘ \\ z, \end{matrix}^{· ∘ ∘ •2z^{3}}

This refers to Example 6 in Table 3. In this case we have the following PI trees with edges n ≥ 0.

Trees  \begin{matrix}× \\ · \\ · \\ ∘ \\ × \\ • \\ ∘ \\ ∘ \end{matrix} ·_{∘}^{×} ×_{∘} × \begin{matrix}× \\ · \\ · \\ · \\ ∘ \\ × \\ • \\ · \\ ∘ \\ ∘ \\ × \\ • \\ · \\ ∘ \\ ∘ \\ × \\ · \\ ∘ \\ ∘ \\ • \end{matrix}
No. of trees 1 1 1 1 + 2 = 3  1 + 2 · 3 = 7
No. of edges 0 1 2  3  4

Table 5: PI trees corresponding to the B-sequence 1, 2, 0, 0, …

For n = 5 edges we get 7 trees with root degree 1 and 6 trees with root degree 3. So the total number of such trees with 5 edges is 13.

This sequence also counts Dyck paths where all maximal U and D runs are of length 1 or 3 and each U^{3} run has weight 2. We illustrate this with the following table.

In the following theorem we present an interpretation for each entry in the first column of the pseudo-involution Bell array (\frac{f(z)}{z}, f(z)) with B-sequence b_{0}, b_{1}, b_{2}, . . .. Another interpretation in terms Dyck paths can also be proved in the similar fashion.

Dyck paths  \begin{matrix}· \\ · \\ · \end{matrix}  \begin{matrix}· \\ · \\ · \\ · \\ · \end{matrix}  \begin{matrix}· \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \end{matrix} ×  \begin{matrix}· \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \\ · \end{matrix}
No. of Dyck paths 1  1  1  1 + 2 = 3 1 + 2 · 3 = 7
No. of UD’s  0  1  2  3  4

Table 6: Dyck paths corresponding to the B-sequence 1, 2, 0, 0, …

Theorem 14. Let (\frac{f(z)}{z}, f(z)) be a pseudo involution Bell array with B-sequence (b_{0}, b_{1}, …), where each b_{i} is a nonnegative integer. Then the function \frac{f(z)}{z} counts the number of PI trees with the following building blocks.

\{  ^{\begin{matrix}× \\ 1, \end{matrix}} \begin{matrix}· \\ ∘ \\ b_{0}z, \end{matrix}^{· ∘ ∘ •b_{1}z^{3},} \begin{matrix}b_{2}z^{5}, \\ ∘ \\ · \\ • \\ ∘ \\ • \\ ∘ \\ ⋯ \end{matrix}  \}

Proof. Since (\frac{f(z)}{z}, f(z)) is a pseudo involution with B-sequence b_{0}, b_{1}, b_{2}, …, we can write

f(z) = z + zf(z)B(zf(z)).

That is

\frac{f(z)}{z} = 1 + f(z)B(zf(z)).

Let \frac{f(z)}{z} = g(z). Then g(z) = 1 + zg(z)B(z^{2}g(z)). In expanded form g(z) can be written as

g(z) = 1 + zg(z)(b_{0} + b_{1}z^{2}g(z) + b_{2}z^{4}(g(z))^{2} + ⋯)
= 1 + b_{0}zg(z) + b_{1}z^{3}(g(z))^{2} + b_{2}z^{5}(g(z))^{3} + ⋯

If the tree is nontrivial the root degree is 2n + 1 with n + 1 active nodes and the attached weight is b_{n}. This gives the term b_{n}z^{2n+1}(g(z))^{n+1} and summing yields the generating function g(z).

\begin{matrix}× \\ g \\ ⟷ \end{matrix}  ^{\begin{matrix}× \\ 1, \end{matrix}} \begin{matrix}· \\ · \\ g \\ b_{0}zg(z), \end{matrix}^{·g··gb_{1}z^{3}(g(z))^{2},} \begin{matrix}b_{2}z^{5}(g(z))^{3}, \\ g \\ · \\ · \\ g \\ · \\ g \\ · \\ ⋯ \end{matrix}

This shows that the generating function g(z) = \frac{f(z)}{z} counts the PI trees with the given building blocks.

5 Acknowledgments

We thank the referee for thoughtful and helpful comments.

References

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

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

[3] G.-S. Cheon, S.-T. Jin, and L. W. Shapiro, An equivalence relation for formal power series, Linear Algebra Appl. 491 (2016), 123–137.

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

[5] G.-S. Cheon, H. Kim, and L. W. Shapiro, An algebraic structure for Faber polynomials, Linear Algebra Appl. 433 (2010), 1170–1179.

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

[7] T.-X. He and L. Shapiro, Row sums and alternating sums of Riordan arrays, Linear Algebra Appl. 507 (2016), 77–95.

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

[9] V. Hoggatt and M. Bicknell-Johnson, Sequences of matrix inverses from Pascal, Catalan, and related convolution arrays, Fibonacci Quart. 14 (1976), 224–232.

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

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

[12] RiMA-SKKU, Riordan Generators, http://riordan.skku.edu/Lab.

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

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

[15] R. P. Stanley, Enumerative Combinatorics, Vol. I, 2nd edition, Cambridge University Press, 2011.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: pseudo-involution, Riordan group, B-sequence, PI tree.

(Concerned with sequences \underline{A000245}, \underline{A004148}, \underline{A023431}, \underline{A091561}, \underline{A091565}, \underline{A102893}, \underline{A105633}, \underline{A187256}, and \underline{A233658}.)

Received November 11 2016; revised versions received February 2 2017; February 12 2017. Published in Journal of Integer Sequences, February 18 2017.

Return to Journal of Integer Sequences home page.