The asymptotic number of set partitions with unequal block sizes

A. Knopfmacher

Department of Computational and Applied Mathematics University of Witwatersrand Johannesburg, South Africa

e-mail: arnoldk@gauss.cam.wits.ac.za

A. M. Odlyzko AT&T Labs - Research

Florham Park, New Jersey 07932, USA e-mail: amo@research.att.com

B. Pittel^{1}

Department of Mathematics

Ohio State University Columbus, Ohio 43210, USA

e-mail: bgp@math.ohio-state.edu

L. B. Richmond

Department of Combinatorics and Optimization

University of Waterloo Waterloo, Ontario N2L 3G1, Canada

e-mail: lbrichmo@watdragon.uwaterloo.ca

D. Stark^{2}

Department of Mathematics and Statistics

University of Melbourne Parkville, Victoria 3052, Australia e-mail: dstark@maths.mu.oz.au

G. Szekeres Department of Mathematics University of New South Wales

Kensington, New South Wales 2033, Australia e-mail: G.Szekeres@unsw.edu.au

N. C. Wormald^{3}

Department of Mathematics and Statistics

University of Melbourne Parkville, Victoria 3052, Australia

e-mail: nick@maths.mu.oz.au

Submitted: April 20, 1998; Accepted: October 21, 1998.

1Research 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.

2Current address: BRIMS, Hewlett-Packard Labs, Filton Road, Stoke Gifford, Bristol Bs12 6QZ, UK 3Research supported by Australian Research Council

Abstract

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.

Mathematics Subject Classification (1991): 05A18, 05A16

1. Introduction

The literature on enumerating set partitions is not as extensive as that on ordinary partitions, but it is large. We refer to [4, 11, 17] 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 [6] has shown that b_{n} has the explicit generating function

F (z) = ∑_{n=0}^{∞} \frac{b_{n}}{n!} z^{n} = ∏_{k=1}^{∞} (1 + \frac{z^{k}}{k!} ) .  (1.1)

In addition, according to Wilf (p. 96 in [22]), 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 [7]) leads to the generating function

G(z) = ∏_{k=1}^{∞} (1 − \frac{z^{k}}{k!} )^{−1} .  (1.2)

The function G(z) has a first order pole at z = 1 with residue

R = ∏_{k=2}^{∞} (1 − \frac{1}{k!})^{−1} = 2.529477 ….

the electronic journal of combinatorics 6 (1999), #R2 2

The next smallest singularities are the first order poles at ±\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

H(z) = ∏_{k=1}^{∞} (1 + \frac{z^{k}}{k} ) ,  (1.3)

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 [12] used a Tauberian theorem to show that

[z^{n}]H(z) ∼ e^{−γ} as n → ∞ ,

where γ = 0.577 … 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 [15].

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} ∼ k/e as k → ∞ .

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) ≤ min_{x>0} F (x)x^{−n} ,

the electronic journal of combinatorics 6 (1999), #R2 3

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. [16]). For our function F (z), defined by (1.1), 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 ϵm ≤ k ≤ (1 − ϵ)m and m → ∞, 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 (1.1) and define a_{n} by

a_{n} = [z^{n}]F (z) = \frac{b_{n}}{n!} = ∑_{h_{1}<h_{2}<···<hr ; ∑ h_{j} =n} \frac{1}{∏_{j=1}^{r} h_{j}!} .  (1.4)

We will show in Proposition 2.2 that the largest term in this sum, when n = m(m+1)/2+k, 0 ≤ k ≤ m, is

\frac{(m + 1 − k)!}{∏_{j=1}^{m+1} j!} ,

which comes from r = m, {h_{1}, …, h_{m}} = {1, 2, …, 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,

b_{n} = n!\frac{(m + 1 − k)!f(m, k)}{∏_{j=1}^{m+1} j!} .  (1.5)

Figure 1 presents a graph of log f(200, k) for 0 ≤ k ≤ 200, which represents the values of a_{n} for 20100 ≤ n ≤ 20300. It shows that the oscillations of f(m, k) are large even for small values of m.

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 → ∞. 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} ∼ \frac{1}{2} log B_{n} as n → ∞.

Figure 1: log f(200, k)

\begin{matrix}j & −3 & −2 & −1 & 0 & 1 & 2 & 3 \\ ratio & \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{matrix}

Table 1: Asymptotic behavior of the ratio b_{N+j+1}/b_{N+j} for N = m(m + 1)/2 as m → ∞.

Equation (1.4) 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. (1.2). The same sum over compositions (ordered partitions) of n is B(n) = ∑_{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

∑ ; ∑ h_{j}=n \frac{1}{∏_{j=1}^{r} h_{j}}

over partitions with distinct parts we have the generating function H(z) of Eq. (1.3) considered by Greene and Knuth. The corresponding sums over unrestricted partitions and the electronic journal of combinatorics 6 (1999), #R2 5

compositions are treated in [14].

The shape of an unrestricted set partition was studied in [8] and [19]. 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 ([8]). 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, …, 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.

2. Main results

Let p(n) and Q(x) be defined by

Q(x) = ∑_{k=0}^{∞} p(n)x^{n} = ∏_{l=1}^{∞} \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

p(n) ≤ exp(π\sqrt{2n/3})  (2.1)

(valid for all n ≥ 1; see Apostol [2] for instance) and the more precise

p(n) ∼ \frac{1}{4\sqrt{3}n} exp (π\sqrt{2n/3})  (2.2)

as n → ∞. Moreover, it is well known from Erdős and Lehner [10], that for almost all partitions of n the largest part is asymptotic to (π\sqrt{2/3})^{−1}n^{1/2} log n; thus

p(n, [n^{1/2} log n]) ∼ p(n)  (2.3)

as n → ∞.

Theorem 2.1. Let n = k + m(m + 1)/2 and 0 ≤ k ≤ m. Then with f(m, k) defined by (1.5), we have as m → ∞ the asymptotic relations

f(m, k) ∼ \{ \begin{matrix}\frac{[m]_{k}}{m^{k}} p(k) , & if k = o(m^{2/3}/ log m) , \\ \frac{1}{(s + 1)!} ∑_{v≥0} ∑_{{d_{0}<···<dv \atop d_{0}+···+dv=s+1}} ∏_{j=0}^{v} d_{j}! , & if k = m − s, s fixed . \end{matrix}

Theorem 2.2. Let n = k + m(m + 1)/2 and 0 ≤ k ≤ m. Then with ω(m) denoting an arbitrary function such that ω(m) → ∞ as m → ∞, we have as m → ∞

f(m, k) ∼ ∑_{t=0}^{k} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t)

for \sqrt{m} log m < k < m − ω(m).

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.

Proposition 2.1. Let n = k + m(m + 1)/2, 0 ≤ k ≤ m. Then with f(m, k) defined by (1.5) and ω(m) denoting an arbitrary function → ∞ as m → ∞, we have as m → ∞

f(m, k) ∼ ∑_{t=0}^{k} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t)

if 0 ≤ k < m − ω(m), and

f(m, k) ∼ Q(1 − k/m)

provided Cm^{3/4} log m < k < m − ω(m) for some C > 0.

Remark. Note that the formula given for f(m, k) in Theorem 2.1 or Proposition 2.1 is asymptotic to p(k) for k = o(\sqrt{m}). It is curious that, as shown in Proposition 2.1, 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 2.2 for a wide range of k. For 0 < μ < 1/3, define

S_{1} = S_{1}(μ) = \frac{1}{(24μk)^{1/4}} (\frac{1 − μ}{1 − 3μ})^{1/2} exp (F (μk) + 2c\sqrt{μk}) ,  (2.4)

where c = π/\sqrt{6} and F (t) is defined for 0 ≤ t ≤ k by

F (t) = (m − k + t) log (1 + \frac{t}{m − k} ) + t log (1 − \frac{k}{m}) − t.

Also, define

S_{0} = e^{F (k)}p(k) ∼ \frac{1}{4\sqrt{3}k} exp (2c\sqrt{k} + (m − k) log (\frac{m}{m − k} ) − k) ,

where we used (2.2). Our final asymptotic formula for f(m, k) in terms of simple functions is the following. Note that we permit β → 0 and β → ∞.

Theorem 2.3. Take m and k as in Theorem 2.1. Set

β = cm/k^{3/2}

and determine ξ by

β = \frac{8}{27} + \frac{2}{27c^{4}} \frac{log m}{m^{\frac{1}{3}}} + \frac{ξ}{m^{\frac{1}{3}}} .

For 0 < β ≤ 2/3\sqrt{3}, let μ be the (unique) solution of

μ^{1/2}(1 − μ) = β, 0 < μ ≤ 1/3.

Then

