WHERE THE TYPICAL SET PARTITIONS MEET AND JOIN.

Boris Pittel

Received: May 16, 1999; Accepted: January 15, 2000

Abstract. The lattice of the set partitions of [n] ordered by refinement is studied. Suppose r partitions p_{1}, …, p_{r} are chosen independently and uniformly at random. The probability that the coarsest refinement of all p_{i} ’s is the finest partition {{1}, …, {n}} is shown to approach 0 for r = 2, and 1 for r ≥ 3. The probability that the finest coarsening of all p_{i} ’s is the one-block partition is shown to approach 1 for every r ≥ 2.

Introduction. Let Π_{n} be the set of all set partitions of [n], ordered by refinement. That is, for two partitions p and p′, p ⪯ p′ if each block of p′ is a union of blocks of p. It is well known, Stanley [6], that Π_{n} is a lattice; it means that every pair of partitions p, p′ has the greatest lower bound inf{p, p′} (p inf p′ or p meet p′) and the least upper bound sup{p, p′} (p sup p′ or p join p′). Namely, inf{p, p′} is the partition whose blocks are the pairwise intersections of blocks of p and p′, and it is the “coarsest” (simultaneous) refinement of p and p′. sup{p, p′} is a partition whose every block is both a union of blocks of p and a union of blocks of p′, with no proper subset of the block having that property; so it is the finest “coarsening” of p and p′. Assigning to each p the same probability, 1/|Π_{n}|, we transform Π_{n} into the probability space with uniform measure. There is a sizeable literature on the properties of the uniformly distributed partition, see Pittel [5] and the references therein. Closer to the subject of this paper, Canfield and Harper [1] and Canfield [2] used the probabilistic tools to find the surprisingly sharp bounds for the length of the largest antichain in Π_{n}. In [5] we proved that the total number of refinements of the random partition is asymptotically lognormal. In the present paper we study the properties of inf_{1≤i≤r} p_{i}, sup_{1≤i≤r} p_{i}, under the assumption that the uniform partitions p_{1}, …, p_{r} are independent. (Formally, we study

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 05A18, 05A19, 05C30, 05C80, 06A07, 60C05, 60Fxx.

Key words and phrases. Set partitions lattice, meet, join operations, enumeration, random, limiting probabilities..

Research supported in part by the NSF grant # DMS-9803410, and also by the Microsoft Research.

the distributions of two random (partition-valued) variables defined on the product of r copies of the probability space Π_{n}.) Specifically, we want to know how likely it is that inf_{i} p_{i} is the minimum partition p_{min} = {{1}, …, {n}}, and that sup_{i} p_{i} is the maximum partition p_{max} = {[n]}. We also discuss (briefly) the behavior of inf(sup)_{i}p_{f_{i}} where p_{f} is a partition of [n] into the level sets for a uniformly random mapping f : [n] → [n].

I stumbled upon these problems trying to answer a question which was posed by Stephanie Rieser (Steve Milne’s doctoral student at the Ohio State University) during the Herb Wilf’s Festschrift (University of Pennsylvania, Summer 1996). Stephanie asked for a formula of the number of partitions p′ which intersect minimally (“are disjoint from”) a given partition. These are p′ with the property inf{p, p′} = p_{min} ! Few weeks later I sent Stephanie an answer that expressed the number in question as a certain coefficient of the explicit (multivariate) generating function. I understood then vaguely that this solution might be relevant for (asymptotic) enumeration of minimally intersecting partitions, (pairs and tuples). However, I hadn’t got back to these issues until earlier this year.

In Section 1 we enumerate the minimally intersecting partitions, with Corollary 1 containing the answer to Rieser’s question, and end up (Theorem 1, Theorem 2) with a formula for the total number of r-tuples of such partitions. In Section 2 we use the enumerational results to estimate the probability that r independent partitions intersect minimally. It turns out (Theorem 3) that this probability is fast approaching zero as n → ∞ if r = 2, and its limit is 1 for every other r > 2. We look closer at inf{p_{1}, p_{2}} and prove (Theorem 4) that this refinement of p_{1} and p_{2} is unlikely to have blocks of size three or more, and that the number of two-element blocks is asymptotically Poisson, with a parameter close to 0.5 log^{2} n. We conclude by proving (Theorem 5) that sup_{i} p_{i} = p_{max} with probability tending to 1, for every r ≥ 2.

1. Enumeration of minimally intersecting partitions.

