\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage{tikz}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{question}[theorem]{Question}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Constructing Pseudo-Involutions  \\
\vskip .1in
in the Riordan Group
}
\vskip 1cm
\large
Dev Phulara\\
National Security Agency\\
Fort Meade, MD 20755\\
USA\\
\href{mailto:drphula@nsa.gov}{\tt drphula@nsa.gov} \\
\href{mailto:phulara@comcast.net}{\tt phulara@comcast.net} \\
\ \\
Louis Shapiro\\
Howard University\\ 
Washington, DC 20059\\
USA\\
\href{mailto:lshapiro@howard.edu}{\tt lshapiro@howard.edu}\\
\end{center}

\vskip .2 in

\begin{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 $\big(g(z),f(z)\big)$ is a pseudo-involution. As a 
combinatorial application, we find the interpretation of each entry in the Bell array $\big(g(z),f(z)\big)$ with a 
given $B$-sequence.
\end{abstract}

\section{Introduction}\label{sec:introduction}

A Riordan array originally introduced by Shapiro et al.\ \cite{SGWW} is defined in terms of generating functions 
of its columns. Let $g(z)=g_0+g_1z+g_2z^2+\cdots$, $g_0\neq 0$ and $f(z)= f_1z+f_2z^2+f_3z^3+\cdots$, $f_1\neq 0$ 
be two formal power series. 
The Riordan array generated by $g(z)$ and $f(z)$ is an infinite lower triangular array $D$ whose $k$th column has the 
generating function $g(z)\big(f(z)\big)^k$ for all $k\geq 0$. We denote $D$ by $\big(g(z),f(z)\big)$. In other words 
$D=(d_{n,k})_{n,k\geq 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)\big(f(z)\big)^k$. 

The set $\mathcal R$ of all Riordan arrays forms a group under the matrix multiplication operation. In terms of 
generating functions, the product of two arrays $\big(g(z),f(z)\big)$ and $\big(\alpha(z),\beta(z)\big)$ can be written as
\[
\big(g(z),f(z)\big)\cdot \big(\alpha(z),\beta(z)\big) = \big(g(z)\alpha(f(z)),\beta(f(z))\big).
\]

The usual identity matrix $(1,z)$ serves as the group identity and for any $\big(g(z),f(z)\big)\in\mathcal R$, 
$\big(\frac{1}{g(\overline{f}(z))},\overline{f}(z)\big)$ 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.\ 
\cite{MRSV} and Sprugnoli \cite{SP} 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

\begin{theorem}
An array $D=(d_{n,k})_{n,k\geq 0}$ is Riordan if and only if there exist unique sequences 
$A = (a_0, a_1, a_2,\ldots)$ 
and $Z= (z_0, z_1, z_2,\ldots)$ such that
\begin{enumerate}
\item [\rm 1.] $d_{n+1,k+1}=\sum_{i=0}^{\infty}a_id_{n,k+i}$ and
\item [\rm 2.] $d_{n+1,0} = \sum_{i=0}^{\infty}z_id_{n,i}$.
\end{enumerate}
\end{theorem}

The sequences $A$ and $Z$ in this theorem are called the $A$-sequence and $Z$-sequence respectively. See also \cite{HS}. 
See \cite{CKS} for another characterization of Riordan arrays (in terms of Stieltjes transform matrix). 
See also \cite{HSh}.

A nontrivial element $D = \big(g(z),f(z)\big)\in \mathcal 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,\ldots)$ along the diagonal. An element 
$D=\big(g(z),f(z)\big)$ is a pseudo-involution if and only if $DM$ is an involution or equivalently $MD$ is an 
involution or $D^{-1}=MDM$. See \cite{CN, CK, CJS, CJKS, CKS1} 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{center}
\begin{tikzpicture}
\draw (0,0)rectangle(1,1);
\draw (1,0)rectangle(1,1);
\draw (2,0)rectangle(1,1);
\draw (3,0)rectangle(1,1);
\draw (4,0)rectangle(1,1);
\draw (5,0)rectangle(1,1);
\draw (1,-1)rectangle(1,1);
\draw (2,-1)rectangle(1,1);
\draw (1.5,-0.5)circle [x radius = 0.2cm, y radius = 0.2 cm];

\node at (0.5,0.5){\footnotesize{$a_0$}};
\node at (1.5,0.5){\footnotesize{$a_1$}};
\node at (2.5,0.5){\footnotesize{$a_2$}};
\node at (3.5,0.5){\footnotesize{$a_3$}};
\node at (4.5,0.5){\footnotesize{$a_4$}};
\node at (5.5,0.5){\footnotesize{$\cdots$}};
\node at (1.5,-0.5){\footnotesize{$\times$}};
\end{tikzpicture}
\end{center}
However there are many situations where it is useful to expand to an $A$-matrix \cite{MRSV}
\begin{center}
\begin{tikzpicture}
\draw (0,0)rectangle(1,1);
\draw (1,0)rectangle(2,1);
\draw (2,0)rectangle(3,1);
\draw (-1,1)rectangle(0,2);
\draw (0,1)rectangle(1,2);
\draw (1,1)rectangle(2,2);
\draw (2,1)rectangle(3,2);

\draw (-1,2)rectangle(0,3);
\draw (0,2)rectangle(1,3);
\draw (1,2)rectangle(2,3);
\draw (2,2)rectangle(3,3);

\draw (-1,3) -- (-1,4) -- (4,4) --(4,0) -- (3,0);

\node at (-0.5,3.5){\footnotesize{$\cdots$}};
\node at (1.5,3.5){\footnotesize{$\cdots$}};
\node at (3.5,2.5){\footnotesize{$\cdots$}};
\node at (3.5,1.5){\footnotesize{$\cdots$}};
\node at (3.5,0.5){\footnotesize{$\cdots$}};
\node at (0.5,0.5){\footnotesize{$\times$}};
\draw (0.5,0.5)circle [x radius = 0.2cm, y radius = 0.2 cm];

\node at (1.5,0.5){\footnotesize{$a_{0,2}$}};
\node at (2.5,0.5){\footnotesize{$a_{0,3}$}};

\node at (-0.5,1.5){\footnotesize{$a_{1,0}$}};
\node at (0.5,1.5){\footnotesize{$a_{1,1}$}};
\node at (1.5,1.5){\footnotesize{$a_{1,2}$}};
\node at (2.5,1.5){\footnotesize{$a_{1,3}$}};

\node at (-0.5,2.5){\footnotesize{$a_{2,0}$}};
\node at (0.5,2.5){\footnotesize{$a_{2,1}$}};
\node at (1.5,2.5){\footnotesize{$a_{2,2}$}};
\node at (2.5,2.5){\footnotesize{$a_{2,3}$}};
\end{tikzpicture}
\end{center}
A modest example is given by 
\begin{center}
\begin{tikzpicture}
\draw (0,0)rectangle(1,1);
\draw (-1,1)rectangle(0,2);
\draw (0,1)rectangle(1,2);
\draw (1,1)rectangle(2,2);
\draw (0,2)rectangle(1,3);