f(m, k) ∼ \{ \begin{matrix}S_{0} , & if ξ → ∞, \\ S_{0} + S_{1} , & if ξ = O(1), \\ S_{1} , & if ξ → −∞ and k = o(m), \\ \frac{1}{(s + 1)!} ∑_{v≥0} ∑_{{d_{0}<···<dv \atop d_{0}+···+dv=s+1}} ∏_{j=0}^{v} d_{j}! , & if k = m − s, s fixed . \end{matrix}

Moreover, for ξ = O(1),

f(m, k) ∼ \frac{\sqrt{2}}{\sqrt{3}c^{\frac{1}{6}} m^{\frac{7}{96}}} exp (\frac{15}{32}c^{\frac{4}{3}} m^{\frac{1}{3}} )

× (\frac{1}{9\sqrt{2c}} exp (\frac{513}{64}c^{\frac{4}{3}} ξ − \frac{243}{128}c^{2}) + \frac{2^{\frac{1}{4}}}{3^{\frac{1}{4}}} exp (\frac{81}{64}c^{\frac{4}{3}} ξ − \frac{217}{384}c^{2})) .

Remark on “continuity” of estimates.

This theorem was proved by continuously adding unsuspecting collaborators until the proverbial camel’s back could hold no longer. Conceptually, what is a camel, if not a horse designed by a committee? In our case, it was not even a camel, just a function f(m, k). Its graph in Figure 1 has some suspicious humps, due, no doubt, to the tail behavior! So it would be comforting to check that the last theorem provides a piece-wise smooth asymptotic description for f(m, k) dependent on how large k is, compared to m. The first three formulas for f(m, k) indicate three distinct modes of asymptotic behavior, subcritical (ξ → ∞), near-critical (ξ = O(1)), and supercritical (ξ → −∞). The ξ- parametrization and the last formula for the near-critical case ξ = O(1) provides a smooth interpolation (a magnified bridge) between the three modes. Indeed, it will be seen in the proof that, for ξ = O(1), the first of the two terms in the long parenthetical factor comes from S_{0}, the the electronic journal of combinatorics 6 (1999), #R2 8

second - from S_{1}, and the first (second, resp.) term is dominant if ξ → ∞ (if ξ → −∞, resp.). Thus, for k = o(m), the various asymptotics gracefully merge into each other at the borders of their respective spheres of influence, and f(m, k) has no humps, except legal ones! (Actually we shall see that the estimate S_{0} + S_{1} is valid for ε_{1} < β < \frac{8}{27} + ε_{2}, for ε_{1} > 0 and ε_{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) = ∑_{k≥1} k!x^{k} we see that the terms with v ≥ 1 are bounded by [x^{s+1}]f(x)^{v+1}. However [x^{s+1}] ∑_{v≥0} f(x)^{v+1} ∼ (s + 1)! by Bender[3, Theorem 3]. Thus lim_{s→∞} f(m, m − s) = 1, and so the expression for k = m − O(1) merges with the expression for large k in Proposition 2.1. Further remarks. It is also worth checking the extent of overlap of the various formulae we have for f(m, k). If k = δm^{\frac{2}{3}} then

S_{0} ∼ p(k)\frac{[m]_{k}}{m^{k}} ∼ p(k) exp (−\frac{1}{2}δ^{2}m^{\frac{1}{3}} − \frac{1}{6}δ^{3} + O(m^{− \frac{1}{3}} ))

and so by Theorem 2.3 the range of the first expression in Theorem 2.1 can be extended to o(m^{\frac{2}{3}} ) and even ξ → ∞, which is the limit of its range of validity.

We next check the range of validity of the second formula in Proposition 2.1. If k = xm^{\frac{3}{4}} then β = cx^{− \frac{3}{2}} m^{− \frac{1}{8}} = o(1) so f(k, m) ∼ S_{1}. Now since \sqrt{μ}(1 − μ) = β we have μ = β^{2} + 2β^{4} + 7β^{6} + O(β^{8}) so

μk = c^{2}x^{−2}m^{\frac{1}{2}} + 2c^{4}x^{−5}m^{\frac{1}{4}} + 7c^{6}x^{−8} + O (m^{− \frac{1}{4}} ) ,

(m − k + μk) log (1 + \frac{μk}{m − k} ) = μk + \frac{(μk)^{2}}{2(m − k)} + O(m^{− \frac{1}{2}} ),

μk log (1 − \frac{k}{m}) = −\frac{μk^{2}}{m} − \frac{μk^{3}}{2m^{2}} + O(m^{− \frac{1}{4}} ).

Thus

F (μk) = −\frac{c^{2}}{x} m^{\frac{1}{4}} + \frac{c^{4}}{2x^{4}} + O(m^{− \frac{1}{4}} ).

Furthermore

2c(μk)^{\frac{1}{2}} = 2c^{2}x^{−1}m^{\frac{1}{4}} + 2c^{4}x^{−4} + O(m^{− \frac{1}{4}} )

so

exp(F (μk) + 2c\sqrt{μk}) = exp (\frac{c^{2}}{x} m^{\frac{1}{4}} + \frac{5c^{4}}{2x^{4}} + O(m^{− \frac{1}{8}} )) .

As (24μk)^{\frac{1}{4}} ∼ \sqrt{2π}m^{\frac{1}{8}} x^{\frac{−1}{2}} we now have

S_{1} ∼ \frac{x^{1/2}m^{−1/8}}{\sqrt{2π}} exp (\frac{c^{2}m^{1/4}}{x} + \frac{5c^{4}}{2x^{4}} ) .

However

Q(1 − k/m) = Q (e^{\frac{k}{m} − \frac{k^{2}}{2m^{2}} +O( \frac{k^{3}}{m^{3}} )})

and it is well known (see for instance Andrews [1]) that

Q(e^{s}) = e^{π^{2}/6s}\sqrt{s/2π}(1 + O(s))  (2.5)

and hence Q(1 − k/m) ≁ f(k, m) if k = xm^{3/4} for fixed x.

Note next that if k = o(m) but km^{−3/4} → ∞ then β → 0 so μ ∼ β^{2} and μk ∼ c^{2}m^{2}/k^{2} = o(m^{1/2}). Thus

(m − k + t) log (1 + \frac{t}{m − k} ) = t + O (\frac{t^{2}}{m − k} ) = t + o(1),

so the sum over those t for which t = μk + O ((μk)^{7/8}) in ∑_{t} e^{F (t)}p(t) is asymptotic to ∑_{t} p(t)(1 − k/m)^{t} (summed over these t). We shall see however that the sum over the other t in ∑_{t} e^{F (t)}p(t) is negligible. If |t − μk| ≥ (μk)^{7/8} then p(t)(1 − k/m)^{t} ≤ p(μk)(1 − μk/m)^{μk} exp(−δ(μk)^{1/4}) for some δ > 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) ∼ Q(1 − k/m), the second formula in Proposition 2.1, is m − k → ∞ and km^{−3/4} → ∞.

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 ∼ 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 ≤ k ≤ m. Let

Π(n, r) = {(h_{1}, h_{2}, …, h_{r}) : 1 ≤ h_{1} < h_{2} < ⋯ < h_{r}, ∑_{j=1}^{r} h_{j} = n}  (2.6)

be the set of partitions of the integer n into r distinct parts, and let

Π(n) = ⋃_{r≥1} Π(n, r) .

Note that Π(n, r) = ∅ for r ≥ m + 1. For π ∈ Π(n, r), π = (h_{1}, h_{2}, …, h_{r}), let

P (π) = \frac{1}{∏_{j=1}^{r} h_{j}!} .

the electronic journal of combinatorics 6 (1999), #R2 10

Thus

a_{n} = ∑_{π∈Π(n)} P (π) .

We will say that π = (h_{1}, h_{2}, …, h_{r}) = [u, u′]−[w] if {h_{1}, …, h_{r}} = {u, u+1, …, u′}−{w}. Thus π consists of all the integers in an interval with the possible exception of a single integer, the “hole.” In the case of the partition π_{0} = [1, m + 1] − [m + 1 − k], we will say that π_{0} is the canonical partition of n.

Proposition 2.2. For any r, the maximum of P (π) over π ∈ Π(n, r) is achieved uniquely by π = [u, u′] − [w] for some u ≤ w ≤ u′. The maximum of P (π) over all π ∈ Π(n) is achieved by the canonical partition π_{0}.

To get started in our analysis when m−k → ∞ it is convenient to characterise partitions according to which block or part sizes are missing. For π ∈ Π(n, m) as in (2.6), let d_{0} < ⋯ < d_{v}, where v = h_{m} − m − 1 ≥ 0, denote the “holes” of π, that is all the numbers from 1 to h_{m} − 1 which do not appear in π. Observe that properly inserting the missing numbers into π results in the complete staircase diagram with m + v + 1 steps, that is

∑_{j=1}^{m+v+1} j = n + d_{0} + ⋯ + d_{v},

or

k = n − \frac{m(m + 1)}{2} = λ_{0} + ⋯ + λ_{v}, λ_{i} := m + 1 + i − d_{i}.

Since d_{i} is strictly increasing, λ_{i} is nonincreasing. Also λ_{v} ≥ 1, because d_{v} ≤ h_{m}−1 = v+m. Thus λ = (λ_{0}, …, λ_{v}) is a partition of k, which we call the hole partition corresponding to π or to the associated set partition, from which π can be recovered (given n). When we come to describe the likely shape of π, we will be comparing P (π) to P (π_{0}), and it is immediate that

P (π) = ∏_{j=0}^{v} d_{j}! ( ∏_{j=1}^{m+v+1} j!)^{−1} ,
P (π_{0}) = (m + 1 − k)! ∏_{j=1}^{v}(m + j + 1)! ( ∏_{j=1}^{m+v+1} j!)^{−1} ,

since π_{0} has a single hole m + 1 − k, and its largest part is m + 1. Thus

\frac{P (π)}{P (π_{0})} = \frac{d_{0}!}{(m + 1 − k)!} · ∏_{i=1}^{v} \frac{d_{i}!}{(m + i + 1)!}

= [m + 1 − k + t]_{t} · ∏_{i=1}^{v} \frac{1}{[m + 1 + i]_{λ_{i}}} ,  (2.7)

where t = λ_{1} + … + λ_{v}. It is this formula that will make the notion of the hole partition so useful for us.

The partition

t = λ_{1} + … + λ_{v}

will itself play an important role around the difficult range k ≈ m^{2/3}. It is important to note the upper bound

λ_{1} ≤ k − t,

which holds because λ_{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 {λ_{i}}. We can conclude various results about the shape of a random partition from our main results on asymptotics.

Define Ω_{n} to be the probability space whose elements are partitions λ = {λ_{0}, …, λ_{v}} of k, with probability proportional to the number of partitions of an n-set with hole partition λ. Note that r can be regarded as a random variable on Ω_{n} since it is determined in a natural way from λ by the fact that the r smallest integers other than those holes determined by λ sum to n. We say that a random partition π is 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 π and the uniformly distributed partitions of the same number (with the same part size bound, if it is specified) tends to 0 as n → ∞. We also say that an event occurs almost surely if its probability tends to 1 as n → ∞.

First we consider small k. Proposition 2.3. For sufficiently large D, and k < m^{2/3}/D log n, we have r = m almost surely, and λ ∈ Ω_{n} is distributed asymptotically uniformly as a random partition of k.

Next we have a less conclusive result for a wider range of k. Proposition 2.4. For k ≥ 0 with m − k → ∞, for λ = (λ_{0}, …, λ_{v}) ∈ Ω_{n}, r = m almost surely, and

(i) the sub-partition (λ_{1}, …, λ_{v}) is distributed asymptotically uniformly as a random partition of k − λ_{0} with largest part at most λ_{0}.

(ii) conditional upon k, the distribution of λ_{0} and the distribution of a random variable X with P(X = j) proportional to

\frac{[m + 1 − j]_{k−j}}{m^{k−j}} p(k − j, j)

have total variation distance tending to 0.

When k grows considerably larger than the trouble-spot near m^{2/3}, we can simplify the previous statement by dropping the bound on the part size. This can be stated as follows.

Proposition 2.5. For some c > 0, if k > cm^{2/3} and m−k → ∞ then for λ = (λ_{0}, …, λ_{v}) ∈ Ω_{n}, the sub-partition (λ_{1}, …, λ_{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 P(X = i) proportional to

\frac{[m + 1 − k + i]_{i}}{m^{i}} p(i)

have total variation distance tending to 0.

In fact, from the proof of Theorem 2.3, it is easy to deduce more about the distribution of X.

For the remaining, very large, values of k, we have the following.

Proposition 2.6. 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}, …, d_{v} are a random partition of s + 1 into distinct parts in which the probability is asymptotically proportional to ∏_{j=0}^{v} d_{j}!.

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 2.6 when m − k is bounded. On the other hand, when m − k → ∞ Proposition 2.4 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 λ_{1}, …, λ_{v} as discussed in Proposition 2.4, and so this proposition determines its distribution asymptotically, as do Propositions 2.3 and 2.5. The simplest result on this is given by Proposition 2.3, that for k < m^{2/3}/D log n, v will be distributed asymptotically as the number of parts, plus 1, in a random partition of k.

3. Structure of Proof

The propositions and theorems are proved in this section, and proofs of the lemmas used here are given in the next section. First we show that almost all of the set partitions under consideration have precisely r = m blocks, unless m − k is bounded, in which case d_{0} is bounded.

Lemma 3.1. For m − k → ∞,

a_{n} ∼ ∑_{h_{1}<h_{2}<···<hm ; ∑ h_{j} =n} \frac{1}{∏_{j=1}^{r} h_{j}!} .

If m−k is bounded, the contribution to the summation in (1.4) from partitions with d_{0} → ∞ is negligible.

Considering the definition of f(m, k) at (1.4) and (1.5), we can write f(m, k) as the sum of P (π)/P (π_{0}) over all π ∈ Π(n, r) and over all appropriate r. Lemma 3.1 implies that only terms with r = m are significant for m − k → ∞, and so in this case

f(m, k) ∼ ∑_{t=0}^{k} \frac{[m + 1 − k + t]_{t}}{m^{t}} g(m, t, k − t) = \frac{[m + 1]_{k}}{m^{k}} g(m, k)  (3.1)

where

g(m, s, b) = ∑_{{b≥λ_{1}≥λ_{2}≥···≥λv \atop λ_{1}+···λv=s}} ∏_{i=1}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}}  (3.2)

and (as seen by writing λ_{0} for k − t)

g(m, s) = ∑_{λ_{0}≥λ_{1}≥···≥λv ; ∑ λ_{i}=s} ∏_{i=0}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} .  (3.3)

