\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb}
\usepackage{amsmath}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=4.00.0.2321}
%TCIDATA{Created=Thursday, April 17, 2003 10:55:03}
%TCIDATA{LastRevised=Friday, April 18, 2003 09:05:36}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{CSTFile=40 LaTeX article.cst}

\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
%\input{tcilatex}

\begin{document}

\author{G.E. Cossali \and Universit\`{a} di Bergamo-24044 Dalmine- Italy
\and cossali@unibg.it}
\title{A common generating function for Catalan numbers and other integer
sequences}
\date{}
\maketitle

\begin{abstract}
Catalan numbers and other integer sequences (like triangular numbers) are
shown to be particular cases of the same sequence array $g(n,m)=\frac{\left(
2n+m\right) !}{m!n!(n+1)!}$ . Some features of the sequence array are
pointed out and a unique generating function is proposed.
\end{abstract}

\section{Introduction}

Catalan numbers can be found in many different combinatoric problems, as
shown in [1], and exhaustive information about this sequence can be found in
[2]. In this note it will be shown that Catalan numbers (A000108) and other
known sequences (triangular numbers A000217, A034827, A001700, A002457,
A002802, A002803, A007004, A024489) can be derived by the same generating
function and are related to the same polynomial set.

\section{The polynomials $j_m(y)$}

Consider the following recurrence relation defining the polynomials $%
j_{m}(y) $: 
\begin{equation}
\begin{array}{c}
j_{0}(y)=1 \\ 
j_{m+1}\left( y\right) =y\cdot \ j_{m}\left( y\right)
+\sum_{s=0}^{m}j_{s}\left( y\right) j_{m-s}\left( y\right)%
\end{array}
\label{polyrec}
\end{equation}

It may immediately be noticed that for $y=0$ the formula coincides with the
recursive definition of the Catalan numbers: 
\begin{equation}
C_{s+1}=\sum_{m=0}^{s}C_{m}C_{s-m}  \label{catarec}
\end{equation}%
where: 
\begin{equation}
C_{n}=\frac{2n!}{n!(n+1)!}=\frac{1}{n+1}\binom{2n}{n}  \label{catadef}
\end{equation}

This means that $C_{n}$ is the zero order coefficient of the n-order
polynomial $\ j_{n}\left( y\right) $, i.e.: 
\begin{equation}
j_{m}(y)=\sum_{q=0}^{m}e(m,q)\ y^{q}  \label{jn}
\end{equation}%
and $e(m,0)=C_{m}$. The first values of $e(m,q)$ are shown in table 1.

\begin{center}
\begin{eqnarray*}
&&%
\begin{tabular}{lllllllll}
$m\;\diagdown \;q$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & 
\textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} \\ 
\textbf{0} & 1 &  &  &  &  &  &  &  \\ 
\textbf{1} & 1 & 1 &  &  &  &  &  &  \\ 
\textbf{2} & 2 & 3 & 1 &  &  &  &  &  \\ 
\textbf{3} & 5 & 10 & 6 & 1 &  &  &  &  \\ 
\textbf{4} & 14 & 35 & 30 & 10 & 1 &  &  &  \\ 
\textbf{5} & 42 & 126 & 140 & 70 & 15 & 1 &  &  \\ 
\textbf{6} & 132 & 462 & 630 & 420 & 140 & 21 & 1 &  \\ 
\textbf{7} & 429 & 1716 & 2772 & 2310 & 1050 & 252 & 28 & 1%
\end{tabular}
\\
&&\text{Table n.1. Some of the }e(m,q)\text{ coefficients}
\end{eqnarray*}
\end{center}

Equation (\ref{jn}) can be introduced into (\ref{polyrec}): 
\begin{equation*}
\sum_{q=0}^{m+1}e(m+1,q)\ y^{q}=\sum_{q=0}^{m}e(m,q)\
y^{q+1}+\sum_{s=0}^{m}\sum_{p=0}^{m-s}e(m-s,p)\ \sum_{r=0}^{s}e(s,r)\ y^{p+r}
\end{equation*}%
and transformed as follows: 
\begin{equation*}
\begin{array}{c}
\sum_{q=0}^{m+1}e(m+1,q)\ y^{q}=\sum_{q=1}^{m+1}e(m,q-1)\
y^{q}+\sum_{s=0}^{m}\sum_{p=0}^{m-s}e(m-s,p)\ \sum_{r=0}^{s}e(s,r)\ y^{p+r}=
\\ 
=\sum_{q=1}^{m+1}e(m,q-1)\ y^{q}+\sum_{p=0}^{m}\ \sum_{r=0}^{m-p}\ y^{p+r}\ 
\left[ \sum_{s=r}^{m-p}e(m-s,p)\ e(s,r)\right] = \\ 
=\sum_{q=1}^{m+1}e(m,q-1)\ y^{q}+\sum_{p=0}^{m}\ \sum_{q=p}^{m}\ y^{q}\ 
\left[ \sum_{s=q-p}^{m-p}e(m-s,p)\ e(s,q-p)\right] = \\ 
=\sum_{q=1}^{m+1}e(m,q-1)\ y^{q}+\sum_{q=0}^{m}\ \sum_{p=0}^{q}\ \ \left[
\sum_{s=q-p}^{m-p}e(m-s,p)\ e(s,q-p)\right] y^{q}= \\ 
=\sum_{q=1}^{m+1}e(m,q-1)\ y^{q}+\sum_{q=0}^{m}\ \sum_{p=0}^{q}\ \ \left[
\sum_{l=q}^{m}e(m-l+p,p)\ e(l-p,q-p)\right] y^{q}%
\end{array}%
\end{equation*}%
The following set of equations can then be obtained for any $m\in \mathbf{Z}%
^{\ast }$ ($\mathbf{Z}^{\ast }$ is the set of non-negative integer numbers):

1) for $q=0$: 
\begin{equation*}
e(m+1,0)=\sum_{s=0}^{m}e(m-s,0)\ e(s,0)
\end{equation*}
whose solution is: 
\begin{equation}
e(m,0)=C_{m}=\frac{1}{m+1}\binom{2m}{m}  \label{qzero}
\end{equation}

2) for $0<q\leq m$: 
\begin{equation}
e(m+1,q)=e(m,q-1)+\sum_{p=0}^{q}\ \ \sum_{l=q}^{m}e(m-l+p,p)\ e(l-p,q-p)
\label{enkeq}
\end{equation}

3) for $q=m+1$: 
\begin{equation}
e(m+1,m+1)=e(m,m)=\cdots =1  \label{qmax}
\end{equation}

It is useful to introduce the modified matrix $g(n,k)$ defined as: 
\begin{equation}
\begin{array}{c}
g(n,k)=e(n+k,k) \\ 
e(n,k)=g(n-k,k)%
\end{array}
\label{geconv}
\end{equation}

\begin{center}
Table 2 reports the first values: 
\begin{eqnarray*}
&&%
\begin{tabular}{lllllllll}
$m\;\diagdown \;q$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & 
\textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} \\ 
\textbf{0} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 
\textbf{1} & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 \\ 
\textbf{2} & 2 & 10 & 30 & 70 & 140 & 252 & 420 & 660 \\ 
\textbf{3} & 5 & 35 & 140 & 420 & 1050 & 2310 & 4620 & 8580 \\ 
\textbf{4} & 14 & 126 & 630 & 2310 & 6930 & 18018 & 42042 & 90090 \\ 
\textbf{5} & 42 & 462 & 2772 & 12012 & 42042 & 126126 & 336336 & 816816 \\ 
\textbf{6} & 132 & 1716 & 12012 & 60060 & 240240 & 816816 & 2450448 & 6651216
\\ 
\textbf{7} & 429 & 6435 & 51480 & 291720 & 1312740 & 4988412 & 16628040 & 
49884120%
\end{tabular}
\\
&&\text{Table n.2. \ Some values of the coefficients }g(m,q)
\end{eqnarray*}
\end{center}

\bigskip Equations (\ref{qzero}), (\ref{enkeq}), (\ref{qmax}) then become:

1) for $q=0$: 
\begin{equation}
g(n,0)=C_{n}  \label{gqzero}
\end{equation}

2) for $0<q\leq n+1$ 
\begin{equation}
g(n+1,q)=g(n+1,q-1)+\sum_{p=0}^{q}\ \ \sum_{l=0}^{n}g(n-l,p)\ q(l,q-p)
\label{gnkeq}
\end{equation}%
where $m-q$ was substituted by $n=m-q$. Moreover, from (\ref{qmax}): $%
g(0,n)=1.$

The solution of (\ref{gnkeq}) can be written as: 
\begin{equation}
g(n,q)=\frac{\left( 2n+q\right) !}{q!n!(n+1)!}=C_{n}\dbinom{2n+q}{q}
\label{gnksol}
\end{equation}

In fact, (\ref{gqzero}) is satisfied, and substituting (\ref{gnksol}) into (%
\ref{gnkeq}) : 
\begin{eqnarray}
C_{n+1}\dbinom{2(n+1)+q}{q} &=&C_{n+1}\dbinom{2(n+1)+q-1}{q-1}+
\label{solution} \\
&&+\sum_{l=0}^{n}C_{n-l}C_{l}\left[ \sum_{p=0}^{q}\ \ \dbinom{2(n-l)+p}{p}%
\dbinom{2l+q-p}{q-p}\right]
\end{eqnarray}

It is possible to show that (see appendix): 
\begin{equation*}
\sum_{p=0}^{q}\ \ \dbinom{2(n-l)+p}{p}\dbinom{2l+q-p}{q-p}=\dbinom{2n+q+1}{q}
\end{equation*}%
and: 
\begin{equation*}
\begin{array}{c}
\dbinom{2(n+1)+q}{q}-\dbinom{2(n+1)+q-1}{q-1}=\dbinom{2(n+1)+q-1}{q-1}\left[ 
\dfrac{2(n+1)+q}{q}-1\right] = \\ 
=\left\{ \dfrac{\left[ 2(n+1)+q-1\right] !}{\left[ q-1\right] !\left[ 2(n+1)%
\right] !}\right\} \left[ \dfrac{2(n+1)}{q}\right] =\left\{ \dfrac{\left(
2n+q+1\right) !}{q!\left( 2n+1\right) !}\right\} =\dbinom{2n+q+1}{q}%
\end{array}%
\end{equation*}

By using the recursive definition (\ref{catarec}) of Catalan numbers, (\ref%
{solution}) becomes an indentity.

\section{Some features of the array g(n,q)}

The sequence: 
\begin{equation*}
g(n,q)=\frac{2n+q!}{q!n!(n+1)!}=C_{n}\dbinom{2n+q}{q}
\end{equation*}%
can be seen as a generalisation of the Catalan sequence as it reduce to the
Catalan sequence for $q=0$. There are also some other interesting features,
in Table 3 are reported the known names of the integer sequences, referenced
in \textit{The On-line Encyclopedia of Integer Sequences [2], }that can be
extracted by the matrix $g(n,q)$. 
\begin{eqnarray*}
&&%
\begin{tabular}{llllllll}
&  & A000108 & A001700 & A002457 & A002802 & A002803 & none \\ 
& $m\;\diagdown \;q$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & 
\textbf{4} & \textbf{5} \\ 
- & \textbf{0} & 1 & 1 & 1 & 1 & 1 & 1 \\ 
A000217 & \textbf{1} & 1 & 3 & 6 & 10 & 15 & 21 \\ 
A034827 & \textbf{2} & 2 & 10 & 30 & 70 & 140 & 252 \\ 
none & \textbf{3} & 5 & 35 & 140 & 420 & 1050 & 2310 \\ 
none & \textbf{4} & 14 & 126 & 630 & 2310 & 6930 & 18018 \\ 
- & \textbf{5} & 42 & 462 & 2772 & 12012 & 42042 & 126126 \\ 
- & \textbf{6} & 132 & 1716 & 12012 & 60060 & 240240 & 816816%
\end{tabular}
\\
&&\text{Table n.3. }g(m,q)\text{ numbers and names of known sequences.}
\end{eqnarray*}%
\newline

The first five columns correspond to the known sequences: A000108 (Catalan),
A001700, A002457, A002802, A002803. The first two rows correspond to the
sequences A000217 ($g(1,q)$, triangular numbers) and A034827. For the other
rows and columns no reference was found by the author. Also the sequence on
the main diagonal $g(k,k)$ (1,3,30,420,6930,126126,$\ldots $) is known as
A007004 and the sequence on the diagonal $g(k,k+1)$ (1,6,70,1050,18018, $%
\ldots $) is known as A024489.

\section{Generating function}

Consider the algebraic equation in $J$: 
\begin{equation}
-xJ^{2}+(1-yx)J-1=0  \label{opera}
\end{equation}

and its solutions: 
\begin{equation}  \label{generating}
J(x,y)=\frac{(1-yx)\pm \sqrt{\left( 1-yx\right) ^2-4x}}{2x}
\end{equation}
Let now suppose that $J(x,y)$ admits the Taylor expansion in $x$ (which
exclude the solution $J(x,y)=\frac{(1-yx)+\sqrt{\left( 1-yx\right) ^2-4x}}{2x%
}$ unlimited in $x=0$) : 
\begin{equation}  \label{taylor}
J(x,y)=\sum_{m=0}^\infty j_m\left( y\right) x^m
\end{equation}

substituting (\ref{taylor}) into equation (\ref{opera}): 
\begin{equation*}
\begin{array}{c}
0=-x\sum_{m=0}^{\infty }j_{m}\left( y\right) x^{m}\sum_{m=0}^{\infty
}j_{n}\left( y\right) x^{n}+\sum_{m=0}^{\infty }j_{m}\left( y\right)
x^{m}-yx\sum_{m=0}^{\infty }j_{m}\left( y\right) x^{m}-1= \\ 
=-x\sum_{s=0}^{\infty }j_{s}\left( y\right) \sum_{m=s}^{\infty
}j_{s-m}\left( y\right) x^{s}+\sum_{m=0}^{\infty }j_{m}\left( y\right)
x^{m}-y\sum_{m=0}^{\infty }j_{m}\left( y\right) x^{m+1}-1= \\ 
=-\sum_{s=0}^{\infty }\sum_{m=0}^{s}j_{s}\left( y\right) j_{s-m}\left(
y\right) x^{s+1}+\sum_{s=0}^{\infty }j_{s}\left( y\right)
x^{s}-y\sum_{s=0}^{\infty }j_{s}\left( y\right) x^{s+1}-1= \\ 
=j_{0}(y)-1+\sum_{s=0}^{\infty }\left[ -\sum_{m=0}^{s}j_{s}\left( y\right)
j_{s-m}\left( y\right) +j_{s+1}\left( y\right) -yj_{s-1}\left( y\right) %
\right] x^{s+1}%
\end{array}%
\end{equation*}%
then: 
\begin{equation}
\begin{array}{c}
j_{0}(y)=1 \\ 
j_{s+1}\left( y\right) =y\ j_{s}\left( y\right) +\sum_{m=0}^{s}j_{s}\left(
y\right) j_{s-m}\left( y\right)%
\end{array}
\label{recursive1}
\end{equation}%
which is the recursive definition given by (\ref{polyrec}). This means that: 
\begin{equation*}
j_{m}\left( y\right) =\underset{x\rightarrow 0}{\lim }\frac{1}{m!}\frac{%
d^{m}J(x,y)}{dx^{m}}
\end{equation*}%
and for $y=0$ the function $J(x,0)$ is the generating function of the
Catalan sequence: 
\begin{equation*}
\begin{array}{c}
j_{m}(0)=C_{m} \\ 
J(x,0)=\frac{1-\sqrt{1-4x}}{2x}=C_{a}(x)%
\end{array}%
\end{equation*}%
Now, using equation (\ref{jn}) and (\ref{taylor}) : 
\begin{equation}
\begin{array}{c}
J(x,y)=\sum_{m=0}^{\infty }\sum_{q=0}^{m}e(m,q)\
y^{q}x^{m}=\sum_{q=0}^{\infty }\sum_{m=q}^{\infty }e(m,q)\ y^{q}x^{m}= \\ 
=\sum_{q=0}^{\infty }y^{q}\sum_{m=0}^{\infty }e(m+q,q)\
x^{m+q}=\sum_{q=0}^{\infty }\left( yx\right) ^{q}\sum_{m=0}^{\infty }g(m,q)\
x^{m}%
\end{array}
\label{Jxy}
\end{equation}%
then, the function: 
\begin{equation*}
L(x,z)=\frac{(1-z)-\sqrt{\left( 1-z\right) ^{2}-4x}}{2x}=J(x,z/x)
\end{equation*}%
can be expanded as (see equation (\ref{Jxy})): 
\begin{equation}
L(x,z)=\sum_{q=0}^{\infty }\sum_{m=0}^{\infty }g(m,q)\ x^{m}z^{q}
\label{Lxz}
\end{equation}%
and it can be seen as the generating function of $g(m,q)$: 
\begin{equation*}
g(m,q)=\underset{x,z\rightarrow 0}{\lim }\frac{1}{m!q!}\frac{\partial
^{m+q}L(x,z)}{\partial x^{m}\partial z^{q}}
\end{equation*}

It is interesting to observe that: 
\begin{eqnarray*}
L(x,z) &=&\sum_{q=0}^{\infty }\sum_{m=0}^{\infty }g(m,q)\
x^{m}z^{q}=\sum_{m=0}^{\infty }C_{m}\sum_{q=0}^{\infty }\dbinom{2m+q}{q}%
z^{q}x^{m}= \\
&=&\sum_{m=0}^{\infty }C_{m}T_{m}(z)x^{m}
\end{eqnarray*}%
with: 
\begin{equation*}
T_{m}(z)=\sum_{q=0}^{\infty }\dbinom{2m+q}{q}z^{q}
\end{equation*}%
and it can be proven that: 
\begin{equation*}
T_{m}(z)=\frac{1}{(1-z)^{2m+1}}
\end{equation*}%
as: 
\begin{equation*}
\frac{1}{q!}\frac{d^{q}T_{m}(z)}{dz^{q}}=\frac{(2m+1)\cdots (2m+q)}{q!\
(1-z)^{2m+1+q}}
\end{equation*}%
and: 
\begin{equation*}
\underset{z\rightarrow 0}{\lim }\frac{1}{q!}\frac{d^{q}T_{m}(z)}{dz^{q}}=%
\frac{(2m+q)!}{q!\ 2m!}=\dbinom{2m+q}{q}
\end{equation*}

The generating function $L(x,z)$ can then be written also in the form: 
\begin{equation*}
L(x,z)=\frac{1}{(1-z)}\sum_{n=0}^{\infty }C_{n}\left[ \frac{x}{(1-z)^{2}}%
\right] ^{n}=\frac{1}{(1-z)}C_{a}\left[ \frac{x}{(1-z)^{2}}\right]
\end{equation*}
that better shows the strong link existing between the sequence array $%
g(n,q) $ and the Catalan numbers

\section{Appendix}

The following binomial identity: 
\begin{equation}  \label{idbas}
\sum_{p=0}^q\dbinom{m+p}m\dbinom{n+q-p}n=\dbinom{m+n+q+1}q
\end{equation}
holds for any $m,n,q$ non-negative integers:

\begin{proof}
Let introduce the symbol: 
\begin{equation*}
M(m,n,q)=\sum_{p=0}^{q}\dbinom{m+p}{m}\dbinom{n+q-p}{n}
\end{equation*}%
then the proposition (\ref{idbas}) is equivalent to: 
\begin{equation*}
M(m,n,q)=\dbinom{m+n+q+1}{q}
\end{equation*}%
The proof is based on the use of the binomial identity: 
\begin{equation}
\sum_{k=r}^{n}\dbinom{k}{r}=\dbinom{n+1}{r+1}  \label{idbin}
\end{equation}%
that can also be written as: 
\begin{equation*}
\sum_{k=0}^{m}\dbinom{r+k}{r}=\dbinom{m+r+1}{r+1}
\end{equation*}%
The identity (\ref{idbas}) holds for $n=0$ and any $m,q$. In fact: 
\begin{equation*}
M(m,0,q)=\sum_{p=0}^{q}\dbinom{m+p}{m}\dbinom{q-p}{0}=\sum_{p=0}^{q}\dbinom{%
m+p}{m}=\dbinom{m+q+1}{m+1}=\dbinom{m+q+1}{q}
\end{equation*}%
where the binomial identity (\ref{idbin}) was used.

For any $n\neq 0$, using again (\ref{idbin}) and with $q,m\in \mathbf{Z}%
^{\ast }$: 
\begin{equation*}
\begin{array}{c}
M(m,n,q)=\sum_{p=0}^{q}\dbinom{m+p}{m}\dbinom{n+q-p}{n}=\sum_{p=0}^{q}%
\dbinom{m+p}{m}\dbinom{\left( n-1\right) +q-p+1}{\left( n-1\right) +1}= \\ 
=\sum_{p=0}^{q}\dbinom{m+p}{m}\sum_{k=0}^{q-p}\dbinom{n-1+k}{n-1}%
=\sum_{k=0}^{q}\sum_{p=0}^{q-k}\dbinom{m+p}{m}\dbinom{n-1+k}{n-1}= \\ 
=\sum_{k=0}^{q}\dbinom{q-k+m+1}{m+1}\dbinom{n-1+k}{n-1}=M(m+1,n-1,q)%
\end{array}%
\end{equation*}%
By applying repeatedly the rule $M(m,n,q)=M(m+1,n-1,q)$ it is easy to
obtain: 
\begin{equation*}
M(m,n,q)=M(m+n,0,q)=\dbinom{m+n+q+1}{q}
\end{equation*}
\end{proof}

\begin{thebibliography}{9}
\bibitem{1} R.P. Stanley. 
\newblock {\textit{Enumerative Combinatorics},
Vol. 2}. \newblock Cambridge University Press, 1999.

\bibitem{2} N.J.A. Sloane. 
\newblock {\em On-Line Encyclopedia of Integer
Sequences}. \newblock published electronically at:
http://www.research.att.com/$\sim $/njas/sequences.
\end{thebibliography}

\end{document}