\documentclass[12pt,reqno]{article}

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

\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{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf A Catalan Transform and Related \\
\vskip .1in
Transformations on Integer Sequences}
\vskip 1cm
\large
Paul Barry\\
School of Science\\
Waterford Institute of Technology\\
Ireland\\
\href{mailto:pbarry@wit.ie}{\tt pbarry@wit.ie} \\
\end{center}
\vskip .2 in

\begin{abstract} We introduce and study an invertible transformation on integer
sequences related to the Catalan numbers. Transformation pairs are
identified among classical sequences. A closely related
transformation which we call the generalized Ballot transform is also studied,
along with associated transformations. Results
concerning the Fibonacci, Jacobsthal and Pell numbers are derived. Finally, we
derive results about combined transformations.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 


%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%
%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{xca}[theorem]{Exercise}

%\begin{document}

\section{Introduction} In this note, we report on a transformation of integer sequences that might
reasonably be called the Catalan transformation. It is easy to describe both by formula (in relation to the general term of a sequence) and in terms of its action on the
ordinary generating function of a sequence. It and its inverse can also be described succinctly in terms of the Riordan group. 

Many classical ``core'' sequences can be paired through this transformation. It is also linked to several other known transformations, most notably the binomial transformation.
Unless otherwise stated, the integer sequences we shall study will be indexed by $\mathbf{N}$, the nonnegative integers. Thus the Catalan numbers, with general term C$(n)$, are described by
\begin{displaymath}\mathrm{C}(n)=\frac{1}{n+1}{{2n}\choose{n}}\end{displaymath} with ordinary generating function given by
\begin{displaymath}\mathrm{c}(x)=\frac{1-\sqrt{1-4x}}{2x}.\end{displaymath}

In the following, all sequences $a_n$ will have offset $0$, that is, they begin $a_0, a_1, a_2,\ldots$.
We use the notation $1^n$ to denote the all $1's$ sequence $1,1,1,\ldots$ with ordinary generating function $1/(1-x)$ and $0^n$ to
denote the sequence $1,0,0,0,\ldots$ with ordinary generating function 1. This
is Sloane's sequence \seqnum{A000007}.
We have $0^n=\delta_{n,0}={{0}\choose{n}}$ as an integer sequence.  This notation allows us to regard $\ldots(-2)^n,(-1)^n,0^n,1^n,2^n,\ldots$ as a sequence of successive binomial transforms; see the next section.  

In order to characterize the effect of the so-called Catalan transformation, we shall look at its effect on some common sequences, including the Fibonacci and Jacobsthal numbers.
The Fibonacci numbers \cite{Fib} are amongst the most studied of mathematical objects.
They are easy to define, and are known to have a rich set of
properties. Closely associated to the Fibonacci numbers are the Jacobsthal numbers \cite{Jac}. In a sense that will be
made exact below, they represent the next element after the
Fibonacci numbers in a one-parameter
family of linear recurrences.  These and many of the integer
sequences that will be encountered in this note are to be found in The On-Line
Encylopedia of Integer Sequences \cite{SL1}, \cite{SL2}. Sequences in this database will be referred to by their Annnnnn number. For instance, the Catalan numbers are \seqnum{A000108}.

The Fibonacci numbers F$(n)$ \seqnum{A000045} are the
solutions of the
recurrence\begin{equation}a_{n}=a_{n-1}+a_{n-2},\textrm{
}a_{0}=0,\textrm{ }a_{1}=1\end{equation} with
\begin{equation}\textrm{F}(n):0, 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, 144,\ldots\end{equation} The Jacobstahl numbers J$(n)$ \seqnum{A001045} are
the solutions of the recurrence
\begin{equation}a_{n}=a_{n-1}+2a_{n-2},\textrm{ }a_{0}=0,\textrm{
}a_{1}=1\end{equation} with \begin{equation}\textrm{J}(n):0, 1, 1,
3, 5, 11, 21, 43, 85, 171, 341, 683, 1365,\ldots\end{equation}
\begin{equation}\textrm{J}(n)=\frac{2^n}{3}-\frac{(-1)^n}{3}\end{equation}
When we change the initial conditions to $a_{0}=1,\textrm{
}a_{1}=0$, we get a sequence which we will denote by J$_{1}(n)$ \seqnum{A078008},
given by
\begin{equation}\mathrm{J}_{1}(n): 1,0,2,2,6,10,22,42,86,170,342\ldots\end{equation}\begin{equation}\label{eqJ1}\mathrm{J}_{1}(n)=
\frac{2^n}{3}+\frac{2(-1)^n}{3}\end{equation} We see that
\begin{equation}2^n=2\mathrm{J}(n)+\mathrm{J}_{1}(n)\end{equation}
The Jacobsthal numbers are the case
$k=2$ for the one-parameter family of recurrences
\begin{equation}\label{recJac} a_{n}=a_{n-1}+ka_{n-2},\textrm{ }a_{0}=0,\textrm{
}a_{1}=1\end{equation} where the Fibonacci numbers correspond to the
case $k=1$.
The Pell numbers Pell$(n)$ \seqnum{A000129} are the solutions of the recurrence \begin{equation}a_{n}=2a_{n-1}+a_{n-2},\textrm{
}a_{0}=0,\textrm{ }a_{1}=1\end{equation} with
\begin{equation}\textrm{Pell}(n):0, 1, 2, 5, 12, 29, 70, 169,\ldots\end{equation}
The Pell numbers are the case $k=2$ of the one-parameter family of recurrences
\begin{equation}\label{recPell} a_{n}=ka_{n-1}+a_{n-2},\textrm{ }a_{0}=0,\textrm{
}a_{1}=1\end{equation} where again the Fibonacci numbers correspond to the
case $k=1$.

\section{Transformations and the Riordan Group} We shall introduce transformations that operate on integer sequences.
An example of such a transformation that is widely used in the study
of integer sequences is the so-called binomial transform \cite{Bin}, which associates
to the sequence with general term $a_n$ the sequence with general
term $b_n$ where
\begin{equation}b_n=\sum_{k=0}^n{{n}\choose{k}}a_k\end{equation} If we consider the sequence to be the vector
$(a_0,a_1,\ldots)$
 then we obtain the binomial transform of the sequence by multiplying this (infinite) vector with the lower-triangle matrix $\mathbf{Bin}$ whose $(i,j)$-th element is equal to
${{i}\choose{j}}$:
\begin{displaymath}\mathbf{Bin}=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 2 & 1
& 0 & 0 & 0 & \ldots \\ 1 & 3 & 3 & 1 & 0 & 0 & \ldots \\ 1 & 4 &
6 & 4 & 1 & 0 & \ldots
\\1 & 5 & 10 & 10 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} Note that we index matrices starting at $(0,0)$. This
transformation is invertible, with
\begin{equation}a_n=\sum_{k=0}^n{{n}\choose{k}}
(-1)^{n-k}b_k\end{equation} We note that $\mathbf{Bin}$
corresponds to Pascal's triangle. Its row sums are $2^n$, while
its diagonal sums are the Fibonacci numbers F$(n+1)$.

If $\cal{A}$$(x)$ is the ordinary generating
function of the sequence $a_n$, then the generating function of
the transformed sequence $b_n$ is $(1/(1-x))\cal{A}$$(x/(1-x))$.

The \emph{Riordan group} is a set of infinite lower-triangular matrices,
where each matrix is defined by a pair of generating functions
$g(x)=1+g_1x+g_2x^2+\ldots$ and $f(x)=f_1x+f_2x^2+\ldots$ where
$f_1\ne 0$ \cite{SGW}. The associated matrix is the matrix whose $k$-th
column is generated by $g(x)f(x)^k$ (the first column being
indexed by 0). The matrix corresponding to the pair $g, f$ is
denoted by $(g, f)$ or $\cal{R}$$(g,f)$. The group law is then
given by
\begin{displaymath} (g, f)*(h, l)=(g(h\circ f), l\circ
f)\end{displaymath} The identity for this law is $I=(1,x)$ and the
inverse of $(g, f)$ is $(g, f)^{-1}=(1/(g\circ \bar{f}), \bar{f})$
where $\bar{f}$ is the compositional inverse of $f$.

If $\mathbf{M}$ is the matrix $(g,f)$, and $a=\{a_n\}$ is
an integer sequence with ordinary generating function $\cal{A}$
$(x)$, then the sequence $\mathbf{M}a$ has ordinary generating
function $g(x)$$\cal{A}$$(f(x))$.

