%&latex

%will accept 10pt 11pt or 12 pt in following line
%\renewcommand{\baselinestretch}{1.3} sets the interline spacing at 
%generous double-spacing
\documentclass[12pt]{article}

\headsep -1pt
\marginparwidth 0pt
\oddsidemargin  0pt
\evensidemargin  0pt
\marginparsep 0pt
\topmargin  0pt
\textwidth   6.3in
\textheight  8.5in
\renewcommand{\baselinestretch}{1.3}
\parskip = 3mm
%\setstretch{1.5}

\usepackage{amsmath,amsthm}
\usepackage{amssymb}
%\usepackage{mathabx}
\usepackage{color}
\usepackage{xspace}
% load hyperref last
\usepackage[colorlinks=true,
linkcolor=green,
filecolor=brown,
citecolor=green]{hyperref}
\def\red{\textcolor{red} }
\def\blue{\textcolor{blue} }
\def\v{\vert}
\def\th{\theta}
\def\a{\ensuremath{\mathcal A}\xspace}
\def\b{\ensuremath{\mathcal B}\xspace}
\def\s{\ensuremath{\mathcal S}\xspace}

\renewcommand{\baselinestretch}{1.2}


\newcommand{\StirlingPartition}[2]{\genfrac{ \{ }{ \} }{0pt}{}{#1}{#2}}
\newcommand{\StirlingCycle}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}



\begin{document}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{cor}[lemma]{Corollary}
%\vspace*{-5mm}
\begin{center}
{\Large
On Generating Functions Involving the Square Root of a Polynomial                      \\ 
}


\vspace{10mm}
DAVID CALLAN  \\
Department of Statistics  \\
\vspace*{-2mm}
University of Wisconsin-Madison  \\
\vspace*{-2mm}
1300 University Ave  \\
\vspace*{-2mm}
Madison, WI \ 53706-1532  \\
{\bf callan@stat.wisc.edu}  \\
\vspace{5mm}


September 21, 2006
\end{center}



\begin{abstract}
    Many familiar counting sequences, such as the Catalan, Motzkin, 
    Schr\"{o}der and Delannoy numbers, have a generating function (GF) 
    that is algebraic of degree 2. For example, the GF for the 
    central Delannoy numbers is $\frac{1}{\sqrt{1-6x+x^{2}}}$. Here 
    we characterize GFs of the form $\frac{1}{\sqrt{1+Ax+Bx^{2}}}$ 
    that yield counting sequences and point out that they have a unified combinatorial 
    interpretation in terms of colored lattice paths. We do likewise 
    for the related forms $1-\sqrt{1+Ax+Bx^{2}}$ and 
    $\frac{1+Ax-\sqrt{1+2Ax+Bx^{2}}}{2Cx^{2}}$.

\end{abstract}



\vspace*{10mm}


{\Large \textbf{1 \quad Introduction}  } 
In this paper, all generating functions (GFs) are ordinary power 
series generating functions. Thus the GF for the formal power series 
$1+x+x^{2}+\ldots$ is $\frac{1}{1-x}$. A counting GF is one whose 
series expansion has nonnegative integer coefficients.


Many familiar counting GFs are algebraic of degree 2 and 
only involve the square root of a low-degree polynomial. 
A few such GFs are recalled in Table 1 below, with hyperlinks to the On-Line Encyclopedia of Integer Sequences \cite{oeis}.


\newpage
  \begin{center}
    \renewcommand{\arraystretch}{1.5}
   Some Algebraic Generating Functions of Degree 2 \\
   
   \vspace*{4mm}
\begin{tabular}{|c|l|c|}
    \hline
    number sequence $(a_{n})_{n\ge 0}$ & first few terms  & GF 
    $=\sum_{n\ge 0}a_{n}x^{n}$  \\
    \hline\hline
    \htmladdnormallink{even central binomial coefficients}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000984}