Note that g(m, s) is the same as g(m, s, b) except that it has no restriction on the largest part size.

Lemma 3.2. For some constant c, the summation in (3.1) is asymptotically unchanged when it is restricted to

t < c min{m^{2/3}, m^{2}/k^{2}}

and it is also asymptotically unchanged if λ_{1} in (3.2) is resticted to

λ_{1} < \sqrt{m}(log m)^{3/2}.

Due to these upper bounds on t, it is possible to determine the behaviour of g(m, s, b) when k is not near m^{2/3} using the following lemma.

Lemma 3.3. For D large enough and s < m^{2/3}/D log m,

g(m, s) ∼ p(s)

as s → ∞, and furthermore, for some fixed function w(n) → 0, almost all partitions λ_{0}, …, λ_{v} of s satisfy

|1 − ∏_{i=0}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} | ≤ w(n).

Values of t between the upper bounds in Lemmas 3.2 and 3.3 are taken care of primarily by the following result, which we prove by analysing a function which has already been studied in connection with card shuffling.

Lemma 3.4. (i) For M_{s} = o(s) with M_{s} > \sqrt{s} log s and s = O(m^{2/3}),

g(m, s, M_{s}) ∼ p(s)

as s → ∞, and furthermore

(ii) for some fixed function w(n) → 0, almost all partitions λ_{1}, …, λ_{v} of s with λ_{1} ≤ M_{s}

satisfy

|1 − ∏_{i=1}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} | ≤ w(n).

Proof of Theorem 2.1 First consider k < m^{2/3}/D log m. Lemma 3.1 implies that only terms with r = m are significant, Lemma 3.3 gives g(m, k) ∼ p(k), and so the formula on the right in (3.1) becomes

\frac{[m + 1]_{k}}{m^{k}} p(k) ∼ \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}, …, d_{v} denote the holes in π. Partitions with less than m parts are now significant in (1.4). 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

1 + 2 + ⋯ + (m + 1) − d_{0} − d_{1} − ⋯ − d_{v} = h_{1} + h_{2} + ⋯ + h_{r}
= (1 + 2 + ⋯ + m) + k
= 1 + 2 + ⋯ + (m + 1) − s − 1,

so d_{0} + d_{1} + ⋯ + d_{v} = s + 1. Since P (π) = ∏_{i=0}^{v} d_{i}! ∏_{i=1}^{m+1} \frac{1}{i!}, the second part of Theorem 2.1 follows if these are the only significant partitions. So now suppose h_{r} ≥ m + 2. Then

h_{1} + h_{2} + ⋯ + h_{r} ≥ 1 + 2 + ⋯ + (m + 2) − d_{0} − ⋯ − d_{v}
> n + (m + 2) − d_{0} − ⋯ − d_{v}.

But the sum on the left is n and so, since the d_{i} are distinct, d_{v} ≥ \sqrt{m}. From Lemma 3.1 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 (1.4) by at least d_{v}/d_{0} → ∞. 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. Proof of Theorem 2.2 Take any k > \sqrt{m} log m, but m − k → ∞. We break the terms in the summation in (3.1) into groups according to the value of t. Case 1. t ≥ k − k^{2/3}.

By Lemma 3.2 we can assume k = O(m^{2/3}). Then

\frac{[m + 1]_{k−t}}{m^{k−t}} ∼ 1

for all such t. Thus, on multiplication by this quantity, the sum of the terms with t in this range is

∑_{t=⌈k−k^{2/3}⌉}^{k} \frac{[m + 1 − k + t]_{t}}{m^{t}} g(m, t, k − t) ∼ ∑_{t=⌈k−k^{2/3}⌉}^{k} \frac{[m]_{k}}{m^{k}} g(m, t, k − t).

But this equals \frac{[m]_{k}}{m^{k}} g(m, k, ⌈k^{2/3}⌉). Now by Lemma 3.4 this is asymptotic to \frac{[m]_{k}}{m^{k}} p(k), which is in turn asymptotic to

∑_{t=⌈k−k^{2/3}⌉}^{k} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t)

