% Partitions paper - version of March 26 1998 %\documentstyle[11pt,boxit]{article} %\documentstyle[11pt]{article} \documentstyle[11pt,amssymbols]{article} %\input amssym.def %\input amssym.tex %\newcommand{\lab}[1]{\label{#1}\ {\bf[#1]}\ } % displays labels \newcommand{\lab}[1]{\label{#1}} % hides labels \setlength{\textwidth}{6.2in} \setlength{\textheight}{9.2in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.35in} \setlength{\headheight}{0in} %%%GREEK LETTERS \newcommand{\La}{\Lambda} \newcommand{\Ga}{\Gamma} \newcommand{\Dt}{\Delta} \newcommand{\bDt}{\mbox{\boldmath $\Delta$}} \newcommand{\la}{\lambda} \newcommand{\af}{\alpha} \newcommand{\be}{\beta} \newcommand{\ep}{\epsilon} \newcommand{\vp}{\varphi} \newcommand{\vt}{\vartheta} \newcommand{\om}{\omega} \newcommand{\Om}{\Omega} \newcommand{\Th}{\Theta} \newcommand{\tht}{\theta} \newcommand{\Sg}{\Sigma} \newcommand{\In}{\infty} \newcommand{\dr}{\Rightarrow} \newcommand{\dt}{\delta} \newcommand{\ga}{\gamma} \newcommand{\sig}{\sigma} \newcommand{\zt}{\zeta} \newcommand{\et}{\eta} \newcommand{\lf}{\lfloor} \newcommand{\rf}{\rfloor} \newcommand{\lc}{\lceil} \newcommand{\rc}{\rceil} \newcommand{\lt}{\left(} \newcommand{\rt}{\right)} \newcommand{\dd}{\ldots} %\newcommand{\ZZ}{{\Bbb Z}} \def\ZZ{\hbox{\rm Z\kern-3pt Z}} \newcommand{\df}{\displaystyle\frac} \newcommand{\dis}{\displaystyle} \newcommand{\ds}{\displaystyle\sum} \newcommand{\bzero}{{\bf 0}} \newtheorem{coro}{Corollary}[section] \newtheorem{conj}{Conjecture}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}{Theorem}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{remark}{\bf Remark}[section] \newtheorem{exam}{Example}[section] \newcommand{\eqn}[1]{(\ref{#1})} \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\vsp}{\vspace{.1in}} \newcommand{\pf}{\noindent{\bf Proof.~}} \newcommand{\eeq}{\end{equation}} \newcommand{\beql}[1]{\begin{equation}\lab{#1}} \def\binom#1#2{{#1}\choose{#2}} \def\blackslug{\hbox{\kern1pt\vrule height6pt width4pt depth1pt\kern1pt}} \def\qed{\penalty 500\hbox{\quad\blackslug}\ifmmode\else\par \vskip4.5pt plus3pt minus2pt\fi} \def\blacksquare{\blackslug} \def\blam{{\bf \lambda}} \def\bE{{\bf E}} \def\bP{{\bf P}} \def\pr{\bP} % extra defs \def\bi{\bigskip\noindent} \def\si{\smallskip\noindent} \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \newcommand{\bean}{\begin{eqnarray*}} \newcommand{\eean}{\end{eqnarray*}} \newcommand{\bea}{\begin{eqnarray}} \newcommand{\eea}{\end{eqnarray}} \def\non{\nonumber} \def\no{\noindent} \def\eps{\varepsilon} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \newcommand{\Bnu}{\mbox{\boldmath $\nu$}} \newcommand{\Bmu}{\mbox{\boldmath $\mu$}} %%%Filename is periodsec.sty%%% \makeatletter % put a period after section or subsection number in header \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} % put a period after theorem and theorem-like numbers \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \thispagestyle{empty} \renewcommand{\baselinestretch}{1} \def\spacea{0.2} \def\spaceb{0.9} %%%%%%%%%%%%%%%%%%%%%%% Picture defs \def\figureone{ \input epsf \begin{figure}[htb] \epsfxsize = 10cm \vbox{\vskip .8cm\hbox{\centerline{\epsffile{psfile.ps}}} \smallskip} \caption{ $\log f(200,k)$ } \end{figure} } \begin{document} \begin{center} {\Large {\bf The asymptotic number of set partitions with unequal block sizes}} \\ \vspace{\baselineskip} \vspace{\spaceb\baselineskip} {\em A. Knopfmacher} \\ \vspace{\spacea\baselineskip} Department of Computational and Applied Mathematics \\ University of Witwatersrand \\ Johannesburg, South Africa \\ e-mail: arnoldk@gauss.cam.wits.ac.za \\ \vspace{\spaceb\baselineskip} {\em A. M. Odlyzko} \\ \vspace{\spacea\baselineskip} AT\&T Labs - Research \\ Florham Park, New Jersey 07932, USA \\ e-mail: amo@research.att.com \\ \vspace{\spaceb\baselineskip} {\em B. Pittel}\footnote{Research supported by the ``Focus on Discrete Probability Program" at the Dimacs Center of Rutgers University in Spring of 1997, and under NSA Grant MDA 904-96-1-0053.} \\ \vspace{\spacea\baselineskip} Department of Mathematics \\ Ohio State University \\ Columbus, Ohio 43210, USA \\ e-mail: bgp@math.ohio-state.edu \\ \vspace{\spaceb\baselineskip} {\em L.~B. Richmond} \\ \vspace{\spacea\baselineskip} Department of Combinatorics and Optimization \\ University of Waterloo \\ Waterloo, Ontario N2L 3G1, Canada \\ e-mail: lbrichmo@watdragon.uwaterloo.ca \\ \vspace{\spaceb\baselineskip} {\em D. Stark}\footnote{Current address: BRIMS, Hewlett-Packard Labs, Filton Road, Stoke Gifford, Bristol Bs12 6QZ, UK} \\ \vspace{\spacea\baselineskip} Department of Mathematics and Statistics\\ University of Melbourne \\ Parkville, Victoria 3052, Australia \\ e-mail: dstark@maths.mu.oz.au \\ \vspace{\spaceb\baselineskip} {\em G. Szekeres} \\ \vspace{\spacea\baselineskip} Department of Mathematics \\ University of New South Wales \\ Kensington, New South Wales 2033, Australia \\ e-mail: G.Szekeres@unsw.edu.au\\ \vspace{\spaceb\baselineskip} {\em N.~C. Wormald}\footnote{Research supported by Australian Research Council} \\ \vspace{\spacea\baselineskip} Department of Mathematics and Statistics\\ University of Melbourne \\ Parkville, Victoria 3052, Australia \\ e-mail: nick@maths.mu.oz.au \\ \newpage {\bf ABSTRACT} \vspace{.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \hspace*{.25in} The asymptotic behavior of the number of set partitions of an $n$-element set into blocks of distinct sizes is determined. This behavior is more complicated than is typical for set partition problems. Although there is a simple generating function, the usual analytic methods for estimating coefficients fail in the direct approach, and elementary approaches combined with some analytic methods are used to obtain most of the results. Simultaneously, we obtain results on the shape of a random partition of an $n$-element set into blocks of distinct sizes. %\clearpage \vspace{.5\baselineskip} \large\normalsize %\thispagestyle{empty} \setcounter{page}{1} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hspace*{\parindent} The literature on enumerating set partitions is not as extensive as that on ordinary partitions, but it is large. We refer to \cite{BOR,GS, Pi} for references to recent papers. In this note we investigate $b_n$, the number of partitions of an $n$-element set with blocks of unequal sizes. Carlitz \cite{Car} has shown that $b_n$ has the explicit generating function \beql{eqN101} F(z) = \sum_{n=0}^\In \frac{b_n}{n!} z^n = \prod_{k=1}^\In \lt 1 + \frac{z^k}{k!} \rt ~. \eeq In addition, according to Wilf (p.~96 in \cite{W}), $F(z)$ is a special case of an enumerator in an exponential family for hands whose cards all have different weights. One interesting aspect of our work is that although $F(z)$ is defined very simply and is entire, we do not obtain our estimates by the usual analytic methods which start by applying Cauchy's formula to express a coefficient as a contour integral. There are other problems with similar generating functions for which the asymptotics are easy to derive. For example, evaluation of sums of multinomial coefficients (p.~126 in \cite{C}) leads to the generating function \beql{eqN102} G(z) = \prod_{k=1}^\In \lt 1 - \frac{z^k}{k!} \rt^{-1} ~. \eeq The function $G(z)$ has a first order pole at $z=1$ with residue $$ R = \prod_{k=2}^\In \lt 1- \frac{1}{k!} \rt^{-1} = 2.529477 \dd ~. $$ The next smallest singularities are the first order poles at $\pm \sqrt{2}$. Therefore $[z^n] G(z)$, the coefficient of $z^n$ in the Taylor series expansion of $G(z)$, satisfies $$ [z^n] G(z) = R+ O(2^{-n/2} ) ~. $$ The analysis of $[z^n] G(z)$ is simple because $G(z)$ has a single dominant singularity at $z=1$. If we consider \beql{eqN105} H(z) = \prod_{k=1}^\In \lt 1 + \frac{z^k}{k} \rt ~, \eeq then $[z^n] H(z)$ is the probability that a permutation on $n$ letters will have all cycle lengths distinct. The unit circle is a natural boundary of analyticity for $H(z)$ and there are no singularities of $H(z)$ in $|z| < 1$, so the situation is more complicated than for $G(z)$. Greene and Knuth \cite{GK} used a Tauberian theorem to show that $$ [z^n] H(z) \sim e^{- \ga} ~~~\mbox{as}~~~ n \to \In~, $$ where $\ga = 0.577 \dd$ is Euler's constant. A generating function similar to $H(z)$ arises when we consider the analogous problem of determining the probability that a polynomial over a finite field with $q$ elements has only distinct degree irreducible factors. See \cite{KW}. The function $F(z)$ is entire and has nonnegative coefficients, so at first glance it might appear that it should be easy to obtain the asymptotics of its coefficients, easier even than for $H(z)$. The usual method for doing this is the saddle point method. It works well in many situations where the generating function is smooth and grows rapidly. However, it cannot be applied to $F(z)$. The basic saddle point conditions are not satisfied, as the high order logarithmic derivatives of $F(z)$ for $z$ real are not sufficiently small. At a more fundamental level, the saddle point method fails here because it requires that on a circle centered at the origin, the integrand can be large only in a small neighborhood of the positive real axis. The function $F(z)$ has $k$ evenly spaced zeros on each circle of radius $$ (k!)^{1/k} \sim k/e ~~~\mbox{as}~~~ k \to \In ~. $$ On the other hand, on the circle of radius $r = (k+ 1/2)/e$, a short analysis shows that $|F(z)| > F(r)/10$, say. Therefore the integrand is not small outside a small region, and the saddle point method cannot possibly work. The generating function $F(z)$ is also one of the relatively rare cases where the simple bound $$ [z^n] F(z) \le \min_{x > 0} F(x) x^{-n} ~, $$ gives a poor result. This bound holds for all generating functions with nonnegative coefficients, and it is often too weak by only a fractional power of $n$ (cf.~\cite{O}). For our function $F(z)$, defined by \eqn{eqN101}, this bound is off only by a constant factor when $n=k+m$ $(m+1)/2$ for $k$ either very small or very close to $m$. It is poor when $\ep m \le k \le (1- \ep ) m$ and $m \to \In$, on the other hand. For most values of $n$, we shall use elementary estimates and some well-known bounds for ordinary partitions (of a number) to express most values of $b_n$ in terms of the number of ordinary partitions of $k$ with bounded or determined largest part. For some particularly recalcitrant values of $n$, this requires more sophisticated analytic techniques. Analysis of the partitions of $k$ completes the task. We use \eqn{eqN101} and define $a_n$ by \beql{eqN109} a_n = [z^n] F(z) = \frac{b_n}{n!} = \sum_{h_1 < h_2 < \cdots < h_r \atop \sum h_j =n} \frac{1}{\prod\limits_{j=1}^r h_j !} ~. \eeq We will show in Proposition~\ref{oldpr201} that the largest term in this sum, when $n=m(m+1)/2 +k$, $0 \le k \le m$, is $$ \frac{(m+1-k)!}{\prod\limits_{j=1}^{m+1} j!} ~, $$ which comes from $r=m$, $\{ h_1 , \dd , h_m \} = \{ 1,2, \dd , m+1 \} - \{ m+1-k \}$. This proposition is not actually used as part of the proof of our asymptotic estimates, but rather to motivate the following definition. We define $f(m,k)$ to be $a_n$ divided by this largest term, that is, \beql{eqN1011} b_n = n! \frac{(m+1-k)! f(m,k)}{\prod\limits_{j=1}^{m+1} j!} ~. \eeq Figure~1 presents a graph of $\log f(200,k)$ for $0 \le k \le 200$, which represents the values of $a_n$ for $20100 \le n \le 20300$. It shows that the oscillations of $f(m,k)$ are large even for small values of $m$. \figureone One disadvantage of $f(m,k)$ as a measure of the behavior of $b_n$ is that it compares $b_n$ to the contribution of the largest term, which does not behave smoothly. Table~1 presents another measure of the irregularity in the behavior of the coefficients $b_n$. It shows the asymptotic form of $b_{n+1}/b_n$ for $n$ near $m(m+1)/2$ as $m \to \In$. It is of interest to note that $b_n$ grows roughly like the square root of the total number of partitions of an $n$ element set, denoted say by $B_n$, in the sense that $\log b_n \sim \frac{1}{2}\log B_n$ as $n \to \infty$. %\pagestyle{empty} \begin{table}[htb] $$ \begin{array}{c|c c c c c c c} j & -3&-2 &-1&0&1&2&3 \\ \hline \phantom{\raisebox{6mm}{.}}{\rm ratio}\phantom{\raisebox{6mm}{.}} &\frac{1}{8} m^2 & \frac{1}{4} m^2 & \frac{1}{2} m^2 & \frac{1}{2} m& m& \frac{3}{4} m& \frac{5}{6} m \\ \end{array} $$ \caption{Asymptotic behavior of the ratio $b_{N+j+1} / b_{N+j}$ for $N = m(m+1)/2$ as $m \to \In$.} \end{table} Equation~\eqn{eqN109} shows that $b_n$ can be interpreted as a certain weighted sum over the ordinary partitions of $n$ with distinct parts. The analogous combinatorial sum over unrestricted partitions of $n$ has as its exponential generating function the function $G(z)$ of Eq.~\eqn{eqN102}. The same sum over compositions (ordered partitions) of $n$ is $B(n) = \sum_{k=1}^n k! S(n,k)$, the number of ordered partitions of an $n$ element set. Finally, by the multinomial theorem, the same sum over ordered $n$-tuples of nonnegative integers is $n^n$. For the similar weighted sum $$ \sum_{\sum h_j =n} \frac{1}{\prod\limits_{j=1}^r h_j} $$ over partitions with distinct parts we have the generating function $H(z)$ of Eq.~\eqn{eqN105} considered by Greene and Knuth. The corresponding sums over unrestricted partitions and compositions are treated in \cite{KR}. The shape of an {\it unrestricted\/} set partition was studied in \cite{DP} and \cite{P2}. It was proved, for instance, that in a typical set partition almost all elements of the set are in blocks of size close to $\log n$ (\cite{DP}). This situation contrasts sharply with the present topic of partitions with distinct block sizes. In this case, we show that a typical partition has blocks of sizes $1, 2, \ldots, s$, where $s$ is approximately $\sqrt{2n}$, with a few missing. We obtain various precise results about the distribution of the missing sizes, from which the shape is determined completely. \section{Main results} Let $p(n)$ and $Q(x)$ be defined by $$ Q(x)= \sum_{k=0}^\In p(n) x^n = \prod_{l=1}^\In \frac{1}{1-x^l}, $$ so that $p(n)$ denotes the number of partitions of (the number) $n$, and $Q$ is its ordinary generating function. Also, define $p(n,k)$ to be the number of partitions of $n$ with largest part at most $k$. We will have use of the rough bound \beql{pnbound} p(n)\le \exp(\pi \sqrt {2n/3})\eeq (valid for all $n\ge 1$; see Apostol \cite{A} for instance) and the more precise \beql{pnasym} p(n) \sim \frac{1}{4\sqrt{3}n}\exp\left(\pi\sqrt{2n/3}\right) \eeq as $n \to\infty$. Moreover, it is well known from Erd\"os and Lehner \cite{EL}, that for almost all partitions of $n$ the largest part is asymptotic to $(\pi\sqrt{2/3})^{-1}n^{1/2}\log n$; thus \beql{maxpart} p(n,[n^{1/2}\log n])\sim p(n) \eeq as $n\to\infty$. \begin{theorem} \lab{prelim} Let $n= k+m(m+1)/2$ and $0 \le k \le m$. Then with $f(m,k)$ defined by \eqn{eqN1011}, we have as $m \to \In$ the asymptotic relations $$ f(m,k) \sim \left\{ \begin{array}{ll} {\displaystyle \frac{[m]_k}{m^k} p(k)}~, & \mbox{if}~~ k = o(m^{2/3}/\log m)~, \\ ~~ \\ [-.07in] \df{1}{(s+1)!} \ds_{v \ge 0} \ds_{d_0 < \cdots < d_v \atop d_0 + \cdots + d_v = s+1} \prod_{j=0}^v d_j !~, & \mbox{if}~~k=m-s,~~s ~\mbox{fixed}~. \end{array} \right. $$ \end{theorem} \begin{theorem} \lab{main1} Let $n= k+m(m+1)/2$ and $0 \le k \le m$. Then with $\omega(m)$ denoting an arbitrary function such that $\omega(m)\to \In$ as $m \to \In$, we have as $m\to \In$ $$f(m,k) \sim \sum_{t=0}^k \frac{[m+1-k+t]_t}{m^t} p(t,k-t)$$ for $\sqrt m \log m< k < m-\omega(m)$. \end{theorem} This formula is actually valid for the small $k$ range as well, and when $k$ is fairly large it can be expressed in an interesting way. \begin{prop}\lab{rewrite} Let $n= k+m(m+1)/2$, $0 \le k \le m$. Then with $f(m,k)$ defined by \eqn{eqN1011} and $\omega(m)$ denoting an arbitrary function $\to \In$ as $m \to \In$, we have as $m \to \In$ $$ f(m,k) \sim \sum_{t=0}^k \frac{[m+1-k+t]_t}{m^t} p(t,k-t)$$ if $0 \le k < m-\omega(m)$, and $$f(m,k) \sim Q (1- k/m)$$ provided $Cm^{3/4}\log m < k < m-\omega(m)$ for some $C>0$. \end{prop} \vsp \noindent {\bf Remark.} Note that the formula given for $f(m,k)$ in Theorem \ref{prelim} or Proposition \ref{rewrite} is asymptotic to $p(k)$ for $k=o(\sqrt m)$. It is curious that, as shown in Proposition \ref{rewrite}, the asymptotics change from this Taylor series coefficient of a generating function to a value of that generating function as $k$ varies. To obtain the asymptotics of $f(m,k)$ it is still necessary to evaluate the summation involving $p(t,k-t)$ in Theorem \ref{main1} for a wide range of $k$. For $0\leq\mu\leq1/3$, define \begin{equation}\label{S1def} S_1=S_1(\mu) =\frac{1}{{\left(24 \mu k\right)}^{1/4}} {\left(\frac{1-\mu}{1-3\mu}\right)}^{1/2} \exp\left(F(\mu k)+ 2c\sqrt{\mu k}\right), \end{equation} where $c=\pi/\sqrt{6}$ and $F(t)$ is defined for $0\leq t\leq k$ by $$ F(t)=(m-k+t)\log\left(1+\frac{t}{m-k}\right) +t\log\left(1-\frac{k}{m}\right)-t. $$ Also, define $$ S_0=e^{F(k)}p(k)\sim\frac{1}{4\sqrt{3}k} \exp\left(2c\sqrt{k} +(m-k)\log\left(\frac{m}{m-k}\right)-k\right), $$ where we used (\ref{pnasym}). Our final asymptotic formula for $f(m,k)$ in terms of simple functions is the following. Note that we permit $\beta\to 0$ and $\beta \to \infty$. \begin{theorem}\lab{main3} Take $m$ and $k$ as in Theorem~\ref{prelim}. Set $$\beta = cm/ k^{3/2}$$ and determine $\xi$ by $$\beta = \frac{8}{27}+\frac{2}{27c^4}\frac{\log m} {m^{\frac13}} +\frac{\xi}{m^{\frac13}}.$$ For $0<\beta\le 2/3\sqrt{3}$, let $\mu$ be the (unique) solution of $$ \mu^{1/2}(1-\mu)=\beta, \ \ \ \ 0<\mu\le 1/3. $$ Then $$ f(m,k) \sim \left\{ \begin{array}{ll} {\displaystyle S_0}~, & \mbox{if}~~\xi \to \infty, \\ ~~ \\ [-.07in] {\displaystyle S_0+S_1}~, & \mbox{if}~~ \xi=O(1), \\ ~~ \\ [-.07in] \displaystyle{S_1}~, & \mbox{if}~~\xi \to -\infty~~ \mbox{and}~~k=o(m), \\ ~~ \\ [-.07in]\df{1}{(s+1)!} \ds_{v \ge 0} \ds_{d_0 < \cdots < d_v \atop d_0 + \cdots + d_v = s+1} \prod_{j=0}^v d_j !~, & \mbox{if}~~k=m-s,~~s ~\mbox{fixed}~. \end{array} \right. $$ Moreover, for $\xi=O(1)$, $$f(m,k)\sim\frac{\sqrt 2}{\sqrt 3 c^{\frac{1}{6}}m^{\frac{7}{96}}} \exp\left({\frac{15}{32}c^{\frac{4}{3}}m^{\frac{1}{3}}}\right) \left( \frac{1}{9\sqrt {2 c}} \exp\left({\frac{513}{64}c^{\frac{4}{3}}\xi -\frac{243}{128}c^{2}}\right) +\frac{2^{\frac14}}{3^{\frac14}} \exp\left({\frac{81}{64}c^{\frac{4}{3}}\xi -\frac{217}{384}c^{2}}\right) \right).$$ \end{theorem} \no {\bf Remark on continuity.} What is a camel? A horse designed by a committee. This paper had a committee but no horses, only functions. Figure 1 has some suspicious humps (due, no doubt, to the tail behaviour). So it is desirable to show that the function in Theorem 2.3 has no unexpected humps. It will be seen in the proof that in the expression for $f(m,k)$ when $\xi$ is bounded, the first of the two terms in the long parenthetical factor comes from $S_0$ and the second from $S_1$, so the three expressions for $k=o(m)$ merge into each other. (Actually we shall see that the estimate $S_0+S_1$ is valid for $\eps_1<\beta<\frac{8}{27}+\eps_2$, for $\eps_1>0$ and $\eps_2$ sufficiently small.) Next consider large $k$, in particular the expression in Theorem 2.1 for $k=m-O(1)$. If we let $f(x)=\sum_{k\ge 1}k!x^{k}$ we see that the terms with $v\ge 1$ are bounded by $[x^{s+1}]f(x)^{v+1}$. However $[x^{s+1}]\sum_{v\ge 0}f(x)^{v+1}\sim(s+1)!$ by Bender\cite[Theorem 3]{Bender}. Thus $ \lim_{s\rightarrow\infty}f(m,m-s)=1$, and so the expression for $k=m-O(1)$ merges with the expression for large $k$ in Proposition \ref{rewrite}. \no {\bf Further remarks.} It is also worth checking the extent of overlap of the various formulae we have for $f(m,k)$. If $k=\delta m^{\frac{2}{3}}$ then \[ S_0\sim p(k)\frac{[m]_k}{m^{k}}\sim p(k)\exp\left(-\frac{1}{2}\delta^{2}m^{\frac{1}{3}}-\frac{1}{6} \delta^{3}+O(m^{-\frac{1}{3}}) \right) \] and so by Theorem \ref{main3} the range of the first expression in Theorem \ref{prelim} can be extended to $o(m^{\frac{2}{3}})$ and even $\xi \to \infty$, which is the limit of its range of validity. We next check the range of validity of the second formula in Proposition \ref{rewrite}. If $k=xm^{\frac{3}{4}}$ then $\beta =cx^{-\frac{3}{2}}m^{-\frac{1}{8}}=o(1)$ so $f(k,m)\sim S_1$. Now since $\sqrt\mu(1-\mu)=\beta$ we have $\mu =\beta^{2}+2\beta^{4}+7\beta^{6}+O(\beta^{8})$ so \[ \mu k=c^{2}x^{-2}m^{\frac{1}{2}}+2c^{4}x^{-5}m^{\frac{1}{4}} +7c^{6}x^{-8}+O\left(m^{-\frac{1}{4}}\right), \] \[(m-k+\mu k)\log\left(1+\frac{\mu k}{m-k}\right)= \mu k+\frac{(\mu k)^{2}}{2(m-k)}+O(m^{-\frac{1}{2}}), \] \[ \mu k \log\left(1-\frac{k}{m}\right)=-\frac{\mu k^{2}}{m}-\frac{\mu k^{3}}{2m^{2}}+ O(m^{-\frac{1}{4}}). \] Thus \[ F(\mu k)=-\frac{c^{2}}{x}m^{\frac{1}{4}}+\frac{c^{4}}{2x^{4}} +O(m^{-\frac{1}{4}}). \] Furthermore \[ 2c(\mu k)^{\frac{1}{2}}=2c^{2}x^{-1}m^{\frac{1}{4}} +2c^{4}x^{-4}+O(m^{-\frac{1}{4}}) \] so \[ \exp(F(\mu k)+2c\sqrt{\mu k})=\exp\left(\frac{c^{2}}{x}m^{\frac{1}{4}} +\frac{5c^{4}}{2x^{4}}+O(m^{-\frac{1}{8}})\right). \] As $(24\mu k)^{\frac{1}{4}}\sim\sqrt{2\pi}m^{\frac{1}{8}}x^{\frac{-1}{2}}$ we now have \[ S_1\sim\frac{x^{1/2}m^{-1/8}}{\sqrt{2\pi}} \exp\left(\frac{c^{2}m^{1/4}}{x}+\frac{5c^{4}}{2x^{4}}\right). \] However \[ Q(1-k/m)=Q\left(e^{\frac{k}{m}-\frac{k^{2}}{2m^{2}}+ O\left(\frac{k^{3}}{m^{3}}\right)}\right) \] and it is well known (see for instance Andrews \cite{Andrews}) that \beql{Qes} Q(e^{s})=e^{\pi^{2}/6s}\sqrt{s/2\pi}(1+O(s)) \eeq and hence $Q(1-k/m)\not\sim f(k,m)$ if $k=xm^{3/4}$ for fixed $x$. Note next that if $k=o(m)$ but $km^{-3/4}\rightarrow\infty$ then $\beta\rightarrow 0$ so $\mu\sim\beta^{2}$ and $\mu k\sim c^{2}m^{2}/k^{2}=o(m^{1/2})$. Thus \[ (m-k+t)\log\left(1+\frac{t}{m-k}\right)=t+O\left(\frac{t^{2}}{m-k}\right)= t+o(1), \] so the sum over those $t$ for which $t=\mu k+O\left((\mu k)^{7/8}\right)$ in $\sum_{t}e^{F(t)}p(t)$ is asymptotic to $\sum_{t}p(t)(1-k/m)^{t}$ (summed over these $t$). We shall see however that the sum over the other $t$ in $\sum_{t} e^{F(t)}p(t)$ is negligible. If $|t-\mu k|\geq(\mu k)^{7/8}$ then $p(t)(1-k/m)^{t}\le p(\mu k)(1-\mu k/m)^{\mu k}\exp(-\delta(\mu k)^{1/4})$ for some $\delta>0$ so the sum over these $t$ of $p(t)(1-k/m)^{t}$ is asymptotic to $Q(1-k/m)$. Thus the range of validity of $f(k,m)\sim Q(1-k/m)$, the second formula in Proposition \ref{rewrite}, is $m-k\rightarrow\infty$ and $km^{-3/4}\rightarrow\infty$. As a final remark, it can be easily verified that, as functions of $k$, both $f(m,k)$ and $S_0$ attain their respective maxima at $k\sim c^{2/3}m^{2/3}$. {From} now on, whenever we refer to $n$, $m$ and $k$, we will always assume that $n=m(m+1)/2 +k$, $0 \le k \le m$. Let \beql{eqZ201} \Pi (n,r) = \left\{ (h_1 , h_2 ,\dd , h_r ) : 1 \le h_1 < h_2 < \cdots < h_r , ~ \sum_{j=1}^r h_j = n \right\} \eeq be the set of partitions of the integer $n$ into $r$ distinct parts, and let $$ \Pi (n) = \bigcup_{r \ge 1} \Pi (n,r) ~. $$ Note that $\Pi (n,r) = \emptyset$ for $r \ge m+1$. For $\pi \in \Pi (n,r)$, $\pi = (h_1 , h_2 , \dd , h_r )$, let $$ P( \pi ) = \frac{1}{\prod\limits_{j=1}^r h_j !} ~. $$ Thus $$ a_n = \sum_{\pi \in \Pi (n)} P( \pi ) ~. $$ We will say that $\pi = (h_1 , h_2 , \dd , h_r ) = [u,u'] - [w]$ if $\{ h_1 , \dd , h_r \} = \{ u, u+1 , \dd , u' \} - \{ w \}$. Thus $\pi$ consists of all the integers in an interval with the possible exception of a single integer, the ``hole.'' In the case of the partition $\pi_0= [1, m+1 ] - [ m+1 -k ]$, we will say that $\pi_0$ is the {\em canonical} partition of $n$. \begin{prop} \lab{oldpr201} For any $r$, the maximum of $P( \pi )$ over $\pi \in \Pi (n,r)$ is achieved uniquely by $\pi = [u,u'] - [w]$ for some $u \le w \le u'$. The maximum of $P( \pi )$ over all $\pi \in \Pi (n)$ is achieved by the canonical partition $\pi_0$. \end{prop} To get started in our analysis when $m-k \to\infty$ it is convenient to characterise partitions according to which block or part sizes are missing. For $\pi \in \Pi (n,m)$ as in (\ref{eqZ201}), let $d_0< \cdots < d_v$, where $v=h_m-m-1\ge 0$, denote the ``holes'' of $\pi$, that is all the numbers from $1$ to $h_m-1$ which do not appear in $\pi$. Observe that properly inserting the missing numbers into $\pi$ results in the complete staircase diagram with $m+v+1$ steps, that is $$ \sum_{j=1}^{m+v+1}j=n+d_0+\cdots+d_v, $$ or $$ k=n-\frac{m(m+1)}{2}=\lambda_0+\cdots+\lambda_v,\quad \lambda_i:=m+1+i-d_i. $$ Since $d_i$ is strictly increasing, $\lambda_i$ is nonincreasing. Also $\lambda_v\ge 1$, because $d_v\le h_m-1=v+m$. Thus $\lambda=(\lambda_0,\dots, \lambda_v)$ is a partition of $k$, which we call the {\it hole\/} partition corresponding to $\pi$ or to the associated set partition, from which $\pi$ can be recovered (given $n$). When we come to describe the likely shape of $\pi$, we will be comparing $P(\pi)$ to $P(\pi_0)$, and it is immediate that \bean P(\pi)&=&\prod_{j=0}^vd_j!\left(\prod\limits_{j=1}^{m+v+1}j!\right)^{-1},\\ P(\pi_0)&=&(m+1-k)!\prod_{j=1}^v(m+j+1)!\left(\prod\limits_{j=1}^{m+v+1}j! \right)^{-1}, \eean since $\pi_0$ has a single hole $m+1-k$, and its largest part is $m+1$. Thus \bea \frac{P(\pi)}{P(\pi_0)}&=&\frac{d_0!}{(m+1-k)!}\cdot\prod_{i=1}^v\frac{d_i!} {(m+i+1)!}\non\\ &=&\bigl[m+1-k+t\bigr]_t \cdot\prod_{i=1}^v\frac{1}{\bigl[m+1+i\bigr]_{\lambda_i} },\lab{Pratio} \eea where $t=\lambda_1+\dots+\lambda_v$. It is this formula that will make the notion of the hole partition so useful for us. The partition $$t=\lambda_1+\dots+\lambda_v$$ will itself play an important role around the difficult range $k \approx m^{2/3}$. It is important to note the upper bound $$\la_1\le k-t,$$ which holds because $\lambda_0=k-t$. By the ``shape'' of a partition of an $n$-set we mean the multiset of the cardinalities of its blocks. As noted just above, for the partitions into distinct parts, the shape (which is a set) is characterised by the partition $\{\la_i\}$. We can conclude various results about the shape of a random partition from our main results on asymptotics. Define $\Om_n$ to be the probability space whose elements are partitions $\la = \{\la_0, \ldots, \la_v\}$ of $k$, with probability proportional to the number of partitions of an $n$-set with hole partition $\la$. Note that $r$ can be regarded as a random variable on $\Om_n$ since it is determined in a natural way from $\la$ by the fact that the $r$ smallest integers other than those holes determined by $\la$ sum to $n$. We say that a random partition $\pi$ is {\em distributed asymptotically uniformly} as a partition of a number (possibly with a bound on the largest part size) if the total variation distance between the distribution of $\pi$ and the uniformly distributed partitions of the same number (with the same part size bound, if it is specified) tends to 0 as $n \to \infty$. We also say that an event occurs {\em almost surely} if its probability tends to 1 as $n \to \infty$. First we consider small $k$. \begin{prop}\lab{shape1} For sufficiently large $D$, and $k 0$, if $k>cm^{2/3}$ and $m-k\to\infty$ then for $\la = (\la_0, \ldots,\la_{v}) \in \Om_n$, the sub-partition $(\la_1, \ldots, \la_v)$ is distributed asymptotically uniformly as a random partition of $t$, where the distribution of $t$ and the distribution of a random variable $X$ with $\pr(X=i)$ proportional to $$\frac{[m+1-k+i]_{i}}{m^{i}}p(i)$$ have total variation distance tending to 0. \end{prop} In fact, from the proof of Theorem \ref{main3}, it is easy to deduce more about the distribution of $X$. For the remaining, very large, values of $k$, we have the following. \begin{prop}\lab{shape4} If $s$ is fixed and $k=m-s$ then in a random partition of $n$ with distinct block sizes, $h_r=m+1$ almost surely. Furthermore, the holes $d_0, \ldots , d_v$ are a random partition of $s+1$ into distinct parts in which the probability is asymptotically proportional to $\prod_{j=0}^v d_j!$. \end{prop} These propositions have immediate corollaries for random partitions of an $n$-set into blocks of distinct sizes. For instance, the largest part almost surely has size $m+1$ by Proposition \ref{shape4} when $m-k$ is bounded. On the other hand, when $m-k\to\infty$ Proposition \ref{shape2} gives that $r=m$ almost surely, which means the largest part has size $m+1+v$. Here $v$ is the number of parts in the random partition $\la_1, \ldots ,\la_v$ as discussed in Proposition \ref{shape2}, and so this proposition determines its distribution asymptotically, as do Propositions \ref{shape1} and \ref{shape3}. The simplest result on this is given by Proposition \ref{shape1}, that for $k\sqrt s \, \log s$ and $s = O(m^{2/3})$, $$ g(m,s,M_s)\sim p(s) $$ as $s \to \infty$, and furthermore \item{(ii)} for some fixed function $w(n) \to 0$, almost all partitions $\la_1, \ldots, \la_v$ of $s$ with $\la_1 \le M_s$ satisfy $$\left| 1-\prod_{i=1}^v\frac{m^{\lambda_i}}{[m+1+i]_{\lambda_i}}\right| \le w(n).$$ \end{description} \end{lemma} \noindent {\bf Proof of Theorem~\ref{prelim}} \no First consider $k < m^{2/3}/D \log m$. Lemma~\ref{requalm} implies that only terms with $r=m$ are significant, Lemma~\ref{gms} gives $g(m,k) \sim p(k)$, and so the formula on the right in (\ref{fsimply}) becomes $$\frac{[m+1]_k}{m^k}p(k)\sim \frac{[m]_k}{m^k}p(k).$$ This gives the first part of the theorem. Next consider $m-k$ bounded, let $s$ denote $m-k$, and as usual let $d_0, \ldots, d_v$ denote the holes in $\pi$. Partitions with less than $m$ parts are now significant in (\ref{eqN109}). Note that the largest part $h_r$ is at least $m$. If $h_r=m$ then $k=0$, and $m-k$ is not bounded so we do not have to consider this here. Next suppose $h_r=m+1$. We will show that this is the only significant case. Note that \begin{eqnarray*} 1+2+\cdots+(m+1)-d_0-d_1-\cdots-d_v&=&h_1+h_2+\cdots+h_r\\ &=&(1+2+\cdots+m)+k\\ &=&1+2+\cdots+(m+1)-s-1, \end{eqnarray*} so $d_0+d_1+\cdots+d_v=s+1$. Since $P(\pi) = \prod_{i=0}^{v}d_i! \prod_{i=1}^{m+1}\frac{1}{i!}$, the second part of Theorem \ref{prelim} follows if these are the only significant partitions. So now suppose $h_r\geq m+2$. Then \begin{eqnarray*} h_1+h_2+\cdots+h_r&\ge&1+2+\cdots+(m+2)-d_0-\cdots-d_v\\ &>&n + (m+2) - d_0 - \cdots - d_v. \end{eqnarray*} But the sum on the left is $n$ and so, since the $d_i$ are distinct, $d_v\ge \sqrt m$. {From} Lemma \ref{requalm} we have $d_0$ bounded. So adding 1 to the part $d_0-1$ (if $d_0=1$, this means creating a new part 1) and subtracting 1 from the part $d_v+1$ multiplies the contribution to (\ref{eqN109}) by at least $d_v/d_0\to\infty$. The number of ways of reversing this operation is bounded (the only possible ambiguity caused by holes moving to 0 or to the top at $h_r$) and we conclude that these partitions are not significant. \qed \no {\bf Proof of Theorem~\ref{main1}} \no Take any $k>\sqrt m \log m$, but $m-k \to\infty$. We break the terms in the summation in (\ref{fsimply}) into groups according to the value of $t$. \noindent {\bf Case 1.} $t\ge k-k^{2/3}$. By Lemma \ref{bounds} we can assume $k = O(m^{2/3})$. Then $$\frac{[m+1]_{k-t}}{m^{k-t}}\sim 1$$ for all such $t$. Thus, on multiplication by this quantity, the sum of the terms with $t$ in this range is $$ \sum_{t=\lceil k-k^{2/3}\rceil}^k \frac{[m+1-k+t]_t}{m^t} g(m,t,k-t) \sim \sum_{t=\lceil k-k^{2/3}\rceil}^k \frac{[m]_k}{m^k} g(m,t,k-t).$$ But this equals $\frac{[m]_k}{m^k} g(m,k,\lceil k^{2/3}\rceil)$. Now by Lemma \ref{gtop} this is asymptotic to $\frac{[m]_k}{m^k} p(k)$, which is in turn asymptotic to $$ \sum_{t=\lceil k-k^{2/3}\rceil}^k \frac{[m+1-k+t]_t}{m^t} p(t,k-t)$$ by \eqn{maxpart}. \noindent {\bf Case 2.} $\log m < t < k-k^{2/3}$. \no By Lemma \ref{bounds}, we can assume that $\la_0$ ($=k-t$) is at most $ \sqrt{m}(\log m)^{3/2}$. This is $o(k)$. So by Lemma \ref{gtop}, and then using (\ref{maxpart}), $g(m,t,k-t)\sim p(t)\sim p(t,k-t)$, and so \beql{oneterm} \frac{[m+1-k+t]_t}{m^t} g(m,t,k-t) \sim \frac{[m+1-k+t]_t}{m^t} p(t,k-t) \eeq as required. Since Lemma \ref{gtop} requires $s \to\infty$, we deal with small $t$ separately in the next case. \noindent {\bf Case 3.} $t \le \log m$. Here, immediately from the definition (\ref{gmsbdef}), $g(m,t,k-t)\sim p(t,k-t)$ and so we again have (\ref{oneterm}). This gives the theorem. \qed \no {\bf Proof of Proposition~\ref{rewrite}} \no Since $p(t,k-t)$ is equal to the number of partitions of $k$ with largest part equal to $k-t$, the formula in Theorem \ref{main1} can be written as \beql{firstsum} \sum_{\la_0=0}^k \frac{{[m+1-\la_0]}_{k-\la_0}}{m^{k-\la_0}} p(k-\la_0,\la_0) \eeq or \beql{secondsum} \sum_{\la_0\ge \la_1 \ge \cdots\atop \la_0+ \la_1 + \cdots =k} \frac{{[m+1-\la_0]}_{k-\la_0}}{m^{k-\la_0}}. \eeq The summand in (\ref{secondsum}) for any term with $\la_0 < m^{1/2-\epsilon}$ ($\epsilon >0$ arbitrarily small) is asymptotic to $[m]_k/m^k$. Hence these terms contribute asymptotically $p(k)[m]_k/m^k$ to the summation. On the other hand, the contribution from terms with $\la_0 \ge m^{1/2-\epsilon}$ can be estimated using (\ref{firstsum}), where for each $\la_0$ the term is at most $p(k-\la_0,\la_0) \le p(k-\la_0)$. For $k\leq \sqrt{m}\log m$, this contribution is $o(p(k)[m]_k/m^k)$. The first part of Proposition~\ref{rewrite} follows. {From} Lemma \ref{bounds}, only the terms with $t0$ and $m+1-k>\omega^3(n)$, then by (\ref{star}) \begin{eqnarray*} \sum_{t\geq\omega(n)} \frac{{[m+1-k+t]}_t}{m^t} p(t,k-t) &\leq& \sum_{t\geq\omega(n)}{(1-x/2)}^t p(t)\\ &=&o(1). \end{eqnarray*} Note that \begin{eqnarray*} \sum_{t<\omega(n)} \frac{{[m+1-k+t]}_t}{m^t} p(t,k-t)&\sim& \sum_{t<\omega(n)} \frac{{[m+1-k+t]}_t}{m^t} p(t)\\ &\sim& \sum_{t<\omega(n)} {(1-k/m)}^tp(t)\\ &\sim&Q(1-k/m).\qed \end{eqnarray*} \noindent {\bf Proof of Theorem~\ref{main3}} \no The last part of the theorem, referring to $m-k$ bounded, is the same as in Theorem \ref{prelim}. For $m-k \to \infty$ but $k \ne o(m)$, the theorem is covered by Proposition~\ref{rewrite} together with the check (in the remarks after the statement of the present theorem) that the formula there corresponds with the formula in the present theorem for such $k$. For the rest, we can assume $k=o(m)$ and start from $$ f(m,k) \sim\sum_{t=0}^{k} \frac{[m+1-k+t]_t}{m^t} p(t,k-t), $$ which is valid for $k=o(m)$, according to Proposition~\ref{rewrite}. By Stirling's formula, \begin{eqnarray*} \log\frac{[m+1-k+t]_t}{m^t} &=&\log(m+1-k+t)!-\log(m+1-k)!-t\log m\\ &=&(m-k+t+3/2)\log(m-k+t+1)-t\\ &&-\, (m-k+3/2)\log(m-k+1)-t\log m+o(1)\\ &=&(m-k)\log\left(1+\frac{t}{m-k}\right)-t+ t\log\left(1-\frac{k-t}{m}\right)+o(1)\\ &=&(m-k+t)\log\left(1+\frac{t}{m-k}\right) +t\log\left(1-\frac{k}{m}\right)-t+o(1)\\ &=&F(t)+o(1). \end{eqnarray*} (We note for later reference that \beql{tag3.10} F^\prime (t)=\log\left(1-\frac{k-t}m\right),\quad F^{\prime\prime}(t)= \frac{1}{m-k+t},\quad F^{\prime\prime\prime}(t)=O(m^{-2}).) \eeq Thus \beql{tag3.11} f(m,k)\sim\sum_{t=0}^ke^{F(t)}p(t,k-t). \eeq To proceed, notice that $$ p(t,k-t)\le p(t)\le \exp (2c\sqrt {t}) $$ by \eqn{pnbound}, and so $$ e^{F(t)}p(t,k-t)\le e^{G(t)},\quad G(t):=F(t)+2c\sqrt{t}. $$ Recall that we introduced $\beta$ via $k^{3/2}=cm/\beta$. \si {\bf Case 1.\/} Consider the small $\beta$'s first. Pick a small $\varepsilon >0$ and suppose that $\beta\le \varepsilon$ and that $k=o(m)$, which is equivalent to $\beta k^{1/2}\to\infty$. An easy calculation shows that $G(t)$ has two stationary points \bean t_0&=&\beta^2 k\left[1+O\left(\beta^2+\frac{1}{\beta k^{1/2}}\right)\right], \\ t_1&=&k-\beta k\bigl(1+O(\beta)\bigr), \eean which are a local maximum and local minimum respectively. Further, with more algebra, \bea G(t_0)&=&\left(2c\sqrt{t_0}-\frac{kt_0}{m}\right)\left[1+O\left(\beta^2+\frac {1}{\beta k^{1/2}}\right)\right]\non\\ &=&c\beta k^{1/2}\left[1+O\left(\beta^2+\frac{1}{\beta k^{1/2}}\right)\right], \lab{tag3.12}\\ G(k)&=&-\frac{k^2}{2m}\left(1+O\bigl(\beta+(\beta k^2{1/2})^{-1}\bigr)\right)+2c\sqrt{k}\non\\ &=&-\frac{ck^{1/2}}{2\beta}\left(1+O\bigl(\beta+(\beta k^{1/2})^{-1}\bigr)\right ).\lab{tag3.13} \eea Since $G(t_0)\ge G(k)$, $G(t)$ attains its absolute maximum at $t_0$. Also, for $t\le t^*=t_0+t_0^{7/8}$, \bea G^{\prime\prime}(t)&=&\frac{1}{m-k+t}-\frac{c}{2t^{3/2}}\lab{tag3.14}\\ &\le &-\frac{c}{2.5t_0^{3/2}},\non \eea whence \bea e^{G(t^*)}&\le& \exp\left(G(t_0)-\frac{c(t^*-t_0)^2}{5t_0^{3/2}}\right)\non\\ &=&\exp\bigl(G(t_0)-{\scriptstyle\frac{1}{5}}ct_0^{1/4}\bigr).\lab{tag3.15} \eea Introduce $t^{**}=\beta k$. It is easy to see that \bea G(t^{**})&=&-\frac{t^{**}k}{m}\left[1+O\left(\beta^2+\frac{1}{\beta k^{1/2}}\right) \right]\non\\ &=&-ck^{1/2}\left[1+O\left(\beta^2+\frac{1}{\beta k^{1/2}}\right)\right], \lab{tag3.16} \eea and that, for $t\in \bigl[t^*,t^{**}\bigr]$, \bean G^\prime (t)&\le&G^\prime (t^*)=G^\prime (t_0)+G^{\prime\prime}(\tilde t)( t^*-t_0)\\ &&\quad\quad \bigl(\mbox{for some }\tilde t\in [t_0,t^*]\bigr)\\ &\le&-\frac{c}{2.5}t_0^{-5/8}. \eean (The inflection point $\hat t$ of $G(t)$ is of order $k\beta^{2/3}\gg k\beta$, so that $G^\prime (t)$ decreases for $t\le t^{**}$.) Therefore, for $t\in [t^*,t^{**}]$, we bound \beql{tag3.17} \frac{e^{G(t+1)}}{e^{G(t)}}\le \exp\left(-\frac{c}{2.5}t_0^{-5/8}\right), \eeq so the terms $e^{G(t)}$ are bounded by the terms of a geometric progression with denominator given by the right hand expression. Combining \eqn{tag3.13}--\eqn{tag3.17}, we bound \bea \sum_{t\ge t^*}e^{G(t)}&\le& e^{G(t_0)}\frac{e^{-ct_0^{1/4}/5}}{1-e^{-ct_0^{-5/8} /2.5}}+k\max\{G(t^{**}),G(k)\}\non\\ &\le&e^{G(t_0)}\cdot e^{-ct_0^{1/4}/6}+e^{-ck^{1/2}/2}.\lab{tag3.18} \eea Analogously to \eqn{tag3.15} and \eqn{tag3.17}, for $t_*=t_0-t_0^{7/8}$ and $t\in [2,t_*]$, \bean e^{G(t_*)}&\le&\exp\bigl(G(t_0)-ct_0^{1/4}/5\bigr),\\ \frac{e^{G(t-1)}}{e^{G(t)}}&\le&\exp\left(-\frac{c}{2.5}t_0^{-5/8}\right), \eean so that \beql{tag3.19} \sum_{t\le t_*}e^{G(t)}\le e^{G(t_0)}\cdot e^{-ct_0^{1/4}/6}. \eeq Finally, using (3.13), we obtain \bean \sum_{t\in (t_*,t^*)}e^{G(t)}&\sim&e^{G(t_0)}\int\limits_{t_*}^{t^*} \exp\left(\frac{G^{\prime\prime}(t_0)}{2}(t-t_0)^2\right)\,dt\\ &\sim&e^{G(t_0)}\cdot\sqrt{\frac{2\pi}{-G^{\prime\prime}(t_0)}}\ . \eean To evaluate $G^{\prime\prime}(t_0)$ we note that from $G^\prime (t_0)=0$ it follows that $$ \frac{k-t_0}{m}\sim \frac{c}{\sqrt{t_0}}. $$ Therefore \bean -G^{\prime\prime}(t_0)&=&\frac{c}{2t_0^{3/2}}-\frac{1}{m-k+t_0}\\ &\sim&\frac{c}{2t_0^{3/2}}-\frac{1}{m}\sim\frac{c}{2t_0^{3/2}}-\frac{c} {t_0^{1/2}(k-t_0)}\\ &=&\frac{c(k-3t_0)}{2t_0^{3/2}(k-t_0)}. \eean Thus, observing from \eqn{pnasym} that $$ p(t,k-t)\sim p(t)\sim\frac{e^{2c\sqrt{t}}}{4\sqrt{3}t_0} $$ uniformly for $t\in (t_*,t^*)$, we evaluate \bea \sum_{t=0}^ke^{F(t)}p(t,k-t) &=&\frac{1+o(1)}{4\sqrt{3}t_0}\sum_{t\in (t_*,t^*)} e^{G(t)}+O\left(e^{G(t_0)}\cdot e^{-ct_0^{1/4}}+e^{-ck^{1/2}/2}\right)\non\\ &\sim&\frac{e^{G(t_0)}}{(24t_0)^{1/4}}\left(\frac{k-t_0}{k-3t_0}\right)^{1/2} \non\\ &\sim&S_1 \lab{tag3.21} \eea since $t_0 \sim \mu k$. \qed \bi {\bf Case 2.\/} Now consider the case of large $\beta$'s, that is $\beta\ge \varepsilon$, or $k^3=O(m^2)$. \si Expanding $F(t)$ at $k$ and using (3.10), \bean e^{F(t)}p(t,k-t)=&O\left(e^{F(k)}e^{g(t)}\right),\\ g(t):=&\frac{(k-t)^2}{2m}+2c\sqrt{t}. \eean If the equation $$ g^\prime (t)=-\frac{k-t}{m}+\frac{c}{\sqrt{t}}=0 $$ has a root $\tau^*$ then, setting $\mu^*=\tau^*/k$, we get $$ \beta=\sqrt{\mu^*}(1-\mu^*). $$ Note that $\sqrt{y}(1-y)$ attains its maximum (equal to $\frac{2}{3\sqrt{3}}$) for $y>0$ at $y=1/3$. Thus, if $\beta>\frac{2}{3\sqrt{3}}$, then there is no root $\tau^*$, and $g(t)$ is strictly increasing for all $t$'s. If $\beta=\frac{2}{3\sqrt{3}}$, then there is a unique root $\tau^*=k/3$, but it is an inflection point for $g(t)$, which therefore remains strictly increasing for all $t$'s. If $\beta<\frac{2} {3\sqrt{3}}$, then there are two roots $0<\tau_00$ be given. \si {\it Case 2(a).\/} $\beta\ge \frac{8}{27}+\varepsilon$. A little algebra shows that $g(t)=g(k)$ for some $t8/27$ and $\sqrt{\tau_0}(k-\tau_0)=\beta k^{3/2}$, $\tau_{0}> k/9$ and so $(k-t)(\sqrt k + \sqrt t)$ is decreasing on $\tau_0 \le t\le k$. Thus $g(t) k/9$. We know that $g(t)$ is increasing if $\beta\ge \frac{2}{3\sqrt{3}}$. If $\beta<\frac{2}{3\sqrt{3}}$, then there exists $\tau_2\in (\tau_1,k)$ such that $g(\tau_0)=g(\tau_2)$. Since $\beta$ is bounded away from $\frac{8}{27}$, the difference $k-\tau_2$ is of order $k$ exactly. (This follows from the conditions $$ g(\tau_0)=g(\tau_2),\quad g^\prime (\tau_0)=0.) $$ Thus, in either case, \bea e^{F(k)}\sum_{t=0}^{k-k^{5/8}}e^{g(t)}&= &O\left(k\exp\bigl[F(k)+g(k-k^{5/8}) \bigr]\right)\non\\ &=&O\left(k\exp\bigl[F(k)+2c\sqrt{k}-ck^{1/8}\bigr]\right). \lab{tag3.23} \eea On the other hand, $F(t)\sim F(k)$ uniformly for $t\in [k-k^{5/8},k]$, since $k=O(m^{2/3})$; so \bea \sum_{t=k-k^{5/8}}^k e^{F(t)}p(t,k-t)&\sim& e^{F(k)}\sum_{t=k-k^{5/8}}^k p(t,k-t)\non\\ &=&e^{F(k)}\sum_{t=k-k^{5/8}}^k P(k,k-t)\non\\ &\sim&e^{F(k)}p(k)\non\\ &\sim&\frac{\exp\bigl[G(k)\bigr]}{4\sqrt{3}k}. \lab{tag3.24} \eea (We have used the formula $p(a,b)=P(a+b,b)$, where $P(a+b,b)$ is the number of partitions of $a+b$ with the largest part equal to $b$ exactly. We also know that for almost all partitions of $\nu$ the largest part is of order $O\bigl( \sqrt{\nu}\log\nu\bigr)$.) Comparing \eqn{tag3.23} and \eqn{tag3.24} we get \beql{bigbeta} \sum_{t=0}^ke^{F(t)}p(t,k-t)\sim\frac{\exp\bigl[G(k)\bigr]}{4\sqrt{3}k}\sim S_0. \eeq \si {\it Case 2(b).\/} $\beta\le 8/27+\varepsilon<\frac{2}{3\sqrt{3}}$. The equation $$ G^\prime (t)=\log\left(1-\frac{k-t}{m}\right)+\frac{c}{\sqrt{t}}=0 $$ has two roots $00$. For this remaining range, from \eqn{tag3.11}, \eqn{bigbeta} and \eqn{tag3.27} we have \beql{fisS0S1} f(m,k)\sim S_0 + S_1. \eeq It is interesting that $S_0$ and $S_1$ represent the contributions to $f(m,k)$ from two parts of the summation in (\ref{tag3.11}), one for $t$ close to $k$ and the other for $t$ close to $\mu k$. For most values of $k$, one dominates the other, but at the point where they become comparable in magnitude they are still two distinct local maxima of the expression being summed, and one takes over from the other as global maximum as $k$ increases. So it only remains to determine which of $S_0$ and $S_1$ dominates the other. For $\eps \le \beta\le \frac{8}{27}+\eps$, we only need to investigate when $\log(S_0/S_1)$ goes to 0 or to $\infty$. Note that we have $k^3=O(m^2)$, and in particular we can assume $\mu\le\frac{1}{3}-\eps$. Then first considering the exponents in $S_0$ and $S_1$, $$ 2c\sqrt{k}+(m-k)\log\left(1+\frac{k}{m-k}\right)-k = 2c\sqrt{k} -\frac{1}{2}k^2/m + O(k^3/m^{2}), $$ $$ F(\mu k) + 2c\sqrt{\mu k} = 2c\sqrt{\mu k} +\frac{1}{2}\mu^2 k^2/m-\mu k^2/m+O(k^3/m^{2}), $$ and so \begin{eqnarray} \log\left(\frac{S_0}{S_1}\right)&=& 2c(1-\sqrt{\mu})\sqrt{k} -\frac{1}{2}(1-2\mu+\mu^2)\frac{k^2}{m}-\frac{3}{4}\log k + \frac{1}{2} \log(1-3\mu)+O\left(1+\frac{k^3}{m^{2}}\right)\nonumber\\ &=& 2c(1-\sqrt{\mu})\sqrt{k}-\frac{c}{\beta}{(1-\mu)}^2 \sqrt{k}-\frac{3}{4}\log k + \frac{1}{2} \log(1-3\mu)+O\left(1+\frac{k^3}{m^{2}}\right)\nonumber\\ &=& c\sqrt{k}\left(2-2\sqrt{\mu}- \frac{1-\mu}{2\sqrt{\mu}}\right)-\frac{3}{4}\log k + \frac{1}{2} \log(1-3\mu)+O\left(1+\frac{k^3}{m^{2}}\right)\nonumber\\ &=&\frac{c\sqrt{k}}{2\sqrt{\mu}}(1-\sqrt{\mu}) (3\sqrt{\mu}-1)-\frac{3}{4}\log k + \frac{1}{2} \log(1-3\mu)+O\left(1+\frac{k^3}{m^{2}}\right)\lab{S0overS1}. \end{eqnarray} Notice that $\sqrt k/\sqrt \mu$ is of the order of $k^2/m\to\infty$ and therefore overpowers $\log k$ and the error terms. So the behaviour of this expression is determined by the sign and magnitude of $(1-\sqrt{\mu})(3\sqrt{\mu}-1)$. Setting this equal to zero and ignoring the error term gives $$\mu =\frac{1}{9}+\frac{\log k}{c \sqrt k} +O(1/m^3),\qquad \beta = \frac{8}{27}+\frac{2}{27c^4}\frac{\log m} {m^{\frac13}}. $$ We conclude that with $\xi$ defined as in the statement of the theorem, $S_0=o(S_1)$ for $\xi \to -\infty$ and $S_1=o(S_0)$ for $\xi \to \infty$. This establishes the formulae for $f(m,k)$ in these two cases. For $\xi=O(1)$ we already have (\ref{fisS0S1}), but taking the expansions in the previous paragraph about $$\mu = \frac19 + \frac{\tau+\xi}{m^{\frac13}},$$ where $$\tau = \frac{2\log m}{27 c^{4/3}}$$ to the $k^3/m^2$ terms, we find with $\theta=k/m$ \begin{eqnarray*} \beta &=& \frac{8}{27} + \frac{\tau+\xi+o(1)}{m^{\frac13}},\\ S_0&=&\frac{1}{4\sqrt 3 \theta m}e^{m((4\beta - 1)\theta^2/2-\theta^3/6+O(\theta^4))}\\ &\sim&\frac{\sqrt 2}{\sqrt 3 c^{\frac{1}{6}}m^{\frac{7}{96}}} \exp\left({\frac{15}{32}c^{\frac{4}{3}}m^{\frac{1}{3}}}\right) \frac{1}{9\sqrt {2 c}} \exp\left({\frac{513}{64}c^{\frac{4}{3}}\xi -\frac{243}{128}c^{2}}\right) \\ S_1&=&\frac{2 ^{1/4}}{ 3 ^{1/4}\theta ^{1/4} m^{1/4}}e^{m(-\mu(2-\mu)\theta^2/2+ 2 \beta \sqrt \mu \theta^2 -\mu(3-3\mu+\mu^2)\theta^3/6+O(\theta^4))}\\ &\sim & \frac{\sqrt 2}{\sqrt 3 c^{\frac{1}{6}}m^{\frac{7}{96}}} \exp\left({\frac{15}{32}c^{\frac{4}{3}}m^{\frac{1}{3}}}\right) \frac{2 ^{\frac14}}{ 3 ^{\frac14}} \exp\left({\frac{81}{64}c^{\frac{4}{3}}\xi -\frac{217}{384}c^{2}}\right) \end{eqnarray*} as required. (We omit the details of the final calculations, which were performed with the assistance of Maple.) \qed {\bf Note.\/} As we have seen, the asymptotic formula for $f(m,k)$ depends essentially on the shape of $g(t)=(k-t)^2/2m+2c\sqrt{t}$. This formula and the classification of possible modes are curiously similar to those for van der Waals ({\it phenomenological\/}) equation that connects pressure $p$, volume $V$ and temperature $T$ (Uhlenbeck and Ford \cite{UFM}, pp. 33--34): $$ p=\frac{\gamma T}{V-\beta}-\frac{\alpha}{V^2}. $$ \no {\bf Proof of Proposition~\ref{oldpr201}} \no Suppose that $\pi \in \Pi (n,r)$, and suppose that $x$ and $y$ are positive integers such that $$ \begin{array}{l} x < y ~, \\ ~~ \\ [-.09in] x,y \not\in \{ h_1 , \dd , h_r \} ~, \\ ~~ \\ [-.09in] x-1 , y+1 \in \{ h_1 , \dd , h_r \} , ~~ x-1 = h_i , ~~y+1 = h_j ~. \end{array} $$ Consider now $\pi ' = (h'_1 , \dd , h'_r ) \in \Pi (n,r)$ with $h'_i = h_i +1 = x$, $h'_j = h_j -1 = y$, and $h'_t = h_t$ for all other $t$. Then $P( \pi' ) > P( \pi )$. Therefore the $\pi \in \Pi (n,r)$ which maximizes $P( \pi )$ cannot have two integers $x$ and $y$ with $h_1 < x < y < h_r$ and $x,y \not\in \{ h_1 , h_2 , \dd , h_r \}$, which proves the claim for $\Pi(n,r)$. Suppose that $\pi \in \Pi (n,r)$ with $r < m$ maximizes $P( \pi )$ for that $r$. Then $1 < h_1$, as otherwise we would have one integer at least 2 missing (by the first part of the proposition), hence $$\sum_{j=1}^r h_j \le 1 +3+4+ \cdots + (r+1) = {\binom{r+2}{2}} -2 < {\binom{m+1}{2}} ~.$$ If $2 < h_1$, then $\pi' \in \Pi (n, r+1)$ with $\pi ' = (h'_0 , h'_1 , \dd , h'_r )$, $h'_0 =1$, $h'_1 = h_1 -1$, $h'_t = h_t$ for $t \ge 2$ yields $P( \pi ') > P( \pi )$. If $2= h_1$, then there is an integer $y$, $2 < y < h_r$, such that $y \not\in \{ h_1 , \dd , h_r \}$. We let $h_j = y+1$. Then $\pi ' = (h'_0 , \dd , h'_r)$ with $h'_0 =1$, $h'_j = h_j -1 =y$, and $h'_t = h_t$ for all other $t$ has the property that $P( \pi ') > P ( \pi )$. Thus in all cases we have found a $\pi ' \in \Pi (n,r+1)$ with $P( \pi ') > P( \pi )$, which completes the proof of the proposition. \qed \no {\bf Proof of Proposition \ref{shape1}\/} \no The statement that almost surely $r=m$ follows, as we have seen, from Lemma \ref{requalm}. In view of (\ref{Pratio}), the partition $\la$ in (\ref{gdef}) corresponds to the hole partition of $\pi$. So the rest follows from (\ref{eqN109}), (\ref{eqN1011}), (\ref{fsimply}), (\ref{gdef}) and Lemma \ref{gms}. \qed \no {\bf Proof of Proposition \ref{shape2}\/} \no As with the previous proposition, according to Lemma \ref{requalm}, $r=m$ almost surely. For the rest, note that from (\ref{eqN109}), (\ref{eqN1011}), and Lemma \ref{bounds}, we can restrict $t$ to $O(m^{2/3})$ and $\la_1$ to at most $\sqrt{m}(\log m)^{3/2}$. The rest of the proof is obtained essentially by examining the proof of Theorem \ref{main1}. Firstly, for any particular $t\ge k-k^{2/3}$, almost all partitions with the given bound on the maximum part size contribute $[m+1-k+t]_t/m^t$ asymptotically to the summation in (\ref{gmsbdef}). Since this depends only on $t$, both parts of the proposition now follow easily in this case. Next, for $t< k-k^{2/3}$, firstly consider the case that $\sqrt{m}(\log m)^{3/2} =o(t)$. Then the upper bound on part size is $o(t)$, so putting $s=t$ in Lemma \ref{gtop}, we obtain the asymptotic uniformity required in (i). Secondly, if $t=O(\sqrt{m}(\log m)^{3/2})$, Lemma \ref{gms} with $s=t$ suffices, the upper bound on the part size being negligible by \eqn{maxpart}. The statement (ii) in the case $k>\sqrt m \log m$ follows from the proof of Theorem \ref{main1}, whilst for smaller $k$ it follows from Proposition \ref{shape1}. \qed \no {\bf Proof of Proposition \ref{shape3}\/} \no In the light of the proof of Theorem \ref{main1}, we only need to consider Cases 2 and 3, where it was shown that the restriction on the maximum part size can be ignored when counting the partitions. It follows that the restriction can be dropped from Proposition \ref{shape2}. \qed \no {\bf Proof of Proposition \ref{shape4}} \no This follows immediately from the fact that in the proof of Theorem \ref{prelim} for the case $k=m-s$, the $d_i$ represent the holes in the partition. \qed \section{Proofs of lemmas} \noindent {\bf Proof of Lemma~\ref{requalm}} \no If $r\ge m+1$, then $\sum_{i=1}^{r}h_i\ge 1+2+\cdots+(m+1)>n$, so this case never arises. We first deal with the statement about $m-k\to\infty$. The first idea of the proof is to analyse a mapping from partitions with $r$ parts to those with $r+1$ parts. Consider a partition with $r\le m-1$ parts. Such a partition must have at least two holes, since a partition with at most one hole has $m$ parts by the definition of $m$. Recall that $d_0$ denotes the smallest hole. So $h_{d_0-1}=d_0-1$ and $h_{d_0}>d_0$. Informally, the mapping is obtained by inserting a part of size $d_0$, which gives a partition of $n+d_0$, and then compensating by reducing the size of some of the larger parts. Inductively, this compensation can always be accomplished because any partition of a number at least $n+1$ into $m$ or less distinct parts must have at least one hole, and hence a part whose size can be decreased. The compensation is done by replacing the part $h_{d_0}$ by $d_0+1$, $h_{d_0+1}$ by $d_0+2$, etc., until the sum of the parts is reduced to $n$. To be precise, write $q_i=h_i-i-1$ for $i\ge d_0$. Then $0 \le q_{d_0} \le q_{{d_0}+1}\le \cdots$. Determine $l$ and $j$ by $$d_0=q_{d_0} + q_{d_0+1}+ \cdots +q_j+l, \qquad 0\le l j+2 \end{array}\right.$$ This partition contributes $\frac{1}{\prod_{i=1}^{r+1}h_i^\prime !}$ to (\ref{eqN109}), whereas the original partition contributed $\frac{1}{\prod_{i=1}^{r}h_i!}$. The compensation spoken of above reduces the sum of the parts $h_i$ for $i=d_0, d_0+1, \ldots, j$ by a total of $d_0$, but each remains at least $d_0+1$. Hence the ratio of the old to the new contributions is at most $$ \frac{d_0!}{d_0^{d_0} } \leq \sqrt{2\pi d_0}e^{-{d_0}} $$ as $d_0\to\infty$ by Stirling's formula. In how many ways can we reverse this operation? We pick $d_0$, we pick $l\le d_0$, we note that the lowest hole in the partition $\{h'_i\}$ occurs exactly at $j+2$. Then the number of possible partitions $q_{d_0}, q_{d_0+1}, \ldots, q_j$ of $d_0-l$ into $j-d_0+1$ nonnegative parts is at most $p(d_0-l)$. Thus, the contribution of the original partitions to (\ref{eqN109}) is bounded by $$ \frac{p(d_0)d_0\sqrt{2\pi d_0}}{e^{d_0}}(1+o(1)) $$ times the contribution of all partitions with $r+1$ parts. Since the sum over $d_0$ of this expression converges (by (\ref{pnbound}), the lemma is proven for $d_0\to\infty$. Suppose now, with $m-k\geq \omega(n)$, that the smallest hole is at $d_0\le \omega^{1/3}(n)$. We first show that there exists a hole above $\omega^{1/2}(n)$. If not, then the sum of the largest parts is \begin{eqnarray*} &\ge& \omega^{1/2}(n)+(\omega^{1/2}(n)+1)+\cdots+h_r\\ &=&\frac{h_r(h_r+1)}{2}- \frac{\omega^{1/2}(n)\,(\omega^{1/2}(n)-1)}{2}\\ &\ge&\frac{h_r(h_r+1)}{2}-\frac{\omega(n)}{2}. \end{eqnarray*} Thus $n$, the sum of all the parts, satisfies $\frac{h_r(h_r+1)}{2}-\frac{\omega(n)}{2}\le n \le \frac{h_r(h_r+1)}{2}$. Now $n=m(m+1)/2+k$ implies $h_r=m+1$ and $k\ge m-\omega(n)/2$ or $m-k\le \omega(n)/2$. Since we are supposing $m-k\ge\omega(n)$ that is not possible. We know, therefore, that there is a hole above $\omega^{1/2}(n)$, say at $d^\prime$. We subtract one from the first part above this hole and add one to the part $d_0-1$. That is, move the hole at $d'$ up one and the hole at $d_0$ down one (with the understanding that if $d_0=1$, we merely fill this hole in rather than moving it to 0). The ratio of the contributions to (\ref{eqN109}) of the old and new partitions is $d^\prime/d_0>\omega^{1/6}(n)$. The number of ways to reverse this operation is at most 2 and so we conclude the partitions with $r\le m-1$ are negligible if $m-k>\omega(n)$. This establishes the first part of the lemma. The proof of the second part of the lemma, when $m-k$ is bounded, is similar to the first of the two arguments above, with the following modifications. We assume $d_0\to\infty$. After filling in the hole at $d_0$, also delete the part $m-k+1$. Then this becomes the smallest hole, and the number of parts remains the same. For $n$ sufficiently large, every partition of at least $n+1$ into $m$ or fewer parts with its smallest hole at $m-k+1$ must have another hole, and so again the compensation referred to above can always be carried out. The rest of the argument follows just as before (in the case $d_0\to\infty$) except that there is an extra factor $(m-k+1)!$ in the ratio of the contributions, which is negligible because it is bounded. \qed \noindent {\bf Proof of Lemma~\ref{bounds}} \no The ratio between the contribution of the partition $\pi = \{h_j\}$ to (\ref{eqN109}) and that of the canonical partition $\pi_0 = \{h_j'\}$ is, by (\ref{Pratio}), \beql{ratiobound} \frac{\prod_j h_j^\prime !}{\prod_j h_j !} \leq \frac{{[m+1-(k-t)]}_t}{{(m+1-(k-t))}^t} \leq \exp\left(-\frac{t(t-1)}{2m}\right). \eeq The number of partitions with a given value of $t$ is bounded above by $p(t)$. The total contribution to (\ref{eqN109}) for a given $t$ is therefore bounded by $$ p(t)\exp\left(-\frac{t(t-1)}{2m}\right) \leq \exp\left(\kappa\sqrt{t}-\frac{t(t-1)}{2m}\right) $$ by (\ref{pnbound}). Take $c>{(2\kappa)}^{2/3}$ to prove the statement about $t0$. The product of these two factors is $$O(p(s) \exp(\lambda_0^2/m -C\lambda_0/\sqrt t)) = O(p(s)\exp(-CD (\log m) /2))$$ for $m$ sufficiently large. Summing over all $\lambda_0$ in this case multiplies by at most $m$, so for $D$ large enough these partitions contribute $o(p(s))$ to $g(m,s)$. Now (\ref{gbound}) follows by induction. Note that by (\ref{maxpart}), for $D$ sufficiently large, almost all partitions fall into Case 1 and hence for almost all of them, \beql{rand1} \prod_{i=0}^v \frac{m^{\lambda_i}}{[m+1+i]_{\lambda_i}} \le e^{o(1)}.\eeq To prove the corresponding lower bound $$g(m,s) \ge p(s)(1+O(r(m,D))),$$ we only need to observe that a random partition of $s$ will almost surely have at most $(D (\log m) \sqrt{s})$ parts, by (\ref{maxpart}) applied to the dual partition. Calculations as above show that the contribution of such a partition to $g(m,s)$ is asymptotically at least $1$. The lower bound follows, as does the statement about random partitions, in view of (\ref{rand1}). \qed \noindent {\bf Proof of Lemma~\ref{gtop} (i)} \no It is enough to show $$ \bE \left(\prod \frac{1}{[m+1+i]_{\la_i}} 1_{\{\la_1\le M_s\}}\right) /\bP\left(\la_1\le M_s\right) \sim m^{-s}, $$ where $\la_1\ge \cdots \ge \la_v$ is a random partition of $s$, $1_H$ denotes the indicator function of the event $H$ and $M_s>\sqrt{s}\log s$. This assumption about $M_s$ implies $\bP\left(\la_1\le M_s\right)\to 1$, by (\ref{maxpart}), hence it suffices that \beql{falling} \bE \left(\prod \frac{1}{[m+1+i]_{\la_i}} 1_{\{\la_1\le M_s\}}\right) \sim m^{-s}. \eeq Given a partition $\blam$ of $s$, we define $\rho(\blam)$ as $$ \rho(\blam)=\sum_j\left[\lambda_j^2-(2j-1)\lambda_j\right]. $$ The function $\rho(\blam)$ arises in the analysis of card shuffling; see \cite{DS}. Using Stirling's formula we find that \begin{eqnarray*} \prod \frac{1}{[m+1+i]_{\la_i}} &=& m^{-s}(1+O(s/m))\exp\left(\sum_i \frac{\la_i^2-2i\la_i}{2(m+1)} \right.\\ &&+\sum_i\frac{i^2\la_i - i\la_i^2}{2(m+1)^2} + \sum_i\frac{\la_i^3}{6(m+1)^2}\\ &&+\left.O\left(\sum_i\frac{\la_i^4+i\la_i^3+i^2\la_i^2 +i^3\la_i}{(m+1)^3} \right)\right\} \end{eqnarray*} Now $i\la_i \le s$ and $\sum\la_i^a \le (\sum\la_i)^a \le s^a$ so $\sum \la_i^4 = O(s^4)$, $\sum i\la_i^3 = O(s^3)$, $\sum i^2\la_i^2 = O(s^3)$, $\sum i^3\la_i = O(s^4)$. Also $\sum i^2\la_i = O(s^2)$, $\sum i\la_i^2 = O(s^2)$, $\sum \la_i^3 = O(s\sum \la_i^2) = o(m\sum \la_i^2)$ since $s = O(m^{2/3})$. Hence \begin{eqnarray}\label{patrick} \prod_{i=1}^v\frac{1}{[m+1+i]_{\la_i}}& =& m^{-s} \exp \left( \sum_i \frac{\la_i^2-2i\la_i}{2(m+1)} + O\left(\frac{\sum\la_i^3}{m^2}\right) + o(1)\right)\\ &=& m^{-s} \exp\left( \frac{\rho(\blam)}{2(m+1)}-\frac{\sum\lambda_i}{2(m+1)} + O\left(\frac{\sum\la_i^3}{m^2}\right) + o(1)\right)\nonumber\\ &=& m^{-s} \exp\left( \frac{\rho(\blam)}{2(m+1)} + O\left(\frac{\sum\la_i^3}{m^2}\right) + o(1)\right),\nonumber \end{eqnarray} where the $o(1)$ is independent of $\la$. We know from \cite{P} that that $\rho(\lambda)/s^{3/2}=O_p(s^{-1/4})$ (a weaker result from \cite{DS}, $\rho(\lambda)/s^{2}=o_p(1)$, is not sufficient for our purposes here); therefore $ \frac{\rho(\blam)}{2(m+1)} \Rightarrow \delta_0, $ where $\delta_x$ denotes the point mass at $x$. We know from \ref{maxpart} that $\lambda_1<\sqrt{s}\log s$ almost surely, so $\frac{\sum\la_i^3}{m^2}\Rightarrow \delta_0$. By a standard result (\cite{Bil}, page 341) we can add these three functions and revert to (\ref{patrick}) to get $$ \sum_i \frac{\la_i^2-2i\la_i}{2(m+1)} + O\left(\frac{\sum\la_i^3}{m^2}\right)+o(1) \Rightarrow \delta_0 $$ and so \beql{Zs} Z_s \Rightarrow \delta_1 \eeq where \begin{eqnarray*} Z_s &=&m^s\prod_{i=1}^s\frac{1}{[m+1+i]_{\la_i}}1_{\{\la_1\le M_s\}}\\ &=&\exp\left(\sum_i \frac{\la_i^2-2i\la_i}{2(m+1)} + O\left(\frac{\sum\la_i^3}{m^2}\right)+o(1)\right)1_{\{\la_1\le M_s\}} \end{eqnarray*} by (\ref{patrick}). It is well known from probability theory that if variables $Z_n$ converge weakly, so that $Z_n\Rightarrow Z$, and $\bE {Z_n}^{1+\epsilon} =O(1)$ for some $\epsilon>0$, then $\bE Z_n \to \bE Z$; see \cite{Bil}, page 348. Therefore, the following lemma establishes (\ref{falling}) by taking any $\beta>1$, and so completes the proof of Lemma \ref{gtop} (i). \begin{lemma}\label{expbound} Let $X_j$ be the number of parts of size $j$ in a random partition of $s$. If $s=O(m^{2/3})$, $\beta>0$ and $M_s=o(s)$, then $$ \bE \left\{\exp\left(\beta m^{-1}\sum_{j=1}^{M_s}j^2X_j\right)\right\}=O(1). $$ \end{lemma} \newpage \noindent {\bf Proof} \no We use a technique found in \cite{P}. In view of the condition on $s$, it is enough to show $$ \bE \left\{\exp\left(\beta s^{-3/2}\sum_{j=1}^{M_s}j^2X_j\right)\right\}=O(1). $$ Let $z$ and ${\bf x}=(x_1,x_2,\dots)$ be such that $\sup\{|z^jx_j|:j\ge 1\}<1$, and $\sum_{j\ge 1}|z^jx_j|<\infty$. Then $$ \sum_{s\ge 0}z^sp(s)\bE\left(\prod_{j\ge 1}x_j^{X_j}\right)= \prod_{j\ge 1}\frac{1}{1-z^jx_j}. $$ Therefore (using Cauchy's formula for the circular contour $\{z=re^{i\theta}: \,\theta\in (-\pi,\pi]\}$), \beql{Cauchy} \bE\left(\prod_{j\ge 1}x_j^{X_j}\right)=\frac{1}{2\pi r^sp(s)} \int_{-\pi}^{\pi}e^{-in\theta}\prod_{j\ge 1}\frac{1}{1-r^je^{ij\theta} x_j}\,d\theta, \eeq where $r$ is such that $\sup\{r^j|x_j|:\,j\ge 1\}<1$, and $\sum_{j\ge 1} r^j|x_j|<\infty$. Let us set $$ x_j=\left\{ \begin{array}{ll} e^{\beta s^{-3/2}j^2}&{\rm if}j\le M_s,\\ 1& {\rm if }j>M_s. \end{array} \right. $$ As for $r$, we choose $r=e^{-cs^{-1/2}},\, c=\pi/\sqrt{6}$. For $j\le M_s$, \beql{inter} -cs^{-1/2}j+\beta s^{-3/2}j^2\le -cs^{-1/2}j/2, \eeq if $s$ is sufficiently large, since $M_s=o(s)$. So $\sup\{r^jx_j:j\ge 1\}<1$, and $\sum_{j\ge 1}r^jx_j<\infty$. Using an inequality $$ \left|\frac{1}{1-z}\right|\le\frac{1}{1-|z|}\exp\left[\Re{\rm e}\, z-|z|\right], \ \ \ (z\in \Bbb C,\,|z|<1), $$ and (\ref{inter}), we bound the integrand by $$ \prod_{j=1}^{M_s}\frac{1}{1-e^{-cjs^{-1/2}+\beta s^{-3/2}j^2}}\cdot\prod _{j>M_s}\frac{1}{1-e^{-cjs^{-1/2}}} \cdot\exp\left[\sum_{j\ge 1}e^{-cjs^{-1/2}/2 }(\cos j\theta -1)\right]. $$ Using the formula \eqn{Qes}, we estimate the product of the two products as follows: \begin{eqnarray}\label{inter2} && \prod_{j=1}^{\infty}\frac{1}{1-e^{-cjs^{-1/2}}}\cdot\prod_{j=1}^{M_s} \frac{1-e^{-cjs^{-1/2}}}{1-e^{-cjs^{-1/2}+\beta s^{-3/2}j^2}} \nonumber\\ &=&\left.\exp\left[\frac{\pi^2}{6z}+\frac{1}{2}\log\frac{z}{2\pi}+O(z)\right] \right|_{z=cs^{-1/2}}\exp\left(2\sum_{j=1}^{M_s}\frac{e^{\beta s^{-3/2}j^2}-1} {e^{cjs^{-1/2}}-1}\right). \end{eqnarray} The exponential bound for the second product is based on the fact that $$ \sup_{1\le j\le M_s}\frac{e^{\beta s^{-3/2}j^2}-1}{e^{cjs^{-1/2}}-1}\to 0, $$ as $s\to\infty$. Indeed, for $j\le s^{3/4}$ the ratio is of order $$ O\left(\frac{s^{-3/2}j^2}{(js^{-1/2})^2}\right)=O(s^{-1/2}); $$ for $s^{3/4}\le j\le M_s$ the ratio is of order \begin{eqnarray*} O\left(\exp\left\{\beta s^{-3/2}j^2-cs^{-1/2}j\right\}\right) &=&O\left( \exp\left\{-cjs^{-1/2}(1-\beta c^{-1}M_s/s)\right\}\right)\\ &=&O\left(\exp\left\{-cjs^{-1/2}/2\right\}\right)\\ &=&O\left(\exp\left\{-cs^{1/4}/2\right\}\right). \end{eqnarray*} Furthermore, the sum of the ratios is of order \begin{eqnarray}\label{inter3} \sum_{j=1}^{s^{3/4}}\frac{s^{-3/2}j^2}{e^{cjs^{-1/2}}-1}+\sum_{j=s^{3/4}} ^{M_s}e^{-cjs^{-1/2}/2} &=&O\left(\int\limits_0^{\infty}\frac{x^2}{e^{cx}-1}\,dx+ \frac{e^{-cs^{1/4}/2}}{1-e^{-cs^{-1/2}/2}}\right)\nonumber\\ &=&O(1). \end{eqnarray} Using (\ref{inter2}), (\ref{inter3}), we bound the product of two products by \beql{interbnd} O\left(\frac{e^{cs^{1/2}}}{s^{1/4}}\right). \eeq The $\theta$-dependent factor is bounded above by $$ \exp\left(-\frac{a\theta^2}{s^{-3/2}+s^{-1/2}\theta^2}\right), $$ $a>0$ being an absolute constant; see (2.9) of \cite{P}. And the integral of this function over $[-\pi,\pi]$ is $O(s^{-3/4})$. Combining this estimate with (\ref{interbnd}), and taking into consideration the outside factor $$ \frac{1}{2\pi r^sp(s)}=O\left(\frac{1}{e^{-cs^{1/2}}p(s)}\right) $$ in (\ref{Cauchy}), we conclude that \begin{eqnarray*} \bE\exp\left(\beta s^{-3/2}\sum_{j=1}^{M_s}j^2X_j\right) &=& O\left(\frac{e^{cs^{1/2}}}{sp(s)r^s}\right)\\ &=&O\left(\frac{e^{2cs^{1/2}}}{sp(s)}\right)\\ &=&O(1), \end{eqnarray*} since $$ p(s)=O\left(\frac{e^{2cs^{1/2}}}{s}\right). \qed $$ \no {\bf Proof of Lemma \ref{gtop} (ii) \/} \no This follows immediately from \eqn{Zs}. \clearpage \begin{thebibliography}{99} \bibitem{Andrews} G.E. Andrews, {\em The Theory of Partitions}, Addison-Wesley, Reading, 1976. \bibitem{A} T.M. Apostol, {\em Introduction to Analytic Number Theory}, Springer, Berlin, 1976. \bibitem{Bender} E.A. Bender, Asymptotic Methods in Enumeration, {\it SIAM Review 16} (1974), 485--515. \bibitem{BOR} E.~A. Bender, A.~M. Odlyzko, and L.~B. Richmond, The asymptotic number of irreducible partitions, {\em European J. Comb. 6} (1985), 1--6. \bibitem{Bil} P. Billingsley, {\em Probability and Measure}, 2nd ed., John Wiley \& Sons, New York, 1986. \bibitem{Car} L. Carlitz, Set partitions, {\em Fibonacci Quart. 14} (1976), 327--342. \bibitem{C} L. Comtet, {\em Advanced Combinatorics}, Reidel, 1974. \bibitem{DP} J. M. DeLaurentis and B. G. Pittel, Counting subsets of the random partition and the ``Brownian Bridge" process, {\em Stochastic Processes Appl. 15} (1983), 115--167. \bibitem{DS} P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, {\em Wahr. Verw. Gebiete} (1981), 159--179. \bibitem{EL} P. Erd\H os and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, {\em Duke Math. J.} (1941), 335--345. \bibitem{GS} W.~M.~Y. Goh and E. Schmutz, Random set partitions, {\em SIAM J. Discrete Math. 7} (1994), 419--436. \bibitem{GK} D.~H. Greene and D.~E. Knuth, {\em Mathematics for the Analysis of Algorithms}, 2nd ed., Birkh\"{a}user Boston, 1982. \bibitem{GH} A. Guttman and M. Hirschhorn, Comment on the number of spiral self-avoiding walks, {\em J. Phys. A. Math. Gen. 17} (1984), 3613--3614. \bibitem{KR} A. Knopfmacher and J.~N. Ridley, Reciprocal sums over partitions and compositions, {\em SIAM J. Discrete Math. 6} (1993), 388-399. \bibitem{KW} A. Knopfmacher and K. Warlimont, Distinct degree factorizations for polynomials over a finite field, {\em Trans. Amer. Math. Soc. 347} (1995), 2235--2243. \bibitem{O} A.~M. Odlyzko, Explicit Tauberian estimates for functions with positive coefficients, {\em J. Comput. Appl. Math. 41} (1992), 187--197. \bibitem{Pi} J. Pitman, Some probabilistic aspects of set partitions. {\em American Mathematical Monthly 104} (1997), 201--209. \bibitem{P} B. Pittel, On a likely shape of the random Ferrers diagram, {\em Advances in Applied Mathematics 18} (1997), 432--488. \bibitem{P2} B. Pittel, Random set partitions: asymptotics of subset counts, {\em J. Combinatorial Theory, Series A 79} (1997), 326--359. \bibitem{S} G. Szekeres, Asymptotic distributions of the number and size of parts in unequal partitions, {\em Bull. Austral. Math. Soc. 36} (1987), 89--97. \bibitem{UFM} G.E. Uhlenbeck and G. W. Ford with E. W. Montroll, {\em Lectures in Statistical Mechanics}, Amer. Math. Soc., 1963, reprinted 1986. \bibitem{W} H.~S. Wilf, {\em generatingfunctionology}, Academic Press, 1990. \end{thebibliography} \end{document}