& 1,2,6,20,70,\ldots & 
    \raisebox{0.5ex}{ $  \frac{1}{\sqrt{1-4x}}$ } \\
    \hline
    \htmladdnormallink{odd central binomial coefficients}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001700}
 & 1,3,10,35,126,\ldots &   
     \raisebox{0.4ex}{ $ \frac{1}{2x\sqrt{1-4x}}-\frac{1}{2x}$ }\\
    \hline
    \htmladdnormallink{Catalan numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108}
 & 1,1,2,5,14,42,\ldots & 
    $\frac{1-\sqrt{1-4x}}{2x}$  \\
    \hline
    \htmladdnormallink{central trinomial coefficients}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002426}
 & 1,1,3,7,19,51,\ldots & 
     \raisebox{0.5ex}{  $\frac{1}{\sqrt{1-2x-3x^{2}}}$ }  \\
    \hline
    \htmladdnormallink{Motzkin numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001006}
 & 1,1,2,4,9,21,\ldots & 
    $\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}}$  \\
    \hline
    \htmladdnormallink{central Delannoy numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001850}
 & 1,3,13,63,321,\ldots & 
      \raisebox{0.5ex}{ $\frac{1}{\sqrt{1-6x+x^{2}}}$ } \\
    \hline
    \htmladdnormallink{big Schr\"{o}der numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006318}
 & 1,2,6,22,90,\ldots & 
    $\frac{1-x-\sqrt{1-6x+x^{2}}}{2x}$  \\
    \hline
    \htmladdnormallink{little Schr\"{o}der numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001003}
 & 1,3,11,45,197,\ldots & 
    $\frac{1-3x-\sqrt{1-6x+x^{2}}}{4x^{2}}$  \\
    \hline
\end{tabular} 

\vspace*{4mm}

Table 1
\end{center}

\vspace*{2mm}

GFs of the form $\frac{1}{\sqrt{1+Ax+Bx^{2}}}$ 
and $\frac{1+Ax-\sqrt{1+2Ax+Bx^{2}}}{Cx^{2}}$ are prominent in Table 1. 
Our main results, Theorems 1 and 2 below, 
determine all counting GFs of these two forms and give a unified 
combinatorial interpretation for them in terms of colored lattice paths. 
We define and count the relevant lattice paths in \S 2, and complete 
the proofs of Theorems 1 and 2 in \S3 using basic facts about orthogonal polynomials.
\S 4 contains some concluding remarks.

The generic unital quadratic polynomial $1+Ax+Bx^{2}$ can be written as $1-2ax +(a^{2}-4b)x^{2}$
with $a:=-A/2$ and $b:=(A^{2}-4B)/16$. 

\begin{theorem}
    Set $G_{a,b}(x)=\frac{1}{\sqrt{1-2ax+(a^{2}-4b)x^{2}}}$. Then
    
    \ \ $($i\,$)$ $G_{a,b}(x)=\sum_{n\ge 0}\Big( \sum_{k=0}^{\lfloor n/2 
    \rfloor}\binom{n}{2k}\binom{2k}{k}a^{n-2k}b^{k}\Big)x^{n}$,
    
    \ $($ii\,$)$ $G_{a,b}(x)$ is a counting GF $\Leftrightarrow a,\,b$ are 
    nonnegative integers,
    
    $($iii\,$)$ when the conditions in $($ii\,$)$ hold, $G_{a,b}(x)$ is the GF 
    for $a^{F}b^{U}$-colored trinomial paths with $x$ marking the 
    number of steps.
\end{theorem}

Theorem 1 refers to exponent $-1/2$ on the quadratic. The situation 
for exponent $+1/2$ is a little more subtle. From the identity
$1-\sqrt{1-2ax+(a^{2}-4b)x^{2}}=ax+2b\sum_{n\ge 0}\Big( \sum_{k=0}^{\lfloor n/2 
    \rfloor}\binom{n}{2k}C_{k}a^{n-2k}b^{k}\Big)x^{n+2}$ (proved below, 
$C_{k}$ is the Catalan number), it is easy to see that this is a counting 
GF $\Leftrightarrow a,\,b$ are nonnegative integers (sufficiency is 
obvious and necessity follows from just the first four coefficients: 
$a,\,2b,\,2ab,\,2a^{2}b+2b^{2}$). But then, also, it is clear that the 
greatest common divisor of all coefficients from the $x^{2}$ term 
onward is $2b$ and so it is natural to consider the refined GF 
$(1-ax-\sqrt{1-2ax+(a^{2}-4b)x^{2}})/(2bx^{2})$. 

\begin{theorem}
    Set $F_{a,b}(x)=(1-ax-\sqrt{1-2ax+(a^{2}-4b)x^{2}})/(2bx^{2})$. Then
    
    \ \ $($i\,$)$ $F_{a,b}(x)=\sum_{n\ge 0}\Big( \sum_{k=0}^{\lfloor n/2 
    \rfloor}\binom{n}{2k}C_{k}a^{n-2k}b^{k}\Big)x^{n}$,
    
    \ $($ii\,$)$ $F_{a,b}(x)$ is a counting GF $\Leftrightarrow a,\,b$ are 
    nonnegative integers,
    
    $($iii\,$)$ when the conditions in $($ii\,$)$ hold, $F_{a,b}(x)$ is the GF 
    for nonnegative $a^{F}b^{U}$-colored trinomial paths with $x$ marking the 
    number of steps.
\end{theorem}

 
\vspace*{8mm}

{\Large \textbf{2 \quad GFs for Colored Trinomial Paths}  } 
A trinomial path is a lattice path of upsteps $U-(1,1)$, downsteps 
$D=(1,-1)$ and flatsteps $F=(1,0)$ that ends at ground level, the 
horizontal line through its initial point. A trinomial $n$-path is 
one consisting of $n$ steps. The name derives from the fact that the 
number of trinomial $n$-paths is clearly the constant term in 
$(x^{-1}+1+x)^{n}$, equivalently,  the central trinomial 
coefficient $[x^{n}](1+x+x^{2})^{n}$. A nonnegative trinomial path, also known as a 
Motzkin path, is one that stays weakly above ground level. For $a,b$ 
nonnegative integers, an $a^{F}b^{U}$-colored trinomial path is one 
in which each flatstep is colored with one of $a$ specified colors and 
each upstep with one of $b$ specified colors. Using the ``symbolic'' 
method \cite{flaj} it is easy to obtain the GF, $F(x)$, for 
$a^{F}b^{U}$-colored Motzkin paths with $x$ marking the number of 
steps:
the underlying path is either of the form $F^{i}\ (i\ge 0)$ 
contributing $a^{i}x^{i}$ to the GF, or $F^{i}UPDQ\ (i \ge 0,\ P,Q$ 
arbitrary Motzkin paths) contributing $a^{i}x^{i}bx^{2}F^{2}$ to the GF. 
This yields 
\[
F(x)=\sum_{i\ge 0}a^{i}x^{i}+\sum_{i\ge 
0}a^{i}x^{i}bx^{2}F(x)^{2}= \frac{1+bx^{2}F(x)^{2}}{1-ax},
\]
a quadratic equation for $F(x)$ with (unique) 
solution 
\[
F(x)=\frac{1-ax-\sqrt{1-2ax+(a^{2}-4b)x^{2}}}{2bx^{2}}.
\]

The GF, $G(x)$, for $a^{F}b^{U}$-colored trinomial paths is obtained 
similarly. The underlying path is (i) empty contributing 1 to 
the GF, or (ii) $FP\ (P$ arbitrary trinomial path) contributing $axG(x)$ 
to the GF, or (iii) $UPDQ\ (P$ arbitrary Motzkin path, $Q$ arbitrary trinomial 
path) contributing $bx^{2}F(x)G(x)$ to the GF, or (iv) $DPUQ\ (P$ 
arbitrary inverted Motzkin path, $Q$ arbitrary trinomial 
path) also contributing $bx^{2}F(x)G(x)$ to the GF. This leads to 
$G(x)=1+axG(x) + 2bx^{2}F(x)G(x)$ whence 
\[
G(x)=\frac{1}{\sqrt{1-2ax+(a^{2}-4b)x^{2}}}.
\]

On the other hand, it is also easy to count these colored paths 
directly by number of upsteps. For Motzkin $n$-paths containing $k$ 
upsteps there are $\binom{n}{2k}$ ways to position the slanted 
steps ($U$ and $D$) among the $n$ steps. There are $C_{k}$ ways to 
arrange the slanted steps because they form a Dyck path 
\cite[Ex.\,6.19\ (i), p.\,221]{ec2}. After applying colors, this 
yields a total of $\binom{n}{2k}C_{k}a^{n-2k}b^{k}$ choices for 
$a^{F}b^{U}$-colored Motzkin $n$-paths containing $k$ $U$s. The count 
for $a^{F}b^{U}$-colored trinomial $n$-paths is the same except that 
$C_{k}$ must be replaced by $\binom{2k}{k}$.

These results are enough to prove most of both Theorems 1 and 2: part 
(iii) and the ``sufficiency'' half of part (ii) obviously follow. 
Part (i) also follows because polynomials that agree on the nonnegative 
integers are identical. Alternatively, one could prove part (i)
directly by setting $a=1$ without loss of generality, equating 
coefficients of $x^{n}$, and then using the automated WZ method 
\cite{a=b} to verify the resulting identities. It remains only to prove 
``necessity'' in part (ii).

\vspace*{8mm}

{\Large \textbf{3 \quad An Application of Orthogonal Polynomials}  } 
The ``necessity'' half of part (ii) in Theorem 1 says: if 
$p_{n}:=\sum_{k=0}^{\lfloor n/2 
\rfloor}\binom{n}{2k}\binom{2k}{k}a^{n-2k}b^{k}$ is a nonnegative 
integer for all $n\ge 0$, then $a$ and $b$ are nonnegative integers. 
Integrality of $a$ and $b$ follows immediately from the integrality of $p_{1}=a$ 
and $p_{2}=a^{2}+b$. Similarly, the nonnegativity of $a$ follows from 
that of $p_{1}$, but nonnegativity of $b$ needs that of $p_{n}$ for 
all $n$ except in the trivial case $a=0$. Assuming $a>0$, we may without 
loss of generality set $a=1$ and consider the polynomials $p_{n}(b)=\sum_{k=0}^{\lfloor n/2 
\rfloor}\binom{n}{2k}\binom{2k}{k}b^{k}$. Now nonnegativity follows from
\begin{prop}
    $p_{n}(b)\ge 0$ for all $n$ implies $b\ge 0$.
\end{prop}
Clearly, $p_{2}(b)=1+6b<0$ on $(-\infty,-1/6)$ and $p_{3}(b)=1 + 12b + 
6b^{2}<0$ on 
$(-1.91\ldots,-0.08\ldots)$, and we claim there exists a sequence of 
successively overlapping intervals $I_{n}$ that cover $(-\infty,0)$ 
such that $p_{n}(b)<0$ on $I_{n}$. Proposition 3 follows. The claim 
in turn follows from the following facts about the zeros of $p_{n}$.
\begin{prop}
    Let $m$ denote $\lfloor n/2 \rfloor$ so that $\deg(p_{n})=m$. Then
    
      \ $($i\,$)$ the zeros of $p_{n}$ are real and simple $($no repeated 
      roots$)$, say $b_{n1}<b_{n2}<\ldots <b_{nm}<0$ $($all zeros are 
      obviously negative$)$,
    
     $($ii\,$)$ the zeros of $p_{n}$ interlace those of $p_{n+1}$, 
    that is, \vspace*{-2mm}
    \[
     \renewcommand{\arraystretch}{1.25}
    \begin{array}{ccc} 
         b_{n1}<b_{n+1,1}<b_{n2}<b_{n+1,2}< \ldots 
         <b_{n,n/2}<b_{n+1,n/2}  & \hspace*{10mm} & \textrm{$n$ even}  \\
         b_{n+1,1}<b_{n1}<b_{n+1,2}<b_{n2}< \ldots 
         < b_{n+1,(n-1)/2} <b_{n,(n-1)/2}<b_{n+1,(n+1)/2}& \hspace*{10mm}  & 
         \textrm{$n$ odd},
    \end{array}
   \]
     \renewcommand{\arraystretch}{1}
    \ $($iii\,$)$ for fixed integer $k\ge 0,\ b_{n,m-k}\to 0$ as $n \to 
    \infty$.
\end{prop}
For the claim, use $I_{n}=(b_{n,m-1},b_{nm})$ and the case $k=0$ of 
part (iii). 

Parts (i) and (ii) of Proposition 4 are reminiscent of orthogonal 
polynomials and indeed the $p_{n}$ are closely related to the 
Legendre polynomials $P_{n}(x)$ which are known to form an orthogonal 
polynomial sequence. 
Recall that the GF for the Legendre polynomials is
\[
\sum_{n\ge 0}P_{n}(x)w^{n}=\frac{1}{\sqrt{1-2xw+w^{2}}}
\]
while the GF for $p_{n}$ is
\[
\sum_{n\ge 0}p_{n}(b)w^{n}=\frac{1}{\sqrt{1-2w+(1-4b)w^{2}}}.
\]
It follows that $P_{n}$ and $p_{n}$ are related by
\begin{equation}
    P_{n}(x)=x^{n} p_{n}\Big(\frac{x^{2}-1}{4x^{2}}\Big).
    \label{star}
\end{equation}
The well known properties of orthogonal polynomials imply that the 
zeros of $P_{n}(x)$ are real, simple and possess the interlacing 
property. Also, $P_{n}$ is alternately even/odd and so its zeros are 
symmetric about 0. In particular, $P_{n}$ has $m:=\lfloor n/2 \rfloor$ 
positive zeros. If $(x_{i})_{i=1}^{m}$ are the positive zeros of 
$P_{n}$ in increasing order, then by (\ref{star}), 
$\big(\frac{1}{4}(1-\frac{1}{x_{i}^{2}})\big)_{i=1}^{m}$ are the 
zeros of $p_{n}$, also in increasing order. Parts (i) and (ii) of Proposition 
4 follow.

Part (iii) is a simple consequence of (\ref{star}), the fact that 
$\cos\theta \to 0$ as $\theta \to \pi/2$, and Bruns' inequalities for 
the zeros of the Legendre polynomials, which show that the zeros of 
$P_{n}(\cos \theta)$ are fairly evenly spaced around the unit 
halfcircle. (All zeros of $P_{n}(x)$ lie in the interval $(-1,1)$, as 
is evident from (\ref{star})\,).

\textbf{Bruns' Inequalities \cite{szego}}\quad Let $\th_{1}<\th_{2}<\ldots<\th_{n}$ 
denote the zeros of $P_{n}(\cos \th)$ in the interval $(0,\pi)$. Then
\[
\hspace*{40mm}\frac{j-\frac{1}{2}}{n+\frac{1}{2}}\pi < \th_{j} < 
\frac{j}{n+\frac{1}{2}}\pi  \hspace*{20mm} j=1,2,\ldots,n.
\]

This completes the proof of Theorem 1. 

Similarly, for Theorem 2 we must show that the following result holds 
for $q_{n}(b):=\sum_{k=0}^{\lfloor n/2 
\rfloor}\binom{n}{2k}C_{k}b^{k}$. 
\begin{prop}
    $q_{n}(b)\ge 0$ for all $n$ implies $b\ge 0$.
\end{prop}
To prove Prop. 5, we again obtain a sequence of overlapping intervals 
covering $(-\infty,0)$ on the $n$th of which $q_{n}$ is negative. 
Here we find
\begin{equation}
    Q_{n}(x)=(n+1)x^{n} q_{n}\Big(\frac{x^{2}-1}{4x^{2}}\Big).
    \label{star2}
\end{equation}
where the $Q_{n}(x)$ are the Jacobi polynomials 
$J(n,1,1,x)$, which are also orthogonal. (The Legendre polynomial $P_{n}(x)$ is $J(n,0,0,x)$.)
So, as before, the two largest zeros of $q_{n}$ yield the overlapping intervals. Bruns' 
inequalities fail here but since $D_{x}\big(xq_{n}(x)\big)=p_{n}(x)$, the zeros of $p_{n}$ separate those of $q_{n}$, and 
Prop. 4\,(iii) with $k=1$ implies that the largest zero of $q_{n} \to 
0$ as $n\to \infty$ and so the overlapping intervals cover all of 
$(-\infty,0)$.

This completes the proof of Theorem 2. Table 2 below contains some OEIS 
sequences whose GFs are
of the types considered above.

\nopagebreak
 \begin{center}
    \renewcommand{\arraystretch}{1.2}

\begin{tabular}{|c|c|c|c|}
    \hline
   \rule{0ex}{3ex} & & \blue{generalized Motzkin GF} & \blue{generalized central trinomial GF}\\
     $a$  &  $b$ & 
     \raisebox{-0.8ex}{   \parbox[b]{15em}{\rule{-1ex}{6ex} 
     $ \frac{ 
     \vphantom{a_{a_{0}}} 
     %\textrm{ \raisebox{0.2ex} {$
     \displaystyle  1-ax-\sqrt{1-2ax+(a^{2}-4b)x^{2} }}{\displaystyle 
     \vphantom{D^{D^{D}}}2bx^{2}} $ }  }
   & $\frac{\displaystyle 1}{\displaystyle \sqrt{1-2ax+(a^{2}-4b)x^{2} }}$   \\
   \rule{0ex}{5ex} &   & 
 \raisebox{1ex}{   \parbox[b]{14em}{\rule{0ex}{3ex} generates this counting series }  }   &  \raisebox{1ex}{generates this counting series}   \\
    \hline\hline
  1    &  1   &  \htmladdnormallink{Motzkin numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001006}    &  \htmladdnormallink{central trinomial coefficients}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002426} 
  \\    \hline
  1    &  2   &  \htmladdnormallink{A025235}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A025235} 
  &  \htmladdnormallink{central coeff $(1+x+2x^{2})^{n}$ }{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084601} 
  \\    \hline
  1   &  3   &  --   &   \htmladdnormallink{central coeff $(1+x+3x^{2})^{n}$ }{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084603} 
 \\    \hline
  2    &  1   &  \htmladdnormallink{shifted Catalan numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108} 
   &   \htmladdnormallink{even central binomial coeffs}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000984} 
 \\    \hline
  2    &  2   &  \htmladdnormallink{restricted plane trees}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A071356} 
   &   \htmladdnormallink{restricted Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006139} 
 \\    \hline
  2    &  3   &  --   &  \htmladdnormallink{central coeff $(1+2x+3x^{2})^{n}$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084609} 
  \\    \hline
  3    &  1  & \htmladdnormallink{restricted hex polyominoes}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002212} 
    &  \htmladdnormallink{restricted Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A026375} 
  \\    \hline
  3    &  2  &  \htmladdnormallink{little Schr\"{o}der numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001003} 
   &  \htmladdnormallink{central Delannoy numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001850} 
  \\    \hline	    
  3    &  3  & \htmladdnormallink{A107264}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A107264} 
    &  --   \\    \hline
  4    &  1  &  \htmladdnormallink{walks on cubic lattice}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005572} 
   &  \htmladdnormallink{central coeff $(1+4x+x^{2})^{n}$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A081671} 
  \\    \hline
  4   &  2  & \htmladdnormallink{A068764}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A068764} 
    &  \htmladdnormallink{transform of central Delannoy}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A080609} 
  \\    \hline    
  4    &  3  &  \htmladdnormallink{eigensequence for INVERT}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007564} 
   &  \htmladdnormallink{colored Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A069835} 
  \\    \hline
  4    &  4   & \htmladdnormallink{rooted bipartite planar maps}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003645}  &  
     \htmladdnormallink{A059304}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059304} 
  \\    \hline
  4    &  5   &  --   &  \htmladdnormallink{A098443}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098443} 
  \\    \hline
  5    &  4   &  \htmladdnormallink{lattice paths w/steps $(k,\pm k)$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059231} 
   & \htmladdnormallink{central coeff $(1+5x+4x^{2})^{n}$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084771} 
   \\    \hline
  5    &  5   &  \htmladdnormallink{colored Motzkin paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A107265} 
   &  --  \\    \hline   
  5    &  6   &  --   &  \htmladdnormallink{colored Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006442} 
  \\    \hline
  6    &  8   &  \htmladdnormallink{A090442}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A090442} 
   &  \htmladdnormallink{central coeff $(1+6x+8x^{2})^{n}$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084773} 
  \\    \hline
  7    &  12   &  \htmladdnormallink{A098659}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098659} 
   &  \htmladdnormallink{central coeff $(1+7x+12x^{2})^{n}$}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A084768} 
  \\    \hline