by (2.3). Case 2. log m < t < k − k^{2/3}. By Lemma 3.2, we can assume that λ_{0} (= k − t) is at most \sqrt{m}(log m)^{3/2}. This is o(k). So by Lemma 3.4, and then using (2.3), g(m, t, k − t) ∼ p(t) ∼ p(t, k − t), and so

\frac{[m + 1 − k + t]_{t}}{m^{t}} g(m, t, k − t) ∼ \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t)  (3.4)

as required. Since Lemma 3.4 requires s → ∞, we deal with small t separately in the next case. Case 3. t ≤ log m.

Here, immediately from the definition (3.2), g(m, t, k − t) ∼ p(t, k − t) and so we again have (3.4). This gives the theorem. Proof of Proposition 2.1 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 2.2 can be written as

∑_{λ_{0}=0}^{k} \frac{[m + 1 − λ_{0}]_{k−λ_{0}}}{m^{k−λ_{0}}} p(k − λ_{0}, λ_{0})  (3.5)

or

∑_{{λ_{0}≥λ_{1}≥··· \atop λ_{0}+λ_{1}+···=k}} \frac{[m + 1 − λ_{0}]_{k−λ_{0}}}{m^{k−λ_{0}}} .  (3.6)

The summand in (3.6) for any term with λ_{0} < m^{1/2−ϵ} (ϵ > 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 λ_{0} ≥ m^{1/2−ϵ} can be estimated using (3.5), where for each λ_{0} the term is at most p(k − λ_{0}, λ_{0}) ≤ p(k − λ_{0}). For k ≤ \sqrt{m} log m, this contribution is o(p(k)[m]_{k}/m^{k}). The first part of Proposition 2.1 follows.

From Lemma 3.2, only the terms with t < cm^{2}/k^{2} are significant in the statement of Theorem 2.1. Note that m^{2}/k^{2} = O(m^{1/2}/ log^{2} m). Suppose k = o(m). Now

[m + 1 − k + t]_{t} = (m + 1 − k)^{t} exp (\frac{t^{2}}{2(m + 1 − k)} + O (\frac{t^{3}}{(m + 1)^{2}} ))
∼ (m + 1 − k)^{t}.  (3.7)

Hence,

∑_{t} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t) ∼ ∑_{t} (1 − k/m)^{t}p(t)
= Q(1 − k/m).

If k ≥ m/ω(n) for some x > 0 and m + 1 − k > ω^{3}(n), then by (3.7)

∑_{t≥ω(n)} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t) ≤ ∑_{t≥ω(n)} (1 − x/2)^{t}p(t)
= o(1).

Note that

∑_{t<ω(n)} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t, k − t) ∼ ∑_{t<ω(n)} \frac{[m + 1 − k + t]_{t}}{m^{t}} p(t)
∼ ∑_{t<ω(n)} (1 − k/m)^{t}p(t)
∼ Q(1 − k/m).

Proof of Theorem 2.3 The last part of the theorem, referring to m − k bounded, is the same as in Theorem 2.1. For m − k → ∞ but k ≠ o(m), the theorem is covered by Proposition 2.1 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) ∼ ∑_{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 2.1. By Stirling’s formula,

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 (1 + \frac{t}{m − k} ) − t + t log (1 − \frac{k − t}{m}) + o(1)
= (m − k + t) log (1 + \frac{t}{m − k} ) + t log (1 − \frac{k}{m}) − t + o(1)
= F (t) + o(1).

the electronic journal of combinatorics 6 (1999), #R2 18

(We note for later reference that

F′(t) = log (1 − \frac{k − t}{m}) , F′′(t) = \frac{1}{m − k + t}, F′′′(t) = O(m^{−2}).)  (3.8)

Thus

f(m, k) ∼ ∑_{t=0}^{k} e^{F (t)}p(t, k − t).  (3.9)

To proceed, notice that

p(t, k − t) ≤ p(t) ≤ exp(2c\sqrt{t})

by (2.1), and so

e^{F (t)}p(t, k − t) ≤ e^{G(t)}, G(t) := F (t) + 2c\sqrt{t}.

Recall that we introduced β via k^{3/2} = cm/β. Case 1. Consider the small β’s first. Pick a small ε > 0 and suppose that β ≤ ε and that k = o(m), which is equivalent to βk^{1/2} → ∞. An easy calculation shows that G(t) has two stationary points

t_{0} = β^{2}k [1 + O (β^{2} + \frac{1}{βk^{1/2}} )] ,
t_{1} = k − βk(1 + O(β)),

which are a local maximum and local minimum respectively. Further, with more algebra,

G(t_{0}) = (2c\sqrt{t_{0}} − \frac{kt_{0}}{m} ) [1 + O (β^{2} + \frac{1}{βk^{1/2}} )]
= cβk^{1/2} [1 + O (β^{2} + \frac{1}{βk^{1/2}} )] ,  (3.10)
G(k) = −\frac{k^{2}}{2m} (1 + O(β + (βk^{2}1/2)^{−1})) + 2c\sqrt{k}
= −\frac{ck^{1/2}}{2β} (1 + O(β + (βk^{1/2})^{−1})) .  (3.11)

Since G(t_{0}) ≥ G(k), G(t) attains its absolute maximum at t_{0}. Also, for t ≤ t^{∗} = t_{0} + t_{0}^{7/8},

G′′(t) = \frac{1}{m − k + t} − \frac{c}{2t^{3/2}}  (3.12)
≤ −\frac{c}{2.5t_{0}^{3/2}} ,

whence

e^{G(t^{∗})} ≤ exp (G(t_{0}) − \frac{c(t^{∗} − t_{0})^{2}}{5t_{0}^{3/2}} )
= exp(G(t_{0}) − \frac{1}{5}ct_{0}^{1/4}).  (3.13)

Introduce t^{∗∗} = βk. It is easy to see that

G(t^{∗∗}) = −\frac{t^{∗∗}k}{m} [1 + O (β^{2} + \frac{1}{βk^{1/2}} )]
= −ck^{1/2} [1 + O (β^{2} + \frac{1}{βk^{1/2}} )] ,  (3.14)

and that, for t ∈ [t^{∗}, t^{∗∗}],

G′(t) ≤ G′(t^{∗}) = G′(t_{0}) + G′′(t̃)(t^{∗} − t_{0})
(for some t̃∈ [t_{0}, t^{∗}])
≤ −\frac{c}{2.5}t_{0}^{−5/8}.

(The inflection point t̂ of G(t) is of order kβ^{2/3} ≫ kβ, so that G′(t) decreases for t ≤ t^{∗∗}.) Therefore, for t ∈ [t^{∗}, t^{∗∗}], we bound

\frac{e^{G(t+1)}}{e^{G(t)}} ≤ exp (−\frac{c}{2.5}t_{0}^{−5/8}) ,  (3.15)

so the terms e^{G(t)} are bounded by the terms of a geometric progression with denominator given by the right hand expression. Combining (3.11)–(3.15), we bound

∑_{t≥t^{∗}} e^{G(t)} ≤ 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)\}
≤ e^{G(t_{0})} · e^{−ct_{0}^{1/4}/6} + e^{−ck^{1/2}/2}.  (3.16)

Analogously to (3.13) and (3.15), for t_{∗} = t_{0} − t_{0}^{7/8} and t ∈ [2, t_{∗}],

e^{G(t_{∗})} ≤ exp(G(t_{0}) − ct_{0}^{1/4}/5),
\frac{e^{G(t−1)}}{e^{G(t)}} ≤ exp (−\frac{c}{2.5}t_{0}^{−5/8}) ,

so that

∑_{t≤t_{∗}} e^{G(t)} ≤ e^{G(t_{0})} · e^{−ct_{0}^{1/4}/6}.  (3.17)

Finally, using (3.13), we obtain

∑_{t∈(t_{∗},t^{∗})} e^{G(t)} ∼ e^{G(t_{0})} ∫_{t_{∗}}^{t^{∗}} exp (\frac{G′′(t_{0})}{2}(t − t_{0})^{2}) dt
∼ e^{G(t_{0})} · \sqrt{\frac{2π}{−G′′(t_{0})}} .

the electronic journal of combinatorics 6 (1999), #R2 20 To evaluate G′′(t_{0}) we note that from G′(t_{0}) = 0 it follows that

\frac{k − t_{0}}{m} ∼ \frac{c}{\sqrt{t_{0}}} .

Therefore

−G′′(t_{0}) = \frac{c}{2t_{0}^{3/2}} − \frac{1}{m − k + t_{0}}
∼ \frac{c}{2t_{0}^{3/2}} − \frac{1}{m} ∼ \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})}.

Thus, observing from (2.2) that

p(t, k − t) ∼ p(t) ∼ \frac{e^{2c\sqrt{t}}}{4\sqrt{3}t_{0}}

uniformly for t ∈ (t_{∗}, t^{∗}), we evaluate

∑_{t=0}^{k} e^{F (t)}p(t, k − t) = \frac{1 + o(1)}{4\sqrt{3}t_{0}} ∑_{t∈(t_{∗},t^{∗})} e^{G(t)} + O (e^{G(t_{0})} · e^{−ct_{0}^{1/4}} + e^{−ck^{1/2}/2})
∼ \frac{e^{G(t_{0})}}{(24t_{0})^{1/4}} (\frac{k − t_{0}}{k − 3t_{0}} )^{1/2}
∼ S_{1}  (3.18)