Lemma 1. Let a partition p of [n] be given, and let i_{1}, … i_{k} denote the sizes of blocks in p listed in any order. For a given ℓ > 1, define N(p, ℓ) as the total number of partitions p′ with ℓ blocks exactly that intersect p minimally. Then

(1.1)  N(p, ℓ) = \frac{i!}{ℓ!} · [x^{i}] (∏_{α=1}^{k}(1 + x_{α}) − 1)^{ℓ} .

Here i! = ∏_{α=1}^{k} i_{α}!, and the second factor is the coefficient of ∏_{α=1}^{k} x_{α}^{i_{α}} in the power

expansion for the indicated function.

Corollary 1. N(p), the overall number of the partitions p′ that intersect p minimally, is given by

(1.2)  N(p) = i![x^{i}] exp (∏_{α=1}^{k}(1 + x_{α}) − 1) .

Note. As a partial check, for p = ∪_{i}{i}, N(p) is the Bell number B(n). And indeed

[x_{1} ⋯ x_{n}] exp (∏_{α=1}^{n}(1 + x_{α}) − 1) =e^{−1}[x_{1} ⋯ x_{n}] ∑_{j=0}^{∞} \frac{1}{j!} ∏_{α=1}^{n}(1 + x_{α})^{j}

=e^{−1}[x_{1} ⋯ x_{n}] ∑_{j=0}^{∞} \frac{1}{j!} ∏_{α=1}^{n}(1 + jx_{α})

=e^{−1} ∑_{j=0}^{∞} \frac{j^{n}}{j!} ,

which is the Dobinski formula for B(n), Comtet [1].

Proof of Lemma 1. Given ℓ ≥ 1, j_{1}, … j_{ℓ} ≥ 1, such that

(1.3)  ∑_{β=1}^{ℓ} j_{β} = n,

denote by N(p, j) the total number of partitions p′ with ℓ blocks of sizes j_{1}, …, j_{ℓ} which intersect p minimally. Every p′ is characterized, albeit incompletely, by the matrix [ε_{αβ}], 1 ≤ α ≤ k, 1 ≤ β ≤ ℓ. Here ε_{αβ} ∈ {0, 1} is the cardinality of intersection of the α-th block in p and the β -th block in p′, cardinality of the latter being j_{β}. That is

∑_{α} ε_{αβ} = j_{β}, 1 ≤ β ≤ ℓ,

∑_{β} ε_{αβ} = i_{α}, 1 ≤ α ≤ k,

and the total number of solutions of this system is

(1.4)  [x^{i}y^{j}] ∏_{α,β}(1 + x_{α}y_{β}).

Now, there are i_{α}! ways to decide how to assign the elements from the α-th block of p to those i_{α} nonzero ε_{αβ} ’s, and the overall number of partitions p′ appears to be the expression (1.4) times i!. However each such p′ has been counted more than once. If m_{j} is the multiplicity of j in the multiset {j_{1}, …, j_{ℓ}}, then the compensating factor is

(\frac{ℓ!}{m_{1}! ⋯ m_{n}!})^{−1} · (m_{1}! ⋯ m_{n}!)^{−1} = \frac{1}{ℓ!}.

Hence

(1.5)  N(p, j) = \frac{i!}{ℓ!} · [x^{i}y^{j}] ∏_{\begin{matrix}1≤α≤k \\ 1≤β≤ℓ \end{matrix}}(1 + x_{α}y_{β}).

Our j satisfies (1.3). It is easy to see that the second factor on the right in (1.5) is zero if j does not meet (1.3). Consequently N(p, ℓ), the total number of partitions p′ with ℓ blocks that intersect p minimally is given by

N(p, ℓ) = ∑_{\begin{matrix}j_{1}+···+j_{ℓ}=n \\ j_{1},...,j_{ℓ}>0 \end{matrix}} N(p, j)

(1.6)  =\frac{i!}{ℓ!} · [x^{i}] ( ∑_{j_{1},...,j_{ℓ}>0}[y^{j}] ∏_{α,β}(1 + x_{α}y_{β})) .

It is crucially important that we are able to drop the condition ∑_{β} j_{β} = n in the last sum. Using inclusion-exclusion principle, we substitute

∑_{A⊆[ℓ]}(−1)^{|A|}S(A, x),

for the sum. Here

S(A, x) = ∑_{\begin{matrix}j_{1},...,j_{ℓ}≥0 \\ j_{β}=0 if β∈A \end{matrix}}[y^{j}] ∏_{α,β}(1 + x_{α}y_{β})