\end{tabular}
 \nopagebreak
 
\vspace*{4mm}
Table 2 
\end{center}


\vspace*{8mm}

{\Large \textbf{4 \quad Further Remarks}  } 
The middle coefficient of $(1+ay+by^{2})^{n}$ is the constant term in 
$(y^{-1}+a+by)^{n}$ and 
and it is easy to see directly that this is the number of 
$a^{F}b^{U}$-colored trinomial $n$-paths as defined above. By Theorem 
1, then, the GF for the middle coefficient of $(1+ay+by^{2})^{n}$ is 
$(1-2ax+( a^{2}-4b)x^{2})^{-\frac{1}{2}}$.
Graham, Knuth and Patashnik \cite[p.\,575]{gkp} attribute this result to Herbert Wilf, 
citing his book \emph{generatingfunctionology} \cite{wilf} 
but it does not seem to be there! 

There is a continued fraction expansion for $F_{a,b}(x)$ of Theorem 2:
\[
\frac{1-ax-\sqrt{1-2ax+(a^{2}-4b)x^{2}}}{2bx^{2}}=
\cfrac{1}{1-ax-\cfrac{bx^{2}}{1-ax- \cfrac{bx^{2}}{1-ax- \vphantom{ 
\frac{bx^{2}}{x^{2}} }\ldots }  }}
\]
This is easy to prove directly and is a special case of a general 
theorem on combinatorial interpretation of continued fractions \cite{cf}.