since t_{0} ∼ μk. Case 2. Now consider the case of large β’s, that is β ≥ ε, or k^{3} = O(m^{2}). Expanding F (t) at k and using (3.10),

e^{F (t)}p(t, k − t) = O (e^{F (k)}e^{g(t)}) ,
g(t) := \frac{(k−t)^{2}}{2m} + 2c\sqrt{t}.

If the equation

g′(t) = −\frac{k − t}{m} + \frac{c}{\sqrt{t}} = 0

has a root τ^{∗} then, setting μ^{∗} = τ^{∗}/k, we get

β = \sqrt{μ^{∗}}(1 − μ^{∗}).

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 β > \frac{2}{3\sqrt{3}}, then there is no root τ^{∗}, and g(t) is strictly increasing for all t’s. If β = \frac{2}{3\sqrt{3}}, then the electronic journal of combinatorics 6 (1999), #R2 21

there is a unique root τ^{∗} = k/3, but it is an inflection point for g(t), which therefore remains strictly increasing for all t’s. If β < \frac{2}{3\sqrt{3}}, then there are two roots 0 < τ_{0} < k/3 < τ_{1} < 1, so that g(t) is increasing on [0, τ_{0}] ∪ [τ_{1}, 1], and decreasing on [τ_{0}, τ_{1}]. The single inflection point is k(β/2)^{2/3}.

Let ε > 0 be given. Case 2(a). β ≥ \frac{8}{27} + ε. A little algebra shows that g(t) = g(k) for some t < k iff

k − t = \frac{4βk^{3/2}}{\sqrt{k} + \sqrt{t}}.  (3.19)

Since β > 8/27 and \sqrt{τ_{0}}(k − τ_{0}) = βk^{3/2}, τ_{0} > k/9 and so (k − t)(\sqrt{k} + \sqrt{t}) is decreasing on τ_{0} ≤ t ≤ k. Thus g(t) < g(k), (∀ t < k), if τ_{0} satisfies

k − τ_{0} < \frac{4βk^{3/2}}{\sqrt{k} + \sqrt{τ_{0}}} ,

which is clearly true once again using \sqrt{τ_{0}}(k − τ_{0}) = βk^{3/2} and τ_{0} > k/9.

We know that g(t) is increasing if β ≥ \frac{2}{3\sqrt{3}}. If β < \frac{2}{3\sqrt{3}}, then there exists τ_{2} ∈ (τ_{1}, k) such that g(τ_{0}) = g(τ_{2}). Since β is bounded away from \frac{8}{27}, the difference k − τ_{2} is of order k exactly. (This follows from the conditions

g(τ_{0}) = g(τ_{2}), g′(τ_{0}) = 0.)

Thus, in either case,

e^{F (k)} ∑_{t=0}^{k−k^{5/8}} e^{g(t)} = O (k exp[F (k) + g(k − k^{5/8})])
= O (k exp[F (k) + 2c\sqrt{k} − ck^{1/8}]) .  (3.20)

On the other hand, F (t) ∼ F (k) uniformly for t ∈ [k − k^{5/8}, k], since k = O(m^{2/3}); so

∑_{t=k−k^{5/8}}^{k} e^{F (t)}p(t, k − t) ∼ e^{F (k)} ∑_{t=k−k^{5/8}}^{k} p(t, k − t)
= e^{F (k)} ∑_{t=k−k^{5/8}}^{k} P (k, k − t)
∼ e^{F (k)}p(k)
∼ \frac{exp[G(k)]}{4\sqrt{3}k}.  (3.21)

the electronic journal of combinatorics 6 (1999), #R2 22

(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 ν the largest part is of order O(\sqrt{ν} log ν).) Comparing (3.20) and (3.21) we get

∑_{t=0}^{k} e^{F (t)}p(t, k − t) ∼ \frac{exp[G(k)]}{4\sqrt{3}k} ∼ S_{0}.  (3.22)

Case 2(b). β ≤ 8/27 + ε < \frac{2}{3\sqrt{3}}. The equation

G′(t) = log (1 − \frac{k − t}{m}) + \frac{c}{\sqrt{t}} = 0

has two roots 0 < t_{0} < 1/3 < t_{1} < k (cf. Case 1), which are relatively close to τ_{0} and τ_{1} respectively; more precisely

t_{i} − τ_{i} = O (\frac{k^{2}}{m} ) = O(k^{1/2}), i = 1, 2.

Arguing basically as in Case 1, we obtain

∑_{t=0}^{t_{1}} e^{F (t)}p(t, k − t) = (1 + o(1)) ∑_{|t−t_{0}|≤t_{0}^{7/8}} e^{F (t)}p(t) + O(e^{G(t_{0}±t_{0}^{7/8})})
∼ \frac{1}{4\sqrt{3}t_{0}} ∑_{|t−t_{0}|≤t_{0}^{7/8}} e^{G(t)}
∼ \frac{e^{G(t_{0})}}{4\sqrt{3}t_{0}} · \sqrt{\frac{2π}{−G′′(t_{0})}},
−G′′(t_{0}) ∼ \frac{c}{2t_{0}^{3/2}} − \frac{1}{m} ∼ \frac{c(k − 3t_{0})}{2t_{0}^{3/2}(k − t_{0})},

or

∑_{t=0}^{t_{1}} e^{F (t)}p(t, k − t) ∼ \frac{e^{G(t_{0})}}{(24t_{0})^{1/4}} (\frac{k − t_{0}}{k − 3t_{0}} )^{1/2} .  (3.23)

Since k − t_{1} is of order k exactly, we get (see Case 2(a)):

∑_{t=t_{1}}^{k} e^{F (t)}p(t, k − t) ∼ \frac{e^{G(k)}}{4\sqrt{3}k} .  (3.24)

From (3.23) and (3.24) it follows that

∑_{t=0}^{k} e^{F (t)}p(t, k − t) = (1 + o(1))\frac{e^{G(t_{0})}}{(24t_{0})^{1/4}} (\frac{k − t_{0}}{k − 3t_{0}} )^{1/2}

+(1 + o(1))\frac{e^{G(k)}}{4\sqrt{3}k}

∼ S_{1} + S_{0}  (3.25)

the electronic journal of combinatorics 6 (1999), #R2 23

after a little algebra. This finishes Case 2(b).

The parts of the theorem for k = o(m) have now been established by (3.18) and (3.22) except for the range ε ≤ β ≤ \frac{8}{27} + ε, for some ε > 0. For this remaining range, from (3.9), (3.22) and (3.25) we have

f(m, k) ∼ S_{0} + S_{1}.  (3.26)

It is interesting that S_{0} and S_{1} represent the contributions to f(m, k) from two parts of the summation in (3.9), one for t close to k and the other for t close to μ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 ε ≤ β ≤ \frac{8}{27} + ε, we only need to investigate when log(S_{0}/S_{1}) goes to 0 or to ∞. Note that we have k^{3} = O(m^{2}), and in particular we can assume μ ≤ \frac{1}{3} − ε. Then first considering the exponents in S_{0} and S_{1},

2c\sqrt{k} + (m − k) log (1 + \frac{k}{m − k} ) − k = 2c\sqrt{k} − \frac{1}{2}k^{2}/m + O(k^{3}/m^{2}),

F (μk) + 2c\sqrt{μk} = 2c\sqrt{μk} + \frac{1}{2}μ^{2}k^{2}/m − μk^{2}/m + O(k^{3}/m^{2}),

and so

log (\frac{S_{0}}{S_{1}} ) = 2c(1 − \sqrt{μ})\sqrt{k} − \frac{1}{2}(1 − μ)^{2} \frac{k^{2}}{m} − \frac{3}{4} log k + \frac{1}{2} log(1 − 3μ) + O (1 + \frac{k^{3}}{m^{2}} )
= 2c(1 − \sqrt{μ})\sqrt{k} − \frac{c}{β} (1 − μ)^{2}\sqrt{k} − \frac{3}{4} log k + \frac{1}{2} log(1 − 3μ) + O (1 + \frac{k^{3}}{m^{2}} )
= c\sqrt{k} (2 − 2\sqrt{μ} − \frac{1 − μ}{2\sqrt{μ}}) − \frac{3}{4} log k + \frac{1}{2} log(1 − 3μ) + O (1 + \frac{k^{3}}{m^{2}} )
= \frac{c\sqrt{k}}{2\sqrt{μ}}(1 − \sqrt{μ})(3\sqrt{μ} − 1) − \frac{3}{4} log k + \frac{1}{2} log(1 − 3μ) + O (1 + \frac{k^{3}}{m^{2}} ) . (3.27)

It is easily verified that \sqrt{k}/\sqrt{μ} dominates here. So the behaviour of this expression is determined by the sign and magnitude of (1 − \sqrt{μ})(3\sqrt{μ} − 1). Setting this equal to zero and ignoring the error term gives

μ = \frac{1}{9} + \frac{log k}{c\sqrt{k}} + O(1/m^{3}), β = \frac{8}{27} + \frac{2}{27c^{4/3}} \frac{log m}{m^{\frac{1}{3}}}.

