<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

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

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

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

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

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

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

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


\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
On Generating Functions Involving the \\
\vskip .1in
Square Root of a Quadratic Polynomial                      
}
\vskip 1cm
\large
David Callan  \\
Department of Statistics  \\
University of Wisconsin-Madison  \\
1300 University Avenue  \\
Madison, WI \ 53706-1532  \\
USA \\
\href{mailto:callan@stat.wisc.edu}{\tt callan@stat.wisc.edu}  \\
\end{center}

\vskip .2 in

\begin{abstract}
Many familiar counting sequences, such as the Catalan, Motzkin, 
Schr\"{o}der and Delannoy numbers, have a generating function 
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 determine all generating functions
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}

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


%\usepackage{amsmath,amsthm}
%\usepackage{amssymb}
%\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}



%\newtheorem{lemma}{Lemma}
%\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{cor}[theorem]{Corollary}






\vspace*{10mm}


\section{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}+\cdots$ 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}$ &amp; first few terms  &amp; 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}
&amp; 1,2,6,20,70,\ldots &amp; 
    \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}
 &amp; 1,3,10,35,126,\ldots &amp;   
     \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}
 &amp; 1,1,2,5,14,42,\ldots &amp; 
    $\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}
 &amp; 1,1,3,7,19,51,\ldots &amp; 
     \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}
 &amp; 1,1,2,4,9,21,\ldots &amp; 
    $\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}
 &amp; 1,3,13,63,321,\ldots &amp; 
      \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}
 &amp; 1,2,6,22,90,\ldots &amp; 
    $\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}
 &amp; 1,3,11,45,197,\ldots &amp; 
    $\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.
Section 4 contains a concluding remark.

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^{H}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^{H}b^{U}$-colored trinomial paths with $x$ marking the 
    number of steps.
\end{theorem}

 
\vspace*{8mm}

\section{GFs for Colored Trinomial Paths} 

A trinomial path is a lattice path of upsteps $U=(1,1)$, downsteps 
$D=(1,-1)$ and horizontal steps $H=(1,0)$ that starts at the origin and ends 
on the $x$-axis. 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, better known as a 
Motzkin path, is one that stays weakly above the $x$-axis. For $a,b$ 
nonnegative integers, an $a^{H}b^{U}$-colored trinomial path is one 
in which each horizontal step is colored with one of $a$ specified colors and 
each upstep with one of $b$ specified colors. Using Flajolet's ``symbolic'' 
method \cite{flaj} it is easy to obtain the GF, $F(x)$, for 
$a^{H}b^{U}$-colored Motzkin paths with $x$ marking the number of 
steps:
the underlying path is either of the form $H^{i}\ (i\ge 0)$ 
contributing $a^{i}x^{i}$ to the GF, or $H^{i}UPDQ\ (i \ge 0,\ P,Q$ 
arbitrary Motzkin paths) contributing $a^{i}x^{i}bx^{2}H^{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^{H}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 the equation
$G(x)=1+axG(x) + 2bx^{2}F(x)G(x)$ with solution 
\[
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^{H}b^{U}$-colored Motzkin $n$-paths containing $k$ $U$s. The count 
for $a^{H}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) (of each theorem) 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)
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}

\section{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&gt;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&lt;0$ on $(-\infty,-1/6)$ and $p_{3}(b)=1 + 12b + 
6b^{2}&lt;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)&lt;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}&lt;b_{n2}&lt;\cdots &lt;b_{nm}&lt;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}&lt;b_{n+1,1}&lt;b_{n2}&lt;b_{n+1,2}&lt; \cdots 
         &lt;b_{n,n/2}&lt;b_{n+1,n/2}  &amp; \hspace*{10mm} &amp; \textrm{$n$ even}  \\
         b_{n+1,1}&lt;b_{n1}&lt;b_{n+1,2}&lt;b_{n2}&lt; \cdots 
         &lt; b_{n+1,(n-1)/2} &lt;b_{n,(n-1)/2}&lt;b_{n+1,(n+1)/2}&amp; \hspace*{10mm}  &amp; 
         \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})\,).

\bigskip

\textbf{Bruns' Inequalities \cite{szego}}\quad Let $\th_{1}&lt;\th_{2}&lt;\cdots&lt;\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 &lt; \th_{j} &lt; 
\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}$ tends 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. Boldface $a,b$ indicate cases where the 
quadratic degenerates to a linear polynomial, that is, where $a^{2}-4b=0$.

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