For example,
the Binomial matrix $\mathbf{Bin}$ is the element
$(\frac{1}{1-x},\frac{x}{1-x})$ of the Riordan group, while its
inverse is the element $(\frac{1}{1+x},\frac{x}{1+x})$. It can be
shown more generally \cite{Sp} that the matrix with general term
${{n+ak}\choose{m+bk}}$ is the element
$(x^m/(1-x)^{m+1},x^{b-a}/(1-x)^b)$ of the Riordan group. This
result will be used in a later section,
 along with characterizations of terms of the form ${{2n+ak}\choose{n+bk}}$
 [11]. As an example, we cite the result that the lower triangular
 matrix with general term ${{2n}\choose{n-k}}={{2n}\choose{n+k}}$
 is given by the Riordan array
 $(\frac{1}{\sqrt{1-4x}},\frac{1-2x-\sqrt{1-4x}}{2x})=(\frac{1}{\sqrt{1-4x}},xc(x)^2)$
 where $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function
 of the Catalan numbers.
 
 A lower-triangular matrix that is related to
 $(\frac{1}{\sqrt{1-4x}},xc(x)^2)$ is the matrix
 $(\frac{1}{\sqrt{1-4x}},x^2c(x)^2)$. This is no longer a
 \emph{proper} Riordan array: it is a \emph{stretched} Riordan array, as
 described in [1]. The row sums of this array are then the
 diagonal sums of $(\frac{1}{\sqrt{1-4x}},xc(x)^2)$, and hence
 have expression $\sum_{k=0}^{\lfloor n/2
 \rfloor}{{2(n-k)}\choose{n}}$.

\section{The Catalan transform}
We initially define the Catalan transformation by its action on ordinary generating functions.
For this, we let $\mathcal{A}(x)$ be the generating function of a sequence. The \emph{Catalan transform} of that sequence is defined
to be the sequence whose generating function is $\mathcal{A}(x$c$(x))$. The Catalan transform thus corresponds to the element of the Riordan group given by
$(1,x\textrm{c}(x))$. That this transformation is invertible is demonstrated by
\begin{proposition}The inverse of the Catalan transformation is given by
\begin{displaymath} \mathcal{A}(x)\to \mathcal{A}(x(1-x))\end{displaymath}
\end{proposition}

\begin{proof} 
We prove a more general result. Consider the
Riordan matrix $(1, x(1-kx))$. Let $(g^{*}, \bar{f})$ denote its
Riordan inverse. We then have \begin{displaymath}
(g^{*},\bar{f})(1,x(1-kx))=(1,x)\end{displaymath} Hence
\begin{displaymath} \bar{f}(1-k\bar{f})=x\Rightarrow
k\bar{f}^2-\bar{f}+x=0\Rightarrow
\bar{f}=\frac{1-\sqrt{1-4kx}}{2k}\end{displaymath}

Since $g=1$, $g^{*}=1/(g\circ \bar{f})=1$ also, and thus
\begin{displaymath}(1,x(1-kx))^{-1}=(1,\frac{1-\sqrt{1-4kx}}{2k})\end{displaymath}
Setting $k=1$, we obtain \begin{displaymath}
(1,x(1-x))^{-1}=(1,x\mathrm{c}(x))\Rightarrow
(1,x\mathrm{c}(x))^{-1}=(1,x(1-x))\end{displaymath} as required. \end{proof}
\noindent In the sequel,the following identities will be useful: $\mathrm{c}(x(1-x))=\frac{1}{1-x}$ and
 $\mathrm{c}(x)=\frac{1}{1-xc(x)}$.

