\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://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 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}$ & 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. 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>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}