\node at (0.5,0.5){\footnotesize{$\times$}};
\draw (0.5,0.5)circle [x radius = 0.2cm, y radius = 0.2 cm];
\node at (-0.5,1.5){\footnotesize{$1$}};
\node at (1.5,1.5){\footnotesize{$1$}};
\node at (0.5,2.5){\footnotesize{$1$}};
\end{tikzpicture}
\end{center}
This produces the large Schr\"oder numbers. 

Recently Merlini and Sprugnoli \cite{MS} studied binary words avoiding certain patterns using 
$A$-matrices such as 
\begin{center}
 \begin{tikzpicture}[scale=2]
 \draw[step=.5cm, dashed] (-1,-1) grid (1,2.5); 
 \filldraw[fill = white!20] (-0.5,0) circle (0.17 cm);
 \filldraw[fill = white!20] (-0.5,0.5) circle (0.17 cm);
 \filldraw[fill = white!20] (-0.5,1) circle (0.17 cm);
 \filldraw[fill = white!20] (-0.5,2) circle (0.17 cm);
 \node at (-0.5,0) {\footnotesize{1}};
 \node at (-0.5,0.5) {\footnotesize{$c_2$}};
 \node at (-0.5,1) {\footnotesize{$c_4$}};
 \node at (-0.5,2) {\footnotesize{$c_q$}};
 \filldraw (-0.5,1.4) circle (0.03 cm);
 \filldraw (-0.5,1.6) circle (0.03 cm);
 
 \filldraw[fill = white!20] (0,0) circle (0.19 cm);
 \filldraw[fill = white!20] (0,0.5) circle (0.19 cm);
 \filldraw[fill = white!20] (0,1) circle (0.19 cm);
 \filldraw[fill = white!20] (0,2) circle (0.19 cm);
 \filldraw (0,-0.5) circle (0.07 cm);
 \node at (0,0) {\tiny{$-c_2$}};
 \node at (0,0.5) {\tiny{$-c_4$}};
 \node at (0,1) {\tiny{$-c_6$}};
 \node at (0,2) {\tiny{$-c_{q-2}$}};
 \filldraw (0,1.4) circle (0.03 cm);
 \filldraw (0,1.6) circle (0.03 cm);
 
 \filldraw[fill = white!20] (0.5,-0.5) circle (0.17 cm);
 \filldraw[fill = white!20] (0.5,0) circle (0.17 cm);
 \filldraw[fill = white!20] (0.5,0.5) circle (0.17 cm);
 \filldraw[fill = white!20] (0.5,1) circle (0.17 cm);
 \filldraw[fill = white!20] (0.5,2) circle (0.17 cm);
 \node at (0.5,-0.5) {\footnotesize{$1$}};
 \node at (0.5,0) {\footnotesize{$c_2$}};
 \node at (0.5,0.5) {\footnotesize{$c_4$}};
 \node at (0.5,1) {\footnotesize{$c_6$}};
 \node at (0.5,2) {\footnotesize{$c_{q-2}$}};
 \filldraw (0.5,1.4) circle (0.03 cm);
 \filldraw (0.5,1.6) circle (0.03 cm);
 \end{tikzpicture}
\end{center}

Here is a picture of the $A$-matrix that produces the $B$-sequence.
\begin{center}
\begin{tikzpicture}
\draw (0,0)rectangle(1,1);
\draw (0,1)rectangle(1,2);
\draw (-1,1)rectangle(0,2);
\draw (1,2)rectangle(2,3);
\draw (2,3)rectangle(3,4);
\draw (3,4)rectangle(4,5);

\node at (3.4,4.4){{$\cdot$}};
\node at (3.5,4.5){{$\cdot$}};
\node at (3.6,4.6){{$\cdot$}};

\node at (0.5,0.5){\footnotesize{$\times$}};
\draw (0.5,0.5)circle [x radius = 0.2cm, y radius = 0.2 cm];
\node at (0.5,1.5){\footnotesize{$b_0$}};
\node at (1.5,2.5){\footnotesize{$b_1$}};
\node at (-0.5,1.5){\footnotesize{$1$}};
\node at (2.5,3.5){\footnotesize{$b_2$}};
\end{tikzpicture}
\end{center}
See also \cite{RIMA} for several online software tools for exploring Riordan arrays. 

This paper is organized as follows. In Section~\ref{PI} we present some ways of 
constructing pseudo-involutions. In Section~\ref{Bseq} 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 $A$-sequence of 
a pseudo-involution with a given $B$-sequence. Finally in Section~\ref{Appl} we present combinatorial interpretations 
for all involutions in the Bell subgroup.

\section{(Pseudo)-involutions}\label{PI}

Given a formal power series $g(z)=1+\sum_{n\geq 1}g_nz^n$, we want to find a generating function $f(z)$ such that 
$\big(g(z),f(z)\big)^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\in\mathbb{N}$.

\begin{theorem}\label{th:involution}
Let $g(z)=1+\sum_{n\geq 1}g_nz^n$ be a power series where $g=1+zg^k$, for some $k\in\mathbb{N}$. Then 
$\big(g(z),-z(g(z))^{2k-1}\big)^2=I$.
\end{theorem}

\begin{proof}
Since $g(z)=1+zg^k$, we can write $g$ as
\begin{align*}
g(z) &= \frac{1}{1-zg^{k-1}}\\
	 &=\big(1-zg^{k-1}\big)^{-1}.\\
\end{align*}
So $zg^{k-1} =z(1-zg^{k-1})^{-(k-1)}$. Now set 
\begin{equation}\label{eq:1}
F=F(z)=zg^{k-1}.	 
\end{equation}
Then $F=z(1-F)^{-(k-1)}$. Apply $\overline{F}$ to this equation to get $$z=\overline{F}(1-z)^{-(k-1)}.$$ Then
\begin{equation}\label{eq:2}
\overline{F}=z(1-z)^{k-1}.
\end{equation}
Starting with Eq.~\ref{eq:1}, we get $$F\big(f(z)\big)=f(z)g\big(f(z)\big)^{k-1}=f\cdot 
\big(g(f)\big)^{k-1}=f\big(\frac{1}{g}\big)^{k-1}=\frac{f}{g^{k-1}}.$$
Now apply $\overline{F}$ to get 
\[
f(z)=\overline{F}\big(\frac{f}{g^{k-1}}\big)=\frac{f}{g^{k-1}}\big(1-\frac{f}{g^{k-1}}\big)^{k-1}.
\]
This implies
\begin{align*}
			& g^{k-1}=\big(1-\frac{f}{g^{k-1}}\big)^{k-1}\\