\begin{tabular}{|c|c|c|c|}
    \hline
   \rule{0ex}{3ex} &amp; &amp; \blue{generalized Motzkin GF} &amp; \blue{generalized central trinomial GF}\\
     $a$  &amp;  $b$ &amp; 
     \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}} $ }  }
   &amp; $\frac{\displaystyle 1}{\displaystyle \sqrt{1-2ax+(a^{2}-4b)x^{2} }}$   \\
   \rule{0ex}{5ex} &amp;   &amp; 
 \raisebox{1ex}{   \parbox[b]{14em}{\rule{0ex}{3ex} generates this counting series }  }   &amp;  \raisebox{1ex}{generates this counting series}   \\
    \hline\hline
  1    &amp;  1   &amp;  \htmladdnormallink{Motzkin numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001006}    &amp;  \htmladdnormallink{central trinomial coefficients}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002426} 
  \\    \hline
  1    &amp;  2   &amp;  \htmladdnormallink{A025235}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A025235} 
  &amp;  \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   &amp;  3   &amp;  --   &amp;   \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
 \textbf{ 2}    &amp;  \textbf{1}   &amp;  \htmladdnormallink{shifted Catalan numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000108} 
   &amp;   \htmladdnormallink{even central binomial coeffs}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000984} 
 \\    \hline
  2    &amp;  2   &amp;  \htmladdnormallink{restricted plane trees}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A071356} 
   &amp;   \htmladdnormallink{restricted Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006139} 
 \\    \hline
  2    &amp;  3   &amp;  --   &amp;  \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    &amp;  1  &amp; \htmladdnormallink{restricted hex polyominoes}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002212} 
    &amp;  \htmladdnormallink{restricted Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A026375} 
  \\    \hline
  3    &amp;  2  &amp;  \htmladdnormallink{little Schr\"{o}der numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001003} 
   &amp;  \htmladdnormallink{central Delannoy numbers}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001850} 
  \\    \hline	    
  3    &amp;  3  &amp; \htmladdnormallink{A107264}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A107264} 
    &amp;  --   \\    \hline
  4    &amp;  1  &amp;  \htmladdnormallink{walks on cubic lattice}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005572} 
   &amp;  \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   &amp;  2  &amp; \htmladdnormallink{A068764}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A068764} 
    &amp;  \htmladdnormallink{transform of central Delannoy}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A080609} 
  \\    \hline    
  4    &amp;  3  &amp;  \htmladdnormallink{eigensequence for INVERT}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007564} 
   &amp;  \htmladdnormallink{colored Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A069835} 
  \\    \hline
  \textbf{4}    &amp;  \textbf{4}   &amp; \htmladdnormallink{rooted bipartite planar maps}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003645}  &amp;  
     \htmladdnormallink{A059304}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059304} 
  \\    \hline
  4    &amp;  5   &amp;  --   &amp;  \htmladdnormallink{A098443}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098443} 
  \\    \hline
  5    &amp;  4   &amp;  \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} 
   &amp; \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    &amp;  5   &amp;  \htmladdnormallink{colored Motzkin paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A107265} 
   &amp;  --  \\    \hline   
  5    &amp;  6   &amp;  --   &amp;  \htmladdnormallink{colored Delannoy paths}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006442} 
  \\    \hline
  6    &amp;  8   &amp;  \htmladdnormallink{A090442}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A090442} 
   &amp;  \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
   \textbf{6}    &amp;  \textbf{9}   &amp;  \htmladdnormallink{A101601}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A101601} 
   &amp;  \htmladdnormallink{A098658}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098658} 
  \\    \hline
  7    &amp;  12   &amp;  \htmladdnormallink{A098659}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098659} 
   &amp;  \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
  \textbf{8}    &amp;  \textbf{16}   &amp;  \htmladdnormallink{A098430}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A098430} 
   &amp;  -- \\    \hline
\end{tabular}
 \nopagebreak
 
\vspace*{4mm}
Table 2 
\end{center}


\vspace*{8mm}

\section{Concluding remarks}

The middle coefficient of $(1+ay+by^{2})^{n}$ is the constant term in
$(y^{-1}+a+by)^{n}$ 
and, by counting terms in the expansion, it is easy to see that this is the number of
$a^{H}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!



\begin{thebibliography}{99}


\bibitem{oeis} N. J. A. Sloane, {\it The On-Line Encyclopedia of
Integer Sequences}, \\
\href{http://www.research.att.com/~njas/sequences/index.html}{\tt http://www.research.att.com/\char'176njas/sequences/index.html} .

\bibitem{flaj} Robert Sedgewick and Philippe Flajolet, 
{\it 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
\href{http://www-math.mit.edu/~rstan/ec/}{\tt http://www-math.mit.edu/\char'176rstan/ec/} .

\bibitem{a=b} Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger, \emph{A=B},
AK Peters, Ltd., 1996. Free download available from 
\href{http://www.cis.upenn.edu/~wilf/AeqB.html}{\tt http://www.cis.upenn.edu/\char'176wilf/AeqB.html} .

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

\bibitem{gkp} Ronald L. Graham, Donald 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 
\href{http://www.math.upenn.edu/~wilf/DownldGF.html}{\tt 
 http://www.math.upenn.edu/\char'176wilf/DownldGF.html} .

\end{thebibliography}



\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } generating function, colored lattice path.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000984},
\seqnum{A001003}, 
\seqnum{A001006},
\seqnum{A001700},
\seqnum{A001850},
\seqnum{A002212},
\seqnum{A002426},
\seqnum{A003645},
\seqnum{A005572}, 
\seqnum{A006139},
\seqnum{A006318},
\seqnum{A006442},
\seqnum{A007564},
\seqnum{A025235},
\seqnum{A026375}, 
\seqnum{A059231}, 
\seqnum{A059304},
\seqnum{A068764},
\seqnum{A069835}, 
\seqnum{A071356}, 
\seqnum{A080609},
\seqnum{A081671},
\seqnum{A084601}, 
\seqnum{A084603},
\seqnum{A084609},
\seqnum{A084768}.
\seqnum{A084771},
\seqnum{A084773},
\seqnum{A090442},
\seqnum{A098430},
\seqnum{A098443},
\seqnum{A098658},
\seqnum{A098659},
\seqnum{A101601},
\seqnum{A107264}, and
\seqnum{A107265}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 24 2006;
revised version received  May 4 2007.
Published in {\it Journal of Integer Sequences}, May 7 2007.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                



</pre></body></html>