\begin{thebibliography}{99}


\bibitem{oeis}Neil J.\,Sloane (founder and maintainer), The On-Line Encyclopedia of Integer Sequences
\htmladdnormallink{
http://www.research.att.com:80/~njas/sequences/index.html?blank=1}{http://www.research.att.com:80/~njas/sequences/index.html?blank=1} .


\bibitem{flaj} Robert Sedgewick and Philippe Flajolet, 
An Introduction to the Analysis of Algorithms,
Addison-Wesley, 1996.

\bibitem{ec2} Richard P.~Stanley, \emph{Enumerative Combinatorics} 
Vol.\,2, Cambridge University Press, 1999. Exercise 6.19 and related 
material on Catalan numbers are available 
online at
\htmladdnormallink{http://www-math.mit.edu/$\,\widetilde{\ }\,$rstan/ec/ }{http://www-math.mit.edu/~rstan/ec/}.


\bibitem{a=b} Marko Petkovsek, Herbert S. Wilf and Doron Zeilberger, \emph{A=B},
AK Peters, Ltd., 1996, free download available from 
\htmladdnormallink{http://www.cis.upenn.edu/\%7Ewilf/AeqB.html}{http://www.cis.upenn.edu/\%7Ewilf/AeqB.html} .


\bibitem{szego} Gabor Szego, \emph{Orthogonal Polynomials}, 4th ed., AMS, Providence, RI, 1975.

\bibitem{gkp} R.\,E.\,Graham, D.\,E.\,Knuth, Oren Patashnik, 
\emph{Concrete Mathematics} 
(2nd edition), Addison-Wesley, 1994.

\bibitem{wilf} Herbert S. Wilf, {\em generatingfunctionology}, 
Academic Press, New York, 1990,  free download available from 
\htmladdnormallink{http://www.math.upenn.edu/\%7Ewilf/DownldGF.html
}{http://www.math.upenn.edu/\%7Ewilf/DownldGF.html
} .

\bibitem{cf} Philippe Flajolet, Combinatorial aspects of continued fractions, \emph{Disc. Math.} \textbf{32} (1980)
125--161.

\end{thebibliography}



\end{document}



 $P_{n}(x)$ satisfies the defining recurrence
\[
P_{0}=1;\ P_{1}=x;\ 
P_{n}=\frac{2n-1}{n}xP_{n-1}-\frac{n-1}{n}P_{n-2}\hspace*{5mm}n\ge 2,
\]
while the GF defining $p_{n}(b)$ implies the parallel recurrence
\[
p_{0}=1;\ p_{1}=1;\ 
p_{n}=\frac{2n-1}{n}p_{n-1}-\frac{n-1}{n}(1-4b)p_{n-2}\hspace*{5mm}n\ge 2.
\]




\bibitem{gkp} R.\,E.\,Graham, D.\,E.\,Knuth, Oren Patashnik, 
\emph{Concrete Mathematics} 
(2nd edition), Addison-Wesley, 1994.

\bibitem{wilf} Herbert S. Wilf, {\em generatingfunctionology}, 
Academic Press, New York, 1990,  free download available from 
\htmladdnormallink{http://www.math.upenn.edu/\%7Ewilf/DownldGF.html
}{http://www.math.upenn.edu/\%7Ewilf/DownldGF.html
} .



http://www.math.upenn.edu/%7Ewilf/DownldGF.html



A Delannoy path is a lattice path consisting of upsteps $U=(1,1)$, downsteps 
$D=(1,-1)$ and horizontal steps $H=(2,0)$ that starts at the origin 
and ends on the $x$-axis. The size of a Delannoy path 
is $n=$ \#\,$U$s + \#\,$H$s; thus a Delannoy $n$-path ends at 
$(2n,0)$. They are counted by the (central) 
\htmladdnormallink{Delannoy number}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001850} 
  \\    \hline	    
$D_{n}$. A $(c,d)$-colored Delannoy $n$-path is one in which each horizontal 
step is given one of $c$ specified colors and each
upstep one of $d$ specified colors. 
\begin{prop}
    The GF for $(c,d)-colored Delannoy paths counted by size $n$ is 
    (1-(2c+4d)x+c^{2}x^{2})^{-\frac{1}{2}}$.
\end{prop}

\begin{prop}
    $\sum_{n \ge 0}\Big([y^{n}](1+cy+dy^{2})^{n}\Big) x^{n}=(1-2cx+( c^{2}-4d)x^{2})^{-\frac{1}{2}}$.
\end{prop}

We conclude this section with a more systematic list of functions than in Table 1, all guaranteed by Theorem 3 
to generate a counting sequence, some in OEIS \cite{oeis}, some not.