\Rightarrow & g=1-\frac{f}{g^{k-1}}\\
\Rightarrow & f=g^{k-1}-g^k\\
\Rightarrow & f=g^{k-1}(1-g).\\
\end{align*}
But $1-g=-zg^k$ so $f=g^{k-1}(-zg^k)=-zg^{2k-1}$.
\end{proof}

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 {\it Fibonacci Quarterly} \cite{HB}. These occur again in Section~\ref{Bseq} 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{table}[ht]
\begin{center}
\begin{tabular}{|l||l|l|l|}
\hline
$k$ & $g=1+zg^k$ & $f=-zg^{2k-1}$ & $(g,-zg^{2k-1})^2=I$\\
\hline
\hline
$k=1$ & $P=1+zP$ & $f=-zP$ & $(P,-zP)^2=I$\\
\hline
$k=2$ & $C=1+zC^2$ & $f=-zC^3$ & $(C,-zC^3)^2=I$\\
\hline
$k=3$ & $T=1+zT^3$ & $f=-zT^{5}$ & $(T,-zT^{5})^2=I$\\
\hline
$k=4$ & $Q=1+zQ^4$ & $f=-zQ^7$ & $(Q,-zQ^7)^2=I$\\
\hline
\end{tabular}
\caption{Some special cases of Theorem~\ref{th:involution}}
\label{T:involutionstab}
\end{center}
\end{table}

Another interesting relationship among these examples will be presented in Section~\ref{Bseq} after presenting the notion 
of $B$-sequences.

For $g(z)=1+\sum_{n\geq 1}g_nz^n$ and $f(z)=z+\sum_{n\geq 2}f_nz^n$, we know that if $\big(g(z),f(z)\big)$ is 
a pseudo-involution 
then $\big(g(z),-f(z)\big)$ is an involution so $f(-f(-z))=z$. Then we use \cite [Exercise 168, p.\ 134]{RS} to 
specify the even indexed coefficients ($f_2,f_4,\ldots$) arbitrarily which then determine the odd indexed coefficients 
($f_3,f_5,\ldots$) 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 
$\big(f(z)/z,f(z)\big)$ is a pseudo-involution. Moreover it has been established \cite[Thm.\ 2.3]{CK} that if 
$\big(g(z),f(z)\big)$ is an involution, then $g(z)=\pm\exp (\Phi (z,zf(z)))$ for some antisymmetric function $\Phi$. 
However we do not know the answer of the following question.

\begin{question}
Given $f(z)$ such that $f(-f(-z))=z$ or $\overline{f}(z) = -f(-z)$, what are the possibilities 
for $g(z)$ so that $\big(g(z),f(z)\big)$ is an involution, particularly in combinatorial situations{\rm ?} 
\end{question}

Another way to find more involutions and thus pseudo-involutions comes from basic group theory. If $\alpha$ and $\beta$ 
are two noncommuting involutions then $\langle\alpha, \beta\rangle$ is a dihedral group and $(\alpha \beta)^n\beta$ is an involution 
for all integers $n$, where $\alpha\beta$ plays the role of a rotation. In the Riordan group if $M_1$ and $M_2$ are 
noncommuting involutions then $\langle M_1,M_2\rangle$ is a dihedral group.

\begin{proposition}\label{Prop}
Let $D_1$ and $D_2$ be two pseudo-involutions. Then both $(D_1D_2^{-1})^nD_2$ and $D_1(D_1^{-1}D_2)^n$ 
are pseudo-involutions for all integers $n$. 
\end{proposition}

\begin{proof}
Let $H_1 = D_1M$ and $H_2 = D_2M$. Then $H_1$ and $H_2$ are involutions and so for all integer $n$, 
$(H_1 H_2)^nH_2$ is an involution and 
\begin{align*}
(H_1 H_2)^nH_2 &= (D_1MD_2M)^nD_2M\\
			   &= (D_1D_2^{-1})^nD_2M.
\end{align*}

Hence $(D_1D_2^{-1})^nD_2$ is a pseudo-involution. On the other hand if we let $J_1 = MD_1$ and $J_2 = MD_2$, then 
\begin{align*}
J_1 (J_1 J_2)^n &= MD_1(MD_1MD_2)^n\\
				&= MD_1(D_1^{-1}D_2)^n.
\end{align*}

Since $J_1 (J_1 J_2)^n$ is an involution, $D_1(D_1^{-1}D_2)^n$ is also a pseudo-involution.
\end{proof}

The following result was first proved \cite{CJKS} using induction on $n$ but it follows more quickly from the 
proposition we just proved.

\begin{corollary}\label{pi-nth}
Let $D=\big(g(z),f(z)\big)$ be a pseudo involution. Then so is $D^n$, for all $n\in \mathbb{Z}$.
\end{corollary}

\begin{proof}
Let $D_1 = D$ and $D_2 = (1,z)$. Then $D_1$ and $D_2$ are pseudo-involutions and thus Proposition \ref{Prop} applies.
\end{proof}

\section{Relationship with $B$-sequences}\label{Bseq}

Let $A(z)$ be the generating function of the $A$ sequence of a Riordan array $\big(g(z),f(z)\big)$. We can write $f(z)$ in terms 
of $A$ as follows
\begin{displaymath}
f(z) = zA\big(f(z)\big).
\end{displaymath}
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

\begin{lemma}
Let $A(z)$ be the generating function of the $A$-sequence of the pseudo-involution Riordan array $\big(g(z),f(z)\big)$. Then 
\[
A(z) = \frac{-z}{f(-z)} = \frac{z}{-f(-z)}.
\]
\end{lemma}

The following concept was discussed by Cheon et al.\ \cite{CJKS}. There the term ``$\Delta$-sequence" was used instead of $B$-sequence.

\begin{definition}
For a Riordan array $D = (d_{n,k})_{n,k\geq 0}$, a sequence $(b_0, b_1, b_2,\ldots)$ is said to be a {\it $B$-sequence} 
if and only if 
\[
d_{n+1,k} = d_{n,k-1} +\sum_{j\geq 0}b_j\cdot d_{n-j, k+j}.
\]
\end{definition}

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\geq k+j$. That is $2j\leq n-k$.

In the following theorem we link the $A$-sequence with the $B$-sequence. It also follows from a notion of 
$A$-matrix \cite{MRSV}.

\begin{theorem}\label{th:agf}
Let $B(z)= b_0+b_1z+b_2z^2+\cdots =\sum_{k\geq 0}b_kz^k$ be the $B$-sequence of a pseudo involution 
$D=\big(g(z),f(z)\big)$. Then the $A$-sequence of $D$ is given by 
\begin{equation*}\label{eq:af}
A(z) = 1+zB\big(-zf(-z)\big) = 1 + zB\bigg(\frac{z^2}{A(z)}\bigg).
\end{equation*}
\end{theorem}

