%% plain TeX (erc's file: "ercSZEKejc.tex") \magnification1200 \hsize = 6truein \vsize = 9truein \normalbaselines \overfullrule=0pt \font\smcp=cmcsc8 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 4 (no. 2) (1997), \#R6 \hfill\folio} \fi} \nopagenumbers \def\oh{{\it o\/}} % little oh notation \def\Oh{{\it O\/}} % big Oh notation \def\OH{\Oh} %START REFERENCES section \catcode`\@=11 \newcount\refn@ \refn@=0 \def\refnumber#1{\global\advance\refn@ by 1\xdef#1{\the\refn@}} \font\authorfont=cmss10 \def\bookfont{\it} \def\articlefont{\rm} % \def\references{\startingsection{References} \def\references{\startingsection{Cited Publications} \narrowspacing \parskip=\normalbaselineskip \normalbaselines} % 1=number 2=author 3=title 4=university start a thesis ref. % 5=year \def\thesis#1#2#3#4#5{\item{#1.}{\authorfont #2, \bookfont #3},{\rm \/ Doctoral Thesis, #4, #5}} % 1=number 2=author 3=title 4=publisher start a book ref. % 5=year \def\book#1#2#3#4#5{\item{#1.}{\authorfont #2, \bookfont #3}, {#4}, {#5}} % 1=number 2=author 3=title 4=publisher book ref. with two % 5=year 6=second publisher 7=second year diff pubs given \def\Doublebook#1#2#3#4#5#6#7{\item{#1.}{\authorfont #2, \bookfont #3}, {#4}, {#5}; {also published by} {#6}, {#7}.} % 1=number 2=author \def\personalcommunication#1#2{\item{#1.}{\authorfont #2, {\rm personal communication.}}} % 1=number 2=author 3=title start a paper ref. \def\reference#1#2#3{\item{#1.}{\authorfont #2, \articlefont #3,}} % 1=journal 2=volume 3=year 4=pages (use --) if in a journal \def\journal#1#2#3#4{\it #1\/ \bf #2 \rm (#3) \/ #4} % 1=editors 2=title 3=publisher 4=year 5=pages if in a collection \def\collection#1#2#3#4#5{\rm in \bookfont #2 \rm (#1), #3, #4, pages #5} % 1=title 2=publisher 3=year if in a collection, but % no editors or pages \def\cono #1#2#3{\rm in \bookfont #1, \rm #2, #3} % 1=journal if to appear \def\toappear#1{\it #1, \rm to appear} % if it is a preprint \def\preprint {\rm preprint} % if it is submitted \def\submitted#1{\it #1,\/ \rm submitted} % if it is in preparation \def\inpreparation {\rm in preparation} \catcode`\@=12 \def\onehalf{\textstyle{1 \over 2}} \def\half{\onehalf} \def\P{P} \def\p{p\,} \def\Stepx{Comment~} \def\Stepsx{Comments~} \def\TheInt{\int_0^v {t \over e^t-1}dt} \def\A{\alpha} \def\B{\beta} \def\qrel{\buildrel \rm ? \over \le} \def\qrelX{\buildrel \rm ? \over <} \refnumber\AS \refnumber\BCMOne \refnumber\BCMTwo \refnumber\Comtet \refnumber\EL \refnumber\Erdos \refnumber\HR \refnumber\KKOne \refnumber\KKTwo \refnumber\Knopp \refnumber\Odlyz \refnumber\SzekOne \refnumber\SzekTwo \null \vskip 2truein \vskip 20pt \centerline{From Recursions to Asymptotics: On Szekeres' Formula} \centerline{for the Number of Partitions} \vskip20pt \centerline{E. Rodney Canfield} \centerline{Department of Computer Science} \centerline{University of Georgia} \centerline{Athens, GA 30602, USA} \centerline{\tt erc@cs.uga.edu} \vskip 20pt \centerline{\it For Herb Wilf on his 65-th Birthday} \vskip 20pt \centerline{Submitted: August 1, 1996; Accepted: November 21, 1996} \vskip 20pt \vskip 20pt \centerline{\bf Abstract.} \medskip \noindent We give a new proof of Szekeres' formula for $\P(n,k)$, the number of partitions of the integer $n$ having $k$ or fewer positive parts. Our proof is based on the recursion satisfied by $\P(n,k)$ and Taylor's formula. We make no use of the Cauchy integral formula or any complex variables. The derivation is presented as a step-by-step procedure, to facilitate its application in other situations. As corollaries we obtain the main term of the Hardy-Ramanujan formulas for $p(n)=$ the number of unrestricted partitions of $n$, and for $q(n)=$ the number of partitions of $n$ into distinct parts. \vskip 20pt \noindent AMS-MOS Subject Classification (1990). \noindent Primary: 05A17 \noindent Secondary: 05A20, 05A16, 11P81 \null\vfill \eject \centerline{\bf 1 Introduction.} \vskip 8pt \noindent A {\it partition} of an integer $n$ into $k$ parts is a solution to the system $$ n = x_1 + x_2 + \cdots x_k,~~x_1 \ge x_2 \ge \cdots \ge x_k > 0.$$ Let $\P(n,k)$ be the number of partitions of $n$ into $k$ or fewer parts. We will prove the following. \vskip 20pt \noindent{\bf Theorem.} (Szekeres) Let $\epsilon>0$ be given. Then, uniformly for $k\ge n^{1/6}$, $$ \P(n,k) = {f(u) \over n }\exp\biggl\{ n^{1/2}g(u)+\Oh\Bigl(n^{-1/6+\epsilon} \Bigr) \biggr\}. $$ Here, $u=k/n^{1/2}$, and the functions $f(u)$, $g(u)$ are: $$\eqalignno{ f(u) ~~&=~~ {v \over 2^{3/2} \pi u } \bigl(1 - e^{-v} - \half u^2e^{-v})^{-1/2} &(1.1) \cr g(u) ~~&=~~ {2v \over u} - u \log(1-e^{-v}), &(1.2) \cr }$$ where $v$ ($= v(u)$) is determined implicitly by $$ u^2 = v^2 \Big/ \TheInt. \eqno (1.3) $$ \noindent{\bf Remarks.} The estimate can be made uniform for the entire range $k \ge 1$ by adding $1/k$ to the big-oh term. The last equation uniquely determines $v$ because the right hand side is an increasing function of $v$. \vskip 20pt Szekeres presents his results in two papers [\SzekOne, \SzekTwo], using substantially different approaches for two distinct though slightly overlapping ranges of $k$. The papers are remarkable both for the depth of the analysis contained in them, and for the precision of their results. Indeed, Szekeres' is the only known proof that $\p(n,k)$ is unimodal in $k$ for fixed $n$. ($\p(n,k) = \P(n,k)-\P(n,k-1)$ is the number of partitions of $n$ with exactly $k$ parts. No combinatorial proof of this unimodality result is known, and Szekeres' proof itself holds only for $n$ sufficiently large.) As a partial justification for publishing the reproof of an old theorem, I offer the following quotation from the famous paper [\HR, p. 78]: (recall that Hardy and Ramanujan used the theory of linear transformations of elliptic functions to prove their asymptotic formula for $\p(n)$, the total number of partitions of $n$.) \smallskip \item{} ``It is very important, in dealing with such a problem as this, to distinguish clearly the various stages to which we can progress by arguments of a progressively `deeper' and less elementary character. $~\dots~$ the more elementary methods are likely to be applicable to other problems in which the more subtle analysis is impracticable.'' \smallskip \noindent Erd\"{o}s [\Erdos] has given an elementary (meaning complex-variable-free) derivation of the main term in the Hardy-Ramanujan formula using the recursion: $$ n\p(n) = \sum_{\nu,\mu}\nu \p(n-\mu\nu).$$ Our proof also uses a recursion, and differs from Szekeres' in the absence of complex variables. It is perhaps noteworthy that we can recover all of Szekeres' result, including the leading constant, and can consolidate his two formulas into the one given in the Theorem above. Moreover, our method can be used to estimate other two-dimensional arrays of combinatorial significance. For this last reason, we present in the next section a derivation of our result in the form of a step-by-step procedure intended to be generally applicable. In the procedure section we give only the key formulas while the next section of the paper contains more details and justification. In the procedure section we do not give the specific definitions of the functions $a(u), A_1(u), A_2(u)$; these are found in the later section. The origin of the method presented here is [\BCMOne], and a later example is [\BCMTwo]. Both of these deal with graphical enumeration problems. The present paper differs in the area of application (partitions), the $n^{1/2}$ term exponentiated in the approximation formula, and in the procedural style of presentation. This style was chosen both to facilitate future applications and also as a first step toward possible software implementation. Knessl and Keller [\KKOne, \KKTwo] demonstrate a method with similarities to the one presented here. As they point out, their method is formal. Formulas found via their formal method are observed to be asymptotically correct over a certain range by comparison to known results. However, proof of asymptotic correctness is not a part of their method. The reader will see that the first four steps in the following procedure section constitute a formal procedure for arriving at a putative formula; the remaining eighteen steps provide a general approach to proving a big-oh bound on the error. For a comprehensive overview of asymptotic methods in enumeration, the reader may consult [\Odlyz]. \vskip 12pt \centerline{\bf 2 Procedure.} \vskip 8pt \noindent{\bf Step 1.} Start with a recursion for the doubly-indexed sequence to be estimated. $$\P(n,k) ~=~ \P(n-k,k) + \P(n,k-1).$$ \noindent{\bf Step 2.} Guess the form of the estimate. $$ \P(n,k) ~\approx~ n^{-1}\exp\{n^{1/2}g(u)+a(u)\},~~~u=k/n^{1/2}.$$ \noindent{\bf Step 3.} Express the right side of the recursion in terms of $u,g(u),a(u)$, using Taylor series. $$ \eqalign{ \P(n-k,k) ~&\approx~ n^{-1}\exp\{n^{1/2}g(u)+a(u)-ug(u)/2+u^2g'(u)/2+ {A_1(u) \over n^{1/2}} + \cdots \} \cr \P(n,k-1) ~&\approx~ n^{-1}\exp\{n^{1/2}g(u)+a(u)-g'(u)+ {A_2(u) \over n^{1/2}} + \cdots \}. \cr } $$ {\bf Remarks.} Because of its frequent appearance, we define $v$ to be the following function: $$ v(u) ~=~ ug(u)/2-u^2g'(u)/2. $$ It emerges after solving for $g(u)$ in Step 4 that this function $v(u)$ is given by (1.3). For typographical brevity we often omit the argument $u$ from functions such as $v$, $g$, $a$, $g'$, $A_1$, and $A_2$. \vskip 8pt \noindent{\bf Step 4.} Substitute the guessed form into the recursion; equate coefficients of like powers of $n$ on both sides, and solve the resulting differential equations for $g(u)$, $a(u)$. Dividing through by $n^{-1}\exp\{n^{1/2}g+a\}$, and expanding the exponential function, $$ 1 ~=~ e^{-v}\bigl(1+{A_1 \over n^{1/2}}+\cdots \bigr) + e^{-g'}\bigl(1+{A_2 \over n^{1/2}}+\cdots \bigr);$$ this gives one differential equation determining $g(u)$: $$ 1 ~=~ e^{-v} + e^{-g'}, \eqno(2.1) $$ and another determining $a(u)$: $$ 0 ~=~ e^{-v}A_1 + e^{-g'}A_2. \eqno(2.2) $$ \noindent{\bf Step 5.} Solve for $\P(n,k)$ when $k$ is sufficiently small, by other means. $$ \eqalign{ \P(n,k) ~&=~ {1 \over k!} {n-1 \choose k-1} \exp\bigl\{ \Oh(k^3/n) \bigr\},~~~~{\rm ~for~} k = \Oh(n^{1/3}), \cr &=~ {1/2\pi \over n} \exp\biggl\{k \log\bigl( {ne^2 \over k^2} \bigr) +\Oh(k^3/n+1/k) \biggr\}. \cr }$$ \noindent{\bf Remark.} The first equality above is due to Erd\"{o}s and Lehner [\EL]. \vskip 8pt \noindent{\bf Step 6.} Define $b(n,k)$ to be the relative error of the approximation. $$ \P(n,k) ~=~ n^{-1}\exp\{n^{1/2}g(u)+a(u)\}\bigl(1+b(n,k)\bigr). $$ \noindent{\bf Step 7.} Expand the functions $g(u)$, $a(u)$ for small $u$ to see how the approximator behaves for $k$ small. $$\eqalign{ g(u) ~&=~ -2u\log(u) + 2u + \Oh(u^3) \cr a(u) ~&=~ -\log(2\pi) + \Oh(u^4) \cr n^{-1} \exp\{n^{1/2}g(u)+a(u)\} ~&=~ {1/2\pi \over n} \exp\bigl\{ k\log\bigl( {ne^2 \over k^2}\bigr) + \Oh(k^3/n) \bigr\}. \cr }$$ \noindent{\bf Step 8.} Compare Steps 5 and 7 to bound $b(n,k)$ for $k$ sufficiently small. $$ b(n,k) ~=~ \Oh(k^3/n + 1/k),~~~{\rm~for~} k=\Oh(n^{1/3}).$$ \noindent{\bf Step 9.} Hypothesize a bound of the form $k^{\A}/n^{\B}$ for $b(n,k)$, and a range for which it is true. $$|b(n,k)|~\qrel~Ck^\A/n^\B,~~~{\rm~for~}k \ge n^{\delta_1}.$$ \noindent{\bf Step 10.} Determine conditions on $\A,\B$ such that hypothesis $\qrel$ holds for sufficiently large $C$ in some initial infinite segment of $k$. To achieve $$ \max(k^3/n,1/k) ~\le~ Ck^\A/n^\B, ~~~n^{\delta_1} \le k \le n^{\delta_2}, $$ it suffices to have \bigskip ~~~~~~~~~~~~~~~~~~~~\hbox{\vrule\vbox{\hrule \hbox spread 8pt{\hfil\vbox spread 8pt{\vfil \hbox{$\B \le (1+\A)\delta_1,~(3-\A)\delta_2 \le 1-\B,~\delta_1 < \delta_2 < 1/3$}% \vfil}\hfil} \hrule}\vrule}% \smallskip \noindent{\bf Step 11.} In preparation for a proof by induction of the hypothesized bound on $|b(n,k)|$, give a recursion for the latter. Using the definition of Step 6, $$\eqalign{ 1 + b(n,&k) \cr &=~~{ (n-k)^{-1}\exp\{(n-k)^{1/2}g(k(n-k)^{-1/2})+a(k(n-k)^{-1/2})\} \over n^{-1}\exp\{n^{1/2}g(u)+a(u)\} } \bigl(1+b(n-k,k)\bigr) \cr &~~~~~~~~~~+~{ n^{-1}\exp\{n^{1/2}g((k-1)n^{-1/2})+a((k-1)n^{-1/2})\} \over n^{-1}\exp\{n^{1/2}g(u)+a(u)\} } \bigl(1+b(n,k-1)\bigr) \cr &=~T_1(n,k) \bigl(1+b(n-k,k)\bigr) + T_2(n,k) \bigl(1+b(n,k-1)\bigr), \cr }$$ say. \noindent{\bf Step 12.} When using the above $b(n,k)$ recursion in the inductive step, take advantage of $k-1$ in place of $k$: $$ {(k-1)^\A \over n^\B} ~=~ {k^\A \over n^\B} \bigl(1 - \A/k + \Oh(k^{-2}) \bigr); $$ and compensate fairly for $n-k$ in place of $n$: $$ {k^\A \over (n-k)^\B} ~=~ {k^\A \over n^\B} \bigl(1 + \B k/n + \Oh(k^2n^{-2}) \bigr). $$ \vskip 12pt \centerline{\bf Small $u$} \noindent Steps 13 through 16 involve small $u$: $u \le \epsilon_0$. The correct choice of $\epsilon_0$ appears in Step 15. All big-oh assertions in Steps 13 through 16 are uniform for $u \le \epsilon_0$. \vskip 8pt \noindent{\bf Step 13.} Using Taylor series with remainder for $g(u), a(u)$, find estimates beyond the $A_1$ and $A_2$ terms for $T_1(n,k)$ and $T_2(n,k)$ that hold uniformly for $u \le \epsilon_0$. $$ \eqalign{ T_1 ~&=~e^{-v}\Bigl(1 + {A_1 \over n^{1/2}} + \Oh(u^2n^{-1}) \Bigr) \cr T_2 ~&=~e^{-g'}\Bigl(1 + {A_2 \over n^{1/2}} + \Oh(u^{-2}n^{-1}) \Bigr).\cr } $$ \noindent{\bf Step 14.} Rewrite the recursion of Step 11 using the known form of $T_1 + T_2$. Since $e^{-g'} = \Oh(u^2)$, the two differential equations (2.1,2.2) imply that $T_1 + T_2 = 1+\Oh(n^{-1})$. Hence, $$ b(n,k) ~=~ \Oh(n^{-1}) + T_1 \cdot b(n-k,k) + T_2 \cdot b(n,k-1). $$ In view of the final two terms in the latter and the admonition of Step 12, we make the following calculation: $$\eqalign{ &~~~~~~e^{-v}\Bigl(1 + {A_1 \over n^{1/2}} + \Oh(u^2n^{-1}) \Bigr) \Bigl(1 + \B k/n + \Oh(k^2n^{-2}) \Bigr) \cr &~~~+~~~e^{-g'}\Bigl(1 + {A_2 \over n^{1/2}} + \Oh(u^{-2}n^{-1}) \Bigr) \Bigl(1 - \A/k + \Oh(k^{-2}) \Bigr) \cr &= 1 + {\B e^{-v} k \over n} - {\A e^{-g'} \over k} + \Oh(n^{-1}). }$$ \noindent{\bf Step 15.} The difference $\A e^{-g'}/k \,-\, \B e^{-v}k/n$ turns out to be crucial; determine a lower bound for small $u$ by taking the first terms of the Taylor series: $$ \A e^{-g'}/k \,-\, \B e^{-v}k/n ~>~ {\A-\B \over 2}{u \over n^{1/2}} {\rm ~for~} u \le \epsilon_0. $$ This inequality is the defining property of $\epsilon_0$. \vskip 8pt \noindent{\bf Step 16.} Determine conditions on $\A$ and $\B$ so that the inductive step in a proof of hypothesis $\qrel$ goes through for sufficiently large $C$ and $k$ in the range $n^{\delta_2} \le k \le \epsilon_0 n^{1/2}$: $$\eqalign{ |b(n,k)| &~\le~ \Oh(n^{-1}) + Ck^{\alpha}/n^{\beta}\Bigl( 1 + {\B e^{-v} k \over n} - {\A e^{-g'} \over k} + \Oh(n^{-1}) \Bigr) \cr &~\qrel~ Ck^{\alpha}/n^{\beta}. \cr }$$ Since $1/n = \oh(u)$, the induction goes through provided $$ {1 \over n} ~\le~ C {k^\A \over n^\B}{\A - \B \over 3}{u \over n^{1/2}},$$ for which it suffices \bigskip ~~~~~~~~~~~~~~~~~~~~~~~~~~~\hbox{\vrule\vbox{\hrule \hbox spread 8pt{\hfil\vbox spread 8pt{\vfil \hbox{$\B ~\le~ (1+\A) \delta_2, ~~~~\A > \B $}% \vfil}\hfil} \hrule}\vrule}% \vskip 12pt \centerline{\bf Large $u$} \noindent Steps 17 through 20 involve large $u$: $ \epsilon_0 \le u \le 25 \log n $. The value of $\epsilon_0$ is inherited from Step 15. The upper bound $25 \log n$ is small enough that $u = \oh(n^{1/2})$, thus making approximations like the first in (3.1) still valid; and it is large enough to make Steps 21 and 22 easy. All big-oh assertions in Steps 17 through 20 are uniform for $ \epsilon_0 \le u \le 25 \log n$. \vskip 8pt \noindent{\bf Step 17.} Repeat Step 13 for large $u$: $$ \eqalign{ T_1 ~&=~e^{-v}\Bigl(1 + {A_1 \over n^{1/2}} + \Oh(u^4n^{-1}) \Bigr) \cr T_2 ~&=~e^{-g'}\Bigl(1 + {A_2 \over n^{1/2}} + \Oh(u^2e^{-v}n^{-1}) \Bigr).\cr } $$ \noindent{\bf Step 18.} Repeat Step 14 for large $u$. $$\eqalign{ &~~~~~~e^{-v}\Bigl(1 + {A_1 \over n^{1/2}} + \Oh(u^4n^{-1}) \Bigr) \Bigl(1 + \B k/n + \Oh(k^2n^{-2}) \Bigr) \cr &~~~+~~~e^{-g'}\Bigl(1 + {A_2 \over n^{1/2}} + \Oh(u^2e^{-v}n^{-1}) \Bigr) \Bigl(1 - \A/k + \Oh(k^{-2}) \Bigr) \cr &= 1 + {\B e^{-v} k \over n} - {\A e^{-g'} \over k} + \Oh(ue^{-v}n^{-1}). }$$ \noindent{\bf Step 19.} Find a positive lower bound for the crucial difference discussed in Step 15 holding when $u ~\ge~ \epsilon_0$. $$ \A e^{-g'}/k \,-\, \B e^{-v}k/n ~>~ c_1(\A - \B)/k, $$ where $c_1$ is the minimum of $1-e^{-v}$ for $u \ge \epsilon_0$. \vskip 8pt \noindent{\bf Step 20.} Find a condition on $\A$, $\B$, and $C$ so that the induction step goes through for large $u$. We need to know for the range $\epsilon_0 n^{1/2} \le k \le 25n^{1/2}\log n $ that $$ {ue^{-v} \over n} ~\le~ C {k^\A \over n^\B} {c_1(\A - \B) \over k}; $$ for this it suffices to have \bigskip ~~~~~~~~~~~~~~~~~~~~~~~~\hbox{\vrule\vbox{\hrule \hbox spread 8pt{\hfil\vbox spread 8pt{\vfil \hbox{$(1-\A)/2 < 1-\B,~~~~\A > \B $}% \vfil}\hfil} \hrule}\vrule}% \vskip 8pt \noindent{\bf Step 21.} Make a special argument for the range of extraordinarily large $k$; that is, $k > 25n^{1/2}\log n$. \vskip 8pt \noindent{\bf Step 22.} Choose $\A$ and $\B$ subject to the accumulated restrictions so as to prove the best possible bound on $b(n,k)$ of the form $n^{-c}$. Taking $\A$ slightly larger than $1/3$, and $\B = 1/3$, and again making a special argument for $k > 25n^{1/2}\log n$, we obtain the result stated in the Theorem. \vskip 12pt \centerline{\bf 3 Details.} \noindent Within this part of the paper we'll label our remarks as \Stepx 1, \Stepx 2, etc. to parallel the labeling of the Steps in the previous section. \vskip 8pt \noindent{\bf \Stepx 1.} This is a well known recursion, and here is a proof: (see [\Comtet, p. 96], for example) if a partition has fewer than $k$ parts, then it is counted by $\P(n,k-1)$; on the other hand, if it has exactly $k$ strictly positive parts, then each part can be reduced by 1 and there results a partition counted by $\P(n-k,k)$. \vskip 8pt \noindent{\bf \Stepx 2.} This step requires creativity. In the problem under consideration, the number of partitions $P(n,k)$, one can glean the correct form from Szekeres' papers. In attacking a previously unsolved recursion, one might carry out Step 5 first, making an educated guess based on that. Presumably any incorrect assumptions will be exposed as frauds in later steps. Note that the function $f(u)$ in the theorem appears at this point in logarithmic form: $ f = \exp\{a\}.$ \vskip 8pt \noindent{\bf \Stepx 3.} This step involves calculating a number of Taylor expansions. For now we ignore error bounds and carry each expansion out to enough terms to find the differential equations in the next step. Later, in \Stepsx 13 and 17, the quantity indicated by the ellipsis $\cdots$ in each equation must be filled in. (In \Stepx 13 we find suitable big-oh terms for the $\cdots$'s when $u$ is restricted to be smaller than $\epsilon_0$; in \Stepx 17 we do the same for large $u$.) First, for the term $\P(n-k,k)$, $$\eqalignno{ k(n-k)^{-1/2} ~~&=~~ u ~+~ \bigl( u^2/2n^{1/2} + 3u^3/8n + \cdots \bigr) \cr g\bigl(k(n-k)^{-1/2}\bigr) ~~&=~~ g(u) ~+~ u^2g'(u)/2n^{1/2} ~+~ \bigl(3u^3g'(u) + u^4g''(u) \bigr)/8n ~+~ \cdots \cr a\bigl(k(n-k)^{-1/2}\bigr) ~~&=~~ a(u) ~+~ u^2a'(u)/2n^{1/2} ~+~ \cdots \cr (n-k)^{1/2} ~~&=~~ n^{1/2} ~-~ u/2 ~-~ u^2/8n^{1/2} ~+~ \cdots &(3.1) \cr n(n-k)^{-1} ~~&=~~ 1 ~+~ k(n-k)^{-1} ~~=~~ \exp\{u/n^{1/2} + \cdots \} \cr \P(n-k,k) ~~&\approx~~ (n-k)^{-1} \exp \bigl\{ (n-k)^{1/2} g\bigl(k(n-k)^{-1/2}\bigr) ~+~ a\bigl(k(n-k)^{-1/2}\bigr) \bigr\} \cr ~~&=~~ n^{-1} \exp \bigl\{ n^{1/2}g(u)+a(u)\bigr\} \cr ~~&~~~~~~~~~~\times~~e^{-v}\bigl( 1 ~+~ { -uv/4 + u^4g''(u)/8 + u^2a'(u)/2 + u \over n^{1/2}} ~+~ \cdots\bigr). \cr }$$ Second, for the term $\P(n,k-1)$, which is computationally simpler, $$\eqalignno{ (k-1)n^{-1/2} ~~&=~~ u ~-~ n^{-1/2} \cr g\bigl((k-1)n^{-1/2}\bigr) ~~&=~~ g(u) ~-~ g'(u)/n^{1/2} ~+~g''(u)/2n ~+~ \cdots\cr a\bigl((k-1)n^{-1/2}\bigr) ~~&=~~ a(u) ~-~ a'(u)/n^{1/2} ~+~ \cdots &(3.2) \cr \P(n,k-1) ~~&\approx~~ n^{-1} \exp \bigl\{ n^{1/2} g\bigl((k-1)n^{-1/2}\bigr) ~+~ a\bigl((k-1)n^{-1/2}\bigr) \bigr\} \cr ~~&=~~ n^{-1} \exp \bigl\{ n^{1/2}g(u)+a(u)\bigr\} \cr ~~&~~~~~~~~~~\times~~e^{-g'}\bigl( 1 ~+~ { g''(u)/2 -a'(u) \over n^{1/2}} ~+~ \cdots\bigr). \cr }$$ >From these we read off the formulas $$ \eqalignno{ A_1 ~~&=~~ -uv/4 + u^4g''(u)/8 + u^2a'(u)/2 + u \cr A_2 ~~&=~~ g''(u)/2 - a'(u). &(3.3) \cr }$$ \vskip 8pt \noindent{\bf \Stepx 4.} Let us begin by computing all the derivatives we will need from here on. Assume that $g$,$v$, and $a$ are given by (1.2), (1.3) and the logarithm of (1.1); then $$ \eqalignno{ v' ~&=~ v/u + {uv/2 \over e^v - 1 - u^2/2} \cr g' ~&=~ - \log(1-e^{-v}) \cr g'' ~&=~ {-v/u \over e^v - 1 - u^2/2} \cr g''' ~&=~ {(v/u)^2e^v(e^v-1) \over (e^v - 1 - u^2/2)^3} - {3v/2 \over (e^v - 1 - u^2/2)^2} &(3.4) \cr a(u) ~&=~ -\log(2^{3/2}\pi) ~+~ \log{v \over u} - \half \log \bigl(1-e^{-v}(1+u^2/2)\bigr) \cr a'(u) ~&=~ {u-v/2u-uv/4 \over e^v - 1 - u^2/2} - {u^3v/8+uv/4 \over (e^v - 1 - u^2/2)^2} \cr a''(u) ~&=~ \sum_{j=1}^4 {p_j \over (e^v - 1 - u^2/2)^j}, ~p_j = {\rm~polynomial~in~}u,v,u^{-1}. \cr } $$ In the last expression only $p_1 = 1+v^2/4-3v/2+v^2/2u^2$ will be needed explicitly. The calculation of $g'$ verifies relation (2.1). With $A_1$ and $A_2$ defined by (3.3), we want to check relation (2.2). Since only $a'(u)$, and not $a(u)$, enters into the latter relation, the function $a(u)$ is determined by this relation only up to an additive constant. The value $-\log(2^{3/2}\pi)$ chosen above gives the right hand limit $$ a(0^+) ~=~ -\log 2\pi, \eqno(3.5) $$ which is needed later in \Stepx 7. Since each of $A_1$, $A_2$, $e^v$, and $e^{-g'}=1-e^{-v}$ is a rational function of $u$, $v$, and $e^v$, verification of the relation (2.2) is reduced to some (albeit tedious) rational algebra in three variables. \vskip 8pt \noindent{\bf \Stepx 5.}We follow Erd\"{o}s and Lehner [\EL] for this step. It is well known [\Comtet, p. 123] that the binomial coefficient $ {n-1 \choose k-1} $ counts the number of integer $k$-tuples satisfying $$ n = x_1 + \cdots + x_k;~~~~~ x_i > 0, $$ because each such solution corresponds to choosing $k-1$ out of the $n-1$ gaps available when $n$ dots are placed in a row. Such $k$-tuples differ from partitions in that the order of the summands counts; they are called {\it compositions}. How many $(n,k)$-compositions contain a repeated part ? This was answered first in [\EL], and has been readdressed in later literature. The number in question is certainly bounded above by $$ \eqalign{ {k \choose 2} \sum_{h \ge 1}{n-2h-1 \choose k-3} &\le {k \choose 2} \sum_{h \ge 1}{n-2-h \choose k-3} \cr &= {k \choose 2} {n-2 \choose k-2} \cr &= \Oh(k^3/n) {n-1 \choose k-1}. \cr }$$ The number of $(n,k)$-compositions with no repeated part is equal to $k!$ times the number of partitions of $n$ into $k$ positive distinct parts. Reducing the smallest part by 1, the next smallest part by 2, etc., the latter number of partitions is seen to be $\P(n-{k+1 \choose 2},k)$, and so $$ \P(n-{k+1 \choose 2},k) ~~=~~ {1 \over k!} {n-1 \choose k-1} \exp \{ \Oh(k^3/n) \}. $$ The first equation in Step 5 follows, and the second is obtained by using $$ {n-1 \choose k-1} ~~=~~ {k \over n} {n^k \over k!} \exp\{ \Oh(k^2/n)\}$$ and Stirling's formula. \vskip 8pt \noindent{\bf \Stepx 6.} No comment necessary. \vskip 8pt \noindent{\bf \Stepx 7.} We want estimates of $g$ and $a$ for small $u$. In \Stepx 13 we need similar estimates for the higher derivatives of these functions, so we record them all here. The big-oh terms are uniform for bounded $u$. The right side of the equation (1.3) is readily seen to be $v + v^2/4 + \Oh(v^3)$; this can be inverted to obtain $$ v ~=~ u^2 - u^4/4 + \Oh(u^6). $$ This and (3.4) lead to the formulas stated below for $g$ and its derivatives. For $a''(u)$ a different argument is needed since our explicit formula is incomplete. By the Reversion Theorem and other standard results on real power series [\Knopp, Chapter~5, esp. Section~21] it follows that first $v(u)$, then $a(u)$ due to fortuitous cancelling among logarithmic terms, are represented by convergent power series in some interval $(-\eta,+\eta)$ about $u=0$. Given this, the assertions about $a'$ and $a''$ follow from that about $a$. $$ \eqalignno{ g(u) ~~&=~~ -2u\log u ~+~ 2u ~+~ \Oh(u^3) \cr g'(u) ~~&=~~ -2\log u ~+~ \Oh(u^2) \cr g''(u) ~~&=~~ -2/u ~+~ \Oh(u) \cr g'''(u) ~~&=~~ 2/u^2 ~+~ \Oh(1) &(3.6) \cr a(u) ~~&=~~ -\log 2 \pi \, +\, \Oh(u^4) \cr a'(u) ~~&=~~ \Oh(u^3) \cr a''(u) ~~&=~~ \Oh(u^2). \cr }$$ Again, these estimates are uniform for bounded $u$. \vskip 8pt \noindent{\bf \Stepsx 8 through 12.} No comment necessary. \vskip 8pt \noindent Recall that throughout \Stepsx 13 through 16 we have $u \le \epsilon_0$, and all big-oh assertions are uniform for that range. \vskip 8pt \noindent{\bf \Stepx 13.} Reexamining the definition in Step 11 of $T_1$ and $T_2$, we see that what's needed is to make modifications in the formal expansions of Step 3 so that the imprecise $\approx$ signs can be replaced with exact equalities $=$. This is accomplished by determining rigorous big-oh terms for the ellipses $\cdots$ in those expansions. Refer to the series of calculations (3.1). If we find suitable big-oh terms for the six $\cdots$'s appearing in that series of calculations, the final one is in fact the desired $T_1$ formula. Likewise the three $\cdots$'s in (3.2) for $T_2$. All that's needed is Taylor's formula with remainder, which we state here in generic form: $$ G(u+\Delta u) ~~=~~ G(u) ~+~ \Delta u G'(u) ~+~ \half (\Delta u)^2 G''(u) ~+~ {\textstyle{1 \over 6}} (\Delta u)^3 G''(\xi), $$ with $\xi$ between $u$ and $u + \Delta u$. The latter is appropriate for the expression $(n-k)^{1/2}g(k(n-k)^{-1/2})$; for $a(k(n-k)^{-1/2})$ one less term suffices. Replacing $\Delta u$ by $u^2/2n^{1/2} + 3u^3/8n + \Oh(u^4n^{-3/2})$, using the bounds (3.6), and noting $\Delta u = \oh(u)$ so that $g'''(\xi) = \Oh(u^{-2})$, we find that the first five $\cdots$'s in (3.1) can be filled in with, respectively: $\Oh(u^4n^{-3/2})$, $\Oh(u^4\log(u)\,n^{-3/2})$, $\Oh(u^3n^{-1})$, $\Oh(u^3n^{-1})$, and $\Oh(u^2n^{-1})$. These five combine algebraically to determine the sixth as the desired $\Oh(u^2n^{-1})$. In like manner the three ellipses $\cdots$ in (3.2) may be filled in with $\Oh(u^{-2}n^{-3/2})$, $\Oh(u^2n^{-1})$, and $\Oh(u^{-2}n^{-1}).$ \vskip 8pt \noindent{\bf \Stepx 14.} The first assertion, about $b(n,k)$, is immediate from the previous step. The second follows by straightforward algebra, using $A_1 = \Oh(u)$ and $A_2 = \Oh(u^{-1})$ for the two products, and then the relations (2.1,2.2) to simplify the sum. The fact that $e^{-g'} = \Oh(u^2)$ is needed. \vskip 8pt \noindent{\bf \Stepx 15.} By (3.6) we have $e^{-g'} = u^2 + \Oh(u^4)$, and by (2.1) $e^{-v} = 1+\Oh(u^2)$; hence, $$\eqalign{ \A e^{-g'}/k \,-\, \B e^{-v}k/n ~&=~ \bigl( \A e^{-g'}/u \,-\, \B e^{-v}u \bigr)\big/ n^{1/2} \cr ~&=~ \bigl( \A u \,-\, \B u ~+~ \Oh(u^3) \bigr)\big/ n^{1/2}, \cr }$$ which gives the desired lower bound if $\epsilon_0$ is set sufficiently small. \vskip 8pt \noindent{\bf \Stepx 16.} No comment necessary. \vskip 8pt \noindent Recall that throughout \Stepsx 17 through 20 we assume that $u \le \epsilon_0$; further, all big-oh assertions are uniform for that range. \vskip 8pt \noindent{\bf \Stepx 17.} This step is completed in much the same manner as was Step 13. First we need the large $u$ analog of the small $u$ approximations appearing in (3.6). Observe that $$\int_0^{\infty} {t \over e^t-1}dt ~=~ {\pi^2 \over 6},$$ as can be seen by expanding $(e^t-1)^{-1}$ as $\sum_{m=1}^{\infty} e^{-mt}$ and using the well known $\sum_{m=1}^{\infty}m^{-2} = \pi^2/6$. By this we conclude from (1.3) that $$ {v \over u} ~\rightarrow~\pi/6^{1/2} {\rm ~as~}u \rightarrow \infty. \eqno(3.7) $$ Thus for $u \ge \epsilon_0$ the ratio $v/u$ is confined to a closed interval $[\eta,M]$, $0 < \eta < M <\infty$. This plus formulas (1.2) and (3.4) suffice to prove $$ g=\Oh(1),~~~~g',g'',g''' ~=~ \Oh(e^{-v}),~~~~ a',a'' ~=~ \Oh(u^2e^{-v}). \eqno(3.8) $$ Consider again the series of equations (3.1). Because $\Delta u = \Oh(u^2n^{-1/2})$, it follows that $v(\xi)$, the $v$-value corresponding to $\xi$, equals $v(u)+ \oh(1)$; hence, $g'''(\xi_1)=\Oh(e^{-v})$ and $a''(\xi_2) = \Oh(u^2e^{-v})$. We may then calculate that the proper substitutions for the six ellipses $\cdots$ appearing in (3.1), when $u \ge \epsilon_0$, are $\Oh(u^4n^{-3/2})$, $\Oh(u^6e^{-v}n^{-3/2})$, $\Oh(u^6e^{-v}n^{-1})$, $\Oh(u^3n^{-1})$, $\Oh(u^2n^{-1})$, and $\Oh(u^4n^{-1})$. In like manner the three ellipses appearing in (3.2) are filled in with $\Oh(u^2e^{-v}n^{-3/2})$, $\Oh(u^2e^{-v}n^{-1})$, and $\Oh(u^2e^{-v}n^{-1})$. \vskip 8pt \noindent{\bf \Stepx 18.} This is similar to Step 14, and is straightforward using $A_1 = \Oh(u^2)$, $A_2 = \Oh(u^2 e^{-v})$. \vskip 8pt \noindent{\bf \Stepx 19.} Because $t(e^t-1)^{-1}$ is a decreasing function of $t$, we have $$ {v^2 \over u^2} ~=~ \TheInt ~\ge~ v{v \over e^v-1} ~=~ {v^2 \over e^v-1},$$ and so $$ e^v-1 ~\ge~ u^2.$$ Hence, $$\eqalign{ \A e^{-g'}/k \,-\, \B e^{-v}k/n ~&=~ \bigl( \A e^{-g'} \,-\, \B e^{-v}u^2 \bigr)/k \cr &\ge~ \bigl( \A(1-e^{-v}) - \B e^{-v}(e^v-1) \bigr) \big / k \cr &=~ ( \A - \B )(1-e^{-v}) / k, \cr }$$ as needed. \vskip 8pt \noindent{\bf \Stepx 20.} No comment necessary. \vskip 8pt \noindent{\bf \Stepsx 21 and 22.} Define $k_1$, $u_1$ by $$ k_1 = \lfloor 25n^{1/2} \log n\rfloor,~~~u_1 = k_1/n^{1/2}.$$ The following lemma is the key to Steps 21 and 22. \vskip 8pt \noindent{\bf Lemma.} Assume $4 \ge \A-\B > 0$, and $$|b(\nu,k)| \le Ck^{\A}/\nu^{\B} {\rm ~for~} \nu < n {\rm ~or~} (\nu=n {\rm ~and~} k \le k_1).$$ Then, uniformly for $C \ge 1$ and $k \ge k_1$ $$ 1 + b(n,k) ~=~ \bigl( 1+b(n,k_1) \bigr) \bigl( 1+\Oh(Cn^{-24}) \bigr) $$ \noindent{\bf Proof.} The desired result follows from $$\eqalignno{ g(u) - g(u_1) ~&=~ \Oh(n^{-25}) {\rm ~for~} u>u_1 &(i)\cr a(u) - a(u_1) ~&=~ \Oh(n^{-24}) {\rm ~for~} u>u_1 &(ii)\cr P(n,k)/P(n,k_1) ~&=~ 1+\Oh(Cn^{-24}) {\rm ~for~} n \ge k > k_1. &(iii)\cr }$$ To see (i), recall (3.8) that $g'(u) = \Oh(e^{-v})$, and (3.7) that $v/u \rightarrow \pi/6^{1/2} > 1$. For the range of $u$ under discussion $e^{-v} = \oh(e^{-u})$, and so $$ g(u) ~=~ g(u_1)+\int_{u_1}^u g'(t)dt ~<~ g(u_1)+e^{-u_1} ~=~ g(u_1) + \Oh(n^{-25}).$$ Relation (ii) is handled similarly. Since $1+C\nu^{\A-\B} \le 2C\nu^{\A-\B}$ and $g$ is increasing, we have $$ p(\nu)~=~ P(\nu,\nu) ~<~ c_2 C \nu^{\A-\B-1}e^{c_3 \sqrt{\nu}} {\rm ~for~} \nu 5/2.$$ The above limit is determined by (3.7) and (1.2). Since $P(n,k)$ increases with $k$, it suffices to prove (iii) for $k=n$. Using $(n-k_1)^{1/2} < n^{1/2} - 12\log n$ and $c_3 = g(u_1) + \Oh(n^{-24})$, we have for large $n$ $$ \eqalign{ P(n,n)-P(n,k_1)&= \sum_{n \ge k > k_1} P(n-k,k) \cr &< (n-k_1)p(n-k_1) \cr &< c_2 C (n-k_1)^{\A-\B}e^{c_3\sqrt{n-k_1}} \cr &< C n^{\A-\B-30}e^{c_3\sqrt{n}} \cr &< C n^{\A-\B-29}\exp\{n^{1/2}g(u_1)\}. \cr }$$ Dividing through by $P(n,k_1) = n^{-1}\exp\{n^{1/2}g(u_1) +\Oh(1)\}$, we obtain (iii). The proof of the lemma is complete. \vskip 8pt To complete Step 21, use the Lemma and the known result on $b(n,k_1)$ to find, for $n \ge k > k_1$, $$ |b(n,k)| ~\le~ |b(n,k_1)| + \Oh(Cn^{-24}) ~\le~ C\bigl( {k_1^{\A} \over n^{\B}} + \Oh(n^{-24})\bigr).$$ Collecting the conditions needed to prove the Lemma with conditions sufficient to prove the rightmost term above is $\le C(k_1+1)^{\A}/n^{\B}$, we impose \bigskip ~~~~~~~~~~~~~~~~~~\hbox{\vrule\vbox{\hrule \hbox spread 8pt{\hfil\vbox spread 8pt{\vfil \hbox{$ C \ge 1,~~ 4 \ge \A-\B>0,~~ \B < 24 + \min\{0,(\A-1)/2\} $}% \vfil}\hfil} \hrule}\vrule}% \smallskip We now turn to Step 22. Choosing $\A=1/3+\epsilon$, $\B=1/3$, $\delta_2 = 1/4$, and $\delta_1$ sufficiently close to $\delta_2$ satisfies the four accumulated constraints on $\A$ and $\B$. Hence, $|b(n,k)| \le Cn^{-1/6+\epsilon/3}$ for $n$ large and $k \le k_1$ by the $Ck^{\A}/n^{\B}$ bound. By the Lemma, we see that $|b(n,k)| \le Cn^{-1/6+\epsilon/4}$ for large $n$ and all $k$. Since $\epsilon$ is arbitrary, the Theorem has been proved. \vskip 12pt \centerline{\bf 4 Conclusion.} Hardy and Ramanujan gave a complete asymptotic expansion for $p(n)$, and Szekeres did the same for $P(n,k)$. Later Rademacher extended earlier work to find a convergent sum for $p(n)$. I do not know any of the later terms in Szekeres' expansion explicitly, or any results concerning convergence of his expansion. It seems possible that the method described in this paper could produce at least one additional asymptotic term, but I have not done it. As for the size of the overall relative error, $\Oh(n^{-1/6+\epsilon})$, improving on this requires starting the induction in the Erd\"{o}s-Lehner range with something more accurate. For instance, if we show by a combinatorial argument more involved than the one in \Stepx 5 that $$ P(n,k) ~=~ {n-1 \choose k-1} \exp\{c_4k^3/n+\Oh(k^5/n^2)\}, ~~k = \Oh(n^{2/5}), \eqno(4.1) $$ then our conclusion in Step 8 becomes $$ b(n,k) ~=~ \Oh(k^5/n^2+1/k), ~~ k = \Oh(n^{2/5}), $$ and the first constraint on $\A$ and $\B$ in Step 10 improves to $$ \B ~\le~ (1+\A)\delta_1, ~~(5-\A)\delta_2 ~\le~2-\B, ~~ \delta_1 < \delta_2 < 2/5.$$ The correct value of $c_4$ in (4.1), by [\SzekTwo], is $-1/4$, but I do not have a combinatorial proof of this. Such a revised start to the induction improves the $\Oh(n^{-1/6+\epsilon})$ error to $\Oh(n^{-1/4+\epsilon})$. For any $\epsilon > 0$, an overall error of $\Oh(n^{-1/2+\epsilon})$ can be achieved by a sufficiently accurate (hence increasingly complex) combinatorial argument at the start of the induction. To break the $\Oh(n^{-1/2})$ barrior, however, requires introducing an additional term in the exponent of the guessed form, making it $n^{1/2}g(u)+a(u)+a_1(u)n^{-1/2}$, as alluded to in the previous paragraph. As shown by Szekeres [\SzekTwo], classical asymptotic formulas for $p(n)$ and $q(n)$ follow from the Theorem. \vskip 8pt \noindent{\bf Corollary 1.} (Hardy and Ramanujan [\HR]) Let $p(n)$ be the number of partitions of $n$; for any $\epsilon > 0$, $$ p(n) ~=~ {1 \over 4\cdot 3^{1/2}n}e^{\pi\sqrt{2n/3}}\bigl(1+ \Oh(n^{-1/6+\epsilon})\bigr).$$ \noindent{\bf Proof.} Using (3.7), (1.1), and (1.2) $$ g(u) ~\rightarrow~ \pi(2/3)^{1/2},~~ f(u) ~\rightarrow~ 1/4\cdot 3^{1/2}, {\rm ~as~} u \rightarrow \infty. $$ This yields Corollary 1. \vskip 8pt \noindent{\bf Corollary 2.} (Hardy and Ramanujan [\HR]) Let $q(n)$ be the number of partitions of $n$ into distinct parts; for any $\epsilon > 0$, $$ q(n) ~=~ {1 \over 4\cdot 3^{1/4}n^{3/4}}e^{\pi\sqrt{n/3}}\bigl(1+ \Oh(n^{-1/6+\epsilon})\bigr).$$ \noindent{\bf Proof.} Let $q(n,k)$ be the number of partitions of $n$ into $k$ distinct parts. Since $q(n,k)=P(n-{k+1 \choose 2},k)$, we have uniformly for $\epsilon_1 n^{1/2} \le k \le (2^{1/2} - \epsilon_1) n^{1/2}$, ($\epsilon_1$ fixed) $$ q(n,k) ~=~ {F(u) \over n} \exp \bigl\{ n^{1/2}G(u)+\Oh( n^{-1/6+\epsilon}) \bigr\},$$ where $$ \eqalign{ F(u) ~&=~ (1-u^2/2)^{-1} f\bigl(u(1-u^2/2)^{-1/2}\bigr) \exp\{-\half v_*(u)\} \cr G(u) ~&=~ (1-u^2/2)^{1/2} g\bigl(u(1-u^2/2)^{-1/2}\bigr) \cr v_*(u) ~&=~ v\bigl(u(1-u^2/2)^{-1/2}\bigr). \cr }$$ Let $u_0$ satisfy the equation $G'(u_0)=0$; then uniformly for $t = \Oh(n^{1/3})$ $$q(n,u_0n^{1/2}+t) ~=~ {F(u_0) \over n} \exp \bigl\{ n^{1/2}G(u_0)+\half t^2G''(u_0)n^{-1/2} +\Oh( n^{-1/6+\epsilon}) \bigr\}.$$ By a standard argument in asymptotic methods ([\Odlyz], 5.1), a key step of which is $$\sum_{|t|\le n^{1/3}} \exp(\half t^2 G'' n^{-1/2}) =n^{1/4}(1+\oh(1))\int_{-\infty}^{+\infty}e^{G''x^2/2}dx =n^{1/4}(-2\pi/G'')^{1/2}(1+\oh(1)),$$ with a relative error $\oh(1)$ much smaller than the $\Oh (n^{-1/6+\epsilon})$ precision which we are maintaining, one may show that terms $q(n,k)$ with $|k-u_0 n^{1/2}| > n^{1/3}$ contribute insignificantly to $\sum_k q(n,k)$ and conclude $$ q(n) ~=~ {F(u_0) \over n^{3/4}}\sqrt{2\pi \over -G''(u_0)} \exp \bigl\{ n^{1/2}G(u_0)+\Oh(n^{-1/6+\epsilon}) \bigr\}.$$ To obtain the corollary, one must evaluate $u_0$, $G(u_0)$, $F(u_0)$, and $G''(u_0)$, an intriguing exercise for aficionados of algebra and analysis. In the interest of bringing the paper to a close, we will just mention two highlights of the calculation. First, $G'(u)$ has a nice form: $$ G'(u) ~=~ -v_*(u) - \log(1-e^{-v_*(u)}). $$ Hence, to make $G'$ vanish we need $$ v_*(u_0) = \log 2.$$ Determining $u_0$ requires (see [\AS], 27.7.7 and 27.7.3) $$ \int_0^{\log 2}{t \over e^t-1}dt ~=~ -\half (\log 2)^2 + {\pi^2 \over 12}.$$ \eject \centerline{\bf Cited Publications} \book {\AS} {M. Abramowitz and I. Stegun} {Handbook of Mathematical Functions} {Dover} {1973}. \reference {\BCMOne} {E. A. Bender, E. R. Canfield, and B. D. McKay} {The asymptotic number of labeled connected graphs with a given number of vertices and edges} \journal {Random Structues and Algorithms}{1}{1990}{127--169}. \reference {\BCMTwo} {E. A. Bender, E. R. Canfield, and B. D. McKay} {The asymptotic number of labeled graphs with $n$ vertices, $q$ edges, and no isolated vertices} \preprint. \book {\Comtet}{L. Comtet} {Advanced Combinatorics} {D. Reidel} {1974}. \reference {\EL} {P. Erd\"{o}s and J. Lehner} {The distribution of the number of summands in the partitions of a positive integer} \journal {Duke Math. J.}{8}{1941}{335--345}. \reference {\Erdos} {P. Erd\"{o}s} {On an elementary proof of some asymptotic formulas in the theory of partitions} \journal {Annals of Math.(2)}{43} {1942} {437--450}. \reference {\HR}{G. G. Hardy and S. Ramanujan} {Asymptotic formulae in combinatory analysis} \journal {J. London Math. Society} {17}{1918}{75--115}. \reference {\KKOne} {C. Knessl and J. B. Keller} {Partition asymptotics for recursion equations} \journal {SIAM J. Appl. Math.} {50} {1990} {323--338}. \reference {\KKTwo} {C. Knessl and J. B. Keller} {Stirling number asymptotics from recursion equations using the ray method} \journal {Studia Appl. Math.} {84} {1991} {43--56}. \book {\Knopp} {K. Knopp} {Theory and Application of Infinite Series} {Dover} {1990}. \reference {\Odlyz} {A. M. Odlyzko} {Asymptotic enumeration methods} \collection {R. L. Graham, M. Gr\"{o}tschel, and L. Lov\'{a}sz, {\it eds.}} {Handbook of Combinatorics, volume II} {Elsevier} {1995} {1063--1229}. \def\preprint {\rm preprint} \reference {\SzekOne} {G. Szekeres} {An asymptotic formula in the theory of partitions} \journal {Quart. J. of Math. (Oxford) (2)} {2} {1951} {85--108}. \reference {\SzekTwo} {G. Szekeres} {Some asymptotic formulae in the theory of partitions (II)} \journal {Quart. J. of Math. (Oxford) (2)} {4} {1953} {96--111}. \bye