In terms of the Riordan group, the Catalan transform and its inverse are thus given by the elements
$(1, x\textrm{c}(x))$ and $(1, x(1-x))$. The lower-triangular matrix representing the Catalan transformation has the form
\begin{displaymath}\mathbf{Cat}=\left(\begin{array}{ccccccc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & 1
& 1 & 0 & 0 & 0 & \ldots \\ 0 & 2 & 2 & 1 & 0 & 0 & \ldots \\ 0 &
5 & 5 & 3 & 1 & 0 & \ldots
\\0 & 14 & 14 & 9 & 4 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} Where
convenient, we shall denote this transformation by $\mathbf{Cat}$.
The inverse Catalan transformation $\mathbf{Cat}^{-1}$ has the
form
\begin{displaymath}\mathbf{Cat}^{-1}=\left(\begin{array}{rrrrrrc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & -1
& 1 & 0 & 0 & 0 & \ldots \\ 0 & 0 & -2 & 1 & 0 & 0 & \ldots \\ 0 &
0 & 1 & -3 & 1 & 0 & \ldots
\\0 & 0 & 0 & 3 & -4 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} The general
term of the matrix $(1,x(1-x))$ is given by ${{k} \choose
{n-k}}(-1)^{n-k}$. This can be shown by observing that the $k-$th
column of $(1,x(1-x))$ has generating function $(x(1-x))^k$. But
$[x^n](x(1-x))^k={{k} \choose {n-k}}(-1)^{n-k}$. We note that the bivariate
generating function of $(1,x(1-x))$ is $\frac{1}{1-xy(1-x)}$.

We now characterise the general term of the matrix for the Catalan transform.
\begin{proposition} The general term $\mathrm{T}(n,k)$ of the Riordan matrix $(1,\mathrm{c}(x))$ is given by
\begin{displaymath} \mathrm{T}(n,k)=\sum_{j=0}^k{{k}\choose{j}}{{j/2}\choose{n}}(-1)^{n+j}2^{2n-k}\end{displaymath}
\end{proposition}
\begin{proof} We seek $[x^n](x\mathrm{c}(x))^k$. To this end, we develop
the term $(x\mathrm{c}(x))^k$ as follows: 


\begin{tabular}
{l}
$x^k\mathrm{c}(x)^k=x^k\left(\frac{1-\sqrt{1-4x}}{2x}\right)^k=\frac{1}{2^k}(1-\sqrt{1-4x})^k=\frac{1}{2^k}\sum_{j=0}^k{{k}\choose{j}}(-\sqrt{1-4x})^j$\\
$=\frac{1}{2^k}\sum_{j}{{k}\choose{j}}(-1)^j(1-4x)^{j/2}=\frac{1}{2^k}\sum_{j}{{k}\choose{j}}(-1)^j\sum_{i}{{j/2}\choose{i}}(-4x)^i$\\
$=\frac{1}{2^k}\sum_{j}{{k}\choose{j}}(-1)^j\sum_{i}{{j/2}\choose{i}}(-4)^ix^i=\sum_{j}{{k}\choose{j}}\sum_{i}{{j/2}\choose{i}}(-1)^{i+j}2^{2i-k}x^i$
\end{tabular} \\ Thus $[x^n](x\mathrm{c}(x))^k=\sum_{j=0}^k{{k}\choose{j}}{{j/2}\choose{n}}(-1)^{n+j}2^{2n-k}$. 
Alternatively we can obtain $[x^ny^k]G(x,y)$ where $G(x,y)=\frac{1}{1-xyc(x)}$ is the bivariate
generating function of the Riordan matrix $(1,x\mathrm{c}(x))$. \end{proof}
The above proposition shows that the Catalan
transform of a sequence $a_n$ has general term $b_n$ given by
\begin{displaymath}b_n=\sum_{k=0}^n\sum_{j=0}^k{{k}\choose{j}}{{j/2}\choose{n}}(-1)^{n+j}2^{2n-k}a_k\end{displaymath}
The following proposition gives alternative versions for this
expression.
\begin{proposition} Given a sequence ${a_n}$, its Catalan transform ${b_n}$ is given by
\begin{displaymath}b_n=\sum_{k=0}^n\frac{k}{2n-k}{{2n-k}\choose{n-k}}a_k=
\sum_{k=0}^n\frac{k}{n}{{2n-k-1}\choose{n-k}}a_k
\end{displaymath} or
\begin{displaymath} b_n=\sum_{j=0}^n\sum_{k=0}^n\frac{2k+1}{n+k+1}(-1)^{k-j}{{2n}\choose{n-k}}{{k}\choose{j}}a_j\end{displaymath}
The inverse transformation is given by
\begin{displaymath}a_n=\sum_{k=0}^{\lfloor n/2 \rfloor}{{n-k}\choose{k}}(-1)^kb_{n-k}=
\sum_{k=0}^n {{k}\choose{n-k}}(-1)^{n-k} b_k \end{displaymath}
\end{proposition}
\begin{proof} We have 

\bigskip

\begin{tabular} {l}
T$(n,k)=2^{2n-k}(-1)^n\sum_{j=0}^k{{k}\choose{j}}{{j/2}\choose{n}}(-1)^j=$\\\\
$2^{2n-k}(-1)^n((-1)^n2^{k-2n}\left({{2n-k-1}\choose{n-1}}-
{{2n-k-1}\choose{n}}\right))=$\\\\
${{2n-k-1}\choose{n-1}}-
{{2n-k-1}\choose{n}}=\frac{k}{n}{{2n-k-1}\choose{n-1}}=\frac{k}{n}{{2n-k-1}\choose{n-k}}$
\end{tabular}

\bigskip

This proves the first two
assertions of the proposition. The last assertion follows from the
expression for the general term of the matrix $(1,x(1-x))$
obtained above. The equivalence of this and the accompanying
expression is easily obtained. The remaining assertion will be a
consequence of results in Section $5$. \end{proof}

Using the last proposition, and \cite{SL1}, it is possible to draw up the 
representative list of Catalan pairs given in Table 1,
that is, sequences and their Catalan transforms.

\begin{center}
\begin{table}
\centering
\begin{tabular}{|c|c|c|c|}\hline
$a_n$&$b_n$&$a_n$&$b_n$\\\hline
$0^n$&$0^n$&A000007&A000007\\\hline
$1^n$&C$(n)$&$1^n$&A000108\\\hline
$2^n$&${{2n}\choose{n}}$&A000079&A000984\\\hline
$2^n-1$&${{2n}\choose{n-1}}$&A000225&A001791\\\hline
$2^n-\sum_{j=0}^{k-1}{{n}\choose{j}}$&${{2n}\choose{n-k}}$&various&various\\\hline
$n$&$3n$C$(n)/(n+2)$&A001477&A000245\\\hline
$n+1$&C$(n+1)$&A000027&A000108$(n+1)$\\\hline
${{n}\choose{2}}$&$5{{2n}\choose{n-2}}/(n+3)$&A000217$(n-1)$&A000344\\\hline
${{n+1}\choose{2}}$&$4{{2n+1}\choose{n-1}}/(n+3)$&A000217&A002057\\\hline
${{n+2}\choose{2}}$&$3{{2n+2}\choose{n}}/(n+3)$&A000217$(n+1)$&A000245\\\hline
$0^n-(-1)^n$&Fine's sequence&-&A000957\\\hline
$(1+(-1)^n)/2$&Fine's sequence&A000035$(n+1)$&A000957$(n+1)$\\\hline
$2-0^n$&$(2-0^n)$C$(n)$&A040000&A068875\\\hline
F$(n)$&G.f.$\frac{xc(x)}{x+\sqrt{1-4x}}$&A000045&-\\\hline
F$(n+1)$&G.f.$\frac{1}{x+\sqrt{1-4x}}$&A000045$(n+1)$&A081696\\\hline
J$(n)$&$\sum_{j=0}^{\lfloor {(n-1)/2}
\rfloor}{{2n-2j-2}\choose{n-1}}$&A001045&A014300\\\hline
J$(n+1)$&$\sum_{j=0}^{\lfloor {n/2}
\rfloor}{{2n-2j-1}\choose{n-1}}+0^n$&A001045$(n+1)$&A026641$(n)+0^n$\\\hline
J$_1(n)$&$\sum_{k=0}^n{{n+k-1}\choose{k}}(-1)^{n-k}$&A078008&A072547\\\hline
$2\sin(\frac{{\pi}n}{3}+\frac{\pi}{3})/\sqrt{3}$&$1^n$&A010892&$1^n$\\\hline
$(-1)^n$F$(n+1)$&$(-1)^n$&$(-1)^n$A000045$(n+1)$&$(-1)^n$\\\hline
$2^\frac{n}{2}(\cos(\frac{{\pi}n}{4})+\sin(\frac{{\pi}n}{4}))$&$2^n$&A009545&A000079\\\hline
\end{tabular}
\caption{Table 1. \ Catalan pairs }
\end{table}
\end{center}

We note that the result above concerning Fine's sequence \seqnum{A000957}
is implicit in the work \cite{DS}.
We deduce immediately that the generating function
for Fine's sequence can be written as
\begin{displaymath}
\frac{x}{1-(x\textrm{c}(x))^2}=
\frac{2x}{1+2x+\sqrt{1-4x}}=
\frac{x}{1+x-x\textrm{c}(x)} .\end{displaymath}
See also \cite{PW}.

\section{Transforms of a Jacobsthal family}
From the above, we see that the Jacobsthal numbers J$(n)$ transform to give the sequence with general term
\begin{displaymath}\sum_{j=0}^{\lfloor {(n-1)/2} \rfloor}{{2n-2j-2}\choose{n-1}}\end{displaymath} and generating function \begin{displaymath}
\frac{x\mathrm{c}(x)}{(1+x\mathrm{c}(x))(1-2x\mathrm{c}(x))}\end{displaymath}
This prompts us to characterize the family of sequences with general term
\begin{displaymath}\sum_{j=0}^{\lfloor {(n-1)/2} \rfloor}{{2n-2j-2}\choose{n-1}}k^j\end{displaymath}
where the transform of the Jacobsthal numbers corresponds to the case $k=1$. Re-casting the ordinary generating function of the
Jacobsthal numbers as
\begin{displaymath}\frac{x}{(1+x)(1-2x)}=\frac{x(1-x)}{(1-x^2)(1-2x)}\end{displaymath} we see that the
Jacobsthal numbers are the case $k=1$ of the one-parameter family of sequences with generating functions
\begin{displaymath}\frac{x(1-x)}{(1-kx^2)(1-2x)}\end{displaymath}
For instance, the sequence for $k=0$ has g.f. $\frac{x(1-x)}{1-2x}$ which is $0,1,1,2,4,8,16,\ldots$. For $k=2$, we obtain
$0,1,1,4,6,16,\ldots$ or \seqnum{A007179}.
The general term for these sequences is  given by
\begin{displaymath}\frac{(\sqrt{k})^{n-1}(1-\sqrt{k})}{2(2-\sqrt{k})}+\frac{(-\sqrt{k})^{n-1}(1+\sqrt{k})}{2(2+\sqrt{k})}+\frac{2^n}{4-k}\end{displaymath}
for $k\neq4$.

They are solutions of the family of recurrences
\begin{displaymath}a_n=2a_{n-1}+ka_{n-2}-2ka_{n-3}\end{displaymath} where $a_0=0$, $a_1=1$ and $a_2=1$.
\begin{proposition} The Catalan transform of the generalized Jacobsthal sequence with ordinary generating function
\begin{displaymath}\frac{x(1-x)}{(1-kx^2)(1-2x)}\end{displaymath} has ordinary generating function given by
\begin{displaymath}\frac{x}{\sqrt{1-4x}(1-k(x\textrm{c}(x))^2)}\end{displaymath} and general term
\begin{displaymath}\sum_{j=0}^{\lfloor {(n-1)/2} \rfloor}{{2n-2j-2}\choose{n-1}}k^j\end{displaymath}
\end{proposition}
\begin{proof} By definition, the Catalan transform of
$\frac{x(1-x)}{(1-kx^2)(1-2x)}$ is
$\frac{xc(x)(1-xc(x))}{(1-kx^2c(x)^2)(1-2xc(x))}$. But
$\mathrm{c}(x)(1-x\mathrm{c}(x))=1$ and
$1-2x\mathrm{c}(x)=\sqrt{1-4x}$. Hence we obtain the first
assertion.

We now recognise that
\begin{displaymath}\frac{1}{\sqrt{1-4x}(1-k(x\mathrm{c}(x))^2)}=\left(\frac{1}{\sqrt{1-4x}},x^2\mathrm{c}(x)^2\right)\frac{1}{1-kx}\end{displaymath}
But this is $\sum_{j=0}^{\lfloor n/2
\rfloor}{{2n-2j}\choose{n}}k^j$. The second assertion follows from
this. \end{proof}
\noindent For example, the transform of the sequence
$0,1,1,2,4,8,\ldots$ can be recognized as
${{2n-2}\choose{n-1}}=\sum_{j=0}^{\lfloor {(n-1)/2}
\rfloor}{{2n-2j-2}\choose{n-1}}0^j$.

As noted in
\seqnum{A014300}, the Catalan transform of the Jacobsthal numbers
corresponds to the convolution of the central binomial numbers
(with generating function $\frac{1}{\sqrt{1-4x}}$) and Fine's sequence
\seqnum{A000957} (with generating function $\frac{x}{1-(xc(x))^2}$). The
above proposition shows that the Catalan transform of the
generalized Jacobsthal numbers corresponds to a convolution of the
central binomial numbers and the ``generalized'' Fine numbers with
generating function $\frac{x}{1-k(xc(x))^2}$.

Using the inverse Catalan transform, we can express the
general term of this Jacobsthal family as
\begin{displaymath}\sum_{k=0}^{\lfloor n/2 \rfloor}{{n-i}\choose{i}}(-1)^i\sum_{j=0}^{\lfloor (n-i-1)/2 \rfloor}{{2n-2i-2j-2}\choose{n-i-1}}k^j\end{displaymath}
This provides us with a closed form for the case $k=4$ in
particular.

We now wish to find an expression for
the transform of J$_{1}(n)$. To this end, we note that
\begin{displaymath}\textrm{J}(n+1)\to\sum_{j=0}^{\lfloor n/2
\rfloor}{{2n-2j-1}\choose{n-1}}+0^n=\sum_{j=0}^{\lfloor (n-1)/2
\rfloor}{{2n-2j-1}\choose{n-1}}+\frac{1+(-1)^n}{2}\end{displaymath}
Then

\begin{tabular}{l}
J$_{1}(n)=$J$(n+1)-$J$(n)\to\sum_{j=0}^{\lfloor \frac{n-1)}{2}
\rfloor}{{2n-2j-1}\choose{n-1}}+\frac{1+(-1)^n}{2}-\sum_{j=0}^{\lfloor
\frac{n-1}{2} \rfloor}{{2n-2j-2}\choose{n-1}}$\\\\
$=\sum_{j=0}^{\lfloor (n-1)/2
\rfloor}{{2n-2j-2}\choose{n-2}}+\frac{1+(-1)^n}{2}$\\
\end{tabular}

The first term of the last expression deserves comment.
Working with generating functions, it is easy to show that under the Catalan transform, we have
\begin{displaymath}(-1)^n\textrm{F}(n+1)/2+\cos(\frac{{\pi}n}{3})/2+\sqrt{3}\sin(\frac{{\pi}n}{3})/6\to\frac{1+(-1)^n}{2}\end{displaymath}
Hence $\sum_{j=0}^{\lfloor (n-1)/2
\rfloor}{{2n-2j-2}\choose{n-2}}$ is the Catalan transform of
\begin{displaymath}\mathrm{J}_{1}(n)-(-1)^n\textrm{F}(n+1)/2-\cos(\frac{{\pi}n}{3})/2-\sqrt{3}\sin(\frac{{\pi}n}{3})/6\end{displaymath}

\section{The Generalized Ballot Transform}
In this section, we introduce and study a transformation that we
will link to the generalized ballot numbers studied in \cite{Ng}. For
this, we define a new transformation $\mathbf{Bal}$ as the
composition of the Catalan transform and the Binomial transform:
\begin{displaymath}
\mathbf{Bal}=\mathbf{Cat}\circ\mathbf{Bin}\end{displaymath} The
Riordan matrix formulation of this transformation is thus given by

\begin{tabular}{l}$\mathbf{Bal}=\mathbf{Cat}\circ\mathbf{Bin}=(1,\textrm{c}(x))(\frac{1}{1-x},\frac{x}{1-x})=(\frac{1}{1-xc(x)},\frac{xc(x)}{1-xc(x)})=$\\$\quad\quad(\textrm{c}(x),\textrm{c}(x)-1)=(\textrm{c}(x),x\textrm{c}(x)^2)$
\end{tabular}

In similar fashion, we can find the
Riordan description of the inverse of this transformation by

\begin{tabular}{l}$\mathbf{Bal}^{-1}=\mathbf{Bin}^{-1}\circ\mathbf{Cat}^{-1}=(\frac{1}{1-x},\frac{x}{1-x})^{-1}(1,\textrm{c}(x))^{-1}=(\frac{1}{1+x},\frac{x}{1+x})(1,x(1-x))$\\\\
$=(\frac{1}{1+x}.1,\frac{x}{1+x}(1-\frac{x}{1+x}))=(\frac{1}{1+x},\frac{x}{(1+x)^2})$\\\end{tabular}

The general term of $\mathbf{Bal}^{-1}$ is easily derived from the
last expression: it is
$[x^n](x^k(1+x)^{-2k+1})={{n+k}\choose{n-k}}(-1)^{n-k}={{n+k}\choose{2k}}(-1)^{n-k}$.
Alternatively we can find the general term in the matrix product
of $\mathbf{Bin}^{-1}$, or ${{n}\choose{k}}(-1)^{n-k}$, with
$\mathbf{Cat}^{-1}$, or ${{k}\choose{n-k}}(-1)^{n-k}$ to get the
equivalent expression
$\sum_{j=0}^{k+n}{{n}\choose{j}}{{k}\choose{j-k}}(-1)^{n-k}$.

We now examine the general term of the transformation
$\mathbf{Bal}=(\textrm{c}(x),\textrm{c}(x)-1)=(\textrm{c}(x),x\textrm{c}(x)^2)$. An initial result
is given by

\begin{proposition} The general term $\mathrm{T}(n,k)$ of the Riordan matrix
$(\mathrm{c}(x),\mathrm{c}(x)-1)$ is given by
\begin{displaymath} \mathrm{T}(n,k)=\sum_{j=0}^k \sum_{i=0}^{j+1}
{{k}\choose{j}}{{j+1}\choose{i}}{{i/2}\choose{n+j+1}}(-1)^{k+n+i+1}2^{2n+j+1}\end{displaymath} and
\begin{displaymath}\mathrm{T}(n,k)=2.4^n\sum_{j=0}^{2k+1}{{2k+1}\choose{j}}{{j/2}\choose{n+k+1}}(-1)^{n+k+j+1}\end{displaymath}
\end{proposition}
\begin{proof} The first assertion follows by observing that the $k-$th column of
$(\textrm{c}(x),\textrm{c}(x)-1)$ has generating function
c$(x)(\textrm{c}(x)-1)^k$. We are thus looking for
$[x^n]\textrm{c}(x)(\textrm{c}(x)-1)^k$. Expanding and
substituting for c$(x)$ yields the result. The second assertion follows by taking
$[x^n]\textrm{c}(x)(x\textrm{c}(x)^2)^k$. \end{proof}
We now show that this transformation has in fact
a much easier formulation, corresponding to the generalized Ballot
numbers of \cite{Ng}. We recall that the generalized Ballot numbers or
generalized Catalan numbers \cite{Ng} are defined by
\begin{displaymath}\textrm{B}(n,k)={{2n}\choose{n+k}}\frac{2k+1}{n+k+1}\end{displaymath}
B$(n,k)$ can be written as
\begin{displaymath}\textrm{B}(n,k)={{2n}\choose{n+k}}\frac{2k+1}{n+k+1}={{2n}\choose{n-k}}-{{2n}\choose{n-k-1}}\end{displaymath}
where the matrix with general term ${{2n}\choose{n-k}}$ is the element
\begin{displaymath} \left(\frac{1}{\sqrt{1-4x}},\frac{1-2x-\sqrt{1-4x}}{2x}\right)=\left(\frac{1}{\sqrt{1-4x}},x\frac{\textrm{c}(x)-1}{x}\right)=\left(\frac{1}{\sqrt{1-4x}},x\textrm{c}(x)^2\right)\end{displaymath}
of the Riordan group [11]. The inverse of this matrix is
$(\frac{1-x}{1+x},\frac{x}{(1+x)^2})$ with general term
$(-1)^{n-k}\frac{2n}{n+k}{{n+k}\choose{2k}}$.
\begin{proposition} The general term of the Riordan matrix $(\mathrm{c}(x),\mathrm{c}(x)-1)$ is given by
\begin{displaymath} \mathrm{T}(n,k)=\mathrm{B}(n,k)={{2n}\choose{n+k}}\frac{2k+1}{n+k+1}\end{displaymath} \end{proposition}
\begin{proof} We provide two proofs - one indirect, the other direct. The first, indirect proof is instructive as it uses properties of Riordan arrays. 

We have
B$(n,k)={{2n}\choose{n-k}}-{{2n}\choose{n-k-1}}$. Hence the
generating function of the $k-$th column of the matrix with
general term B$(n,k)$ is given by
\begin{displaymath}\frac{1}{\sqrt{1-4x}}(c(x)-1)^k-\frac{1}{\sqrt{1-4x}}(c(x)-1)^{k+1}\end{displaymath} Then

\begin{tabular}{l}$\frac{1}{\sqrt{1-4x}}(c(x)-1)^k-\frac{1}{\sqrt{1-4x}}(c(x)-1)^{k+1}=(c(x)-1)^k(\frac{1}{\sqrt{1-4x}}-\frac{c(x)-1}{\sqrt{1-4x}})$\\\\
$=(c(x)-1)^k(\frac{1}{\sqrt{1-4x}}(1-(c(x)-1)))=(c(x)-1)^k(\frac{-c(x)+2}{\sqrt{1-4x}})=(c(x)-1)^kc(x)$\end{tabular}

But this is the generating function of the $k-$th column of
$(\textrm{c}(x),\textrm{c}(x)-1)$.

The second,
direct proof follows from the last proposition. From this, we have

\begin{tabular}{l}
T$(n,k)=2.4^n(-1)^{n+k+1}\sum_{j=0}^{2k+1}{{2k+1}\choose{j}}{{j/2}\choose{n+k+1}}(-1)^j$\\
$=2.4^n(-1)^{n+k+1}\left\{(-1)^{n+k+1}2^{2k+1-2(n+k+1)}\left({{2n+2k+2-2k-1-1}\choose{n+k}}-{{2n+2k+2-2k-1-1}\choose{n+k+1}}\right)\right\}$\\
$=\left\{{{2n}\choose{n+k}}-{{2n}\choose{n+k+1}}\right\}=\left\{{{2n}\choose{n-k}}-{{2n}\choose{n-k-1}}\right\}={{2n}\choose{n+k}}\frac{2k+1}{n+k+1}$
\end{tabular} 
\end{proof}

The numbers B$(n,k)$ have many combinatorial uses. For instance,
\begin{displaymath}\mathrm{B}(n,k)=\mathrm{D}(n+k+1,2k+1)\end{displaymath}
where D$(n,k)$ is the number of Dyck paths of semi-length $n$
having height of the first peak equal to $k$ \cite{PW}. B$(n,k)$ also
counts the number of paths from $(0,-2k)$ to $(n-k,n-k)$ with
permissible steps $(0,1)$ and $(1,0)$ that don't cross the
diagonal $y=x$ \cite{Ng}.

We recall that the classical ballot numbers are
given by
$\frac{k}{2n+k}{{2n+k}\choose{n}}=\frac{k}{2n+k}{{2n+k}\choose{n+k}}$
\cite{HP}.

We now define the \emph{generalized Ballot
transform} to be the transformation corresponding to the Riordan
array
$\mathbf{Bal}=\mathbf{Cat}\circ\mathbf{Bin}=(\textrm{c}(x),\textrm{c}(x)-1)=(\textrm{c}(x),x\textrm{c}(x)^2)$.
 By the
above, the generalized Ballot transform of the sequence $a_n$ is
the sequence $b_n$ where
\begin{displaymath}b_n=\sum_{k=0}^n{{2n}\choose{n+k}}\frac{2k+1}{n+k+1}a_k\end{displaymath}
In terms of generating functions, the generalized Ballot transform
maps the sequence with ordinary generating function $g(x)$ to the
sequence with generating function
c$(x)g$(c$(x)-1)=$c$(x)$g$(x$c$(x)^2)$ where c$(x)$ is the
generating function of the Catalan numbers. We then have
\begin{proposition}Given a sequence $a_n$, its inverse generalized Ballot
transform is given by \begin{displaymath}
b_n=\sum_{k=0}^n(-1)^{n-k}{{n+k}\choose{2k}}a_k\end{displaymath}
If $a_n$ has generating function $g(x)$ then $b_n$ has generating
function $\frac{1}{1+x}g(\frac{x}{(1+x)^2})$\end{proposition}
\begin{proof} We have seen that
$\mathbf{Bal}^{-1}=\mathbf{Bin}^{-1}\circ\mathbf{Cat}^{-1}=(\frac{1}{1+x},\frac{x}{(1+x)^2})$.
The second statement follows from this. We have also seen that the
general term of $\mathbf{Bal}^{-1}$ is
$(-1)^{n-k}{{n+k}\choose{2k}}$. Hence the transform of the
sequence $a_n$ is as asserted. \end{proof} \noindent We can now characterize the Catalan transformation as
\begin{displaymath}\mathbf{Cat}=\mathbf{Bal}\circ\mathbf{Bin}^{-1}\end{displaymath}
Since the general term of $\mathbf{Bin}^{-1}$ is
$(-1)^{n-k}{{n}\choose{k}}$ we immediately obtain the expression

$\sum_{j=0}^n\sum_{k=0}^n\frac{2k+1}{n+k+1}(-1)^{k-j}{{2n}\choose{n-k}}{{k}\choose{j}}$
for the general term of $\mathbf{Cat}$. 
The following table identifies some Ballot transform pairings \cite{SL1}.
\begin{center}
\textbf{Table 2. \ Generalized Ballot transform pairs }
\begin{tabular}{|c|c|c|c|}\hline
$a_n$&$b_n$&$a_n$&$b_n$\\\hline
$(-1)^n$&$0^n$&$(-1)^n$&A000007\\\hline
$0^n$&C$(n)$&A000007&A000108\\\hline
$1^n$&${{2n}\choose{n}}$&$1^n$&A000984\\\hline
$2^n$&$\frac{1}{1-3xc(x)}$&A000079&A007854\\\hline
$n$&$\frac{xc(x)}{1-4c(x)}$&A001477&A000346$(n-1)+0^n/2$\\\hline
$n+1$&$\sum_{k=0}^n{{2n}\choose{k}}$&A000027&A032443\\\hline
$2n+1$&$4^n$&A005408&A000302\\\hline
$(1+(-1)^n)/2$&${{2n+1}\choose{n}}$&A059841&A088218\\\hline
$2-0^n$&${{2n+1}\choose{n+1}}$&A040000&A001700\\\hline
$(2^n+0^n)/2$&-&A011782&A090317\\\hline
$\cos(\frac{2{\pi}n}{3})+\sin(\frac{2{\pi}n}{3})/\sqrt{3}$&$1^n$&A057078&$1^n$\\\hline
$\cos(\frac{{\pi}n}{2})+\sin(\frac{{\pi}n}{2})$&$2^n$&-&A000079\\\hline
$\cos(\frac{{\pi}n}{3})+\sqrt{3}\sin(\frac{{\pi}n}{3})$&$3^n$&A057079&A000244\\\hline
$$F$(n)$&$-$&A000045&A026674\\\hline
$$F$(n+1)$&$-$&A000045$(n+1)$&A026726\\\hline
\end{tabular}\end{center}
In terms of the Riordan group, the above implies that the
generalized Ballot transform and its inverse are given by the elements
$(\textrm{c}(x), x(\textrm{c}(x)-1)/x)$ and $(\frac{1}{1+x},
\frac{x}{(1+x)^2})$. The lower-triangular matrix representing the
Ballot transformation thus has the form
\begin{displaymath}\mathbf{Bal}=\left(\begin{array}{ccccccc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 3
& 1 & 0 & 0 & 0 & \ldots \\ 5 & 9 & 5 & 1 & 0 & 0 & \ldots \\ 14 &
28 & 20 & 7 & 1 & 0 & \ldots
\\42 & 90 & 75 & 35 & 9 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} while the
inverse Ballot transformation is represented by the matrix
\begin{displaymath}\mathbf{Bal}^{-1}=\left(\begin{array}{rrrrrrc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\-1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 &
-3 & 1 & 0 & 0 & 0 & \ldots \\ -1 & 6 & -5 & 1 & 0 & 0 & \ldots \\
1 & -10 & 15 & -7 & 1 & 0 & \ldots
\\-1 & 15 & -35 & 28 & -9 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}
The first matrix is \seqnum{A039599}, while the absolute value of the second matrix is \seqnum{A085478}.

\section{The Signed Generalized Ballot transform}
For completeness, we consider a transformation that may be
described as the signed generalized Ballot transform. As a member
of the Riordan group, this is the element $(\textrm{c}(-x),
1-\textrm{c}(-x))=(\textrm{c}(-x), x\textrm{c}(-x)^2)$. For a
given sequence $a_n$, it yields the sequence with general term
\begin{displaymath}b_n=\sum_{k=0}^n(-1)^{n-k}{{2n}\choose{n+k}}\frac{2k+1}{n+k+1}a_k\end{displaymath}
Looking at generating functions, we get the mapping
\begin{displaymath}
\textrm{$\cal{A}$}(x)\to\textrm{c}(-x)\textrm{$\cal{A}$}(1-\textrm{c}(-x))=\textrm{c}(-x)\textrm{$\cal{A}$}(x\textrm{c}(-x)^2)\end{displaymath}
The inverse of this map is given by
\begin{displaymath}b_n=\sum_{k=0}{{n+k}\choose{2k}}a_k\end{displaymath}
or, in terms of generating functions \begin{displaymath}
\textrm{$\cal{A}$}(x)\to\frac{1}{1-x}\textrm{$\cal{A}$}\left(\frac{x}{(1-x)^2}\right)\end{displaymath}
Example mappings under this transform are $0^n\to(-1)^n$C$(n)$, $1^n\to0^n$, F$(2n+1)\to 1^n$.

We can characterize the effect of its inverse on the power sequences $n \to k^n$ as follows: the image of $k^n$ under the inverse signed generalized Ballot transform is the solution to the recurrence
\begin{displaymath}a_n=(k+2)a_{n-1}-a_{n-2}\end{displaymath}
with $a_0=1$, $a_1=$F$(2k+1)$.

The matrices that represent this inverse pair of transformations are, respectively, the alternating sign
versions of \seqnum{A039599} and \seqnum{A085478}.
The latter
matrix has a growing literature in which it is known as the DFF
triangle \cite{FFA1}, \cite{FFA2}, \cite{Sun2}. As an element of the Riordan group, it is
given by $(\frac{1}{1-x}, \frac{x}{(1-x)^2})$.

It
has a ``companion'' matrix with general element \begin{displaymath}
b_{n,k}={{n+k+1}\choose{2k+1}}=\frac{n+k+1}{2k+1}{{n+k}\choose{2k}}\end{displaymath} called the DFFz
triangle. This is the element \begin{displaymath}
\left(\frac{1}{(1-x)^2},\frac{x}{(1-x)^2}\right)\end{displaymath}
of the Riordan group with inverse
\begin{displaymath}\left(\frac{1-\textrm{c}(-x)}{x}, 1-\textrm{c}(-x)\right)=(\textrm{c}(-x)^2,x\textrm{c}(-x)^2)\end{displaymath}
Another number triangle that is related to the above \cite{Sun2} has general term
\begin{displaymath}a_{n,k}=\frac{2n}{n+k}{{n+k}\choose{2k}}\end{displaymath}
Taking $a_{0,0}=1$, we obtain the matrix \begin{displaymath}\left(\begin{array}{ccccccc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\2 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 4
& 1 & 0 & 0 & 0 & \ldots \\ 2 & 9 & 6 & 1 & 0 & 0 & \ldots \\ 2 &
16 & 20 & 8 & 1 & 0 & \ldots
\\2 & 25 & 50 & 35 & 10 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}
which is the element $(\frac{1+x}{1-x},\frac{x}{(1-x)^2})$ of the Riordan group \cite{Sp}. Its inverse is the matrix
\begin{displaymath}\left(\begin{array}{rrrrrrr} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\-2 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 6 & -4
& 1 & 0 & 0 & 0 & \ldots \\ -20 & 15 & -6 & 1 & 0 & 0 & \ldots \\ 70 &
-56 & 28 & -8 & 1 & 0 & \ldots
\\-252 & 210 & -120 & 45 & -10 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} with general element $(-1)^{n-k}{{2n}\choose{n-k}}$
which is the element \begin{displaymath}\left(\frac{1}{\sqrt{1+4x}}, \frac{1+2x-\sqrt{1+4x}}{2x}\right)\end{displaymath} of the Riordan group.
 We note that $\frac{1+2x-\sqrt{1+4x}}{2x^2}$ is the generating function of $(-1)^n$C$(n)$.

Applying $\mathbf{Bin}^2$ to this matrix yields the matrix
\begin{displaymath}\left(\begin{array}{ccccccc} 1 & 0
& 0 & 0 & 0 & 0 & \ldots \\0 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 0
& 1 & 0 & 0 & 0 & \ldots \\ 0 & 3 & 0 & 1 & 0 & 0 & \ldots \\ 6 &
0 & 4 & 0 & 1 & 0 & \ldots
\\0 & 10 & 0 & 5 & 0 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}
which is the element $(\frac{1}{\sqrt{1-4x^2}}, x\textrm{c}(x^2))$ of the Riordan group.
\section{An Associated Transformation}
We briefly examine a transformation associated to the Ballot
transformation. Unlike other transformations in this study, this
is not invertible. However, it transforms some ``core sequences'' to
other ``core sequences'', and hence deserves study. An example of
this transformation is given by \begin{displaymath}
\textrm{M}_n=\sum_{k=0}^{\lfloor n/2
\rfloor}{{n}\choose{2k}}\textrm{C}(k)\end{displaymath} where M$_n$
is the $n$th Motzkin number \seqnum{A001006}. In general, if $a_n$ is
the general term of a sequence with generating function
$\textrm{$\cal{A}$}(x)$ then we define its transform to be
\begin{displaymath}b_n=\sum_{k=0}^{\lfloor n/2
\rfloor}{{n}\choose{2k}}a_k\end{displaymath} which has
generating function \begin{displaymath}
\frac{1}{1-x}\textrm{$\cal{A}$}(\frac{x^2}{(1-x)^2})\end{displaymath}
The opening assertion concerning the Motzkin numbers follows from
the fact that
\begin{displaymath}\frac{1}{1-x}\textrm{c}\left(\frac{x^2}{(1-x)^2}\right)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}\end{displaymath}
which is the generating function of the Motzkin numbers.

The effect of this transform on the power sequences $n\to k^n$
is easy to describe. We have
\begin{displaymath}\frac{1}{1-kx}\to\frac{1-x}{1-2x-(k-1)x^2}\end{displaymath}
In other words, the sequences $n\to k^n$ are mapped to the
solutions of the one parameter family of recurrences
\begin{displaymath}a_n=2a_{n-1}+(k-1)a_{n-2}\end{displaymath}
satisfying $a_0=1$, $a_1=1$.

For instance,
\begin{displaymath} \sum_{k=0}^{\lfloor n/2
\rfloor}{{n}\choose{2k}}2^k=1,1,3,7,17,\ldots=((1+\sqrt{2})^n+(1-\sqrt{2})^n)/2\end{displaymath}
which is the sequence \seqnum{A001333}.
A consequence of this is the following formula for the Pell numbers \seqnum{A000129}
\begin{displaymath}\sum_{k=0}^{\lfloor n/2
\rfloor}{{n}\choose{2k+1}}2^k=\textrm{Pell}(n)\end{displaymath}
Under this mapping, the central binomial numbers ${{2n}\choose{n}}$ are mapped to the central trinomial numbers \seqnum{A002426} since
\begin{displaymath}\frac{1}{\sqrt{1-4x}}\to\frac{1}{1-x}\frac{1}{\sqrt{1-4x^2/(1-x)^2}}=\frac{1}{\sqrt{1-2x-3x^2}}\end{displaymath}
This is an interesting result, as the central trinomial numbers are also the inverse binomial transform of
the central binomial numbers :
\begin{displaymath}\frac{1}{\sqrt{1-4x}}\to\frac{1}{1+x}\frac{1}{\sqrt{1-4x/(1+x)}}=\frac{1}{\sqrt{1-2x-3x^2}}\end{displaymath}
This transformation can be represented by the ``generalized''
Riordan array $(\frac{1}{1-x},\frac{x^2}{(1-x)^2})$. As such, it
possesses two interesting factorizations. Firstly, we have
\begin{displaymath} \left(\frac{1}{1-x},\frac{x^2}{(1-x)^2}\right)=\left(\frac{1}{1-x},\frac{x}{1-x}\right)(1,x^2)=\mathbf{Bin}\circ(1,x^2)\end{displaymath} Thus the effect of this transform is to ``aerate'' a sequence with
interpolated zeros and then follow this with a binomial transform.
This is obvious from the following identity
\begin{displaymath}\sum_{k=0}^{\lfloor n/2 \rfloor}{{n}\choose{2k}}a_k=\sum_{k=0}^n {{n}\choose{k}}\frac{1+(-1)^k}{2}a_{k/2}\end{displaymath} where we use the usual
    convention that $a_{k/2}$ is to be interpreted as 0 when $k$
    is odd, that is when $k/2$ is not an integer. Secondly, we have
\begin{displaymath}
\left(\frac{1}{1-x},\frac{x^2}{(1-x)^2}\right)=\left(\frac{1-x}{1-2x+2x^2},\frac{x^2}{1-2x+2x^2}\right)\left(\frac{1}{1-x},\frac{x}{1-x}\right)\end{displaymath}
As pointed out in \cite{CMS}, this transformation possesses a left
inverse. Using the methods of \cite{CMS} or otherwise, it is easy to see
that the stretched Riordan array $(1,x^2)$ has left inverse $(1,
\sqrt{x})$. Hence the first factorization yields
\begin{displaymath}\left(\frac{1}{1-x},\frac{x^2}{(1-x)^2}\right)^{\sim 1}=(\mathbf{Bin}\circ(1,x^2))^{\sim 1}=(1,\sqrt{x})\circ\mathbf{Bin}^{-1}=\end{displaymath}
\begin{displaymath}(1,\sqrt{x})\left(\frac{1}{1+x},\frac{x}{1+x}\right)=\left(\frac{1}{1+\sqrt{x}},\frac{\sqrt{x}}{1+\sqrt{x}}\right)\end{displaymath}
where we have used $(.)^{\sim 1}$ to denote left-inverse.

It is instructive to represent these transformations by their
general terms. We look at $(1,x^2)$ first. We have
\begin{displaymath}[x^n](x^2)^k=[x^n]x^{2k}=[x^n]\sum_{j=0}^{\infty}{{0}\choose{j}}x^{2k+j}={{0}\choose{n-2k}}\end{displaymath}
Hence \begin{displaymath}b_n=\sum_{k=0}^{\lfloor n/2
\rfloor}{{n}\choose{2k}}a_k=\sum_{k=0}^n\sum_{j=0}^n{{n}\choose{j}}{{0}\choose{j-2k}}a_j\end{displaymath}
We now wish to express $b_n$ in terms of $a_n$. We have
\begin{displaymath}[x^n](\sqrt{x})^k=[t^{2n}]t^k=[t^{2n}]\sum_{j=0}^{\infty}{{0}\choose{j}}t^{k+j}={{0}\choose{2n-k}} \end{displaymath}
Hence \begin{displaymath}
a_n=\sum_{k=0}^{2n}\sum_{j=0}^k{{0}\choose{2n-k}}{{k}\choose{j}}(-1)^{k-j}b_j\end{displaymath}
We can use the methods of \cite{CMS} to further elucidate the relationship
between $(1,x^2)$ and $(1,\sqrt{x})$. Letting $b(x)$ be the
generating function of the image of the sequence $a_n$ under
$(1,x^2)$, we see that $b(x)=a(x^2)$ where
$a(x)=\sum_{k=0}^{\infty}a_kx^k$. We wish to find the general term
$a_n$ in terms of the $b_n$. We have $a(x)=[b(t) | x=t^2]$ and so

\begin{tabular}{l}$a_n=[x^n]a(x)=[x^n](b(t) |
t=\sqrt{x})=[w^{2n}] (b(t) | t=w ) =$\\\\
$\frac{1}{2n}[t^{2n-1}](b'(t))^{2n}=\frac{1}{2n}2n.b_{2n}=b_{2n}$\\\end{tabular}

 Table 3 displays a list of sequences and their
transforms under this transformation. Note that by the above, we
can recover the original sequence $a_n$ by taking every second
element of the inverse binomial transform of the transformed
sequence $b_n$.
\begin{center}
\textbf{Table 3. \ Transform pairs }\\
\begin{tabular}{|c|c|c|c|}\hline
$a_n$&$b_n$&$a_n$&$b_n$\\\hline
$0^n$&$1^n$&A000007&$1^n$\\\hline
$1^n$&$(2^n+0^n)/2$&$1^n$&A011782\\\hline
$2^n$&$\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n)}{2}$&A000079&A001333\\\hline
$n$&$n2^{n-3}-\frac{{{1}\choose{n}}-{{0}\choose{n}}}{4}$&A001477&-\\\hline
$n+1$& G.f. $\frac{(1-x)^3}{(1-2x)^2}$&A000027&A045891\\\hline
$2n+1$&$2^n(n+2)/2$, $n>1$&A005408&A087447\\\hline
$(1+(-1)^n)/2$&$\sum_{k=0}^{\lfloor n/4 \rfloor}{{n}\choose{4k}}$&A059841&A038503\\\hline
${{2n}\choose{n}}$&G.f.$\frac{1}{\sqrt{1-2x-3x^2}}$&A000984&A002426\\\hline
C$(n)$&Motzkin&A000108&A001006\\\hline
\end{tabular}\end{center}
\section{Combining
transformations} We finish this note by briefly looking at the
effect of combining transformations. For this, we will take the
Fibonacci numbers as an example. We look at two combinations: the
Catalan transform followed by the binomial transform, and the
Catalan transform followed by the inverse binomial transform. For
the former, we have
\begin{displaymath}\mathbf{Bin}\circ\mathbf{Cat}=\left(\frac{1}{1-x},\frac{x}{1-x}\right)(1,x\textrm{c}(x))=\left(\frac{1}{1-x},\frac{x}{1-x}\textrm{c}(\frac{x}{1-x})\right)\end{displaymath}
while for the latter we have
\begin{displaymath}\mathbf{Bin}^{-1}\circ\mathbf{Cat}=\left(\frac{1}{1+x},\frac{x}{1+x}\right)(1,x\textrm{c}(x))=\left(\frac{1}{1+x},\frac{x}{1+x}\textrm{c}(\frac{x}{1+x})\right)\end{displaymath}
Applying the first combined transformation to the Fibonacci
numbers yields the sequence $0, 1, 4, 15, 59, 243, \ldots$ with
generating function \begin{displaymath} \frac{(\sqrt{5x - 1} -
\sqrt{x - 1})}{2((x - 1)\sqrt{5x - 1} - x\sqrt{x -
1)})}\end{displaymath} or
\begin{displaymath}
\frac{\sqrt{1-6x+5x^2}-(1-5x+4x^2)}{2(1-x)(1-6x+4x^2)}\end{displaymath}
Applying the second combined transformation (Catalan transform
followed by the inverse binomial transform) to the Fibonacci
numbers we obtain the sequence $0, 1, 0, 3, 3, 13, 26,\ldots$ with
generating function
\begin{displaymath}\frac{(1+2x)\sqrt{1-2x-3x^2}-(1-x-2x^2)}{2(1+x)(1-2x-4x^2)}\end{displaymath}
It is instructive to reverse these transformations. Denoting the
first by $\mathbf{Bin}\circ\mathbf{Cat}$ we wish to look at
$(\mathbf{Bin}\circ\mathbf{Cat})^{-1}=\mathbf{Cat}^{-1}\circ\mathbf{Bin}^{-1}$.
As elements of the Riordan group, we obtain
\begin{displaymath}(1,x(1-x))\left(\frac{1}{1+x},\frac{x}{1+x}\right)=\left(\frac{1}{1+x-x^2},\frac{x(1-x)}{1+x-x^2}\right)\end{displaymath}
Applying the inverse transformation to the family of functions
$k^n$ with generating functions $\frac{1}{1-kx}$, for instance, we
obtain
\begin{displaymath}\frac{1}{1+x-x^2}\frac{1}{1-\frac{kx(1-x)}{1+x-x^2}}=\frac{1}{1-(k-1)x+(k-1)x^2}\end{displaymath}
In other words, the transformation
$(\mathbf{Bin}\circ\mathbf{Cat})^{-1}$ takes a power $k^n$ and
maps it to the solution of the recurrence
\begin{displaymath}a_n=(k-1)a_{n-1}-(k-1)a_{n-2}\end{displaymath}
with initial conditions $a_0=1$, $a_1=k-1$. In particular, it
takes the constant sequence $1^n$ to $0^n$.

The Jacobsthal numbers J$(n)$, for instance, are transformed into the sequence with ordinary generating function
$\frac{x(1-x)}{1+x-3x^2+4x^3-2x^4}$ with general term

$b_n=\sum_{k=0}^n{{k}\choose{n-k}}\sum_{j=0}^k{{k}\choose{j}}(-1)^{n-j}\mathrm{J}(j)$.

We have
$b_n=2\sqrt{3}\sin({\pi}n/3+{\pi}/3)/9-\frac{\sqrt{3}}{18}\left\{(\sqrt{3}-1)^{n+1}-(-1)^n(\sqrt{3}+1)^{n+1}\right\}$.

We now look at
$(\mathbf{Bin}^{-1}\circ\mathbf{Cat})^{-1}=\mathbf{Cat}^{-1}\circ\mathbf{Bin}$.
As elements of the Riordan group, we obtain
\begin{displaymath}(1,x(1-x))(\frac{1}{1-x},\frac{x}{1-x})=\left(\frac{1}{1-x+x^2},\frac{x(1-x)}{1-x+x^2}\right)\end{displaymath}
Applying the inverse transformation to the family of functions
$k^n$ with generating functions $\frac{1}{1-kx}$, for instance, we
obtain
\begin{displaymath}\frac{1}{1-x+x^2}\frac{1}{1-\frac{kx(1-x)}{1-x+x^2}}=\frac{1}{1-(k+1)x+(k+1)x^2}\end{displaymath}
Thus the  transformation
$(\mathbf{Bin}^{-1}\circ\mathbf{Cat})^{-1}$ takes a power $k^n$
and maps it to the solution of the recurrence
\begin{displaymath}a_n=(k+1)a_{n-1}-(k+1)a_{n-2}\end{displaymath}
with initial conditions $a_0=1$, $a_1=k+1$. In particular, it
takes the constant sequence $1^n$ to
$2^\frac{n}{2}(\cos(\frac{{\pi}n}{4})+\sin(\frac{{\pi}n}{4}))$
(the inverse Catalan transform of $2^n$).

As a
final example, we apply the combined transformation
$\mathbf{Cat}^{-1}\circ\mathbf{Bin}$ to the Fibonacci numbers. We
obtain the sequence
\begin{displaymath}0, 1, 2, 2, 0, -5, -13, -21, -21, 0, 55, 144, 233, 233, 0, -610, -1597, \ldots\end{displaymath}
whose elements would appear to be Fibonacci numbers. This sequence has generating function
\begin{displaymath}\frac{x(1-x)}{1-3x+4x^2-2x^3+x^4}\end{displaymath}
In closed form, the general term of the sequence is
\begin{displaymath}{\phi}^n\sqrt{\frac{2}{5}+\frac{2\sqrt{5}}{25}}\sin(\frac{{\pi}n}{5}+\frac{\pi}{5})
-(\frac{1}{{\phi}})^n\sqrt{\frac{2}{5}-\frac{2\sqrt{5}}{25}}\sin(\frac{2{\pi}n}{5}+\frac{2{\pi}}{5})\end{displaymath}
where ${\phi}=\frac{1+\sqrt{5}}{2}$. \section{Acknowledgements} The author
would like to acknowledge with gratitude the constructive remarks of an anonymous
referee, whose careful reading of the original manuscript led to a
number of valuable suggestions that have improved this version.
\begin{thebibliography}{9}

\bibitem{CMS} C. Corsani, D. Merlini, R. Sprugnoli, Left-inversion of
combinatorial sums, \emph{Discrete Math.}, \textbf{180} (1998),
107--122.

\bibitem{DS} E. Deutsch and L. Shapiro, A survey of the
Fine numbers, \emph{Discrete Math.}, \textbf{241} (2001),
241--265.

\bibitem{FFA1} G. Ferri, M. Faccio and A. D'Amico, A new
numerical triangle showing links with Fibonacci numbers, \emph{The
Fibonacci Quarterly} \textbf{29.4} (1991) 316--320.

\bibitem{FFA2} G.
Ferri, M. Faccio and A. D'Amico, Fibonacci numbers and ladder
network impedance, \emph{The Fibonacci Quarterly} \textbf{30.1}
(1992) 62--67.

\bibitem{HP} P. Hilton and J. Pederson, Catalan
numbers, their generalizations, and their uses, \emph{Math.
Intelligencer} \textbf{13} (1991) 64--75.

\bibitem{Ng} S. Ng, Some
identities and formulas involving generalized Catalan number,
Preprint, 2004. Preprint available at\newline
\href{http://saturn.cs.unp.ac.za/~siuahn/default.htm}{\texttt{http://saturn.cs.unp.ac.za/$\sim$siuahn/default.htm}}

\bibitem{PW} P. Peart and W-J. Woan, Dyck paths with no peaks at height
$k$, \emph{Journal of Integer Sequences}, \textbf{4} (2001),
Article 01.1.3

\bibitem{SGW} L. W. Shapiro, S. Getu, W-J. Woan and
L.C. Woodson, The Riordan group, \emph{Discr. Appl. Math.}
\textbf{34} (1991) 229--239.

\bibitem{SL1} N. J. A.~Sloane, \emph{The
On-Line Encyclopedia of Integer Sequences}. Published
electronically at
\texttt{http://www.research.att.com/$\sim$njas/sequences/},2005

\bibitem{SL2} N. J. A.~Sloane, The On-Line Encyclopedia of Integer
Sequences, \emph{Notices of the AMS}, \textbf{50} (2003),
912--915.

\bibitem{Sp} R. Sprugnoli, Riordan arrays and
combinatorial sums, \emph{Discrete Math.},\textbf{132} (1994) pp
267--290.

\bibitem{Sun1} Y. Sun, The statistic ``number of
\emph{udu's}'' in Dyck paths, \emph{Discrete Math.}, \textbf{287}
(2004) No. 1-3, 177--186.

\bibitem{Sun2} Y. Sun, Numerical triangles
and several classical sequences, Preprint, 2004. Preprint
available at\newline 
\href{http://cfc.nankai.edu.cn/publications/04-accepted/Sun-04A2/Triangl
e.pdf}{\texttt{http://cfc.nankai.edu.cn/publications/04-accepted/Sun-04A2/Triangle.pdf}}

\bibitem{Trz} W. Trzaska, Modified Numerical Triangle and the
Fibonacci Sequence, \emph{The Fibonacci Quarterly} \textbf{29.4}
(1991) 316--320.

\bibitem{Bin} E. W. Weisstein,
http://mathworld.wolfram.com/BinomialTransform.html/,2005

\bibitem{Cat}E. W. Weisstein,
http://mathworld.wolfram.com/CatalanNumber.html/,2005

\bibitem{Fib} E. W. Weisstein,
http://mathworld.wolfram.com/FibonacciNumber.html/,2005

\bibitem{Jac} E. W. Weisstein,
http://mathworld.wolfram.com/JacobsthalNumber.html/,2005

\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B83; Secondary 05A15, 11B37, 11B65.

\noindent \emph{Keywords:} Integer transforms, Catalan numbers, Fibonacci numbers, Jacobsthal numbers.
\bigskip
\hrule
\bigskip
\noindent Concerned with sequences \seqnum{A000007},
\seqnum{A000027},\seqnum{A000035}, \seqnum{A000045},
\seqnum{A000079}, \seqnum{A000108}, \seqnum{A000129},
\seqnum{A000217}, \seqnum{A000225}, \seqnum{A000245},
\seqnum{A000344}, \seqnum{A000957}, \seqnum{A000984},
\seqnum{A001006}, \seqnum{A001045}, \seqnum{A001333},
\seqnum{A001477}, \seqnum{A001791}, \seqnum{A002057},
\seqnum{A002426}, \seqnum{A005408}, \seqnum{A007179},
\seqnum{A009545}, \seqnum{A010892}, \seqnum{A011782},
\seqnum{A014300}, \seqnum{A026641}, \seqnum{A026674},
\seqnum{A026726}, \seqnum{A038503}, \seqnum{A039599},
\seqnum{A040000}, \seqnum{A045891}, \seqnum{A059841},
\seqnum{A068875}, \seqnum{A072547}, \seqnum{A078008},
\seqnum{A081696}, \seqnum{A085478}, \seqnum{A087447}.
\end{document}