\begin{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\big(zf(z)\big)=zA\big(f(z)\big)$. So 
$A\big(f(z)\big)=1+f(z)B\big(zf(z)\big)$. Therefore 
$A\big(f(z)\big)=1+f(z)[b_0+b_1zf(z)+b_2z^2(f(z))^2+\cdots ]$. 
Replace $z$ by $\overline {f}(z)$. Then 
\begin{align*}
A(z) &= 1+z\sum_{k\geq 0}b_k\big(z\overline{f}(z)\big)^k\\
	 &= 1+z\sum_{k\geq 0}b_k\big(-zf(-z)\big)^k\\
	 &= 1 + zB\bigg(\frac{z^2}{A(z)}\bigg).
\end{align*}
\end{proof}

\begin{corollary}
If $\big(g(z),f(z)\big)$ is in the Bell subgroup, then
\begin{equation*}\label{agf}
A(z) = 1 +\sum_{k\geq 0}b_kz^{2k+1}(g(-z))^k.
\end{equation*}
\end{corollary}

\begin{proof}
 We have $f(z)=zg(z)$. So $f(-z)=-zg(-z)$. Therefore
\begin{align*}
A(z) = 1+z\sum_{k\geq 0}b_k\big(z^2g(-z)\big)^k = 1+\sum_{k\geq 0}b_kz^{2k+1}\big(g(-z)\big)^k.
\end{align*}
\end{proof}

In Corollary~\ref{pi-nth}, 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,

\begin{question}
Let $D = \big(g(z),f(z)\big)$ be a pseudo-involution with the $B$-sequence $b_0,b_1,b_2,\ldots$. what is the 
$B$-sequence for $D^2${\rm ?}
\end{question}

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~\ref{th:nonbell} to construct many examples which are not in the Bell 
subgroup. Six out of these 24 examples can also be found \cite{CJKS}. We cluster them in families of $B$-sequences. 
One can use Theorem~\ref{th:agf} to compute the 
$A$-sequence in each case. In these examples $m$, $C$, $T$, and $r$ represent the Motzkin, Catalan, ternary, and 
large Schr\"oder generating functions respectively.

{\bf Geometric $B$-sequences:} One can compute the unique $f(z)$ such that $\big(g(z),f(z)\big)$ is a 
pseudo-involution with the $B$-sequence $b,bk,bk^2,\ldots$ as follows
\begin{displaymath}
f(z) = \begin{cases}
\frac{z}{1-bz	}, & \text{\ if }\ k=0;\\
\frac{1-bz+kz^2-\sqrt{(1-bz+kz^2)^2-4kz^2}}{2kz}, & \text {\ if}\ k\neq 0.
\end{cases}
\end{displaymath}
We include some examples in the following table.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|p{6cm}|p{5cm}|l|}
\hline
 & $g$ & $B$-sequence & Comments \\
\hline
1 & $1,1,1,1,1,1,1,1,\ldots$ & $1,0,0,\ldots$ & Pascal \\
\hline
2 & $1,1,1,2,4,8,17,37,82,185,\ldots$ & $1,1,1,\ldots$ & RNA (\seqnum{A004148}) \\
\hline
3 & $1,2,4,10,28,82,248,770,\ldots$ & $2,2,2,\ldots$ & \seqnum{A187256}\\
\hline
4 & $1,4,16,68,304,1412,6752,\ldots$ & $4,4,4,\ldots$ & $r^2$\\
\hline
\end{tabular}
\caption{Examples with geometric $B$-sequences}
\label{T:geomtab} 
\end{center}
\end{table}

{\bf Linear $B$-sequences:} If the $B$-sequence is $a,b,0,0,0,\ldots$, then the unique $f(z)$ is 
\begin{displaymath}
f(z)=\frac{1-az-\sqrt{(1-az)^2-4bz^3}}{2bz^2}.
\end{displaymath}
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|p{7cm}|p{4cm}|l|}
\hline
 & $g$ & $B$-sequence & Comments \\
\hline
5 & $1,1,1,2,4,7,13,26,52,104,212,\ldots$ & $1,1,0,\ldots$ & \seqnum{A023431}\\
\hline
6 & $1,1,1,3,7,13,29,71,\ldots$ & $1,2,0,\ldots$& \seqnum{A091565} \\
\hline
7 & $1,1,1,4,10,19,49,136,334,850,\ldots$ & $1,3,0,\ldots$ &\\
\hline
8 & $1,2,4,9,22,56,146,388,1048,\ldots$ & $2,1,0,\ldots$ & \seqnum{A091561}\\
\hline
9 & $1,2,4,10,28,80,232,688,2080,\ldots$ & $2,2,0,\ldots$ &\\
\hline
10 & $1,3,9,28,90,297,1001,3432,\ldots$ & $3,1,0,\ldots$ & $C^3\; (\seqnum{A000245})$ \\
\hline
11 & $1,1,1,5,13,25,73,221,565,1553,\ldots$ & $1,4,0,\ldots$ &\\
\hline
12 & $1,4,16,65,268,1120,4738,20264,\ldots$ & $4,1,0,\ldots$ & \\
\hline
\end{tabular}
\caption{Examples with linear $B$-sequences}
\label{T:lintab}
\end{center}
\end{table}

{\bf Others:}
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|p{5cm}|p{5cm}|l|}
\hline
 & $g$ & $B$-sequence & Comments \\
\hline
13 & $1,1,1,2,4,9,21,50,122,\ldots$ & $1,1,2,4,9,21,51,127,\ldots$ & \\
\hline
14 & $1,1,1,2,4,9,21,51,127,\ldots$ & $1,1,2,5,14,42,132,429,\ldots$& $1+zm$ \\
\hline
15 & $1,1,1,2,4,10,28,85,\ldots$ & $1,3,9,28,90,297,1001,\ldots$ & \\
\hline
16 & $1,2,4,9,22,57,154,429,\ldots$ & $2,1,1,1,1,1,\ldots$ & \seqnum{A105633} \\
\hline
17 & $1,4,16,68,304,1409,\ldots$ & $4,4,1,0,0,\ldots$ &\\
\hline
18 & $1,5,25,130,700,3876,\ldots$ & $5,5,1,0,0,\ldots$ & Ternary(\seqnum{A102893})\\
\hline
19 & $1,2,4,12,40,129,424,\ldots$ & $2,4,1,0,0\ldots$ & \\
\hline
20 & $1,7,49,357,2695,\ldots$ & $7,14,7,1,\ldots$ & Quaternary(\seqnum{A233658})\\
\hline
21 & $1,4,16,64,256,1024,\ldots$ & $4,0,0,\ldots$ & $(B,zB^2)$\\
\hline
22 & $1,0,0,2,0,0,5,0,0,14,\ldots$ & $0,1,0,0,\ldots$ & $(C(z^3),zC(z^3))$\\
\hline
23 & $1,0,0,0,0,3,0,0,0,0,12,\ldots$ & $0,0,1,0,0,\ldots$ & $(T(z^5),zT(z^5))$\\
\hline
24 & $1,1,1,2,4,9,21,50,122,\ldots$ & $1,1,2,4,8,\ldots$ & \\
\hline
\end{tabular}
\caption{Examples with other $B$-sequences}
\label{T:othertab}
\end{center}
\end{table}

