\magnification=\magstephalf \parskip1.5pt plus 0.5 pt minus 0.3 pt \font\titf=cmbx10 at 14.4 true pt \font\sc=cmcsc10 at 10pt \font\smallrm=cmr9 \def\eor{\vrule height6pt width5pt depth 0pt} \def\ref#1{\smallskip\noindent#1} \def\quote#1{{\narrower\smallskip\noindent#1\smallskip}} \def\eqdef{\mathrel{\mathop\equiv^{\rm def}}} \def\card{{\rm card}} \def\implies{\Longrightarrow} \def\SS{{\cal S}} \def\Arg{{\rm Arg}} \def\dd{\left(1+{t\cos\phi\over n}\right)^{-n}\,} \def\na{n^{-\alpha-1}} \def\Res{{\rm Res}} \def\CC{{\cal C}} \def\PP{{\cal P}} \vskip1cm \centerline{\titf SINGULARITY ANALYSIS OF} \medskip \centerline{\titf GENERATING FUNCTIONS} \vskip 0.5cm \bigskip \centerline{\sl Philippe Flajolet\footnote{\dag}{\smallrm Work of the first author was done in part while visiting Stanford University, under support from NSF grant CCR-8610181 and ONR grant N-00014-87-K-052.}} \centerline{INRIA, Rocquencourt} \centerline{78150 Le Chesnay (France)} \medskip \centerline{\sl Andrew Odlyzko} \centerline{AT\&T Bell Laboratories} \centerline{Murray Hill, New Jersey 07974 (USA)} \vskip1.3cm \noindent {\bf Abstract:} {\it This work presents a class of methods by which one can translate, on a term-by-term basis, an asymptotic expansion of a function around a dominant singularity into a corresponding asymptotic expansion for the Taylor coefficients of the function. This approach is based on contour integration using Cauchy's formula and Hankel--like contours. It constitutes an alternative to either Darboux's method or Tauberian theorems that appears to be well suited to combinatorial enumerations and a few applications in this area are outlined. } \bigskip\bigskip \centerline{\bf 1. Introduction.} \medskip\noindent Several applications in analysis, especially combinatorics, necessitate determining the asymptotic order of growth of coefficients of a function that is analytic at the origin. It has been recognized for a long time that the function's dominant singularities (the ones of smallest modulus) contain a great deal of information on the coefficients. This paper describes a very general method based on earlier works of ours ([Odlyzko 1982], [Flajolet, Odlyzko 1982]) that applies to functions of ``moderate'' variation. We restrict attention to functions with a unique dominant singularity. (Functions with a {\it finite\/} number of singularities on their circle of convergence can also be treated by a direct extension of our methods, using composite integration contours.) By normalization, we may always assume that the dominant singularity occurs at $z=1$, and we consider functions that satisfy, for some arbitrary real number $\alpha$, $$f(z)\approx (1-z)^\alpha\qquad\qquad (z\to 1).$$ \smallskip Let $f_n$ be a sequence of numbers, with a generating function $f(z)=\sum_{n\ge0}f_n z^n$ that is analytic at the origin. In non-elementary cases that we encounter in combinatorial analysis, the $f_n$ are only accessible via $f(z)$, and $f(z)$ itself is either explicitly defined by a closed-form expression or implicitly specified as the solution to a functional equation. (See for instance [Comtet 1974], [Goulden, Jackson 1983], [Stanley 1986].) The problem is thus to obtain estimates for $f_n$ from whatever analytic information is available on $f(z)$. For example, the generating function of 2-regular graphs [Comtet 1974] is $$f(z)={e^{-z/2-z^2/4}\over \sqrt{1-z}},$$ and the expansion of $f(z)$ at $z=1$, $$f(z)=e^{-3/4}\left[{1\over\sqrt{1-z}}+\sqrt{1-z}+\cdots\right],\eqno(1.1a)$$ has a matching expansion for coefficients $f_n$ as $n\to\infty$, $$\eqalign{f_n&\sim e^{-3/4}\left[{n-{1\over2}\choose n}+ {n-{3\over2}\choose n}+\cdots\right]\cr &\sim e^{-3/4}\left[{1\over\sqrt{\pi n}}+ {c\over\sqrt{n^3}}+\cdots\right].\cr }\eqno(1.1b) $$ Darboux's method is one way of achieving the term-by-term transition from (1.1a) to (1.1b). (It is succintly described, along with Tauberian methods, in Section~5.) The {\it smoothness condition\/} ensuring its validity is that the expansion (1.1a) can be pushed till an error term, sufficiently differentiable on the circle $|z|=1$, is obtained [Henrici 1977], [Bender 1974], [Comtet 1974], [Olver 1974]. We present here a general method that ensures the validity of an expansion like (1.1b), using only {\it order-of-growth\/} information on the remainder terms in the asymptotic expansion of $f(z)$ in a suitable domain of the complex plane. For instance, under suitable analytic conditions, an expansion $$f(z)\sim {1\over \sqrt{1-z}} \bigg( {c_0\over\sqrt{\log(1-z)^{-1}}}+ {c_1\over\log(1-z)^{-1}}+{c_2\over\sqrt{\log^3(1-z)^{-1}}}+\cdots \bigg) \qquad\qquad (z\to1) \eqno(1.2a)$$ ``transfers'' to coefficients as $$f_n\sim{1\over\sqrt{\pi n}} \bigg( {c_0\over\sqrt{\log n}}+ {c_1\over\log n}+ {c_2^\prime\over\sqrt{\log^3 n}}+\cdots \bigg) \qquad\qquad(n\to\infty) \eqno(1.2b)$$ (where $c_2^\prime,c_3^\prime,\ldots$ depend only on $c_0,c_1,\ldots$), but there is no way of achieving this by Darboux's method, since a remainder term introduced in (1.2a) cannot be differentiable at $z=1$ unless the expansion is trivial. \smallskip More generally, we provide sufficient conditions for the validity of the implications $$ \matrix{ f(z)=O(g(z))\hfill&\qquad\implies\qquad&f_n=O(g_n)\hfill &\qquad\qquad\qquad({\bf T1})\cr f(z)=o(g(z))\hfill&\qquad\implies\qquad&f_n=o(g_n)\hfill &\qquad\qquad\qquad({\bf T2})\cr f(z)\sim g(z)\hfill&\qquad\implies\qquad&f_n\sim g_n.\hfill &\qquad\qquad\qquad({\bf T3})\cr } $$ The conditions are that $g(z)$ should belong to a well defined asymptotic scale $\SS$, and that the asymptotic form for $f$ should be valid in a suitable domain of the complex plane, this usually requiring {\it analytic continuation\/} of $f(z)$ outside its circle of convergence. The asymptotic scale $\SS$ we consider here contains functions of $z$ of the form $$g(z)=A\big({1\over 1-z}\big) \qquad\hbox{with}\qquad A(u)\sim u^\beta (\log u)^\gamma (\log\log u)^\delta \ \ \hbox{as}\ \ (u\to\infty) $$ whose coefficients will be later proved to satisfy $$g_n\sim {1\over\Gamma(\beta)}\,{A(n)\over n}.$$ We observe from this last equation that larger singular functions at $z=1$ have larger Taylor coefficients. Thus, again under suitable conditions on $f(z)$, we are justified in applying the transfer principle from the first equation to the second equation in the pair $$ \matrix{ f(z)&=&h_0(z)+h_1(z)+\cdots+h_k(z)+O(g(z))\hfill& \hbox{with}\ \ h_0(z)\gg \cdots\gg h_k(z)\gg g(z)\hfill& \ \ (z\to1)\hfill \cr f_n&=&h_{0,n}+h_{1,n}+\cdots+h_{k,n}+O(g_n)\hfill& \hbox{with}\ \ h_{0,n}\gg\cdots\gg h_{k,n} \gg g_n \hfill& \ \ (n\to\infty)\hfill\cr} \eqno({\bf T0}) $$ when the $h_j(z)$ and $g(z)$ are in $\SS$. Asymptotic expansions in a large class translate term-by-term in a direct way. >From now on, we shall call transfer theorems of types T1, T2, T3, T0, by the more suggestive names of $O$-tranfers, $o$-transfers, $\sim$-transfers and $\Sigma$-transfers (read as ``big $O$'', ``little $o$'', ``sim'' and ``sigma'' transfers!). The most basic transfers are $O$-transfers. A refinement of the proof of a $O$-transfer will usually lead to a $o$-transfer. As a direct consequence of $o$-transfers, we obtain $\sim$-transfers since $$f(z)\sim g(z)\qquad\hbox{is equivalent to}\qquad f(z)=g(z)+o(g(z)).$$ As indicated in the previous paragraph, $\Sigma$-transfers follow directly from $O$-transfers for expansions with an $O(.)$ remainder term as in $(T0)$ and there is an obvious analogue for $o$-transfers where we have an $o(.)$ remainder term. A side issue to be considered is the determination of coefficients of standard singular functions (here, the scale $\SS$). Fortunately, that task can itself be carried out by methods rather similar to the proofs of transfer theorems. \smallskip Several of our statements are inspired by Tauberian theorems, most notably the Hardy-Littlewood theorem [Hardy, Littlewood 1914], though our analysis is quite different since it is based on contour integration. It is clearly less deep, but it has the advantage of great technical simplicity. Tauberian theorems impose no condition on the function, but they require {\it a priori\/} ``side conditions'' on the coefficients (positivity, monotonicity, etc) [Titchmarsh 1939], [Hardy 1949], [Postnikov 1980]. Our method imposes conditions on the function in the complex domain, but no {\it a priori\/} condition on the coefficients. That approach is therefore quite adequate for obtaining expansions of the $\Sigma$-type, for which Tauberian methods tend to be of little help (side-conditions are hard to establish on error terms). Furthermore, in the context of combinatorial enumerations, large classes of generating functions are expected to be analytically continuable since they are obtained as combinations of analytic functionals applied to entire functions. In that context, our conditions are seldom a limitation. \smallskip The paper is organized as follows. In Section 2, we start with a restricted scale $\SS_0$ that contains only functions of the form $(1-z)^{\alpha}$, where $\alpha$ is {\it any\/} (positive or negative) real number. The $O$-transfer theorem (Theorem 1) that covers all values of $\alpha$ requires analytic continuation of $f(z)$ in an angular domain outside its circle of convergence, and validity of the asymptotic expansions there. It is proved --~as are all other results in this paper~-- by choosing a suitable contour (reminiscent of Hankel contours) in Cauchy's integral formula for coefficients of analytic functions, and ``integral splitting''. A modification of the proof gives us $o$-transfers (Corollary 1), from which we deduce $\sim$-transfers (Corollary 2) and a variety of $\Sigma$-transfers of which Corollary 3 is only a typical example. These results, though later generalized, are treated in some detail, as they serve to introduce basic techniques without unnecessary complications. Our next objective, in Section~3, is to extend these theorems to the larger class $\SS$ that has logarithms and iterated logarithms. We first establish (Theorem 2 and Corollary 4) general $O$- and $o$-transfer results for that class. More precise asymptotic estimates require us to characterize the growth of Taylor coefficients of functions that belong to the scale $\SS$ (Theorem 3). This is done by using Hankel contours and modifications of the integral splitting techniques employed in our earlier proofs. Of the variety of conceivable $\sim$-transfers and $\Sigma$-transfers, we only state Corollaries 5 and 6, which correspond to functions with a descending expansion involving powers of logarithms or iterated logarithms. Section 4 discusses various possible extensions. When $\alpha<-1$, so that $f(z)\approx(1-z)^\alpha$ is ``large'' at its singularity, the conditions on the function to be analyzed can be weakened somewhat (Theorem~4). Also, a superset of $\SS$ that includes functions of ``slow variation'' towards infinity is shown to be amenable to transfer methods. Section 5 is a brief discussion of the relation to Darboux's method and Tauberian theorems. We finally conclude, in Section 6, by sketching the transfer part of a few applications to combinatorial enumerations and the analysis of algorithms. \smallskip {\sl Relation to other works}. The Hankel contours are classical tools in the study of the Gamma and Zeta functions [Whittaker, Watson 1927]. They appear to be well suited to extract asymptotic information on coefficients of analytic functions. They have been used in combinatorial applications in [Odlyzko 1982] and [Flajolet, Odlyzko 1982], and in another context (enumeration of polynomials over finite fields) by Car [Car 1982], [Car 1984]. Some results similar to ours, but requiring different analytic conditions, have been derived by [Wong, Wyman 1974]. In analytic number theory, Hankel contours are useful in the study of Dirichlet series with algebraic singularities by means of Perron's formula, a typical example being the sudy of the coefficient of $[n^{-s}]$ in $(\zeta(s))^{1/2}$ [Selberg 1954], [Hardy 1940, p.~62]. They are also useful in the inversion of Laplace or Mellin transforms with algebraic or logarithmic singularities [Doetsch 1955, p.~158]. Techniques of Sections 2 and 3 also bear some resemblance to the Watson-Doetsch lemma for Laplace transforms [Henrici 1977, p.~389]. \bigskip \centerline{\bf 2. A Basic Transfer Theorem.} \medskip\noindent We let $\SS_0$ be the class of functions $g_\alpha(z)=K(1-z)^{\alpha}$ for $\alpha$ a real number and $K$ a constant. The Taylor coefficients of any member of $\SS_0$ are known both exactly\footnote{\dag}{We let as usual $[z^n]f(z)$ denote the coefficient of $z^n$ in the Taylor expansion of $f(z)$: If $f(z)=\sum_n f_n z^n$, then $[z^n]f(z)=f_n$.} $$[z^n]\,(1-z)^\alpha ={n-\alpha-1\choose n} ={\Gamma(n-\alpha)\over \Gamma(-\alpha)\Gamma(n+1)} \eqno(2.1)$$ and asymptotically from Stirling's formula ($\alpha\not\in\{0,1,2,\ldots\}$): $$\eqalign{ &[z^n]\,(1-z)^\alpha\sim{n^{-\alpha-1}\over\Gamma(-\alpha)} \bigg[1+{\alpha(\alpha+1)\over2n}+ {\alpha(\alpha+1)(\alpha+2)(3\alpha+1)\over 24 n^2}+\hfill\cr &\ \ \ +{\alpha^2(\alpha+1)^2(\alpha+2)(\alpha+3)\over48 n^3} + {\alpha(\alpha+1)(\alpha+2)(\alpha+3)(\alpha+4)(15\alpha^3+30\alpha^2+5\alpha-2)\over 5760 n^4} +\cdots\bigg].\cr } \eqno(2.2)$$ Thus the binomial coefficients (2.1), as well as their main asymptotic equivalents in (2.2), form an asymptotic scale. There is in fact a general form of (2.2). \smallskip\noindent {\sc Proposition 1.} {\sl The binomial coefficients expressing $[z^n](1-z)^\alpha$ have an asymptotic expansion as $n\to\infty$, $$[z^n](1-z)^\alpha \sim {n^{-\alpha-1}\over\Gamma(-\alpha)} \left(1+\sum_{k\ge1}{e_k^{(\alpha)}\over n^k} \right), \qquad\qquad \alpha\not\in\{0,1,2,\ldots\}, \eqno(2.3) $$ where} $$e_k^{(\alpha)}= \sum_{l=k}^{2k} (-1)^l \lambda_{k,l} (\alpha+1)(\alpha+2)\cdots(\alpha+l) %l=k to 2k-1 \qquad\hbox{\sl with}\qquad \sum_{k,l\ge0}\lambda_{k,l}v^kt^l= % [v^kt^l] e^t(1+vt)^{-1-1/v}. \eqno(2.4) $$ \smallskip\noindent Proposition 1, though it would probably follow by close inspection of Stirling's formula, is most easily proved by techniques introduced in Section 3, so that we delay the proof till then. We also observe incidentally that in (2.1),(2.2),(2.3), $\alpha$ may be complex: If $\alpha=\sigma+it$, we have $$[z^n](1-z)^{\alpha}\sim {n^{-\sigma-1}\over\Gamma(-\sigma-it)} \big[\cos(t\log n)-i\sin(t\log n)\big]. $$ In that case, the main term in (2.2), (2.3) is of order $n^{-\sigma-1}$ and it is multiplied by a periodic function of $\log n$. \smallskip We now propose to prove a transfer condition of the $O$-type. We give the proof in some detail for two reasons: first, the implied constants in the $O$'s are ``constructive'' and tight, a fact of independent interest; second, it serves as a guiding pattern for deriving later a variety of transfer conditions. We let $\Delta\equiv\Delta(\phi,\eta)$ denote the closed domain $$\Delta(\phi,\eta)=\{z\ /\ |z|\le 1+\eta,\ |\Arg(z-1)|\ge\phi\}, \eqno(2.5)$$ where we take $\eta>0$ and $0<\phi<{\pi\over2}$. This domain has the form of an indented disk depicted on Figure 1a. \smallskip\noindent {\sc Theorem 1.} {\sl Assume that, with the sole exception of the singularity $z=1$, $f(z)$ is analytic in the domain $\Delta=\Delta(\phi,\eta)$, where $\eta>0$ and $0<\phi<{\pi\over2}$. Assume further that as $z$ tends to 1 in $\Delta$, $$f(z)=O(|1-z|^\alpha),\eqno(2.6a)$$ for some real number $\alpha$. Then the $n$-th Taylor coefficient of $f(z)$ satisfies} $$f_n=[z^n]f(z)=O\left(n^{-\alpha-1}\right).\eqno(2.6b)$$ \smallskip\noindent {\sc Proof.} Since the modulus of $(1-z)^\alpha$ is bounded below by a constant $>0$ in any compact set in $\Delta$ that does not contain $1$, and $f(z)$ is analytic in such a set, the {\it local\/} condition (2.6a) of the theorem is equivalent to assuming that for some constant $K>0$, we have in the {\it whole\/} of $\Delta$ with the possible exception of $z=1$, $$|f(z)| % \left|1+{2t\over n}\cos\phi\right|^{1/2}. \eqno(2.11)$$ Thus, from (2.10) and (2.11), we find $$f_n^{(2)}<{J_n\over2\pi} (Kn^{-\alpha-1}) \qquad\hbox{where}\qquad J_n=\int_1^\infty t^\alpha \left(1+{t\cos\phi\over n}\right)^{-n}\,dt \eqno(2.12) $$ It is now easy to see that as $n\to\infty$, $$J_n\to \int_1^\infty t^{\alpha} e^{-t\cos\phi}\,dt$$ and hence all the $J_n$ are bounded above by some constant which depends only on $\alpha$ and $\phi$. In fact, for positive $\lambda$, function $(1+\lambda/n)^{-n}$ is a monotone decreasing function of $n$. In summary, we have proved that %with $\nu=2|\alpha|+4$, $$f_n^{(2)}<{J(\alpha,\phi)\over2\pi} (K n^{-\alpha-1}) \qquad\hbox{where}\qquad J(\alpha,\phi)= % \sup_{n\ge2|\alpha|+4}\, \int_1^\infty t^\alpha \left(1+{t\cos\phi\over \nu}\right)^{-\nu}\,dt \ \ \hbox{and}\ \ \nu=2|\alpha|+4. \eqno(2.13) $$ The fact that $\phi$ is strictly less than ${\pi\over2}$, whence $\cos\phi>0$, is obviously crucial to this part of the analysis. \smallskip 3. {\it Larger circle.} The majorization of $f_n^{(3)}$ gives an exponentially decreasing term: $$\eqalign{ f_n^{(3)}&<{1\over2\pi}\cdot K\eta^{\alpha} \cdot\big(1+\eta\big)^{-n-1}\cdot \big(2\pi(1+\eta)\big)\cr &0$ such that in the whole of $\Delta$, $|f(z)|0$, there exists a $\delta=\delta(\epsilon)>0$ such that for $z$ in $\Delta$, $$|z-1|<\delta \qquad\implies\qquad |f(z)|<\epsilon |1-z|^\alpha.$$ We need to prove, with some fixed constant $K^\prime>0$, that for any $\epsilon>0$, there exists an $n_0=n_0(\epsilon)$ such that $$|f_n|<\epsilon K^\prime n^{-\alpha-1} \qquad\hbox{whenever}\qquad n\ge n_0(\epsilon).$$ In the following derivations, the constants also depend on $\alpha$, $\phi$ and $\eta$, but we shall only indicate the dependence on $\epsilon$. We choose a fixed (but arbitrary) $\epsilon$, with its associated $\delta=\delta(\epsilon)$. \smallskip 1. {\it Smaller circle.} For the part $\gamma_1$ of the contour, we first choose $n_1=n_1(\epsilon)$ such that $1/n_1\le \delta(\epsilon)$. This choice ensures that part $\gamma_1$ of the contour is inside a domain where $|f(z)|<\epsilon|1-z|^\alpha$, and thus for $n>n_1$, as in Equation (2.9), $$f_n^{(1)}< 5(\epsilon n^{-\alpha-1}).\eqno(2.18)$$ \smallskip 2. {\it Rectilinear part.} Following the lines of Equations (2.10)-(2.11), with $z=1+\omega t/n$, we have $$f_n^{(2)}<{1\over2\pi} \int_1^{En} \left|f(1+{\omega t\over n})\right|\,\dd\,{dt \over n}. \eqno(2.19) $$ We now decompose the integral in (2.19), and set $f_n^{(2)}=f_n^{(21)}+f_n^{(22)}$, where $$f_n^{(21)}={1\over2\pi}\int_1^{\log^2n} \qquad\hbox{and}\qquad f_n^{(22)}={1\over2\pi}\int_{\log^2n}^{En}.$$ We can choose $n_{21}=n_{21}(\epsilon)$ such that for all $n\ge n_{21}$, we have $\log^2n/n<\delta(\epsilon)$, and then $1+\omega t/n$ is in the ``epsilon region'' of $f$. Thus $$\eqalign{ f_n^{(21)}&<{1\over 2\pi} \int_{1}^{\log^2n} \epsilon \left({t\over n}\right)^\alpha \,\dd\,{dt\over n}\cr &<(\epsilon n^{-\alpha-1}) \cdot{1\over2\pi}\int_{1}^\infty t^\alpha \,\dd\,dt.\cr } \eqno(2.20)$$ >From the argument used for Eq (2.13), we find $$f_n^{(21)}<(\epsilon n^{-\alpha-1}) {J(\alpha,\phi)\over2\pi}. \eqno(2.21) $$ By similar devices, we get for $f_n^{(22)}$ the bound $$f_n^{(22)}<(Kn^{-\alpha-1})\, {1\over2\pi}\int_{\log^2n}^{En} t^\alpha \,\dd\,dt. \eqno(2.22)$$ The integrand in (2.22) is already exponentially small at $t=\log^2n$. Without loss of generality, we may assume (by taking $\eta$ small enough) that $E<1/(4\cos\phi)$. This guarantees $u=t\cos\phi/n<1/4$, so that, in the given range of values of $t$, $\log(1+u)>u/2$ and $$\dd<\exp\left(-{\cos\phi\over2}\log^2n\right).$$ Thus the integral in (2.22) is (say) $0$ and $|\theta|\le\pi-\phi$ (see Section~4 for a more complete discussion). \smallskip\noindent {\sc Theorem 2.} {\sl Assume that, with the sole exception of the singularity $z=1$, $f(z)$ is analytic in the domain $\Delta=\Delta(\phi,\eta)$, where $\eta>0$ and $0<\phi<{\pi\over2}$. Assume further that as $z$ tends to 1 in $\Delta$, $$f(z)=O\left( (1-z)^\alpha L\big({1\over1-z}\big)\right) \qquad\hbox{where} \qquad L(u)=(\log u)^\gamma (\log\log u)^\delta, \eqno(3.2a) $$ for some real numbers $\alpha$, $\gamma$, $\delta$. Then the $n$-th Taylor coefficient of $f(z)$ satisfies} $$ f_n=[z^n]f(z)=O\left(n^{-\alpha-1}L(n)\right) \eqno(3.2b) $$ \smallskip\noindent {\sc Proof.} Logarithms are taken with their principal determination. Without loss of generality, we may assume that $\eta$ is small enough. Evaluation of the various contributions to Cauchy's integral proceeds very much like in the proof of Corollary 1. \smallskip 1. {\it Smaller circle.} Using trivial bounds, we find with $z=1-e^{i\theta}/n$, and $\theta$ varying in $[-(\pi-\phi),\pi-\phi]$, $$f^{(1)}_n=O\big(\na M_1(n)\big) \qquad\hbox{where}\qquad M_1(n)=\sup_{\theta} |L(ne^{-i\theta})|. $$ It is easy to see that $L(u)$ does not vary much along any arc of a large circle centered at the origin, so that $M_1(n)\sim L(n)$ as $n\to\infty$, and $$f^{(1)}_n=O\big(n^{-\alpha-1}L(n)\big). \eqno(3.3)$$ \smallskip 2. {\it Rectilinear contour.} We set $z=1+\omega t/n$, and use the same splitting as in Corollary 2: $f_n^{(2)}=f_n^{(21)}+f_n^{(22)}.$ First, we have $$f_n^{(21)}=O\left(n^{-\alpha-1}M_2(n)\int_1^{\log^2n} t^\alpha \dd dt \right) \ \ \hbox{where}\ M_2(n)=\sup_{t\in [1,\log^2n]} L(-{n\over \omega t}). \eqno(3.4) $$ Again, the ``slow variation'' of $L(u)$ towards infinity entails that $M_2(n)\sim L(n)$. The integral in (3.4) is $O(1)$, hence $$f_n^{(21)}=O\left(n^{-\alpha-1}L(n)\right). \eqno(3.5)$$ We now turn to $f_n^{(22)}$, for which we have $$f_n^{(22)}<{Kn^{-\alpha-1}\over2\pi} \int_{\log^2n}^{En} t^{\alpha} \big|L(-{n\over\omega t})\big|\,\dd dt. \eqno(3.6)$$ When $z$ is on $\gamma_2$, quantity $u(t)=-n/\omega t$ goes from an area (for $t=En$) where it is $O(1)$ to a neighbourhood of infinity as $e^{-i(\pi-\phi)}\infty$ (for $t=\log^2n$). Over $u(\gamma_2)$, function $L(u)$ is upperbounded by a linear function of $|u|$. (Actually, it cannot grow faster then $|u|^\epsilon$). We thus have $|L(u)|From the bound (3.12) for $f_n^{(3)}$, we see that the same expansion (3.17) holds for $f_n$. All that remains is to compute the $G_k$. But, by a familiar integral [Whittaker, Watson 1927, p.~245], we have $$ G_0\equiv{1\over2i\pi}\int_H (-t)^\alpha e^{-t}\,dt ={1\over\Gamma(-\alpha)} ,$$ and obviously $G_k$ is the $k$-th derivative of $G_0$ with respect to $\alpha$. Our proof is now complete.~~\eor \smallskip\noindent {\sc Theorem 3B.} {\sl Let $\alpha$, $\gamma$ and $\delta$ be complex numbers not in $\{0,1,2,\ldots\}$. Define the function $f(z)$ by $$f(z)=(1-z)^\alpha\left({1\over z}\log{1\over 1-z}\right)^\gamma \left({1\over z}\log\left({1\over z}\log{1\over 1-z}\right)\right)^\delta $$ Then, the Taylor coefficients of $f(z)$ satisfy $$f_n\sim {\na\over\Gamma(-\alpha)} (\log n)^\gamma (\log\log n)^\delta \left(1+ \sum_{k\ge1}{e_k(\log\log n)\over (\log n\log\log n)^k} \right), $$ %where $e_k(x)=e_k^{(\alpha,\gamma,\delta)}(x)$ is a polynomial of degree $k-1$, %$$e_k(x)= %\Gamma(-\alpha)\left({d^k\over d\alpha^k} {1\over\Gamma(-\alpha)}\right) %\sum_{j=0}^{k-1}(-1)^j{\delta\choose j}(k-j)!s_{k,k-j}x^j. %$$ %and $s_{k,l}$ is a Stirling number of the first kind,} %$$s_{k,l}=[v^l]\,v(v+1)(v+2)\cdots(v+k-1).$$ where $e_k(x)=e_k^{(\alpha,\gamma,\delta)}(x)$ is a polynomial of degree $k$,} $$e_k(x)=\Gamma(-\alpha){d^k\over ds^k}{1\over\Gamma(-s)}\bigg|_{s=\alpha} \cdot E_k(x)\qquad\hbox{\sl with}\qquad \sum_{k=0}^\infty E_k(x)u^k=\big(1-xu\big)^\gamma\big(1-{1\over x}\log(1-xu)\big)^\delta.$$ \smallskip\noindent {\sc Proof.} (Sketch). The proof starts with the analog of Eq (3.14), $$n^{\alpha+1} f_n={1\over2i\pi} \int_{H_1} (-t)^\alpha \big(\log(-{n\over t})\big)^\gamma \big(\log\log(-{n\over t})\big)^\delta e^{-t}\,dt+O\big({(\log n)^\gamma (\log\log n)^\delta\over n}\big). \eqno(3.18) $$ and uses (3.15) together with $$ \left(\log\log(-{n\over t})\right)^\delta = (\log\log n)^\delta \left(1+{1\over\log\log n}\log(1-{\log(-t)\over \log n}) \right)^\delta. \eqno(3.19) $$ The right side of (3.19) can then be expanded in descending powers of $\log n$ and $\log\log n$, etc.~~\eor \smallskip The same line of proof now enables us to prove the basic asymptotic estimate for the binomial coefficients already announced in Proposition 1. \smallskip\noindent {\sc Proof of Proposition 1.} Using again a variant of (3.13)-(3.14), we find that $$[z^n](1-z)^\alpha\sim {n^{-\alpha-1}\over\Gamma(-\alpha)} \cdot {1\over2i\pi}\int_{H_1}(-t)^\alpha \left(1+{t\over n}\right)^{-n-1}\,dt \eqno(3.20) $$ and it is the expansion $$\left(1+{t\over n}\right)^{-n-1}= e^{-t}\left(1+{t^2-2t\over 2n}+ {6t^4-40t^3+48\over 48 n^2} +\cdots\right) \eqno(3.21) $$ in descending powers of $1/n$ that provides an explicit form of the $e_k^{(\alpha)}$. \eor \smallskip There are obvious $\sim$- and $\Sigma$-transfer results that follow from these equations. We only cite two simple analogues of Corollary 3. \smallskip\noindent {\sc Corollary 5.} {\sl Assume that $f(z)$ is analytic in $\Delta\setminus\{1\}$, and that as $z\to1$ in $\Delta$, $$f(z)=(1-z)^\alpha \big(\log{1\over 1-z}\big)^\gamma\, \left[ \sum_{j=0}^{m-1} c_j \big(\log{1\over1-z}\big)^{-j} +O\big(\big(\log{1\over 1-z}\big)^{-m}\big) \right] \eqno(3.22a)$$ for some $\alpha,\gamma \not\in\{0,1,2,\ldots\}$. Then as $n\to\infty$,} $$ f_n={n^{-\alpha-1}\over\Gamma(-\alpha)} \log^\gamma n \left[ \sum_{j=0}^{m-1} c_j^\prime \log^{-j}n +O(\log^{-m} n)\right]. \eqno(3.22b) $$ \smallskip\noindent {\sc Proof.} We only need to check that in expansion (3.22a), replacing $$\big(\log{1\over1-z}\big)^\gamma \qquad\hbox{by}\qquad \big({1\over z}\log{1\over1-z}\big)^\gamma $$ introduces error terms that are of order $(1-z)^{\alpha-1}(\log(1-z))^\gamma$, using the expansion of $1/z$ at $z=1$. We then conclude by an application of Theorem 3A and Theorem 2. The $c_j^\prime$ are computable from the $c_j$ by the expansion of Theorem 3A. \eor \smallskip\noindent {\sc Corollary 6.} {\sl Assume that $f(z)$ is analytic in $\Delta\setminus\{1\}$, and that as $z\to1$ in $\Delta$, $$f(z)=(1-z)^\alpha \big(\log{1\over 1-z}\big)^\gamma \big(\log\log{1\over 1-z}\big)^\delta\, \left[ \sum_{j=0}^{m-1} c_j \big(\log\log{1\over1-z}\big)^{-j} +O\big(\big(\log\log{1\over 1-z}\big)^{-m}\big) \right] \eqno(3.23a)$$ for some $\alpha,\gamma \not\in\{0,1,2,\ldots\}$. Then as $n\to\infty$,} $$ f_n={n^{-\alpha-1}\over\Gamma(-\alpha)} (\log n)^\gamma (\log\log n)^\delta \left[ \sum_{j=0}^{m-1} c_j(\log\log n)^{-j} +O\big((\log\log n)^{-m}\big)\right]. \eqno(3.23b) $$ (The coefficients $c_j$ are the same in both expansion.) \smallskip A few historical remarks on the ancestry of Theorem 3 and particular cases not yet explicitly covered are due here. We assumed in the statement of Theorem 3A that neither $\alpha$ nor $\gamma$ are integers. This leaves three cases to be discussed that can also be treated by our methods. \smallskip \item{1.} The case where $\gamma$ is an integer and $\alpha$ not an integer was studied by Jungen [1931]. That important paper\footnote{\dag}{ Jungen proves the classical theorem: {\sl The Hadamard product of a rational function and an algebraic function is an algebraic function.} It may be of interest to combinatorialists to note that this theorem has a multivariate non-commutative ``lifting'' due to Sch\"utzenberger, a special form of which is: {\sl The intersection of a regular language and a context-free language is a context-free language.}} was partly motivated by Hadamard products and singular differential systems with regular singular points. There Jungen makes use of a method introduced by Fr\"obenius (and classical in the study of differential systems) that consists in starting from the binomial expansion (2.1) of $(1-z)^\alpha$ and differentiating with respect to the parameter $\alpha$ to deduce, with $\gamma=k$ an integer, $$[z^n](1-z)^\alpha \log^k{1\over1-z}\sim {\na\over\Gamma(-\alpha)} \left[ E_0(\log n)+{E_1(\log n)\over n}+{E_2(\log n)\over n^2}+\cdots \right], $$ where the $E_j$ are polynomials are of degree at most $k$. In other words, the expansion of our Theorem 3A terminates, and more terms in descending powers of $n$ can be obtained. Another derivation, on which we partly based our proof of Theorem 3, is given by [Flajolet, Puech 1986]. \smallskip \item{2.} When $\alpha$ is a positive integer, $1/\Gamma(-\alpha)=0$, so that the first term in the coefficient expansion of Theorem 3A vanishes and the expansion ``jumps'' to the next term in descending powers of $\log n$. For instance, we have $$[z^n]{1\over \log(1-z)^{-1}}\sim {C\over n\log^2n}. $$ P\'olya cites without proof an example of this case in [Polya 1954, p.9]. P\'olya was also Jungen's advisor so that several of our theorems were probably known (or obvious) to him! \smallskip \item{3.} When both $\alpha$ and $\gamma$ are positive integers, coefficients $f_n$ are $\alpha$-th order differences of integral powers of a logarithm and explicit forms are directly available by the calculus of finite differences. For instance, with $\alpha=k$ (a positive integer) and $\gamma=1$, we have $$[z^n](1-z)^k\log{1\over1-z}=(-1)^k{k!\over n(n-1)\cdots(n-k)}. $$ In this context, one may refer to a short note by Zave [1976] that discusses the case where $\gamma$ is an integer and $\alpha$ a {\it negative\/} integer. This is directly covered by our Theorem 3A, but Zave gives an interesting direct derivation using Bell polynomials and generalized harmonic numbers. \smallskip\noindent In other words, {\sl the results of Theorem 3A remain valid when any of $\alpha$, $\gamma$ may be a positive integer provided we interpret $1/\Gamma(-\alpha)$ as $0$, for $\alpha$ a non negative integer, and terminate descending expansions appropriately when terms become identically zero}. We leave to the reader the pleasure of working out by herself the degeneracy cases for Theorem 3B. \smallskip The first few terms of expansions in Theorems 3A, 3B are given below: $$\eqalign{ &[z^n](1-z)^\alpha\bigg({1\over z}\log{1\over1-z}\bigg)^\gamma= {n^{-\alpha-1}\over\Gamma(-\alpha)}(\log n)^\gamma\bigg[ 1-{C_1\over1!}{\gamma\over\log n}+{C_2\over2!}{\gamma(\gamma-1)\over(\log n)^2}+\cdots \bigg]. \cr &[z^n](1-z)^\alpha\big({1\over z}\log{1\over1-z}\big)^\gamma \bigg({1\over z}\log\big({1\over z}\log{1\over1-z}\big)\bigg)^\delta= {n^{-\alpha-1}\over\Gamma(-\alpha)}(\log n)^\gamma(\log\log n)^\delta \cr &\qquad\cdot\bigg[1-{C_1}{(\delta+\gamma\log\log n)\over \log n\log\log n}+ {C_2\over2} {\delta(\delta-1)+\delta(2\gamma-1)\log\log n+\gamma(\gamma-1)(\log\log n)^2 \over (\log n\log\log n)^2}+\cdots \bigg]. \cr} $$ There $C_j=C_j(\alpha)$ represents $$\Gamma(-\alpha){d^k\over ds^k}{1\over\Gamma(-s)}\bigg|_{s=\alpha}.$$ \bigskip \centerline{\bf 4. Extensions: Large Functions and Slowly Varying Functions.} \medskip\noindent We briefly give here indications on possible extensions of our methods, first to ``large'' functions, then to a set of slowly varying functions. \smallskip\noindent {\bf Large Functions.} For functions in class $\SS$ that become ``large'' enough at their singularity, their dominant singular term being of the type $(1-z)^\alpha$ with $\alpha<-1$, the analyticity conditions of our previous theorems can be weakened. A corresponding form of Theorem 1 was given in [Flajolet, Odlyzko 1982] (but we erroneously stated that form with the condition $\alpha<0$ instead of the more restrictive $\alpha<-1$). For completeness, we state the corrected form and briefly sketch the proof. \smallskip\noindent {\sc Theorem 4.} {\sl Assume that $f(z)$ is analytic in $|z|<1$. Assume further that as $z\to1$ in this domain, $$f(z)=O\big(|1-z|^\alpha\big), \eqno(4.1a) $$ for some real number $\alpha<-1$. Then the $n$-th Taylor coefficient of $f(z)$ satisfies} $$f_n=[z^n]f(z)=O(n^{-\alpha-1}). \eqno(4.1b) $$ \smallskip\noindent {\sc Proof.} As our contour $\cal C$, we now choose $${\cal C}=\{\,z\ \ /\ \ |z|=1-{1\over n}\,\}.$$ For $z\in\CC$, set $z=(1-{1\over n})e^{i\theta}$, where $-\pi<\theta\le\pi$. Note that $|z|^{-n}\le 2e$ for $n\ge2$, and so $$f_n=O\big(\int_0^\pi |1-z|^\alpha \,d\theta\big).$$ Now, for $\pi/2\le\theta\le\pi$, $|1-z|>c$ for some constant $c>0$, so that this region contributes a bounded quantity to $f_n$. We also have $$\Re(1-z)=1-(1-{1\over n})\cos\theta\ge{1\over n},$$ and, since $\sin\theta\ge2\theta/\pi$ for $0\le\theta\le\pi/2$, $$|\Im(1-z)|=(1-{1\over n})\sin\theta\ge{\theta\over10}. $$ Therefore, we get $|1-z|\ge{1\over2}({1\over n}+{\theta\over10})$, and $$\eqalign{ \int_0^{\pi/2} |1-z|^\alpha\,d\theta&=O\big(\int_0^{\pi/2}({1\over n}+{\theta\over10})^\alpha \,d\theta \big)\cr &=O(n^{-\alpha-1}),\cr} $$ which gives our estimate.~~\eor \smallskip Appropriate transfer results of all types will follow under the conditions of Theorem 4. \smallskip\noindent {\bf Slowly Varying Functions.} We notice that, in the general proofs of Section 3, it is possible to use, for all $\alpha$, a contour $\CC$ whose outer circle is of radius $R_n=1+\log^2n/n$, so that $R_n$ here plays the role of $\eta$. We could have used the same contour as in the proofs of Section~3, but it is also intructive to introduce yet another contour. It becomes then possible to extend the range of asymptotic scales leading to $O$--, $o$-- and $\sim$--transfers to a scale that includes functions of the form $(1-z)^\alpha L((1-z)^{-1})$, provided $L(u)$ is of slow variation towards infinity. Such functions capture the features of functions like $\log$, $\log\log$ etc. Function $L(u)$ is said to be of {\sl slow variation\/} at $\infty$ if it satisfies the following conditions: \smallskip \item{V1.}There exists a positive real number $u_0$, and an angle $\phi$ with $0<\phi<{\pi\over2}$ such that $L(u)$ is $\not=0$ and analytic in the domain $$\big\{u\ /\ -(\pi-\phi)\le\Arg(u-u_0)\le(\pi-\phi)\big\}.\eqno(4.2)$$ \item{V2.}There exists a function $\epsilon(x)$, defined for $x\ge0$ with $\lim_{x\to+\infty}\epsilon(x)=0$, such that for all $\theta\in[-(\pi-\phi),\pi-\phi]$ and $u\ge u_0$, we have $$ \left|{L(ue^{i\theta})\over L(u)}-1\right|<\epsilon(u) \qquad\hbox{and}\qquad \left|{L(u\log^2u)\over L(u)}-1\right|<\epsilon(u).\eqno(4.3)$$ \smallskip\noindent {\sc Theorem 5.} {\sl Assume that $L(u)$ is of slow variation at $\infty$, then the conditions $$f(z)=O((1-z)^\alpha L({1\over 1-z})),\ \ \ f(z)=o((1-z)^\alpha L({1\over 1-z})),\ \ \ f(z)\sim(1-z)^\alpha L({1\over 1-z}),$$ as $z\to1$ in $\Delta\setminus\{1\}$, transfer into the corresponding estimates for coefficients:} $$f_n=O(n^{-\alpha-1}L(n)),\ \ \ f_n=o(n^{-\alpha-1}L(n)),\ \ \ f_n\sim {n^{-\alpha-1}\over \Gamma(-\alpha)}L(n).$$ {\sc Proof.} A simple adaptation of the proof of Corollary~1. Inequalities (4.3) permit to estimate the contributions to Cauchy's integral ``near'' the singularity $z=1$, as though the $L((1-z)^{-1})$ terms were not present.~~\eor \smallskip This gives us a still wider range of functions like $$e^{\sqrt{\log u}},\ \ \log\log\log u,\ldots$$ For instance, we have the transfer $$f(z)=O\bigg({1\over\sqrt{1-z}}\exp(\sqrt{\log {1\over 1-z}}\bigg) \ \ \implies\ \ f_n=O(n^{-1/2}e^{\sqrt{\log n}}).$$ The slow variation conditions will just exclude a few functions that are very nearly a power of $(1-z)$, like $$\exp\big({\log(1-z)^{-1}\over\log\log(1-z)^{-1}}\big).$$ \bigskip \centerline{\bf 5. A Comparison with Alternative Methods.} \medskip\noindent It is interesting to note first that Darboux's method and Tauberian theorems are in a sense complementary. The former applies to functions of the form $(1-z)^\alpha$ where $\alpha$ is a sufficiently large positive number, while the latter necessitates $\alpha\le0$. Transfer methods, which require somewhat different validity conditions, cover all values of $\alpha$. \smallskip 1. {\it Darboux's method.} There is a restricted form of Darboux's method which is most commonly encountered in combinatorial analysis. It applies to Taylor coefficients of functions of the form $$f(z)=h(z)(1-z)^\alpha\qquad\qquad \alpha\not\in\{0,1,2,\ldots\}, \eqno(5.1) $$ where $h(z)$ is analytic in $|z|<1+\eta$ for some $\eta>0$. This is for instance the form given in [Henrici 1977]. That form is directly covered by Corollary 4 and Eq (2.27c). The most general form is based on Darboux's lemma (a combination of integration by parts and the Riemann--Lebesgue lemma), also a classical result in Fourier analysis: {\sl If $g(z)$ is analytic in $|z|<1$ and $k$ times continuously differentiable on $|z|=1$, then} $$[z^n]g(z)=o({1\over n^k}). \eqno(5.2) $$ A typical application of the method to a function $f(x)$ therefore consists in finding a form $$f(z)=\sigma(z)+g(z)$$ where $\sigma(z)$ is a simple singular function whose coefficients are known, and $g(z)$ is a remainder term that is amenable to treatment by Darboux's lemma. We have already seen situations where the tranfer approach applies while Darboux's method does not: This may owe to the very nature of the expansion (for example (2.1a)), or to the fact that not enough terms can be obtained till a smooth enough error term (an instance is (2.28a)). Some further examples arising in applications are discussed in Section 6 below. Conversely, it may be that a function is smooth on its circle of convergence, so that Darboux's method applies, but the circle is a natural boundary and no transfer like Theorem 1 is applicable. An artificial example\footnote{\dag}{The natural boundary property for $f(z)$ follows from the classical P\'olya-Carlson theorem: {\sl If a function is represented by a Taylor series that has integer coefficients and radius of convergence 1, either it is rational or it admits the unit circle as a natural boundary.}} is $$ g(z)=\sin(z)\sum_{n=1}^\infty {\lfloor \sqrt n \rfloor\over n^5}z^n. \eqno(5.3) $$ In this case, $g(z)$ is 3 times continuously differentiable on $|z|=1$ and by Darboux, $g_n=o(n^{-3})$. \smallskip In cases where both Darboux and transfer methods are applicable, transfer methods tend to give better estimates. For instance, if we determine the expansion of a function till a term of the form $g(z)=O((1-z)^{k+1/2})$ which is also $k$ times continuously differentiable, we get $g_n=o(n^{-k})$ by Darboux, but a better bound of $O(n^{-k-3/2})$ by transfer. \smallskip 2. {\it Tauberian theorems.} We already gave some indication in the introduction on this subject. In our terminology, a {\sl real Tauberian theorem\/} asserts conditions under which an expansion $$f(x)\sim{c\over (1-x)^\beta},\qquad (x\to1^-)$$ (with $\beta\ge0$) that needs to be valid only along the {\sl real\/} line, translates into an estimate for coefficients in the sense of a Cesar\`o average : $${1\over n}\sum_{j=1}^n f_j\sim c {n^{\beta-1}\over\Gamma(\beta)}.$$ A typical sufficient validity condition is $f_n>0$. If, furthermore, the $f_n$ are monotonic, then, we can infer that $$f_n\sim c {n^{\beta-1}\over\Gamma(\beta)}.$$ Application of Tauberian theorems therefore requires some {\sl a priori\/} conditions --~called Tauberian {\sl side conditions\/}~-- like positivity, monotonicity, to be established on the coefficients. Tauberian theorems are useful mostly for main terms in asymptotic expansions, and they may turn out to be the only applicable tool when the circle of convergence of the function is a natural boundary. Greene and Knuth [Greene and Knuth 1983] have an interesting example of using a Tauberian theorem (complemented by ``bootstrapping''), which gives the asymptotic form of coefficients of the function $$f(z)=\prod_{k\ge1} \left(1+{z^j\over j}\right). \eqno(5.4) $$ Function $f$ has the unit circle as a natural boundary and does not seem amenable to transfer methods. Conversely, a function with somewhat erratic coefficients like $$\sin z \cos\big(\log{1\over 1-z}\big)$$ is easily treated by transfer methods (using transfers of $(1-z)^{\pm i}$), but the coefficients are not smooth enough to allow application of a Tauberian theorem. \smallskip On all those classical questions the reader is encouraged to refer to many excellent books like [De Bruijn 1981], [Olver 1974], [Henrici 1977], and for Tauberian theory, [Hardy 1949] or [Postnikov 1980]. \bigskip \centerline{\bf 6. Applications.} \medskip\noindent In this section, we propose to review a few applications of transfer methods in combinatorial analysis and analysis of algorithms. \smallskip\noindent {\bf 2-3 Trees.} The problem dealt with in [Odlyzko 1982] was at the origin of our interest in transfer methods. It consisted in determining the number of balanced 2-3 trees with $n$ external nodes. This reduces to the determination of the coefficients of a generating function $f(z)$ that satisfies the functional equation $$f(z)=z+f(z^2+z^3). \eqno(6.1) $$ It can be recognized that $f(z)$ is analytic for $|z|<\phi^{-1}$ where $\phi=(1+\sqrt5)/2$ is the golden ratio ($\phi^{-1}$ is a fixed point of $z^2+z^3$). A detailed study of the iteration of polynomial $\sigma(z)=z^2+z^3$ shows that there is a singular expansion at $z=\phi^{-1}$ which is of the form $$\eqalign{ f(z)&=c\log{1\over1-\phi z}+ \sum_{k=-\infty}^{k=+\infty} \Omega_k \big(1-z\big)^{2ik\pi/\lambda}+O\big((1-\phi z)\big)\cr &=c\log{1\over1-\phi z}+ \Omega\big({1\over\lambda}\log(1-\phi z)\big) +O\big((1-\phi z)\big)\cr } \eqno(6.2a) $$ There $\lambda=\log(4-\phi)$ and the infinite sum $\Omega(x)$ in (6.2a) is a fast converging Fourier series with period 1. That singular expansion can be established in an angular sector around the singularity $\phi^{-1}$, so that expansion (6.2a) transfers to coefficients, $$\eqalign{ \phi^{-n}f_n&={c\over n}+ \sum_{k=-\infty}^{+\infty} \omega_k n^{-1-2ik\pi/\lambda}+O({1\over n^2})\cr &={c\over n}+{1\over n} \omega({1\over\lambda} \log n)+O({1\over n^2}),\cr } \eqno(6.2b)$$ where $\omega(x)$ is a Fourier series (with period 1 and mean value 0) that ``corresponds'' to $\Omega(x)$. Form (6.2b) gives the asymptotic number of 2-3 trees with $n$ external nodes. This example illustrates a direct extension of Corollary 3 to the situation where the singular expansion (6.2a) contains infinitely many terms whose complex exponents have a common real part. \smallskip\noindent {\bf Height of Trees.} The problem of estimating the expected height of a binary tree with $n$ internal nodes [Flajolet, Odlyzko 1982] reduces easily to finding an asymptotic expansion for the coefficients of function $f(z)$ given by $$f(z)=\sum_{h\ge0}\big[ y(z)-y_h(z)\big] \qquad\hbox{where}\ \ y_0(z)=0;\ y_{h+1}(z)=1+zy_h(z);\ y(z)=y_\infty(z)={1-\sqrt{1-4z}\over2z}. \eqno(6.3) $$ There is a somewhat delicate analysis to determine the behaviour of the quadratic recurrence at $z=1/4$, from which one obtains $$f(z)=c\log{1\over1-4z}+c_0+O\big((1-4z)^{1/4+\epsilon}\big), \eqno(6.4a) $$ for any $\epsilon>0$. By a direct application of Corollary 3, we derive $$f_n={c\over n}+O(n^{-5/4+\epsilon}). \eqno(6.4b)$$ >From (6.4b), we find after normalization that the expected height of a binary tree with $n$ internal nodes is $2\sqrt{\pi n}+O(n^{1/4+\epsilon})$. Here transfer lemmas are useful since it seems difficult to obtain more terms in expansion (6.4a), and application of Darboux's method (if at all feasible) would have required an expansion till terms of a higher order like $O((1-4z)^{3/2})$. Computation of higher moments led us to developing the contour used in Theorem 4. \smallskip\noindent {\bf Multidimensional Search.} The analysis of partial match retrieval [Flajolet, Puech 1986] in so-called $k$-$d$-trees requires expanding a function $f(z)$ that is a component of the solution to a linear differential system with regular singular points. Using the standard theory of regular singular points, we find a singular expansion $$f(z)=c(1-z)^{-\beta}+O\big({1\over (1-z)^2}\big) \eqno(6.5a) $$ valid at an angle outside the circle of convergence $|z|=1$, where $2<\beta<3$. (For a 2-$d$ search, $\beta=(\sqrt{17}+1)/2$). It would have been possible (though a little more lengthy) to push expansion (6.5a) further, but Theorem 1 or Theorem 4 provide all that is needed to deduce directly $$f_n={c\over\Gamma(\beta)}n^{\beta-1}+O(n). \eqno(6.5b) $$ For instance a partial match search in a 2-$d$ tree will have expected cost $\sim K n^{(\sqrt{17}-3)/2}$. \smallskip\noindent {\bf Common Subexpression Problem.} The analysis of the representation of trees by compact directed acyclic graphs (dags) [Flajolet, Sippala, Steyaert 1987] requires finding the coefficient of $z^n$ in $$f(z)={1\over 2z}\sum_{p\ge0} B_p\left[ \sqrt{1-4z+4z^{p+1}}-\sqrt{1-4z}\right] \qquad\hbox{where}\ \ B_p={1\over p+1}{2p\choose p}. \eqno(6.6) $$ A singularity analysis of (6.6) around $z=1/4$ shows that $$f(z)={c\over\sqrt{(1-4z)\log(1-4z)^{-1}} } \left[1+O\left({1\over\log(1-4z)^{-1}}\right)\right]. \eqno(6.7a) $$ By Theorem 3A and a trivially amended form of Corollary 5, we get $$4^{-n}f_n={c\over\sqrt{\pi n\log n}} \left[1+O\left({1\over\log n}\right)\right] \eqno(6.7b) $$ This example (see also the discussion of (2a)-(2b)) is interesting since it could not be attacked by Darboux's method. As we already indicated, even by pushing the expansion further, there is no way of obtaining a differentiable error term in a more extensive form of (6.7a). Tauberian methods would be possible candidates for attacking (6.7a), but it seems to be quite difficult to establish Tauberian side conditions on the {\it error term\/} in (6.7a), and the situation would get even worse if higher order terms were to be found. By transfer methods, we are able to conclude easily that the expected size of the maximally compacted dag representation of a tree of size $n$ is $\sim cn/\sqrt{\log n}$. \smallskip\noindent {\bf Longest Cycle in Permutations.} This problem, solved by Shepp and Lloyd [Shepp, Lloyd 1966], is equivalent to finding the asymptotic form of the coefficients of $$f(z)=\sum_{k\ge 0} \bigg[{1\over1-z}-e^{z/1+z^2/2+\cdots+ z^k/k} \bigg] ={1\over 1-z} \sum_{k\ge0}\bigg[1-\exp(-\sum_{j\ge k}{z^j\over j})\bigg]. \eqno(6.8) $$ Function $f(z)$ is singular at $z=1$, and it is natural to set $z=e^{-t}$ so that $t\to0$ as $z\to1$ and $z\sim1-t$. Two successive applications of Euler Maclaurin summation to (6.8) provide the approximation $$(1-z)f(z)\sim {G\over t} \qquad\hbox{where}\ \ G=\int_0^\infty \left[1-\exp\big(-\int_x^\infty{e^{-t}\over t}\big)\,dt\right]\,dx. \eqno(6.9a)$$ Thus $F(z)\sim G(1-z)^{-2}$, and by transfer (Corollary 3), the longest cyle in a random permutation of $n$ elements has expected length $$f_n\sim Gn.\eqno(6.9b)$$ We observe that Shepp and Lloyd's original derivation (see also [Knuth 1973a, p.181]) proceeds along quite different lines. They first prove a Poisson approximation and then use a Tauberian theorem. But Tauberian side conditions, though expected combinatorially, are not obvious to establish. In [Flajolet, Odlyzko 1990], we apply an analysis of this type to study random mappings and find the expected diameter of a random mapping of size $n$. \smallskip\noindent {\bf Odd-Even Merge.} The problem of analyzing odd-even merge sorting networks was posed by Knuth in [Knuth 1973b, Ex.5.2.2.16]. Knuth reduces it to finding the Taylor coefficients of a function closely related to $$f(z)={y\over1+y^2}+{y^2\over1+y^4}+{y^4\over1+y^8}+\cdots \qquad\hbox{where}\ \ y={1-\sqrt{1-4z}\over1+\sqrt{1-4z}}. \eqno(6.10) $$ The problem was solved by Sedgewick in 1977 by expanding, then using real approximations on coefficients and finally applying Mellin transform techniques [Sedgewick 1977]. We present here the outline of an alternative approach based on [Flajolet, Prodinger 1986]. Following our general strategy, we try to determine a singular expansion of $f(z)$ around the singularity $z=1/4$. We can set $y(z)=e^{-t}$, so that $t\to0$ as $z\to1/4$, and the problem is to analyze $$F(t)={e^{-t}\over1+e^{-2t}}+{e^{-2t}\over1+e^{-4t}}+ {e^{-4t}\over1+e^{-8t}}+\cdots \qquad\hbox{as}\ \ (t\to0). \eqno(6.11) $$ We assume, to simplify the discussion, that $t$ real and positive (general theorems guarantee that the expansion can be ``continued'' for complex $t$ with $\Re(t)>0$, hence for complex $z$ at an angle from $1/4$). The Mellin transform of $F(t)$ is easily found from (6.11), $$F^*(s)\eqdef \int_0^\infty F(t) t^{s-1}\,dt= {\Gamma(s)L(s)\over1-2^{-s}} \qquad\hbox{where}\qquad L(s)={1\over1^s}-{1\over3^s}+{1\over5^s}-{1\over7^s}+\cdots. \eqno(6.12) $$ >From the familiar Mellin inversion formula and a computation by residues [Doetsch 1955], we obtain an asymptotic expansion of $F(t)$ as $t\to0$, $$ F(t)\sim\sum\Res[F^*(s)t^{-s}], \eqno(6.13) $$ where the sum is extended to all poles $s$ of $F^*(s)$ satisfying $\Re(s)\le0$: There is a double pole at $s=0$, simple imaginary poles at $s=2ik\pi/\log2$ and simple real poles at $s=-2,-4,-6,\ldots$. Thus, $$F(t)\sim{1\over2}\log_2{1\over t}+c_0+ \Omega(\log_2t)+2\sum_{k\ge1} {E_{2k}\over 1-2^{-k}} {t^{2k}\over((2k)!)^2}. \eqno(6.14a)$$ There $\Omega(x)$ is a Fourier series in $x$ and $E_{2n}$ is the Euler number, $E_{2n}=(2n)![z^{2n}]{1\over\cos z}$. Expansion (6.14a) is a {\it full\/} expansion in increasing powers of $t$ which, by transformation $t=-\log y(z)$ yields a full asymptotic expansion of $F(t)$. >From there, we can find a full expansion for the coefficients of $f(z)$ (by transfer) and, in particular, get a complete asymptotic expansion of $f_n$. The same method gives Sedgewick's result (and an infinite expansion): {\sl The expected number of exchanges in odd-even merge applied to two sequences of length $n$ is $1/4n\log_2n+\cdots$.} We refer the reader to [Flajolet, Prodinger 1986] for a similar example treated in detail. This ``synthetic'' method differs from the usual aproach [De Bruijn, Knuth, Rice 1972]: In accordance with our general principles, we operated only at the level of the generating function (using complex Mellin transforms to derive a singular expansion), and concluded directly by a transfer theorem. \smallskip\noindent {\bf Limit distributions in combinatorics.} Consider a bivariate generating function of the form $$P(z,u)=\exp(uG(z)).$$ Such functions arise naturally in counting combinatorial structures $\PP$ that are decomposable as sets of basic building blocks (components) enumerated by $G(z)$. In this context, the polynomials $p_n(u)=[z^n]P(z,u)$ are the generating polynomials giving the distribution of the number of components in a random $\PP$ structure of size $n$. Under the condition that $G(z)$ has a dominant singularity of a logarithmic type, methods of this paper may be used to estimate asymptotically the characteristic function $p_n(e^{it})$ which, once suitably normalised, tends to $e^{-t^2/2}$. >From the continuity theorem for characteristic functions, we deduce that the number of components in a ``large '' ($n\to\infty$) random $\PP$ structure tends to a limiting Gaussian distribution. A typical application is to cycles in permutations. There are extensions to P\'olya's theory of counting, with the corresponding analytic scheme $$P(z,u)=\exp\big({u\over 1}G(z)\pm{u^2\over2}G(z^2)+{u^3\over3}G(z^3)\pm {u^4\over4}G(z^4)+\cdots\,\big).$$ We obtain for instance: {\sl The number of irreducible factors in a random polynomial with coefficients in $GF(q)$ is asymptotically Gaussian}. Under different analytic conditions on the ``generator'' $G(z)$, Bender [1973] and Canfield [1977] have established similar asymptotic normality results. Detailed proofs of results cited here are presented in [Flajolet, Soria~1988]. \bigskip\noindent {\sc Acknowledgements.} The authors would like to express their gratitude to D.~E.~Knuth for encouragement to write up this paper, and for several useful suggestions regarding the presentation. The first named author is thankful to D.~E.~K.~for an invitation at Stanford University during which his work on the subject was done for a large part. \bigskip\noindent {\bf References.} \medskip %% macro definition \def\ref{\goodbreak\smallskip\noindent} \font\sc=cmcsc10 \frenchspacing \ref {\sc E. Bender} [1973]. ``Central and Local Limit Theorems Appplied to Asymptotic Enumeration'', {\sl J. Combinatorial Theory Series A} {\bf 15}, 1973, 91-111. \ref {\sc E. Bender} [1974]. ``Asymptotic Methods in Enumerations'', {\sl SIAM Review\/} {\bf 16}, 1974, 485--515. \ref {\sc E. R. Canfield} [1977]. ``Central and Local Limit Theorems for Coefficients of Binomial Type'', {\sl J. Combinatorial Theory Series A} {\bf 23}, 1977, 275-290. \ref {\sc M. Car} [1982]. ``Factorisation dans ${\bf F}_q[X]$'', {\sl C. R. Acad. Sciences Paris S\'erie I} {\bf 294}, 1982, 147-150. \ref {\sc M. Car} [1984]. ``Ensembles de polyn\^omes irr\'eductibles et th\'eor\`emes de densit\'e'', {\sl Acta Arithmetica} {\bf 44}, 1984, 323-342. \ref {\sc L. Comtet} [1974]. {\sl Advanced Combinatorics.} Reidel, Dordrecht, 1974. \ref {\sc N. G. De~Bruijn} [1981]. {\sl Asymptotic Methods in Analysis.} Dover, New York, 1981. \ref {\sc N. G. De~Bruijn, D. E. Knuth, and S. O. Rice } [1972]. ``The Average Height of Planted Plane Trees,'' in {\sl Graph Theory and Computing}, edited by R.-C.~Read, Academic Press, New York, 1972, 15--22. \ref {\sc P. Flajolet and A. M. Odlyzko} [1982]. ``The Average Height of Binary Trees and Other Simple Trees'', {\sl J. Computer and System Sciences} {\bf 25}, 1982, 171-213. \ref {\sc P. Flajolet and A. M. Odlyzko} [1990]. ``Random Mapping Statistics'', in preparation (1990). \ref {\sc P. Flajolet and H. Prodinger} [1986]. ``Register Allocation for Unary--Binary Trees'', {\sl SIAM J. on Computing\/} {\bf 15}, 1986, 629--640. \ref {\sc P.\ Flajolet and C. Puech} [1986] ``Partial Match Retrieval of Multidimensional Data,'' {\sl Journal of the ACM\/} {\bf 33\/}(2), April~1986, 371--407. \ref {\sc P.\ Flajolet, P. Sipala and J.-M. Steyaert} [1987]. ``The Analysis of Tree Compaction in Symbolic Manipulations,'' preprint. \ref {\sc P. Flajolet and M. Soria} [1988]. ``Normal Limiting Distributions for the Number of Components in Combinatorial Structures'', INRIA Res. Report {\bf 809}, March 1988. (To appear in {\sl J. Comb. Theory\/}.) \ref {\sc I. Goulden and D. Jackson} [1983]. {\sl Combinatorial Enumerations.} Wiley, New York, 1983. \ref {\sc D. H. Greene and D. E. Knuth} [1982]. {\sl Mathematics for the Analysis of Algorithms.} Birkh\"auser, Boston, second edition 1982. \ref {\sc G. H. Hardy} [1940]. {\sl Ramanujan, Twelve lectures Suggested by His Life and Work}, Cambridge University Press. Reprinted by Chelsea Publishing Company, New-York, 1978. \ref {\sc G. H. Hardy} [1949]. {\sl Divergent Series}, Oxford University Press, 1949. \ref {\sc G. H. Hardy and J. E. Littlewood} [1914]. ``Tauberian Theorems Concerning Power Series and Dirichlet's Series Whose Coefficients are Positive'', {\sl Proc. London Math. Soc.} {\bf 13}, 1913/14, 174--191. \ref {\sc P. Henrici} [1977]. {\sl Applied and Computational Complex Analysis.} Three Volumes. Wiley, New York, 1977. \ref {\sc R. Jungen} [1931]. ``Sur les s\'eries de Taylor n'ayant que des singularit\'es algebrico--logarithmiques sur leur cercle de convergence'', {\sl Commentarii Mathematici Helvetici\/} {\bf 3}, 1931, 266--306. \ref {\sc D. E. Knuth} [1973a]. {\sl The Art of Computer Programming. {\rm Volume 1:} Fundamental Algorithms.} Addison-Wesley, Reading, MA, second edition 1973. \ref {\sc D. E. Knuth} [1973b]. {\sl The Art of Computer Programming. {\rm Volume 3:} Sorting and Searching.} Addison-Wesley, Reading, MA, 1973. \ref {\sc D. E. Knuth} [1981]. {\sl The Art of Computer Programming. {\rm Volume 2:} Semi-Numerical Algorithms.} Addison-Wesley, Reading, MA, second edition 1981. \ref {\sc A. M. Odlyzko} [1982]. ``Periodic Oscillations of Coefficients of Power Series that Satisfy Functional Equations'', {\sl Advances in Math.} {\bf 44}, 1982, 180-205. \ref {\sc F. W. J. Olver} [1974]. {\sl Asymptotics and Special Functions}, Academic Press, 1974. \ref {\sc G. P\'olya} [1954]. {\sl Induction and Analogy in Mathematics}, Princeton University Press, 1954. \ref {\sc A. G. Postnikov} [1980]. {\sl Tauberian Theory and its Applications}, in {\sl Proc. Steklov Institute of Mathematics\/} {\bf 144}, English translation by A.M.S., 1980, Issue 2. \ref {\sc R. Sedgewick} [1978]. ``Data Movement in Odd-Even Merging'', {\sl SIAM J. Comput.\/} {\bf 7}, 1978, 239--272. \ref {\sc A. Selberg} [1954]. ``Note on a Paper by L. G. Sathe'', {\sl J. Indian Math. Soc.\/} {\bf 18}, 1954, 83--87. \ref {\sc L. A. Shepp and S. P. Lloyd} [1966]. ``Ordered Cycle Lengths in a Random Permutation'', {\sl Trans. A.M.S.\/} {\bf 121}, 1966, 340-357. \ref {\sc R. P. Stanley} [1986]. {\sl Enumerative Combinatorics}, Wadsworth and Brooks/Cole, Monterey, 1986. \ref {\sc E. C. Titchmarsh} [1939]. {\sl The Theory of Functions}, 2nd Edition, Oxford University Press, 1939. \ref {\sc E. T. Whittaker and G. N. Watson} [1927]. {\sl A Course of Modern Analysis''}, 4th Edition, Cambridge University Press, 1927. \ref {\sc R. Wong and M. Wyman} [1974]. ``The Method of Darboux'', {\sl J. of Approximation Theory\/} {\bf 10}, 1974, 159--171. \ref {\sc D. A. Zave} [1976]. ``A Series Expansion Involving the Harmonic Numbers'', {\sl Information Processing letters\/} {\bf 5}, 1976, 75--77. \bye