We conclude that with ξ defined as in the statement of the theorem, S_{0} = o(S_{1}) for ξ → −∞ and S_{1} = o(S_{0}) for ξ → ∞. This establishes the formulae for f(m, k) in these two cases. the electronic journal of combinatorics 6 (1999), #R2 24

For ξ = O(1) we already have (3.26), but taking expansions of the functions in the previous paragraph about

μ = \frac{1}{9} + \frac{τ + ξ}{m^{\frac{1}{3}}} ,

where

τ = \frac{2 log m}{27c^{4/3}}

to the k^{3}/m^{2} terms, we find with θ = k/m

β = \frac{8}{27} + \frac{τ + ξ + o(1)}{m^{\frac{1}{3}}},
S_{0} = \frac{1}{4\sqrt{3}θm}e^{m((4β−1)θ^{2}/2−θ^{3}/6+O(θ^{4}))}
∼ \frac{\sqrt{2}}{\sqrt{3}c^{\frac{1}{6}} m^{\frac{7}{96}}} exp (\frac{15}{32}c^{\frac{4}{3}} m^{\frac{1}{3}} ) \frac{1}{9\sqrt{2c}} exp (\frac{513}{64}c^{\frac{4}{3}} ξ − \frac{243}{128}c^{2})
S_{1} = \frac{2^{1/4}}{3^{1/4}θ^{1/4}m^{1/4}} e^{m(−μ(2−μ)θ^{2}/2+2β\sqrt{μ}θ^{2}−μ(3−3μ+μ^{2})θ^{3}/6+O(θ^{4}))}
∼ \frac{\sqrt{2}}{\sqrt{3}c^{\frac{1}{6}} m^{\frac{7}{96}}} exp (\frac{15}{32}c^{\frac{4}{3}} m^{\frac{1}{3}} ) \frac{2^{\frac{1}{4}}}{3^{\frac{1}{4}}} exp (\frac{81}{64}c^{\frac{4}{3}} ξ − \frac{217}{384}c^{2})

as required. (We omit the details of the final calculations, which were performed with the assistance of Maple.)

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 (phenomenological) equation that connects pressure p, volume V and temperature T (Uhlenbeck and Ford [21], pp. 33–34):

p = \frac{γT}{V − β} − \frac{α}{V^{2}} .

Proof of Proposition 2.2 Suppose that π ∈ Π(n, r), and suppose that x and y are positive integers such that

x < y ,

x, y ∉ {h_{1}, …, h_{r}} ,
x − 1, y + 1 ∈ {h_{1}, …, h_{r}}, x − 1 = h_{i}, y + 1 = h_{j} .

Consider now π′ = (h′_{1}, …, h′_{r}) ∈ Π(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 (π′) > P (π). Therefore the π ∈ Π(n, r) which maximizes P (π) cannot have two integers x and y with h_{1} < x < y < h_{r} and x, y ∉ {h_{1}, h_{2}, …, h_{r}}, which proves the claim for Π(n, r). the electronic journal of combinatorics 6 (1999), #R2 25

Suppose that π ∈ Π(n, r) with r < m maximizes P (π) 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

∑_{j=1}^{r} h_{j} ≤ 1 + 3 + 4 + ⋯ + (r + 1) = \binom{r + 2}{2} − 2 < \binom{m + 1}{2} .

If 2 < h_{1}, then π′ ∈ Π(n, r + 1) with π′ = (h′_{0}, h′_{1}, …, h′_{r}), h′_{0} = 1, h′_{1} = h_{1} − 1, h′_{t} = h_{t} for t ≥ 2 yields P (π′) > P (π). If 2 = h_{1}, then there is an integer y, 2 < y < h_{r}, such that y ∉ {h_{1}, …, h_{r}}. We let h_{j} = y + 1. Then π′ = (h′_{0}, …, 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 (π′) > P (π). Thus in all cases we have found a π′ ∈ Π(n, r+1) with P (π′) > P (π), which completes the proof of the proposition. Proof of Proposition 2.3 The statement that almost surely r = m follows, as we have seen, from Lemma 3.1. In view of (2.7), the partition λ in (3.3) corresponds to the hole partition of π. So the rest follows from (1.4), (1.5), (3.1), (3.3) and Lemma 3.3. Proof of Proposition 2.4 As with the previous proposition, according to Lemma 3.1, r = m almost surely. For the rest, note that from (1.4), (1.5), and Lemma 3.2, we can restrict t to O(m^{2/3}) and λ_{1} to at most \sqrt{m}(log m)^{3/2}. The rest of the proof is obtained essentially by examining the proof of Theorem 2.2. Firstly, for any particular t ≥ 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 (3.2). 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 3.4, we obtain the asymptotic uniformity required in (i). Secondly, if t = O(\sqrt{m}(log m)^{3/2}), Lemma 3.3 with s = t suffices, the upper bound on the part size being negligible by (2.3). The statement (ii) in the case k > \sqrt{m} log m follows from the proof of Theorem 2.2, whilst for smaller k it follows from Proposition 2.3. Proof of Proposition 2.5 In the light of the proof of Theorem 2.2, 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 2.4. the electronic journal of combinatorics 6 (1999), #R2 26

Proof of Proposition 2.6 This follows immediately from the fact that in the proof of Theorem 2.1 for the case k = m − s, the d_{i} represent the holes in the partition.

4. Proofs of lemmas

Proof of Lemma 3.1 If r ≥ m + 1, then ∑_{i=1}^{r} h_{i} ≥ 1 + 2 + ⋯ + (m + 1) > n, so this case never arises.

We first deal with the statement about m − k → ∞. 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 ≤ 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 ≥ d_{0}. Then 0 ≤ q_{d_{0}} ≤ q_{d_{0}+1} ≤ · · ·. Determine l and j by

d_{0} = q_{d_{0}} + q_{d_{0}+1} + ⋯ + q_{j} + l, 0 ≤ l < d_{j+1}.

The partition with r + 1 parts derived from {h_{i}} is {h′_{i}} where

h′_{i} = \{ \begin{matrix}i & i ≤ j + 1 \\ h_{j+1} − l & i = j + 2 \\ h_{i−1} & i > j + 2 \end{matrix}

This partition contributes _{\frac{1}{∏_{i=1}^{r+1} h′_{i}!}} to (1.4), whereas the original partition contributed \frac{1}{∏_{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, …, 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}}} ≤ \sqrt{2πd_{0}}e^{−d_{0}}

as d_{0} → ∞ by Stirling’s formula. the electronic journal of combinatorics 6 (1999), #R2 27

In how many ways can we reverse this operation? We pick d_{0}, we pick l ≤ 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}, …, 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 (1.4) is bounded by

\frac{p(d_{0})d_{0}\sqrt{2π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 (2.1), the lemma is proven for d_{0} → ∞.

Suppose now, with m − k ≥ ω(n), that the smallest hole is at d_{0} ≤ ω^{1/3}(n). We first show that there exists a hole above ω^{1/2}(n). If not, then the sum of the largest parts is

≥ ω^{1/2}(n) + (ω^{1/2}(n) + 1) + ⋯ + h_{r}
= \frac{h_{r}(h_{r} + 1)}{2} − \frac{ω^{1/2}(n) (ω^{1/2}(n) − 1)}{2}
≥ \frac{h_{r}(h_{r} + 1)}{2} − \frac{ω(n)}{2}.

Thus n, the sum of all the parts, satisfies \frac{h_{r}(h_{r}+1)}{2} − \frac{ω(n)}{2} ≤ n ≤ \frac{h_{r}(h_{r}+1)}{2}. Now n = m(m + 1)/2 + k implies h_{r} = m + 1 and k ≥ m − ω(n)/2 or m − k ≤ ω(n)/2. Since we are supposing m − k ≥ ω(n) that is not possible. We know, therefore, that there is a hole above ω^{1/2}(n), say at d′. 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 (1.4) of the old and new partitions is d′/d_{0} > ω^{1/6}(n). The number of ways to reverse this operation is at most 2 and so we conclude the partitions with r ≤ m − 1 are negligible if m − k > ω(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} → ∞. 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} → ∞) except that there is an extra factor (m − k + 1)! in the ratio of the contributions, which is negligible because it is bounded. the electronic journal of combinatorics 6 (1999), #R2 28

Proof of Lemma 3.2 The ratio between the contribution of the partition π = {h_{j}} to (1.4) and that of the canonical partition π_{0} = {h′_{j}} is, by (2.7),

\frac{∏_{j} h′_{j}!}{∏_{j} h_{j}!} ≤ \begin{matrix}[m + 1 − (k − t)] & t \\ (m + 1 − (k − t)) & t \end{matrix} ≤ exp (−\frac{t(t − 1)}{2m}) .  (4.1)

The number of partitions with a given value of t is bounded above by p(t). The total contribution to (1.4) for a given t is therefore bounded by

p(t) exp (−\frac{t(t − 1)}{2m}) ≤ exp (κ\sqrt{t} − \frac{t(t − 1)}{2m})

by (2.1). Take c > (2κ)^{2/3} to prove the statement about t < cm^{2/3}.

Recall that in a partition π = {h_{j}} ∈ Π(n, m) the holes are at d_{0}, d_{1}, …, d_{v}. Move the hole at d_{0} to a hole at d_{0} − s, where s = m − d_{1} + 2. Also, noting that there are exactly s parts above the hole at d_{1}, move each of these parts down by 1. Call the resulting partition π′ = {h′_{j}}. The ratio between the contributions of π and π′ to (1.4) is

\frac{P (π)}{Π(π′)} = \frac{∏_{j} h′_{j}!}{∏_{j} h_{j}!} = \frac{1/(d_{0} − s)!}{1/d_{0}!} ∏_{t} \frac{(t − 1)!}{t!},

where t runs over all part sizes above the hole at d_{1}. Therefore,

\frac{∏_{j} h′_{j}!}{∏_{j} h_{j}!} = \frac{d_{0}!}{(d_{0} − s)!} ∏_{t} \frac{1}{t} ≤ \frac{d_{0}!}{(d_{0} − s)!} \frac{d_{0}!}{(d_{0} + s)!} ≤ e^{−s^{2}/d_{0}}.

The number of ways of reversing this procedure is bounded above by k. Hence, the proportion of (1.4) which is contributed from all s ≥ \sqrt{m}(log m)^{3/2} is at most

∑_{s≥\sqrt{m}(log m)^{3/2}} ke^{−s^{2}/d_{0}} ≤ ∑_{s≥\sqrt{m}(log m)^{3/2}} ke^{−s^{2}/m} → 0.

This permits the bound on λ_{1} in the statement of the lemma.

If k < 2cm^{2/3} then the fact that t ≤ k implies the statement about t < cm^{2}/k^{2} (for c sufficiently large). Otherwise, we have by t < cm^{2/3} that t < k/2. In this case, since the second-bottom hole in {h_{j}} is at least m − t, the bound in (4.1 ) can be improved to

\begin{matrix}[m + 1 − (k − t)] & t \\ (m + 1 − (k − t)) & t \end{matrix} ≤ exp (−\frac{t(t − 1)}{2m}) (\frac{m + 1 − (k − t)}{m + 1 − t})^{t}
≤ exp (−\frac{t(t − 1)}{2m} − \frac{t(k − 2t)}{m})
= exp (−\frac{t(2k − 3t − 1)}{2m})
< exp (−\frac{t(\frac{1}{2}k − 1)}{2m}) .

the electronic journal of combinatorics 6 (1999), #R2 29

Thus, the contribution to (1.4) is bounded by O(exp (−\frac{tk}{4m}) p(t)). Using (2.1) as before shows that this is negligible if tk/m ≥ c\sqrt{t} (c sufficiently large), or t ≥ cm^{2}/k^{2}, as required. Proof of Lemma 3.3 We prove an upper bound is by induction on s for m fixed; the inductive hypothesis we use is that for some w(m, D) → 0 as m → ∞ with D fixed,

g(m, s) ≤ p(s)(1 + O(w(m, D)))  (4.2)

where O() is independent of s and m. (Or we can replace O(w(m, D)) by o(1) independent of s.)

We can start the induction at any s < m^{1/2−ϵ}, since here

\frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} = exp(O(λ_{i}^{2}/m))