= ∑_{j_{β}≥0, β∈A^{c}}[ ∏_{β∈A^{c}} y_{β}^{j_{β}}] ∏_{α≤k, β∈A^{c}}(1 + x_{α}y_{β})
= ∏_{α≤k}(1 + x_{α})^{|A^{c}|}.

Therefore the sum in (1.6) equals

∑_{A⊆[ℓ]}(−1)^{|A|} ( ∏_{α≤k}(1 + x_{α}))^{ℓ−|A|} = ∑_{m≤ℓ}(−1)^{m}\binom{ℓ}{m} ( ∏_{α≤k}(1 + x_{α}))^{ℓ−m}

= ( ∏_{α≤k}(1 + x_{α}) − 1)^{ℓ} .

Thus (1.1) is proved. □

The corollary follows by summing over ℓ > 0 and noting that the expression on the right in (1.1) is zero for ℓ = 0.

Lemma 2. Let N_{2}(k) denote the number of ordered pairs (p, p′) of minimally intersecting partitions such that p consists of k blocks exactly. Then

(1.7)  N_{2}(k) = e^{−1} \frac{n!}{k!} · [x^{n}] ∑_{ℓ≥0} \frac{1}{ℓ!}[(1 + x)^{ℓ} − 1]^{k}.

Proof of Lemma 2. By Corollary 1,

N_{2}(k) =\frac{1}{k!} ∑_{\begin{matrix}i_{1}+···+i_{k}=n \\ i_{1},...,i_{k}>0 \end{matrix}} \frac{n!}{i!}i! · [x^{i}] exp (∏_{α=1}^{k}(1 + x_{α}) − 1)

=e^{−1} \frac{n!}{k!} ∑_{\begin{matrix}i_{1}+···+i_{k}=n \\ i_{1},...,i_{k}>0 \end{matrix}}[x^{i}] exp (∏_{α=1}^{k}(1 + x_{α})) .

Predictably, we want to use the inclusion-exclusion principle again. In preparation, for a given A ⊆ [k],

S(x, A) := ∑_{\begin{matrix}i_{1}+···+i_{k}=n \\ i_{1},...,i_{k}≥0 \\ i_{α}=0 if a∈A \end{matrix}} [ ∏_{α∈A^{c}} x_{α}^{i_{α}}] exp (∏_{α=1}^{k}(1 + x_{α}))

=[x^{n}] exp ((1 + x)^{|A^{c}|})
=[x^{n}] ∑_{ℓ=0}^{∞} \frac{1}{ℓ!}(1 + x)^{|A^{c}|ℓ}.

Therefore

N_{2}(k) =e^{−1} \frac{n!}{k!}[x^{n}] ∑_{A⊆[k]}(−1)^{|A|}S(x, A)

=e^{−1} \frac{n!}{k!} · [x^{n}] ∑_{ℓ=0}^{∞} \frac{1}{ℓ!}(1 + x)^{|A^{c}|ℓ}

=e^{−1} \frac{n!}{k!} · [x^{n}] ∑_{ℓ=0}^{∞} \frac{1}{ℓ!} ∑_{m=0}^{k}(−1)^{m}\binom{k}{m}(1 + x)^{(k−m)ℓ}

=e^{−1} \frac{n!}{k!} · [x^{n}] ∑_{ℓ=0}^{∞} \frac{1}{ℓ!}[(1 + x)^{ℓ} − 1]^{k}.

□ Theorem 1. N_{2n}, the overall number of ordered pairs (p, p′) of minimally intersecting partitions, is given by

(1.8)  N_{2n} = e^{−2} ∑_{k,ℓ≥0} \frac{(kℓ)_{n}}{k!ℓ!} ,

where (m)_{n} = m(m − 1) ⋯ (m − n + 1).

Proof of Theorem 1. By Lemma 2,

N_{2n} = ∑_{k>0} N_{2}(k)

=e^{−1}n! ∑_{ℓ≥0} \frac{1}{ℓ!} · [x^{n}] ∑_{k≥0} \frac{1}{k!}[(1 + x)^{ℓ} − 1]^{k}

=e^{−1}n! ∑_{ℓ≥0} \frac{1}{ℓ!} · [x^{n}] exp ((1 + x)^{ℓ} − 1)

=e^{−2}n! ∑_{ℓ≥0} \frac{1}{ℓ!} ∑_{k≥0} \frac{1}{k!}\binom{kℓ}{n}