For each generating function $g(z)$ and for each $B$-sequence, there exists a generating function $f(z)$ 
such that the Riordan array $\big(g(z),f(z)\big)$ is a pseudo-involution. In fact we see from Eq.~\ref{eq:af} 
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 $\big(g(z),f(z)\big)$ is pseudo-involution with same 
$B$-sequence.

\begin{theorem}\label{th:nonbell}
Let $(g(z),f(z))$ be a pseudo-involution Riordan array and let $B(z)=b_0+b_1z+b_2z^2+\cdots$ be the generating 
function of its $B$-sequence. Then $\big((g(z))^n,f(z)\big)$ is also a pseudo-involution with the same $B$-sequence, for all 
$n\in\mathbb{N}$.
\end{theorem}

\begin{proof}
Let $\big(g(z),f(z)\big)$ be a pseudo-involution. Then $$\big((g(z), f(z))(1,-z)\big)^2=(g(z),-f(z))^2=(1,z).$$ That is 
$\big(g(z)g(-f(z)),-f(-f(z))\big) = (1,z)$, so $g(z)g(-f(z))=1$ and $-f(-f(z))=z$. Thus for any $n$,
\begin{align*}
\big(((g(z))^n,f(z))(1,-z)\big)^2 &= \big((g(z))^n, -f(z)\big)^2\\
								  &= \big(g(z)g(-f(z))^n,-f(-f(z))\big)\\
								  &= (1,z).
\end{align*}
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$.
\end{proof}

Now we present a relationship among some of the pseudo-involutions presented in Section~\ref{sec:introduction}. 
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 $A$- sequence one can produce the ternary 
Bell matrix. See \cite{CJS} 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{pmatrix}
1 & 0 & 0 & 0 &\cdots \\
3 & 1 & 0 & 0 &\cdots \\
5 & 5 & 1 & 0 &\cdots \\
7 & 14 & 7 & 1 &\cdots \\
\vdots & \vdots & \vdots & \vdots &\ddots \\
\end{pmatrix}.
\]
This is a Riordan array $\Big(\frac{1+z}{(1-z)^2},\frac{z}{(1-z)^2}\Big)$. 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.
\begin{lemma}
\begin{align*}
\begin{pmatrix}
1 & & & & \\
-3x & 1 & & & \\
5x^2 & -5x & 1 & & \\
-7x^3 & 14x^2 & -7x & 1 & \\
9x^4 & -30x^3 & 27x^2 & -9x & 1 \\
\end{pmatrix}\cdot
\begin{pmatrix}
1+x\\
(1+x)^3\\
(1+x)^5\\
(1+x)^7\\
\end{pmatrix}
&=
\begin{pmatrix}
1+x\\
1+x^3\\
1+x^5\\
1+x^7\\
\end{pmatrix}
\end{align*}

\end{lemma}
\begin{proof}
We apply the Fundamental Theorem of Riordan Arrays which states that if 
\begin{align*}
\big(g(z),f(z)\big)
\begin{bmatrix}
\alpha_0\\
\alpha_1\\
\alpha_2\\
\vdots\\
\end{bmatrix} &= 
\begin{bmatrix}
\beta_0\\
\beta_1\\
\beta_2\\
\vdots\\
\end{bmatrix}
\end{align*}
then $\beta(z) = g(z)\alpha(f(z))$, where $\alpha(z)= \sum\alpha_nz^n$ and 
$\beta(z)=\sum\beta_nz^n$. We have
\begin{align*}
g(z) &=\frac{1-xz}{(1+xz)^2},\\
f(z) &=\frac{z}{(1+xz)^2}, \text{ and}\\
\alpha(z) &=\frac{1+x}{1-(1+x)^2z}.\\
\end{align*}
Therefore
\begin{align*}
g(z)\alpha(f(z)) &=\frac{1-xz}{(1+xz)^2}\cdot\frac{1+x}{1-(1+x)^2f(z)}\\
			&=\frac{1-xz}{(1+xz)^2}\cdot\frac{1+x}{1-(1+x)^2\frac{z}{(1+xz)^2}}\\
			&=\frac{(1-xz)(1+x)}{(1+xz)^2-(1+x)^2z}\\
			&=\frac{1+x-xz-x^2z}{1+2xz+x^2z^2-z-2xz-x^2z}\\
			&=\frac{1-x^2z+x-xz}{1+x^2z^2-z-x^2z}\\
			&=\frac{1-x^2z+x-xz}{(1-z)(1-x^2z)}\\
			&=\frac{1}{1-z}+\frac{x}{1-x^2z}.\\
\end{align*}
\end{proof}
An analogous result for the even powers of $1+x$ is as follows.
\begin{lemma}
\begin{align*}
\begin{pmatrix}
1 & & & & \\
-2x & 1 & & & \\
2x^2 & -4x & 1 & & \\
-2x^3 & 9x^2 & -6x & 1 & \\
2x^4 & -16x^3 & 20x^2 & -8x & 1 \\
\end{pmatrix}\cdot
\begin{pmatrix}
1\\
(1+x)^2\\
(1+x)^4\\
(1+x)^6\\
\end{pmatrix}
&=
\begin{pmatrix}
1\\
1+x^2\\
1+x^4\\
1+x^6\\
\end{pmatrix}
\end{align*}
That is $\big(\frac{1-xz}{1+xz},\frac{z}{(1+xz)^2}\big)\cdot\frac{1}{1-(1+x)^2z}=\frac{1}{1-z}+\frac{x^2z}{1-x^2z}$.
\end{lemma}

\section{Applications}\label{Appl}

