\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{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 An Asymptotic Expansion for the\\ \medskip Catalan-Larcombe-French Sequence} \vskip 1cm \large Lane Clark\\ Department of Mathematics\\ Southern Illinois University, Carbondale\\ Carbondale, IL 62901--4408\\ USA\\ \href{mailto:lclark@math.siu.edu}{\tt lclark@math.siu.edu} \\ \end{center} \vskip .5in \begin{abstract} We give an elementary development of a complete asymptotic expansion for the Catalan-Larcombe-French sequence. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \def\clktheorem{\bigskip\noindent{\bf Theorem.}\quad} \def\clktheoremlab#1#2{\bigskip\noindent{\bf Theorem #1}#2.\quad} \def\endclktheorem{\medskip} \def\clklemma#1{\bigskip\noindent{\bf Lemma #1.}\quad} \def\clklemmalab#1#2{\bigskip\noindent{\bf Lemma #1}#2.\quad} \def\endclklemma{\medskip} \def\clkremark{\bigskip\noindent{\bf Remark.}\quad} \def\clkremarks{\bigskip\noindent{\bf Remarks.}\quad} \def\endclkremark{\medskip} \def\nowhitespace{\vskip -6truept} \def\proof{\vskip 6truept\noindent{\bf Proof.}\quad} \def\endproof{\vskip 6truept} \def\qed{$\,\,\,\, \blacksquare$} \def\qed {$\,\,\,\, \blacksquare$} \def\eee{\hbox{e}\,} \def\lldots{\ldots\kern -0.8truept} % % local definitions to this paper % \def\G{{\mathfrak S}} \def\Q{\mathbb Q} \def\R{\mathbb R} \def\C{\mathbb C} \def\N{\mathbb N} \def\P{\mathbb P} \def\Z{\mathbb Z} \def\Var{\hbox{Var}} \def\Pr{\hbox{Pr}\,} \def\des{\hbox{des}} \def\ddes{\hbox{\smallft des}} \def\iinv{\hbox{\smallft inv}} \def\Des{\hbox{Des}} \def\inv{\hbox{inv}} \def\Inv{\hbox{Inv}} \def\dz{\,\text{dz}} %------------------------------------------- % HYPHENATIONS - %------------------------------------------- \hyphenation{asymptotic companion } %------------------------------------------- % DOCUMENT TITLE - %------------------------------------------- %------------------------------------------- % DOCUMENT BODY - %------------------------------------------- \section{Introduction} In their delightful paper, Larcombe and French [3] developed a number of properties of the sequence (A053175) $P_0=1$, $P_1=8$, $P_2=80$, $P_3=896$, $P_4=10816$, $\ldots$ originally discussed by Catalan~[1]. In addition to a generating function, the following formula for $P_n$ was derived % \begin{equation} P_n = \frac{1}{n!} \, \sum_{p+q=n} \binom{2p}{p} \, \binom{2q}{q} \, \frac{(2p)! \, (2q)!}{p!\, q!} \qquad (n\in \N)\, . \end{equation} % Recently, Larcombe et al.\ [4] showed that $P_n/2 \binom{2n}{n}^2 \to 1$ as $n\to \infty$ by a rather lengthy analysis. In this short paper, we give an elementary development of a complete asymptotic expansion for $P_n/2 \binom{2n}{n}^2$. We conclude with a table of numerical calculations as a companion of the theoretical results. \section{Main result} The positive integers are denoted by $\P$; the nonnegative integers by $\N$; the nonnegative rational numbers by $\Q_0$; and the complex numbers by $\C$. Let $z^0 = (z)_0 \equiv 1$ and $(z)_p = (z)\cdots (z-p+1)$ when $z\in \C$ and $p\in \P$. For $z\in \C$ and $p \in \P$, $(z)_p = \sum_{q=0}^p s(p,q) z^q$ where the $s(p,q)$ are the Stirling numbers of the first kind (see [2; pp.\ 212--214]). We write $f(z) = O(g(z))$ provided there exist real constants $C$, $D$ with $|f(z)| \le C|g(z)|$ for all $|z| \ge D$. %The empty sum is $0$ and the empty product is $1$. For $0\le p \le n$, let \[ a_p = \binom{2p}{p}^2 \, \binom{2n-2p}{n-p}^2 p!\, (n-p)! \, \in \P \] hence, $a_p = a_{n-p}$ and, let \[ b_p = \binom{2p}{p} \, \binom{2n-2p}{n-p} \in \P \] hence, $b_p = b_{n-p}$ and $a_p = n! \, b_p^2 \binom{n}{p}^{-1}$. For $0\le p \le n-1$, \[ \frac{b_{p+1}}{b_p} \, = \, \frac{(2p+1)(n-p)}{(p+1)(2n-2p+1)} \] then, for $0 \le p \le (n-1)/2$, \[ 0 < \, \frac{b_{p+1}}{b_p} \, \le 1 \] hence, for $1 \le p \le (n-1)/2$ % \begin{equation} 0 < \, \frac{b_p}{b_0} \, = \, \frac{b_p}{b_{p-1}} \, \cdots \, \frac{b_1}{b_0} \, \le 1 \end{equation} % which is correct for $p=0$ also. Fix $s \ge 1$. For $n = 2m+1 \ge 2s+3$, (1) and symmetry give \begin{align} P_n & = \, \frac{1}{n!} \, \sum_{p=0}^n \binom{2p}{p} \, \binom{2n-2p}{n-p} \, \frac{(2p)! \, (2n-2p)!}{p!\, (n-p)!} \notag \\[8pt] & = \, \frac{1}{n!} \, \sum_{p=0}^n a_p = \, \frac{2}{n!} \, \sum_{p=0}^m a_p = 2 \sum_{p=0}^m b_p^2 \binom{n}{p}^{-1} \notag \\[8pt] & = \, 2b_0^2 \left\{ \sum_{p=0}^s \left( \frac{b_p}{b_0} \right)^2 \binom{n}{p}^{-1} + \sum_{p=s+1}^m \left( \frac{b_p}{b_0} \right)^2 \binom{n}{p}^{-1} \right\} \, . \end{align} % Now $\binom{n}{p}$ is an increasing sequence of positive integers for $0 \le p \le (n-1)/2$, so (2) gives \begin{equation} 0 < \sum_{p=s+1}^m \left( \frac{b_p}{b_0} \right)^2 \binom{n}{p}^{-1} \le n \binom{n}{s+1}^{-1} = O(n^{-s}) \text{\ \ as $n\to\infty$.} \end{equation} For $0 \le p \le (n-1)/2$, \[ \frac{b_p}{b_0} \, = \binom{2p}{p} \, \frac{(n)^2_p}{(2n)_{2p}} \] hence, \begin{equation} \sum_{p=0}^s \left( \frac{b_p}{b_0} \right)^2 \binom{n}{p}^{-1} = \sum_{p=0}^s p! \, \binom{2p}{p}^2 \, \frac{(n)^3_p}{(2n)^2_{2p}} \, . \end{equation} For $z \in \C$, let $f_0(z) \equiv 1$ and, for $1\le p \le s$, let \begin{align} f_p(z) & = p! \binom{2p}{p}^2 \, \frac{(z)_p^3}{(2z)^2_{2p}} = \frac{p!\, \binom{2p}{p}^2 (z)_p}{2^{4p} z^{2p}} \, \prod_{j=1}^p \left( 1 - \, \frac{2j-1}{2z}\, \right)^{-2} \notag \\[8pt] & = \, \frac{p!\, \binom{2p}{p}^2}{2^{4p}} \, \sum_{q=0}^p s(p,q) z^{q-2p} \left\{ \prod_{j=1}^p \left( \sum_{r=0}^\infty (r+1)(j-0.5)^r z^{-r} \right) \right\} \notag \\[8pt] & = \sum_{r=p}^\infty b(p,r) z^{-r} \qquad\qquad (z\in \C; \ |z| \ge s) \end{align} % where $b(p,r) \in \Q_0$ for $r \ge p$ and $b(p,p) = p! \, \binom{2p}{p}^2 / 2^{4p}$. For $1 \le p \le s$, \begin{align*} & |(z)_p| \le (|z|+s)^p \le \left( \textstyle\frac{3}{2}|z|\right)^p \\[-3pt] & \kern 4.0in (|z| \ge 2s) \\[-3pt] & |(2z)_{2p}| \ge (2|z|-2s)^{2p} \ge |z|^{2p} \, , \end{align*} % hence, % \begin{equation} \left| \frac{(z)^3_p}{(2z)_{2p}^2} \right| \le \left( \frac{4}{|z|} \right)^p \qquad\qquad (|z| \ge 2s). \end{equation} % For $r,s \ge p\ge1$, Laurent's Theorem (see [5; V.\ 2, p.\ 6]), standard estimates for the integral and (7) give % \begin{align} \big| b(p,r) \big| & = \left| \, \frac{1}{2\pi i} \, \oint_{|z|=2s} \frac{f_p(z)}{z^{r+1}} \, \dz \, \right| \notag \\[8pt] & \le p! \, \binom{2p}{p}^2 \left( \frac{2}{s} \right)^p \, \frac{1}{(2s)^r} \, \le s! \, \binom{2s}{s}^2 \, . \end{align} % Then (8) gives % \begin{equation} \left| \sum_{r=s}^\infty b(p,r) z^{-r} \right| \le |z|^{-s} s! \, \binom{2s}{s}^2 \sum_{t=0}^\infty |z|^{-t} = O \big( |z|^{-s} \big) \, , \end{equation} % hence, (6,9) give % \begin{equation} f_p(z) = \sum_{r=p}^{s-1} b(p,r) z^{-r} + O\big( |z|^{-s}\big) \end{equation} where $f_s(z) = O\big( |z|^{-s}\big)$. %\[ % \left| \frac{(z)_p^3}{(2z)_{2p}^2} \right| % \le \left( \frac{2}{|z|} \right)^p \qquad\qquad (|z| \ge 2s) %\] %and Laurent's Theorem implies %\[ % \left| \sum_{r=s}^\infty b(r,p) z^{-r} \right| % \le \, \frac{2^s s! \, \binom{2s}{s}^2 (2s)^s}{|z|^s} % \, \sum_{t=0}^\infty % \left( \frac{2s}{|z|} \right)^{t} % = O(|z|^{-s}) %\] %hence, %\[ % f_p(z) = \sum_{r=p}^{s-1} b(r,p) z^{-r} + O(|z|^{-s}). %\] For $s \ge 1$, (10) gives % \begin{align} g_s(z) & := \sum_{p=0}^{s-1} f_p(z) \qquad\qquad (z \in \C; \ |z| \ge s) \notag \\[8pt] & \, = \sum_{r=0}^{s-1} c(s,r) z^{-r} + O(|z|^{-s}) \end{align} % where $c(s,0)=1$ for $s\ge 1$ and $c(s,r) = \sum_{p=1}^r b(p,r) \in \Q_0$ for $1 \le r \le s-1$. Observe that $c(s+1,r) = c(s,r)$ for $0 \le r \le s-1$. The analysis for $n = 2m \ge 2s+2$ is identical except that $P_n$ includes $b_m^2 \binom{n}{m}^{-1}$ not $2b_m^2 \binom{n}{m}^{-1}$. Then (3--5,11) give the following complete asymptotic expansion for $P_n / 2 \binom{2n}{n}^2$. \clktheorem Fix $s \ge 1$. There exist effectively calculable nonnegative rational numbers $c(s,0)=1$, $c(s,1)$, $\ldots$ , $c(s,s-1)$ so that % \[ P_n / 2\binom{2n}{n}^2 = \sum_{r=0}^{s-1} c(s,r) n^{-r} + O(n^{-s}) \text{\ \ as $n\to\infty$}. \quad \text{\qed} \] % %Moreover, $c(s+1,r) = c(s,r)$ for $0 \le r \le s-1$. \endclktheorem Let \[ h_s(n) = \sum_{r=0}^{s-1} c(s,r) n^{-r} \] hence, % \begin{align*} h_1(n) & = 1, \quad h_2(n) = 1 + \frac{1}{4n} \, , \quad h_3(n) = 1 + \, \frac{1}{4n} \, + \, \frac{17}{32n^2}\, , \\[8pt] h_4(n) & = 1 + \, \frac{1}{4n} \, + \, \frac{17}{32n^2} \, + \, \frac{207}{128n^3}\, \quad\text{\ and} \\[8pt] h_5(n) & = 1 + \, \frac{1}{4n} \, + \, \frac{17}{32n^2} \, + \, \frac{207}{128n^3}\, + \, \frac{14875}{2048n^4}\, . \end{align*} % Let $Q_s(n) = \big[ P_n / 2 \binom{2n}{n}^2 - h_s(n) \big] n^s$. Our theorem shows $Q_s(n) = O(1)$ as $n\to\infty$. The table below which gives the first $10$ digits of $Q_2(n)$ and $Q_3(n)$ for several values of $n$ was found using {\em Mathematica}. This provides numerical evidence for our theorem. \begin{center} \begin{tabular}[h]{rll} $n$ \ & \qquad $Q_2(n)$ & \qquad $Q_3(n)$ \\[6pt] 100 & .5481946735 & 1.6944673581 \\ 200 & .5395231003 & 1.6546200668 \\ 300 & .5367229603 & 1.6418880975 \\ 400 & .5353390483 & 1.6356193435 \\ 500 & .5345137769 & 1.6318884961 \\ 600 & .5339656896 & 1.6294137740 \\ 700 & .5335752174 & 1.6276521934 \\ 800 & .5332829178 & 1.6263343131 \\ 900 & .5330559013 & 1.6253112456 \\ 1000 & .5328744940 & 1.6244940166 \\ 2000 & .5320604149 & 1.6208298850 \\ 3000 & .5317898711 & 1.6196133523 \end{tabular} \end{center} \bigskip\bigskip \noindent{\bf Acknowledgement.}\quad I wish to thank the referee for comments and suggestions which have resulted in an improved version of the paper. \bigskip\bigskip \centerline{\bf References} \baselineskip=14truept \parskip=6truept \begin{enumerate} \item E.\ Catalan, Sur les Nombres de Segner, {\it Rend.\ Circ.\ Mat.\ Pal.} {\bf 1} (1887), 190--201. \item L.\ Comtet, Advanced Combinatorics, D.\ Reidel, Boston, MA, 1974. \item P.J.\ Larcombe and D.R.\ French, On the `Other' Catalan Numbers: A Historical Formulation Re-examined, {\it Congr.\ Numer.} {\bf 143} (2000), 33--64. \item P.J.\ Larcombe, D.R.\ French and E.J.\ Fennessey, The Asymptotic Behaviour of the Catalan-Larcombe-French Sequence $\{1,8,80,896,10816,\lldots\}$, {\it Util.\ Math.} {\bf 60} (2001), 67--77. \item A.I. Markushevich, Theory of Functions of a Complex Variable, Chelsea Publishing Co., New York, NY, 1985. \end{enumerate} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 05A16, 41A60. \noindent \emph{Keywords: } asymptotic expansion, Catalan-Larcombe-French sequence. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A053175}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 28 2002; revised version received February 2 2004. Published in {\it Journal of Integer Sequences}, March 23 2004. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document} \end{document}