=e^{−2} ∑_{k,ℓ≥0} \frac{(kℓ)_{n}}{k!ℓ!} .

□ Note. We used k, ℓ both as the numbers of blocks for a generic pair (p, p′) and as the summation indices in (1.8), and in (1.7). Needless to say, (1.8) should not be read as implying that the total number of minimally intersecting pairs (p, p′) with k and ℓ blocks respectively is e^{−2}(kℓ)_{n}/(k!ℓ!). For one thing, the expression is irrational! However, the magnitude of that number is strongly correlated to the (k, ℓ)-th term, at least for the dominant values of k and ℓ.

In the light of this Theorem, the following statement must be true, and it is!

Theorem 2. Given r ≥ 2, let N_{rn} denote the total number of ordered r-tuples of partitions (p_{1}, …, p_{r}) with a property that inf_{i} p_{i} = p_{min} . Then

(1.9)  N_{rn} = e^{−r} ∑_{k_{1},...k_{r}≥0} \frac{(k_{1} ⋯ k_{r})_{n}}{k_{1}! ⋯ k_{r}!} .

Proof of Theorem 2. Let the numbers k_{1}, …, k_{r} > 0 be given. For every s ≤ r, let i_{s} = (i_{s1}, …, i_{sk_{s}}) be a k_{s} -tuple of positive integers that add up to n. Fix a partition p_{1} with k_{1} blocks of given cardinalities, listed in i_{1} . Introduce N(p_{1}, i_{2}, …, i_{r}), the total number of (r − 1)-tuples (p_{2}, …, p_{r−1}) of partitions, such that p_{s} has k_{s} blocks of cardinalities i_{s}, (2 ≤ s ≤ r), with the property inf_{1≤i≤r} p_{i} = p_{min} . Let N(p_{1}, k_{2} …, k_{r}) be the analogous number when only the number of blocks in each p_{s}, (2 ≤ s ≤ r), is given. Analogously to (1.5), we obtain

(1.10)  N(p_{1}, i_{2}, …, i_{r}) = \frac{i_{1}!}{∏_{s=2}^{r} k_{r}!} · [x^{i_{1}}y^{i_{2}} ⋯ z^{i_{r}}] ∏_{\begin{matrix}1≤β_{s}≤k_{s} \\ 1≤s≤r \end{matrix}} (1 + x_{β_{1}}y_{β_{2}} ⋯ z_{β_{r}}) .

Adding up N(p_{1}, i_{2}, …, i_{r}) for given k_{2}, …, k_{r}, and acting like in (1.8), we have:

(1.11)  \begin{matrix}N(p_{1}, k_{2}, …, k_{r}) = & i_{1}! · [x^{i_{1}}] ∑_{\begin{matrix}1≤β_{s}≤k_{s} \\ 2≤s≤r \end{matrix}} u^{∏_{s=2}^{r}(k_{s}−β_{s})} ∏_{t=2}^{r} \frac{(−1)^{β_{t}}}{k_{t}!} \binom{k_{t}}{β_{t}}; \\ u := & ∏_{1≤α≤k_{1}}(1 + x_{α}). \end{matrix}

Then we use

N_{rn} = ∑_{k_{1}} \frac{1}{k_{1}!} ∑_{\begin{matrix}i_{11}+···+i_{1b_{1}} =n \\ i_{11},...i_{k_{1}1}>0 \end{matrix}} \frac{n!}{i_{1}!} ∑_{k_{2},...,k_{r}} N(p_{1}, k_{2}, …, k_{r}),

and, applying the inclusion-exclusion to the condition i_{1} > 0, we arrive at

N_{rn} =n! · [x^{n}] ∑_{k_{1},...,k_{r}≥0} ∏_{s=1}^{r} \frac{1}{k_{s}!} ∑_{β_{1}≤k_{1},...,β_{r}≤k_{r}} u^{∏_{s=1}^{r}(k_{s}−β_{s})} ∏_{t=1}^{r} \frac{(−1)^{β_{t}}}{k_{t}!} \binom{k_{t}}{β_{t}};
u :=1 + x.

An easy induction on r (based on the devices used above for r = 2) shows that the last sum equals

e^{−r} ∑_{k_{1},...,k_{r}≥0} \frac{u^{k_{1}···k_{r}}}{k_{1}! ⋯ k_{r}!},

and it remains to notice that

[x^{n}](1 + x)^{k_{1}···k_{r}} = \binom{k_{1} ⋯ k_{r}}{n}.