In this section we present an interpretation for each entry in the first column of the Bell array 
$\big(\frac{f(z)}{z},f(z)\big)$ with a given 
$B$-sequence $b_0,b_1,b_2,\ldots$. For that we define a {\it PI} ({\it pseudo-involution}) {\it tree}.
A {\it 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{Bmatrix}
\begin{tikzpicture}[scale=0.75]
\node at (-6,-1.8) {\footnotesize{$\times$}};
\fill (-6,-2) circle (0.1pt) node [anchor=north]{\footnotesize {$1,$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-4,0) {\Large {$\cdot$}};
\node at (-4,1.05) {\tiny {$\circ$}};
\draw (-4,0)--(-4,1);
\fill (-4,0) circle (0pt) node [anchor=north]{\footnotesize {$b_0z,$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-2,0) {\Large {$\cdot$}};
\node at (-1.47,1.05) {\tiny {$\circ$}};
\node at (-2.53,1.05) {\tiny {$\circ$}};
\draw (-1.5,1)--(-2,0);
\draw (-2,0)--(-2.5,1);
\draw [thick,dashed] (-2,0)--(-2,1);
\node at (-2,1.05) {\tiny{$\bullet$}};
\fill (-2,0) circle (0pt) node [anchor=north]{\footnotesize {$b_1z^3,$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (0.5,0) {\Large {$\cdot$}};
\fill (0.5,0) circle (0pt) node [anchor=north]{\footnotesize {$b_2z^5,$}};
\draw (0,1)--(0.5,0);
\node at (-0.02,1.05) {\tiny {$\circ$}};
\draw [thick,dashed] (0.5,0)--(0.25,1);
\node at (0.23,1.05) {\tiny {$\bullet$}};
\draw (0.5,1)--(0.5,0);
\node at (0.5,1.05) {\tiny {$\circ$}};
\draw [thick,dashed] (0.5,0)--(0.75,1);
\node at (0.77,1.05) {\tiny {$\bullet$}};
\draw (1,1) --(0.5,0);
\node at (1.02,1.05) {\tiny {$\circ$}};
\node at (2,0.5) {$\cdots$};
\end{tikzpicture}
\end{Bmatrix}
\]

For instance if $b_0=1,\, b_1=2$, and $b_k=0,\, k\geq 2$, we have the building blocks in which 
the term $2z^3$ could represent one red and one green block.
\[
\begin{Bmatrix}
\begin{tikzpicture}[scale=0.75]
\node at (-6,-1.8) {\footnotesize{$\times$}};
\fill (-6,-2) circle (0.1pt) node [anchor=north]{\footnotesize {$1,$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-4,0) {\Large {$\cdot$}};
\node at (-4,1.05) {\tiny{$\circ $}};
\draw (-4,0)--(-4,1);
\fill (-4,0) circle (0pt) node [anchor=north]{\footnotesize {$z,$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-2,0) {\Large {$\cdot$}};
\node at (-1.47,1.05) {\tiny {$\circ$}};
\node at (-2.53,1.05) {\tiny {$\circ$}};
\draw (-1.5,1)--(-2,0);
\draw (-2,0)--(-2.5,1);
\draw [thick,dashed] (-2,0)--(-2,1);
\node at (-2,1.05) {\tiny {$\bullet$}};
\fill (-2,0) circle (0pt) node [anchor=north]{\footnotesize {$2z^3$}};
\end{tikzpicture}
\end{Bmatrix}
\]

This refers to Example~6 in Table~\ref{T:lintab}. In this case we have the following PI trees with edges $n\geq 0$.  

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Trees &
\begin{tikzpicture}[scale=0.75]
\node at (-6,0) {\footnotesize{$\times$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-4,0) {\footnotesize{$\times$}};
\node at (-4,1.05) {\tiny {$\circ$}};
\draw (-4,0)--(-4,1);
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (-2,0) {\footnotesize{$\times$}};
\node at (-2,1) {\Large {$\cdot$}};
\node at (-2,2.05) {\tiny {$\circ$}};
\draw (-2,1)--(-2,0);
\draw (-2,0)--(-2,2);
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (0,0) {\footnotesize{$\times$}};
\node at (0,1) {\Large {$\cdot$}};
\node at (0,2) {\Large {$\cdot$}};
\node at (0,3.05) {\tiny {$\circ$}};
\draw (0,1)--(0,0);
\draw (0,0)--(0,2);
\draw (0,3)--(0,0);

\node at (1,0) {\footnotesize{$\times$}};
\node at (1,1.05) {\tiny {$\bullet$}};
\node at (0.47,1.05) {\tiny {$\circ$}};
\node at (1.53, 1.05) {\tiny{$\circ$}};
\draw [thick, dashed](1,1)--(1,0);
\draw (1,0)--(0.5,1);
\draw (1,0)--(1.5,1);
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\node at (0,0) {\footnotesize{$\times$}};
\node at (0,1) {\Large {$\cdot$}};
\node at (0,2) {\Large {$\cdot$}};
\node at (0,3) {\Large {$\cdot$}};
\node at (0,4.05) {\tiny {$\circ$}};
\draw (0,1)--(0,0);
\draw (0,0)--(0,2);
\draw (0,3)--(0,0);
\draw (0,4)--(0,3);

\node at (1,0) {\footnotesize{$\times$}};
\node at (1,1.05) {\tiny {$\bullet$}};
\node at (0.5,1) {\Large {$\cdot$}};
\node at (1.52, 1.05) {\tiny{$\circ$}};
\node at (0.5, 2.05) {\tiny{$\circ$}};
\draw (0.5,1)--(0.5,2);
\draw [thick, dashed](1,1)--(1,0);
\draw (1,0)--(0.5,1);
\draw (1,0)--(1.5,1);

\node at (2.5,0) {\footnotesize{$\times$}};
\node at (2.5,1.05) {\tiny {$\bullet$}};
\node at (3,1) {\Large {$\cdot$}};
\node at (1.98, 1.05) {\tiny{$\circ$}};
\node at (3, 2.05) {\tiny{$\circ$}};
\draw (3,1)--(3,2);
\draw [thick, dashed](2.5,1)--(2.5,0);
\draw (2.5,0)--(2,1);
\draw (2.5,0)--(3,1);

\node at (4,0) {\footnotesize{$\times$}};
\node at (4,1) {\Large {$\cdot$}};
\node at (4.52,2.05) {\tiny {$\circ$}};
\node at (3.48, 2.05) {\tiny{$\circ$}};
\node at (4, 2.05) {\tiny{$\bullet$}};
\draw (4,1)--(4.5,2);
\draw [thick, dashed](4,1)--(4,2);
\draw (4,0)--(4,1);
\draw (4,1)--(3.5,2);
\end{tikzpicture}\\
\hline
No. of trees & 1 & 1 & 1 & $1+2=3$ & $1+2\cdot 3=7$\\
\hline
No. of edges & 0 & 1 & 2 & 3 & 4\\
\hline
\end{tabular}
\caption{PI trees corresponding to the $B$-sequence $1,2,0,0,\ldots$}
\label{T:PItreestab}
\end{center}
\end{table}
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.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Dyck paths &
\begin{tikzpicture}[scale=0.75]
\node at (-6,0) {\footnotesize{$\times$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\draw (0,0)--(0.25,0.5);
\draw (0.25,0.5)--(0.5,0);

\node at (0,0) {\large{$\cdot$}};
\node at (0.25,0.5) {\large{$\cdot$}};
\node at (0.5,0) {\large{$\cdot$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\draw (0,0)--(0.25,0.5);
\draw (0.25,0.5)--(0.5,0);
\draw (0.5,0)--(0.75,0.5);
\draw (0.75,0.5)--(1,0);

\node at (0,0) {\large{$\cdot$}};
\node at (0.25,0.5) {\large{$\cdot$}};
\node at (0.5,0) {\large{$\cdot$}};
\node at (0.75,0.5) {\large{$\cdot$}};
\node at (1,0) {\large{$\cdot$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\draw (0,1.7)--(0.25,2.2);
\draw (0.25,2.2)--(0.5,1.7);
\draw (0.5,1.7)--(0.75,2.2);
\draw (0.75,2.2)--(1,1.7);
\draw (1,1.7)--(1.25,2.2);
\draw (1.25,2.2)--(1.5,1.7);

\node at (0,1.75) {\large{$\cdot$}};
\node at (0.25,2.2) {\large{$\cdot$}};
\node at (0.5,1.7) {\large{$\cdot$}};
\node at (0.75,2.2) {\large{$\cdot$}};
\node at (1,1.7) {\large{$\cdot$}};
\node at (1.25,2.2) {\large{$\cdot$}};
\node at (1.5,1.7) {\large{$\cdot$}};

\draw [very thick](0,0)--(0.75,1.5);
\draw (0.75,1.5)--(1.5,0);

\node at (0,0) {\Large {$\cdot$}};
\node at (0.25,0.5) {\Large {$\cdot$}};
\node at (0.5,1) {\Large{$\cdot$}};
\node at (0.75,1.5) {\Large {$\cdot$}};
\node at (1,1) {\Large {$\cdot$}};
\node at (1.25,0.5) {\Large{$\cdot$}};
\node at (1.5,0) {\Large {$\cdot$}};
\end{tikzpicture} &
\begin{tikzpicture}[scale=0.75]
\draw (0,2)--(0.25,2.25);
\draw (0.25,2.25)--(0.5,2);
\draw (0.5,2)--(0.75,2.25);
\draw (0.75,2.25)--(1,2);
\draw (1,2)--(1.25,2.25);
\draw (1.25,2.25)--(1.5,2);
\draw (1.5,2)--(1.75,2.25);
\draw (1.75,2.25)--(2,2);

\node at (0,2) {\large{$\cdot$}};
\node at (0.25,2.25) {\large{$\cdot$}};
\node at (0.5,2) {\large{$\cdot$}};
\node at (0.75,2.25) {\large{$\cdot$}};
\node at (1,2) {\large{$\cdot$}};
\node at (1.25,2.25) {\large{$\cdot$}};
\node at (1.5,2) {\large{$\cdot$}};
\node at (1.75,2.25) {\large{$\cdot$}};
\node at (2,2) {\large{$\cdot$}};

\draw [very thick](0,1)--(0.75,1.75);
\draw (0.75,1.75)--(1.5,1);
\draw (1.5,1)--(1.75,1.25);
\draw (1.75,1.25)--(2,1);


\node at (0,1) {\Large {$\cdot$}};
\node at (0.25,1.25) {\Large {$\cdot$}};
\node at (0.5,1.5) {\Large{$\cdot$}};
\node at (0.75,1.75) {\Large {$\cdot$}};
\node at (1,1.5) {\Large {$\cdot$}};
\node at (1.25,1.25) {\Large{$\cdot$}};
\node at (1.5,1) {\Large {$\cdot$}};
\node at (2,1) {\Large{$\cdot$}};
\node at (1.75,1.25) {\Large {$\cdot$}};

\draw [very thick](0,0)--(0.75,0.75);
\draw (0.75,0.75)--(1.5,0);
\draw (0,0)--(-0.25,0.25);
\draw (-0.25,0.25)--(-0.5,0);

\node at (0,0) {\Large {$\cdot$}};
\node at (0.25,0.25) {\Large {$\cdot$}};
\node at (0.5,0.5) {\Large{$\cdot$}};
\node at (0.75,0.75) {\Large {$\cdot$}};
\node at (1,0.5) {\Large {$\cdot$}};
\node at (1.25,0.25) {\Large{$\cdot$}};
\node at (1.5,0) {\Large {$\cdot$}};
\node at (-0.25,0.25) {\Large{$\cdot$}};
\node at (-0.5,0) {\Large {$\cdot$}};

\draw [very thick](0,-1)--(0.75,-0.25);
\draw (0.75,-0.25)--(1,-0.5);
\draw (1,-0.5)--(1.25,-0.25);
\draw (1.25,-0.25)--(2,-1);

\node at (0,-1) {\Large {$\cdot$}};
\node at (0.25,-0.75) {\Large {$\cdot$}};
\node at (0.5,-0.5) {\Large{$\cdot$}};
\node at (0.75,-0.25) {\Large {$\cdot$}};
\node at (1,-0.5) {\Large {$\cdot$}};
\node at (1.25,-0.25) {\Large{$\cdot$}};
\node at (1.5,-0.5) {\Large {$\cdot$}};
\node at (1.75,-0.75) {\Large{$\cdot$}};
\node at (2,-1) {\Large {$\cdot$}};
\end{tikzpicture}\\
\hline
No. of Dyck paths & 1 & 1 & 1 & $1+2=3$ & $1+2\cdot 3=7$\\
\hline
No. of $UD$'s & 0 & 1 & 2 & 3 & 4 \\
\hline
\end{tabular}
\caption{Dyck paths corresponding to the $B$-sequence $1,2,0,0,\ldots$}
\label{T:Dyckpathtab}
\end{center}
\end{table}

In the following theorem we present an interpretation for each entry in the first column of the pseudo-involution 
Bell array $\big(\frac{f(z)}{z},f(z)\big)$ with $B$-sequence $b_0,b_1,b_2,\ldots$. Another interpretation in terms 
Dyck paths can also be proved in the similar fashion.
\begin{theorem}
Let $\big(\frac{f(z)}{z},f(z)\big)$ be a pseudo involution Bell array with $B$-sequence $(b_0,b_1,\ldots)$, 
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{Bmatrix}
\begin{tikzpicture}[scale=0.75]
\node at (-6,0.2) {\footnotesize {$\times$}};
\fill (-6,0) circle (0.1pt) node [anchor=north]{\footnotesize {$1,$}};
\end{tikzpicture} &
\begin{tikzpicture}
\node at (-4,0) {\Large {$\cdot$}};
\draw (-4,0)--(-4,1);
\node at (-4,1.05) {\tiny {$\circ$}};
\fill (-4,0) circle (0pt) node [anchor=north]{\footnotesize {$b_0z,$}};
\end{tikzpicture} &
\begin{tikzpicture}
\node at (-2,0) {\Large {$\cdot$}};
\draw (-1.5,1)--(-2,0);
\node at (-1.48,1.05) {\tiny {$\circ$}};
\draw (-2,0)--(-2.5,1);
\node at (-2.52,1.05) {\tiny {$\circ$}};
\draw [thick,dashed] (-2,0)--(-2,1);
\node at (-2,1.05) {\tiny {$\bullet$}};
\fill (-2,0) circle (0pt) node [anchor=north]{\footnotesize {$b_1z^3,$}};
\end{tikzpicture}&
\begin{tikzpicture}
\fill (0.5,0) circle (0pt) node [anchor=north]{\footnotesize {$b_2z^5,$}};
\draw (0,1)--(0.5,0);
\node at (0,1.05) {\tiny {$\circ$}};
\node at (0.5,0) {\Large {$\cdot$}};
\draw [thick,dashed] (0.5,0)--(0.25,1);
\node at (0.23,1.05) {\tiny {$\bullet$}};
\draw (0.5,1)--(0.5,0);
\node at (0.5,1.05) {\tiny {$\circ$}};
\draw [thick,dashed] (0.5,0)--(0.75,1);
\node at (0.77,1.05) {\tiny {$\bullet$}};
\draw (1,1) --(0.5,0);
\node at (1.02,1.05) {\tiny {$\circ$}};
\node at (2,0.5) {$\cdots$};
\end{tikzpicture}
\end{Bmatrix}
$$
\end{theorem}

\begin{proof}
Since $\big(\frac{f(z)}{z},f(z)\big)$ is a pseudo involution with $B$-sequence $b_0,b_1,b_2,\ldots$, 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^2g(z))$. In expanded form $g(z)$ can be written as 
\begin{align*}
g(z) &= 1 + zg(z)(b_0+b_1z^2g(z)+b_2z^4(g(z))^2+\cdots )\\
	 &= 1 + b_0zg(z)+b_1z^3(g(z))^2+b_2z^5(g(z))^3+\cdots
\end{align*}

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_nz^{2n+1}\big(g(z)\big)^{n+1}$ and summing yields the generating function $g(z)$.

\begin{center}
\begin{tabular}{cccccc}
\begin{tikzpicture}[scale=0.75]
\node at (-9,0.25) {\footnotesize{$\times$}};
\fill (-9,0.2) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (-9,1.75) circle [x radius=0.5 cm, y radius=1.5 cm];
\fill (-7,1.75) circle (0pt) node [anchor=north]{\footnotesize {$\longleftrightarrow$}};
\end{tikzpicture}&
\begin{tikzpicture}
\node at (-6,0.2) {\footnotesize{$\times$}};
\fill (-6,0) circle (0.1pt) node [anchor=north]{\footnotesize {$1,$}};
\end{tikzpicture}&
\begin{tikzpicture}
\node at (-4,0) {\Large {$\cdot$}};
\draw (-4,0)--(-4,1);
\node at (-4,1) {\Large {$\cdot$}};
\fill (-4,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (-4,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\fill (-4,0) circle (0pt) node [anchor=north]{\footnotesize {$b_0zg(z),$}};
\end{tikzpicture}&
\begin{tikzpicture}
\node at (-2,0) {\Large {$\cdot$}};
\draw (-1.5,1)--(-2,0);
\fill (-1.5,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (-1.5,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\node at (-1.5,1) {\Large {$\cdot$}};
\draw (-2,0)--(-2.5,1);
\node at (-2.5,1) {\Large {$\cdot$}};
\fill (-2.5,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (-2.5,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\draw [thick,dashed] (-2,0)--(-2,1);
\fill (-2,0) circle (0pt) node [anchor=north]{\footnotesize {$b_1z^3(g(z))^2,$}};
\end{tikzpicture}&
\begin{tikzpicture}
\fill (0.5,0) circle (0pt) node [anchor=north]{\footnotesize {$b_2z^5(g(z))^3,$}};
\draw (0,1)--(0.5,0);
\fill (0,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (0,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\node at (0,1) {\Large {$\cdot$}};
\node at (0.5,0) {\Large {$\cdot$}};
\draw [thick,dashed] (0.5,0)--(0.25,1);
\draw (0.5,1)--(0.5,0);
\fill (0.5,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (0.5,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\node at (0.5,1) {\Large {$\cdot$}};
\draw [thick,dashed] (0.5,0)--(0.75,1);
\draw (1,1) --(0.5,0);
\fill (1,1) circle (0pt) node [anchor=south]{\footnotesize {$g$}};
\draw (1,1.75) circle [x radius=0.2 cm, y radius=0.75 cm];
\node at (1,1) {\Large {$\cdot$}};
\node at (2,0.5) {$\cdots$};
\end{tikzpicture}
\end{tabular}
\end{center}
This shows that the generating function $g(z)=\frac{f(z)}{z}$ counts the PI trees with the given building blocks.
\end{proof}

\section{Acknowledgments}
We thank the referee for thoughtful and helpful comments.

\begin{thebibliography}{10}
\bibitem{CN} N. T. Cameron and A. Nkwanta, On some (pseudo) involutions in the Riordan group, 
{\it J. Integer Sequences} {\bf 8} (2005), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html}{Article 06.2.3}.

\bibitem{CK} G.-S. Cheon and H. Kim, Simple proofs of open problems about the structure 
of involutions in the Riordan group, {\it Linear Algebra Appl.} {\bf 428} (2008), 930--940.

\bibitem{CJS} G.-S. Cheon, S.-T. Jin, and L. W. Shapiro, An equivalence relation for formal power series, 
{\it Linear Algebra Appl.} {\bf 491} (2016), 123--137.

\bibitem{CJKS} G.-S. Cheon, S.-T. Jin, H. Kim, and L. W. Shapiro, Riordan group involutions and the $\Delta$-sequence, 
{\it Discrete Appl. Math.} {\bf 157} (2009), 1696--1701.

\bibitem{CKS1} G.-S. Cheon, H. Kim, and L. W. Shapiro, An algebraic structure for Faber polynomials, 
{\it Linear Algebra Appl.} {\bf 433} (2010), 1170--1179.

\bibitem{CKS} G.-S. Cheon, H. Kim, and L. W. Shapiro, Riordan group involutions, 
{\it Linear Algebra Appl.} {\bf 428} (2007), 941--952.

\bibitem{HSh} T.-X. He and L. Shapiro, Row sums and alternating sums of Riordan arrays, 
{\it Linear Algebra Appl. } {\bf 507} (2016), 77--95.

\bibitem{HS} T.-X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, 
{\it Discrete Math.} {\bf 309} (2009), 3962--3974.

\bibitem{HB} V.\ Hoggatt and M.\ Bicknell-Johnson, Sequences of matrix inverses from Pascal, 
Catalan, and related convolution arrays, {\it Fibonacci Quart.} {\bf 14} (1976), 224--232.

\bibitem{MS} D. Merlini and R. Sprugnoli, Algebraic aspects of some Riordan arrays related to binary words
avoiding a pattern, {\it Theoret. Comput. Sci.} {\bf 412} (2011), 2988--3001.

\bibitem{MRSV} D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative 
characterizations of Riordan arrays, {\it Canad. J. Math.} {\bf 49} (1997), 301--320.

\bibitem{RIMA} RiMA-SKKU, Riordan Generators, \url{http://riordan.skku.edu/Lab}.

\bibitem{SGWW} L. W. Shapiro, S. Getu, W.-J. Woan, and L. Woodson, The Riordan group, 
{\it Discrete Appl. Math.} {\bf 34} (1991), 229--239.

\bibitem{SP} R. Sprugnoli, Riordan arrays and combinatorial sums, 
{\it Discrete Math.} {\bf 132} (1994), 267--290.

\bibitem{RS} R. P. Stanley,
{\it Enumerative Combinatorics}, Vol.\ I, 2nd edition, 
Cambridge University Press, 2011.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15.

\noindent \emph{Keywords: } pseudo-involution, Riordan group, $B$-sequence, PI tree.

\bigskip
\hrule
\bigskip


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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 11 2016;
revised versions received  February 2 2017; February 12 2017.
Published in {\it Journal of Integer Sequences}, February 18 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


.