and so

∏_{i=0}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} = exp (O (∑ λ_{i}^{2}/m)) = exp(O(s^{2}/m)) = e^{o(1)}.

Now consider any s < m^{2/3}/D log m. Case 1: λ_{0} < D(log m)\sqrt{s}. Then

\frac{m}{m + 1 − λ_{i}} ≤ exp(O(D(log m)\sqrt{s})/m)

so

∏_{i=0}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} ≤ ∏_{i} exp(O(λ_{i}D(log m)\sqrt{s})/m
≤ exp(O(D(log m)s^{3/2}/m))
= e^{o(1)}.

Thus the partitions in Case 1 contribute at most p(s)(1 + w(m, D)/2) to g(m, s) for w(m, D) going to 0 sufficiently slowly. Case 2: s ≥ λ_{0} ≥ D(log m)\sqrt{s}. Here

\frac{m^{λ_{0}}}{[m + 1]_{λ_{0}}} ≤ exp(λ_{0}^{2}/m),

the electronic journal of combinatorics 6 (1999), #R2 30

and we have

∑_{{λ_{1}≥···≥λv \atop λ_{1}+···+λv=s−λ_{0}}} ∏_{i=1}^{v} \frac{m^{d_{i}}}{[m + 1 + i]_{λ_{i}}} ≤ g(m, s − λ_{0})

which is by induction at most

p(s − λ_{0})(1 + O(w(m, D))) ≤ p(s)(1 + O(w(m, D)))e^{−Cλ_{0}/\sqrt{s}}

for some constant C > 0. The product of these two factors is

O(p(s) exp(λ_{0}^{2}/m − Cλ_{0}/\sqrt{t})) = O(p(s) exp(−CD(log m)/2))

for m sufficiently large. Summing over all λ_{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 (4.2) follows by induction. Note that by (2.3), for D sufficiently large, almost all partitions fall into Case 1 and hence for almost all of them,

∏_{i=0}^{v} \frac{m^{λ_{i}}}{[m + 1 + i]_{λ_{i}}} ≤ e^{o(1)}.  (4.3)

To prove the corresponding lower bound

g(m, s) ≥ 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 (2.3) 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 (4.3). Proof of Lemma 3.4 (i) It is enough to show

E (∏ \frac{1}{[m + 1 + i]_{λ_{i}}} 1_{\{λ_{1}≤M_{s}\}}) /P (λ_{1} ≤ M_{s}) ∼ m^{−s},

where λ_{1} ≥ ⋯ ≥ λ_{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 P (λ_{1} ≤ M_{s}) → 1, by (2.3), hence it suffices that

E (∏ \frac{1}{[m + 1 + i]_{λ_{i}}} 1_{\{λ_{1}≤M_{s}\}}) ∼ m^{−s}.  (4.4)

Given a partition λ of s, we define ρ(λ) as

ρ(λ) = ∑_{j} [λ_{j}^{2} − (2j − 1)λ_{j}] .

The function ρ(λ) arises in the analysis of card shuffling; see [9]. Using Stirling’s formula we find that

∏ \frac{1}{[m + 1 + i]_{λ_{i}}} = m^{−s}(1 + O(s/m)) exp (∑_{i} \frac{λ_{i}^{2} − 2iλ_{i}}{2(m + 1)}

+ ∑_{i} \frac{i^{2}λ_{i} − iλ_{i}^{2}}{2(m + 1)^{2}} + ∑_{i} \frac{λ_{i}^{3}}{6(m + 1)^{2}}

+ O (∑_{i} \frac{λ_{i}^{4} + iλ_{i}^{3} + i^{2}λ_{i}^{2} + i^{3}λ_{i}}{(m + 1)^{3}} )\}

Now iλ_{i} ≤ s and ∑ λ_{i}^{a} ≤ (∑ λ_{i})^{a} ≤ s^{a} so ∑ λ_{i}^{4} = O(s^{4}), ∑ iλ_{i}^{3} = O(s^{3}), ∑ i^{2}λ_{i}^{2} = O(s^{3}), ∑ i^{3}λ_{i} = O(s^{4}). Also ∑ i^{2}λ_{i} = O(s^{2}), ∑ iλ_{i}^{2} = O(s^{2}), ∑ λ_{i}^{3} = O(s ∑ λ_{i}^{2}) = o(m ∑ λ_{i}^{2}) since s = O(m^{2/3}). Hence

∏_{i=1}^{v} \frac{1}{[m + 1 + i]_{λ_{i}}} = m^{−s} exp (∑_{i} \frac{λ_{i}^{2} − 2iλ_{i}}{2(m + 1)} + O (\frac{∑ λ_{i}^{3}}{m^{2}} ) + o(1))  (4.5)
= m^{−s} exp (\frac{ρ(λ)}{2(m + 1)} − \frac{∑ λ_{i}}{2(m + 1)} + O (\frac{∑ λ_{i}^{3}}{m^{2}} ) + o(1))
= m^{−s} exp (\frac{ρ(λ)}{2(m + 1)} + O (\frac{∑ λ_{i}^{3}}{m^{2}} ) + o(1)) ,

where the o(1) is independent of λ. We know from [18] that that ρ(λ)/s^{3/2} = O_{p}(s^{−1/4}) (a weaker result from [9], ρ(λ)/s^{2} = o_{p}(1), is not sufficient for our purposes here); therefore \frac{ρ(λ)}{2(m+1)} ⇒ δ_{0}, where δ_{x} denotes the point mass at x. We know from 2.3 that λ_{1} < \sqrt{s} log s almost surely, so ^{\frac{∑ λ_{i}^{3}}{m^{2}}} ⇒ δ_{0}. By a standard result ([5], page 341) we can add these three functions and revert to (4.5) to get

∑_{i} \frac{λ_{i}^{2} − 2iλ_{i}}{2(m + 1)} + O (\frac{∑ λ_{i}^{3}}{m^{2}} ) + o(1) ⇒ δ_{0}

and so

Z_{s} ⇒ δ_{1}  (4.6)

where

Z_{s} = m^{s} ∏_{i=1}^{s} \frac{1}{[m + 1 + i]_{λ_{i}}} 1_{\{λ_{1}≤M_{s}\}}
= exp (∑_{i} \frac{λ_{i}^{2} − 2iλ_{i}}{2(m + 1)} + O (\frac{∑ λ_{i}^{3}}{m^{2}} ) + o(1)) 1_{\{λ_{1}≤M_{s}\}}

by (4.5). the electronic journal of combinatorics 6 (1999), #R2 32

It is well known from probability theory that if variables Z_{n} converge weakly, so that Z_{n} ⇒ Z, and EZ_{n}^{1+ϵ} = O(1) for some ϵ > 0, then EZ_{n} → EZ; see [5], page 348. Therefore, the following lemma establishes (4.4) by taking any β > 1, and so completes the proof of Lemma 3.4 (i).

Lemma 4.1. Let X_{j} be the number of parts of size j in a random partition of s. If s = O(m^{2/3}), β > 0 and M_{s} = o(s), then

E {exp (βm^{−1} ∑_{j=1}^{M_{s}} j^{2}X_{j})} = O(1).

Proof We use a technique found in [18]. In view of the condition on s, it is enough to show

E {exp (βs^{−3/2} ∑_{j=1}^{M_{s}} j^{2}X_{j})} = O(1).

Let z and x = (x_{1}, x_{2}, …) be such that sup{|z^{j}x_{j}| : j ≥ 1} < 1, and ∑_{j≥1} |z^{j}x_{j}| < ∞. Then

∑_{s≥0} z^{s}p(s)E (∏_{j≥1} x_{j}^{X_{j}} ) = ∏_{j≥1} \frac{1}{1 − z^{j}x_{j}} .

Therefore (using Cauchy’s formula for the circular contour {z = re^{iθ} : θ ∈ (−π, π]}),

E (∏_{j≥1} x_{j}^{X_{j}} ) = \frac{1}{2πr^{s}p(s)} ∫_{−π}^{π} e^{−inθ} ∏_{j≥1} \frac{1}{1 − r^{j}e^{ijθ}x_{j}} dθ,  (4.7)

where r is such that sup{r^{j}|x_{j}| : j ≥ 1} < 1, and ∑_{j≥1} r^{j}|x_{j}| < ∞. Let us set

x_{j} = \{ \begin{matrix}e^{βs^{−3/2}j^{2}} & ifj ≤ M_{s}, \\ 1 & ifj > M_{s}. \end{matrix}

As for r, we choose r = e^{−cs^{−1/2}}, c = π/\sqrt{6}. For j ≤ M_{s},

−cs^{−1/2}j + βs^{−3/2}j^{2} ≤ −cs^{−1/2}j/2,  (4.8)

if s is sufficiently large, since M_{s} = o(s). So sup{r^{j}x_{j} : j ≥ 1} < 1, and ∑_{j≥1} r^{j}x_{j} < ∞. Using an inequality

|\frac{1}{1 − z} | ≤ \frac{1}{1 − |z|} exp [ℜe z − |z|] , (z ∈ ℂ, |z| < 1),

the electronic journal of combinatorics 6 (1999), #R2 33 and (4.8), we bound the integrand by

∏_{j=1}^{M_{s}} \frac{1}{1 − e^{−cjs^{−1/2}+βs^{−3/2}j^{2}}} · ∏_{j>M_{s}} \frac{1}{1 − e^{−cjs^{−1/2}}} · exp [∑_{j≥1} e^{−cjs^{−1/2}/2}(cos jθ − 1)] .

Using the formula (2.5), we estimate the product of the two products as follows:

∏_{j=1}^{∞} \frac{1}{1 − e^{−cjs^{−1/2}}} · ∏_{j=1}^{M_{s}} \frac{1 − e^{−cjs^{−1/2}}}{1 − e^{−cjs^{−1/2}+βs^{−3/2}j^{2}}}

= exp [\frac{π^{2}}{6z} + \frac{1}{2} log \frac{z}{2π} + O(z)]|_{z=cs^{−1/2}} exp (2 ∑_{j=1}^{M_{s}} \frac{e^{βs^{−3/2}j^{2}} − 1}{e^{cjs^{−1/2}} − 1}) .  (4.9)

The exponential bound for the second product is based on the fact that

sup_{1≤j≤M_{s}} \frac{e^{βs^{−3/2}j^{2}} − 1}{e^{cjs^{−1/2}} − 1} → 0,

as s → ∞. Indeed, for j ≤ s^{3/4} the ratio is of order

O (\frac{s^{−3/2}j^{2}}{(js^{−1/2})^{2}} ) = O(s^{−1/2});

for s^{3/4} ≤ j ≤ M_{s} the ratio is of order

O (exp {βs^{−3/2}j^{2} − cs^{−1/2}j}) = O (exp {−cjs^{−1/2}(1 − βc^{−1}M_{s}/s)})
= O (exp {−cjs^{−1/2}/2})
= O (exp {−cs^{1/4}/2}) .

Furthermore, the sum of the ratios is of order

∑_{j=1}^{s^{3/4}} \frac{s^{−3/2}j^{2}}{e^{cjs^{−1/2}} − 1} + ∑_{j=s^{3/4}}^{M_{s}} e^{−cjs^{−1/2}/2} = O (∫_{0}^{∞} \frac{x^{2}}{e^{cx} − 1} dx + \frac{e^{−cs^{1/4}/2}}{1 − e^{−cs^{−1/2}/2}} )
= O(1).  (4.10)

Using (4.9), (4.10), we bound the product of two products by

O (\frac{e^{cs^{1/2}}}{s^{1/4}} ) .  (4.11)

The θ-dependent factor is bounded above by

exp (−\frac{aθ^{2}}{s^{−3/2} + s^{−1/2}θ^{2}} ) ,

the electronic journal of combinatorics 6 (1999), #R2 34

a > 0 being an absolute constant; see (2.9) of [18]. And the integral of this function over [−π, π] is O(s^{−3/4}). Combining this estimate with (4.11), and taking into consideration the outside factor

\frac{1}{2πr^{s}p(s)} = O (\frac{1}{e^{−cs^{1/2}}p(s)})

in (4.7), we conclude that

E exp (βs^{−3/2} ∑_{j=1}^{M_{s}} j^{2}X_{j}) = O (\frac{e^{cs^{1/2}}}{sp(s)r^{s}} )
= O (\frac{e^{2cs^{1/2}}}{sp(s)} )
= O(1),

since

p(s) = O (\frac{e^{2cs^{1/2}}}{s} ) .

Proof of Lemma 3.4 (ii) This follows immediately from (4.6). the electronic journal of combinatorics 6 (1999), #R2 35

References

[1] G.E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, 1976.

[2] T.M. Apostol, Introduction to Analytic Number Theory, Springer, Berlin, 1976.

[3] E.A. Bender, Asymptotic Methods in Enumeration, SIAM Review 16 (1974), 485–515.

[4] E. A. Bender, A. M. Odlyzko, and L. B. Richmond, The asymptotic number of irreducible partitions, European J. Comb. 6 (1985), 1–6.

[5] P. Billingsley, Probability and Measure, 2nd ed., John Wiley & Sons, New York, 1986.

[6] L. Carlitz, Set partitions, Fibonacci Quart. 14 (1976), 327–342.

[7] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[8] J. M. DeLaurentis and B. G. Pittel, Counting subsets of the random partition and the “Brownian Bridge” process, Stochastic Processes Appl. 15 (1983), 115–167.

[9] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Wahr. Verw. Gebiete (1981), 159–179.

[10] P. Erdős and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. (1941), 335–345.

[11] W. M. Y. Goh and E. Schmutz, Random set partitions, SIAM J. Discrete Math. 7 (1994), 419–436.

[12] D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms, 2nd ed., Birkhäuser Boston, 1982.

[13] A. Guttman and M. Hirschhorn, Comment on the number of spiral self-avoiding walks, J. Phys. A. Math. Gen. 17 (1984), 3613–3614.

[14] A. Knopfmacher and J. N. Ridley, Reciprocal sums over partitions and compositions, SIAM J. Discrete Math. 6 (1993), 388-399.

[15] A. Knopfmacher and K. Warlimont, Distinct degree factorizations for polynomials over a finite field, Trans. Amer. Math. Soc. 347 (1995), 2235–2243. the electronic journal of combinatorics 6 (1999), #R2 36

[16] A. M. Odlyzko, Explicit Tauberian estimates for functions with positive coefficients, J. Comput. Appl. Math. 41 (1992), 187–197.

[17] J. Pitman, Some probabilistic aspects of set partitions. American Mathematical Monthly 104 (1997), 201–209.

[18] B. Pittel, On a likely shape of the random Ferrers diagram, Advances in Applied Mathematics 18 (1997), 432–488.

[19] B. Pittel, Random set partitions: asymptotics of subset counts, J. Combinatorial Theory, Series A 79 (1997), 326–359.

[20] G. Szekeres, Asymptotic distributions of the number and size of parts in unequal partitions, Bull. Austral. Math. Soc. 36 (1987), 89–97.

[21] G.E. Uhlenbeck and G. W. Ford with E. W. Montroll, Lectures in Statistical Mechanics, Amer. Math. Soc., 1963, reprinted 1986.

[22] H. S. Wilf, generatingfunctionology, Academic Press, 1990.