□ Note. Herb Wilf (private communication) indicated that (1.9) is equivalent to

(1.12)  N_{rn} = ∑_{j=1}^{n} B^{r}(j)S(n, j);

here the S(n, j) are signed Stirling numbers of the first kind. Does the reader see why?

2. Probabilistic asymptotics. Suppose that the partitions p_{1}, …, p_{r} are chosen from Π_{n} uniformly at random (uar), independently of each other. The formulas (1.8), (1.9) are ideally suited for an asymptotic study of

P_{rn} =^{def} Pr( inf_{1≤i≤r} p_{i} = p_{min}).

According to Theorems 1 and 2,

P_{rn} = \frac{N_{rn}}{B^{r}(n)},

where B(n) is the Bell’s n-th number, that is B(n) = |Π_{n}|. By the Moser-Wyman formula [4],

(2.1)  B(n) = \frac{1 + o(1)}{ρ^{1/2}} · exp[n(ρ − 1 + 1/ρ) − 1], n → ∞,

where ρ is defined as the root of ρe^{ρ} = n, and asymptotically

(2.2)  ρ = log n − (1 + o(1)) log log n.

Note. It can be shown that actually o(1) = O(1/ρ) in this formula, [5].

Theorem 3.

(2.3)  P_{rn} = \{ \begin{matrix}(1 + o(1))e^{−ρ^{2}/2}, & if r = 2, \\ 1 − O(log^{−1} n), & if r ≥ 3. \end{matrix}

So lim_{n→∞} P_{rn} is 0 for r = 2 and 1 for every r > 2.

Proof of Theorem 3. The computations are more or less standard, with “less” due to the sum in (1.9) being multiple. So we will outline the argument, paying attention to the key points. A typical partition has about n/ log n blocks. This is why we should expect that the dominant contribution to the series in (1.9) comes from the summands with k_{1}, …, k_{r} all asymptotic to n/ log n. Indeed N_{rn}(k), the generic summand in (1.9), can be transformed—via the Stirling formula for factorials—into

(2.4)

N_{rn}(k) =(1 + O(∑_{s=1}^{r} 1/k_{s} + 1/(k − n)))N_{rn}(k);

N_{rn}(k) :=e^{−r} ∏_{s=1}^{r}(2πk_{s})^{−1/2} · exp(H(k));

H(k) := − n + ∑_{s=1}^{r}(k_{s} − k_{s} log k_{s}) + k log k − (k − n) log(k − n);

k := ∏_{s=1}^{r} k_{s}.

The estimate is uniform for all k > 0 such that k > n. The terms for the values of k left out are either zero, when some k_{s} = 0, or negligible, if k = n. H(k) attains its absolute maximum at a point \overline{k} = (\overline{k}, …, \overline{k}), where \overline{k} is the root of

(2.5)  κ^{r−1} log \frac{κ^{r}}{κ^{r} − n} − log κ = 0.

Therefore n/\overline{k} ∼ log \overline{k}, so that \overline{k} ∼ n/ log n. More accurately, we set \overline{k} = n/x, so that x ∼ log n, and obtain from (2.5):

x − log \frac{n}{x} = −\frac{x^{r+1}}{2n^{r−1}} + O (\frac{log^{2r+1} n}{n^{2r−2}}) .

Comparing the last equation with

ρ − log \frac{n}{ρ} = 0,

we see that

(2.6)  x = ρ − \frac{ρ^{r+1}}{2n^{r−1}} + O (\frac{log^{2r+1} n}{n^{2r−2}}) .

Combination of (2.4)-(2.6) yields

H(\overline{k}) =rn (x^{−1} − x^{−1} log \frac{n}{x} + log \frac{n}{x}) − \frac{n^{2}}{2\overline{k}^{r}} + O (\frac{n^{3}}{\overline{k}^{2r}} )
=nr(ρ^{−1} − 1 + ρ) − \frac{ρ^{r}}{2n^{r−2}} + O (\frac{log^{2r} n}{n^{2r−3}}) .

(For the last line we have used the fact that the displayed function of x has zero derivative at x = ρ.) We notice immediately that the term −ρ^{r}/(2n^{r−2}) is either −ρ^{2}/2 → −∞, if r = 2, or is O(log^{r} n/n), if r > 2. Furthermore, for ∥k − \overline{k}∥ ≤ n^{1/2} log n,

(2.7)  \frac{∂^{2}H(k)}{∂s_{1}∂s_{2}} = \{ \begin{matrix}− \frac{ρ^{2} + ρ}{n} + O (\frac{log^{4} n}{n^{3/2}}) , & if s_{1} = s_{2}, \\ O (\frac{log^{r+2} n}{n^{r}}) , & if s_{1} ≠ s_{2}. \end{matrix}

Introducing

x_{s} = \frac{k_{s} − \overline{k}_{s}}{n^{1/2}} (ρ^{2} + ρ)^{1/2}, Δx_{s} = (\frac{ρ^{2} + ρ}{n})^{1/2} , 1 ≤ s ≤ r,

and using (2.4), (2.7), we get then: within a factor 1 + O(n^{−1/2} log^{4} n),

∑_{∥k−\overline{k}∥≤n^{1/2}} N_{rn}(k) =(2π(ρ + 1))^{−r/2} exp (nr(ρ − 1 + 1/ρ) − r − \frac{ρ^{r}}{2n^{r−2}} )

· ∑_{∥x−\overline{x}∥≤(ρ^{2}+ρ)^{1/2}} exp (−\frac{1}{2} ∑_{s=1}^{r} x_{s}^{2}) ∏_{s=1}^{r} Δx_{s}.

Next, within a factor 1+O(Δx_{1}), the last sum equals the corresponding r-dimensional integral, and the latter is within the distance of order

∫_{|x|>ρ/r}e^{−x^{2}/2} dx = o(e^{−ρ^{2}/(2r^{2})})

from the integral over ℝ^{r}. Thus

(2.8) ∑_{∥k−\overline{k}∥≤n^{1/2}} N_{rn}(k) = (1 + O(n^{−1/2} log^{4} n))\frac{exp (nr(ρ − 1 + ρ^{−1}) − r − \frac{ρ^{r}}{2n^{r−2}} )}{(ρ + 1)^{r/2}}.

In addition, using (k_{1} ⋯ k_{r})_{n} ≤ k_{1}^{n} ⋯ k_{r}^{n} and the Dobinski formula for B(n),

(2.9)  ∑_{∥k−\overline{k}∥>n^{1/2}} N_{rn}(k) ≤ rB^{r−1}(n) · e^{−1} ∑_{|k−\overline{k}|>r^{−1}n^{1/2} log n} \frac{k^{n}}{k!} .

The fraction k^{n}/k! attains its absolute maximum at some k^{∗} so close to n/ρ, whence to \overline{k}, that the condition on k implies |k − k^{∗}| > (2r)^{−1}n^{1/2} log n. The function k^{n}/k! is roughly exp(H(k)), where H(k) = n log k − k log(k/e) is convex. H(k) has its maximum at k = n/ρ, and

H′′(nρ^{−1} + θn^{1/2} log n) ≤ −\frac{ρ^{2}}{2n}, ∀θ ∈ [−1, 1].)

Therefore

exp (H(nρ^{−1} ± (2r)^{−1}n^{1/2}) log n) ≤ exp(−c^{∗} log^{4} n),

and with a bit of extra effort it follows that

e^{−1} ∑_{|k−\overline{k}|>(2r)^{−1}n^{1/2} log n} \frac{k^{n}}{k!} ≤ B(n) exp(−c′ log^{4} n),

with c′ < c^{∗}. Hence (2.9) reduces to

(2.10)  ∑_{∥k−\overline{k}∥>n^{1/2} log n} N_{rn}(k) = O(B^{r}(n)e^{−c′ log^{4} n}).

Using (2.8), (2.10) and (2.1) (see also the note following (2.2)), we conclude that

P_{rn} = (1 + O(ρ^{−1})) exp (−\frac{ρ^{r}}{2n^{r−2}} ) + O(e^{−c′ log^{4} n}).

□

Since p′ := inf{p_{1}, p_{2}} is so unlikely to be the finest partition, an interesting question is what is the size of the largest block of p′ typically? The answer is: two. And how many two-elements sets are there in p′? The answer is: only about log^{2} n/2.

Theorem 4. Introduce Q_{n}(k), the probability that p′ ≠ p_{min} , that the largest block has size two, and that there are k such blocks. If k = o(n^{1/2}), then

(2.11)  Q_{n}(k) = (1 + o(1))e^{−λ} \frac{λ^{k}}{k!} , λ := \frac{ρ^{2}}{2} .

Thus the number of two-element sets in p′ is Poisson distributed with a large parameter ρ^{2}/2, and with probability approaching one p′ has no larger blocks.

Proof of Theorem 4. The total number of (p_{1}, p_{2}) such that p′ has k two-element blocks, and no larger blocks, is

\binom{n}{2k}(2k − 1)!! · N_{2,n−k}.

(We choose 2k elements in \binom{n}{2k} ways, then pair them in

(2k − 1)!! = 1 · 3 ⋯ (2k − 1) = \frac{(2k)!}{2^{k}k!}

ways, and finally select an ordered pair of minimally intersecting partitions on the resulting set of n − 2k + k elements, k of them being the pairs, and n − 2k of them being the singletons left out.) Then

(2.12)  \begin{matrix}Q_{n}(k) = & \frac{\binom{n}{2k}(2k)!B^{2}(n − k)P_{2,n−k}}{2^{k}k!B^{2}(n)} \\ = & (1 + O(k^{2}/n))\frac{n^{2k}}{2^{k}k!} · (\frac{B(n − k)}{B(n)})^{2} · P_{2,n−k}. \end{matrix}

By Theorem 3,

P_{2,n−k} = (1 + O(ρ^{−1}(n − k))) exp (−ρ^{2}(n − k)/2) ,

where ρ(x) satisfies

(2.13)  ρ(x)e^{ρ(x)} = x ⟺ ρ(x) + log ρ(x) = log x.

It follows from the last equation that

(2.14)  ρ(n − k) = ρ + O(k/n).

Furthermore, by (2.1),

\frac{B(n − k)}{B(n)} =(1 + o(1)) exp(f(n − k) − f(n));
(2.15)  f(x) :=x(ρ(x) − 1 + ρ(x)),

and it is easy to see, via (2.13), that f′(x) = r(x). Invoking (2.14) also, we compute

(2.16)  f(n − k) − f(n) = −k(ρ + O(k/n)) = −kρ + O(k^{2}/n).

Putting together (2.12)-(2.16) leads to

Q_{n}(k) =(1 + O(k^{2}/n))\frac{n^{2k}}{2^{k}k!} · e^{−2kρ} · e^{−ρ^{2}/2}
=(1 + O(k^{2}/n))\frac{(ρ^{2}/2)^{k}}{k!} · e^{−ρ^{2}/2}.

□

Note. For a given mapping f : [n] → [n], the sets {i ∈ [n] : f(i) = j} form a partition p_{f} of [n]. If f is chosen uar from the set of all n^{n} mappings then p_{f} is random, but not uniform. We suggest the interested reader show that for f_{1}, f_{2} chosen independently

lim_{n→∞} Pr(inf{p_{f_{1}}, p_{f_{2}}} = p_{min}) = e^{−1/2}.

(Hint: the reader may wish first to show that it is unlikely for inf{p_{f_{1}}, p_{f_{2}}} to have a block of size three or more, and second to evaluate the factorial moments of the number of two-element blocks.) This result shows that two models of random set partitions differ substantially.

It remains to estimate the probability that sup_{1≤i≤r} p_{i} is the one-block partition p_{max} , the coarsest one. Exact enumeration of such r-tuples appears to be very hard. We can prove, however, that for n large, almost all r tuples have that property.

Theorem 5. Denote P_{rn} = Pr( sup_{1≤i≤r} p_{i} = p_{max}). Then

(2.17)  P_{rn} = 1 − O (\frac{log^{r+1} n}{n^{r−1}}) .

Proof of Theorem 5. Given the event sup_{i} p_{i} ≠ p_{max} , there exists a nonempty

proper subset A of [n] such that each p_{i} is obtained by partitioning separately A and [n] \ A. Therefore

(2.18)  1 − P_{rn} ≤ 2 ∑_{m≤n/2} \binom{n}{m} (\frac{B(m)B(n − m)}{B(n)})^{r} .

Using the computations analogous to (2.13)–(2.16), it is easy to prove that R(m), the ratio of the two consecutive terms, (m + 1)-th and m-th, approaches zero uniformly for m ≤ n^{1/2} , say. (The choice of n^{1/2} is somewhat arbitrary.) For m ∈ [n^{1/2}, n/2],

(2.19)

R(m) =(1 + O(log^{−1} n))\frac{n − m}{m} \frac{e^{rρ(m)}}{e^{rρ(n−m)}}
=(1 + O(log^{−1} n)) exp[g(m) − g(n − m)];
g(x) :=(r − 1)ρ(x) − log ρ(x).

Now

g′(x) = ((r − 1) − \frac{1}{ρ}) · \frac{dρ}{dx} = ((r − 1) − \frac{1}{ρ}) \frac{ρ}{x(1 + ρ)}.

So, for x ∈ [n^{1/2}, n/2], there exists a positive c such that g′(x) ≥ c/x. Then, by (2.19),

R(m) ≤(1 + O(log^{−1} n)) exp (−c ∫_{m}^{n−m} x^{−1} dx)
=(1 + O(log^{−1} n)) (\frac{m}{n − m})^{c} .

Therefore, given a > 0, there exists b > 0 so large that

R(m) ≤ 1 − a/ log n, ∀ m ∈ [n^{1/2}, (n/2)(1 − b/ log n)],

for all n > n(a). Consequently, the corresponding terms in the sum on the right of (2.18) are dominated by those of a geometric series with denominator 1−a/ log n, and their overall contribution is bounded by

(2.20)

n (\frac{B(n − 1)}{B(n)})^{r} · \frac{1}{1 − (1 − a/ log n)} =O (n log n exp(−rρ(n)))
=O (\frac{log^{r+1} n}{n^{r−1}}) .

(For the first line we have used (2.15) and (2.16).) For m ∈ [(n/2)(1 − b/ log n), n/2], we use (2.15) again and bound

(2.21)  \binom{n}{m} (\frac{B(m)B(n − m)}{B(n)})^{r} ≤ 2^{n+1} exp(rf(m) + rf(n − m) − rf(n)).

Since

f′(x) = ρ(x), ρ′(x) = \frac{ρ(x)}{x(1 + ρ(x))},

we write for m in question:

f(m) =f(n/2) − ∫_{m}^{n/2}ρ(x) dx
=f(n/2) − (n/2 − m)ρ(n/2) + O(n^{−1}(n/2 − m)^{2}).

Analogously,

f(n − m) = f(n/2) + (n/2 − m)ρ(n/2) + O(n^{−1}(n/2 − m)^{2}).

So

f(m) + f(n − m) − f(n) =2f(n/2) − f(n) + O(n log^{−2} n)
=n(ρ(n/2) − ρ(n)) + O(n log^{−1} n)
= − n ∫_{n/2}^{n} \frac{ρ(x)}{x(1 + ρ(x))} dx + O(n log^{−1} n)
= − n log 2 + O(n log^{−1} n).

Therefore the right-hand side of (2.21) becomes 2^{−n(r−1)(1+o(1))} , and multiplying this bound by (n/2)b/ log n, the number of m’s in question, we get the same 2^{−n(r−1)(1+o(1))} , with a slightly larger term o(1). Thus, by (2.20),

1 − P_{rn} = O (\frac{log^{r+1} n}{n^{r−1}}) .

□

Note. For the random set partitions p_{f}, however,

lim_{n→∞} Pr( sup_{1≤i≤r} p_{f_{i}} = p_{max}) = 0,

for every r ≥ 1. (Does the reader see a simple proof of this?) It is tempting to “explain” such a difference from the case of uniform partitions by the fact that a typical such partition has about n/ log n blocks, while the one induced by the uniformly random mapping has more blocks, about (1 − e^{−1})n. (The number of “no-values” of the uniformly random mapping is close, in probability, to e^{−1}n.) However, the difference between n and n/ log n does not seem to be sufficiently large to account for such a sharp contrast with the uniform partitions.

Acknowledgement. I am indebted to Steve Milne and Steph Rieser for their interest in this study, and to George Andrews, Ira Gessel and Herb Wilf for expert comments. I was delighted to read Herb’s response that contained (1.12), an elegant transform of (1.9). I am very grateful to Christian Borgs, Jennifer Chayes and Jeong Han Kim who supported my request to visit Microsoft in April-June of 1999.

References

1. E. R. Canfield and L.H. Harper, Large antichains in the partition lattice, Random Structures and Algorithms 6 (1995), 89–104.

2. E. R. Canfield, The size of the largest antichain in the partition lattice, J. Comb. Theory, A 83 (1998), 188-201.

3. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht-Holland / Boston-U.S.A., 1974.

4. L. Moser and M. Wyman, An asymptotic for the Bell numbers, Trans. Roy. Soc. Can. 49 (1955), 49–54.

5. B. Pittel, Random set partitions: asymptotics of subset counts, J. Comb. Theory, A 79 (1997), 326–359.

6. R. S. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole, Monterey, California, 1986.

Department of Mathematics, The Ohio State University, Columbus, Ohio 43210-1174