ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.37019

J. Algebra Comb. Discrete Appl.
4(1) • 75–91

Received: 6 October 2015
Accepted: 7 June 2016

Journal of Algebra Combinatorics Discrete Structures and Applications

Multivariate asymptotic analysis of set partitions:
Focus on blocks of fixed size

Research Article

Guy Louchard

Abstract: Using the Saddle point method and multiseries expansions, we obtain from the exponential formula
and Cauchy’s integral formula, asymptotic results for the number T(n,m,k) of partitions of n labeled
objects with m blocks of fixed size k. We analyze the central and non-central region. In the region
m = n/k−nα, 1 > α > 1/2, we analyze the dependence of T(n,m,k) on α. This paper fits within
the framework of Analytic Combinatorics.

2010 MSC: 05A16, 60C05, 60F05

Keywords: Set partitions, Bell numbers, Asymptotics, Saddle point method, Multiseries expansions, Analytic
combinatorics

1. Introduction

Set partitions parameters have long been a topic of investigation. See, for example, Graham et
al. [7], Knuth [9], Mansour [13], Stanley [15], for other investigations of set partitions. Moreover, set
partitions continue to be of interest recently; see Chern et al. [1, 2]. During a talk given by P. Diaconis
at the Conference in honour of Svante Janson’s 60th birthday, our attention was attracted by a classical
parameter of set partitions: the number T(n,m,k) of partitions of n labeled objects with m blocks of
fixed size k. The value of k will be fixed in this paper, so we suppress the k and simply write this number
as T(m,n).

Our goal is to analyze the asymptotic growth of T(m,n) in several regimes.

Let Π(n) be the set of partitions of n labeled objects, with Bn := |Π(n)| denoting the nth Bell
number.

We define the random variable Jn as the number of blocks of size k in a set partition chosen (uni-
formly) at random from the class of all set partitions of n labeled objects. Then the distribution of Jn

Guy Louchard; Université Libre de Bruxelles, Département d’Informatique, CP 212, Boulevard du Triomphe,
B-1050 Bruxelles, Belgium (email: louchard@ulb.ac.be).

75



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

is

P(Jn = m) =
T(m,n)

Bn
.

Fristedt [5] proved that this distribution is asymptotically Gaussian.

Most of our techniques for studying T(m,n) and the distribution of Jn rely on generating functions
treated as analytic (complex-valued) functions. Thus, we now introduce some of these functions.

We note that exp(ez − 1) is the exponential generating function (GF) of the class of set partitions
(see [4, pp. 106–111]). Therefore the Bn’s are exactly the coefficients of this GF:

∞∑
n=0

Bn
zn

n!
= exp(ez − 1).

Now we decompose the number of such set partitions.

The celebrated exponential formula (or polymer expansion) is given as follows. Let

g(z) :=

∞∑
k=1

ak
zk

k!
.

Then

exp(g(z)) =

∞∑
n=0

bn(a1, . . . ,an)
zn

n!
,

where the nth Bell polynomial reads as

bn(a1, . . . ,an) =
∑

λ∈Π(n)

Πnk=1a
Xk(λ)
k ,

and Xk(λ) is the number of blocks in λ of fixed size k, λ denoting a set partition.

Hence, we use

f2(z,y) :=
∞∑
n=0

∞∑
m=0

T(m,n)ym
zn

n!

to denote the analogous bivariate GF (which is exponential in z and ordinary in y); the variable y is
used here to “mark” the blocks of size k. See [4, p. 156] for an introduction to the marking technique. It
follows immediately that

f2(z,y) = exp

(
ez − 1 + (y − 1)

zk

k!

)
. (1)

Now we define

f3(z) := [y
m]f2(z,y) =

∞∑
n=0

T(m,n)
zn

n!
. (2)

To find f3(z), we take the mth derivative of f2(z) with respect to y, then divide by m! and evaluate at
y = 1, so that

f3(z) = exp

(
ez − 1 −

zk

k!

)
(zk/k!)m

m!
. (3)

76



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

In this paper, we will use multiseries expansions: multiseries are in effect power series (in which the
powers may be non-integral but must tend to infinity) and the variables are elements of a scale. The
scale is a set of variables of increasing order. The series is computed in terms of the variable of maximum
order, the coefficients of which are given in terms of the next-to-maximum order, etc. This is more precise
than mixing different terms. This technique was used in the analysis of Stirling numbers (of the first and
second kind) and Eulerian numbers in Louchard [10–12].

Our paper is organized as follows: in Section 2, we consider the central region, where we re-derive,
with more precision, the asymptotic Gaussian property of Jn. In Section 3, we analyze the large deviation
m = n/k − nα, with 1 > α > 1/2. The appendix provides a brief justification of some integration
procedures.

2. Central region

We use several saddle points. To ease this paper’s reading, we summarize the different values we
need. We consistently use “root” to be interpreted as “root of smallest modulus.”

In section 2,
ρ is the root of ρeρ = n,
ρ̃k is the root of ρ̃k exp(ρ̃k) = n−k,

ρk is the root of ρkeρk −
k(ρk)

k

k!
+ km−n = 0,

In section 3,

ρ∗ is the root of ρ∗eρ
∗
−
k(ρ∗)k

k!
−knα = 0,

ρ is the root of ρeρ = knα.

2.1. The moments

In this section, we first derive asymptotics for the Bell numbers and then proceed to the analysis of
the moments of Jn. For the Bell numbers, we could use Salvy and Shackell [14] or Chern et al. [1]. But
the first paper uses n/ρ in the scale and the second paper uses the solution of ueu = n + 1. We prefer to
use n and ρ: the root (of smallest modulus) of ρeρ = n. The scale of the multiseries is n � ρk � ρ (we
assume here k ≥ 2).

We define m` :=
∏`−1
j=0(m− j) = (m)(m− 1)(m− 2) · · ·(m− ` + 1) as the `th falling factorial of m.

Now we use this notation to study the `th falling factorial of Jn. We have

E((Jn)`) =
∞∑
m=0

m`P(Jn = m) =
∞∑
m=0

m`
T(m,n)

Bn
=

∑∞
m=0 m

` T(m,n)

Bn
.

From (1), we have
∞∑
m=0

m` T(m,n) = n! [zn]
∂`

∂y`
f2(z,y)

∣∣∣∣
y=1

= n! [zn](zk/k!)` exp(ez − 1)

=
n!

(k!)`
[zn−k`] exp(ez − 1)

=
n!

(k!)`
Bn−k`

(n−k`)!

77



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

=

(
n

k,k, . . . ,k︸ ︷︷ ︸
`

,n−k`

)
Bn−k`.

In particular, for ` = 1 and ` = 2, respectively, we have

∞∑
m=0

mT(m,n) =

(
n

k

)
Bn−k and

∞∑
m=0

(m)(m− 1)T(m,n) =
(

n

k,k,n− 2k

)
Bn−2k.

Therefore, the first and second falling moments of Jn are

E(Jn) =
(
n

k

)
Bn−k
Bn

and E((Jn)(Jn − 1)) =
(

n

k,k,n− 2k

)
Bn−2k
Bn

.

Now we need an asymptotic expansion of Bn. Set

f4(z) := exp(e
z).

Let the saddle point be given by ρ and let Ω denote the circle ρeiθ. We compute

(Bn/n!)(e) =
(
[zn] exp(ez − 1)

)
(e) = [zn] exp(ez) = [zn]f4(z).

By Cauchy’s theorem, it follows that

(Bn/n!)(e) =
1

2πi

∫
Ω

f4(z)

zn+1
dz

=
1

ρn
1

2π

∫ π
−π

f4(ρe
iθ)e−niθ dθ using z = ρeiθ

=
1

ρn
1

2π

∫ π
−π

exp
(

ln(f4(ρe
iθ)) −niθ

)
dθ

=
1

ρn
f4(ρ)

2π

∫ π
−π

exp

[
−

1

2
κ2θ

2 −
i

6
κ3θ

3 + · · ·
]
dθ, (4)

where

κi(ρ) :=

(
∂

∂u

)i
ln(f4(ρe

u))|u=0 .

See Good [6] for a neat description of this technique. We have

ρ = W(n),

where W is Lambert’s W function (see Corless et al. [3]). We use the principal branch, which is analytic
at 0. Let us set L := ln(n). We have the well-known asymptotic expressions

ρ = L− ln L +
ln L

L
+ O

(
(ln L)2

L2

)
,

ln(ρ) = ln (L) −
ln (L)

L
+ O

(
(ln L)2

L2

)
.

All expressions involving ρ in the sequel can of course be expanded into powers of L, but this would
lead to huge formulae.

78



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

The dominant part of (4) gives

f4(ρ)

ρn
= exp(n/ρ−n ln(ρ)).

Now we turn to the integral. We have for instance

κ2 = n(1 + ρ),

κ3 = n(1 + 3ρ + ρ
2).

We now proceed as in Flajolet and Sedgewick [4, ch. VIII]. Let us choose a splitting value θ0 such
that κ2θ20 → ∞, and κ3θ30 → 0, as n → ∞. For instance, we can use θ0 = n−5/12. We must prove that
the integral

Kn =

∫ 2π−θ0
θ0

exp
(

ln(f4(ρe
iθ)) −niθ

)
dθ

is such that |Kn| is exponentially small. This is done in Appendix 3. Now we use the classical trick of
setting

−κ2θ2/2! +
∞∑
`=3

κ`(iθ)
`/`! = −u2/2.

Computing θ as a series in u, this gives, by Lagrange’s inversion,

θ =
1
√
n

∞∑
i=1

aiu
i,

with, for instance,

a1 =
1

√
1 + ρ

.

This expansion is valid in the dominant integration domain

|u| ≤
√
nθ0
a1

=
√

1 + ρn1/12.

Setting dθ = dθ
du
du, we integrate on u = [−∞,∞]. This extension of the range is justified as in Flajolet

and Sedgewick [4, ch. VIII]. (From now on, we only provide a few terms in our expansions, but of course
we use more terms in our computations. Also, all O terms in the sequel may depend on k,ρ.) This
integration gives

Bne

n!
=
f4(ρ)

ρn
H1 =

1
√

2π
√

1 + 1/ρ
exp(E1)H2,

where

E1 := n/ρ−n ln(ρ) −L/2 − ln(ρ)/2; (5)

H1 :=
H2√

2πn(1 + ρ)
;

H2 := 1 −
1

24

2ρ4 + 9ρ3 + 16ρ2 + 6ρ + 2

(1 + ρ)
3
n

+ O
(

1

n2

)
. (6)

79



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

Now we turn to Bn−`k. We compute

ln(n− `k) = L−
`k

n
−

1

2

(`k)
2

n2
+ O

(
1

n3

)
.

We will use ρ̃`,k as the root of ρ̃`,k exp(ρ̃`,k) = n− `k, i.e., ρ̃`,k = W(n− `k). This gives

ρ̃`,k = ρ−
ρ`k

n (1 + ρ)
−

1

2

ρ2 (2 + ρ) (`k)
2

(1 + ρ)
3
n2

+ O
(

1

n3

)
,

with

ln(ρ̃`,k) = ln (ρ) −
`k

n (1 + ρ)
−

1

2

(`k)
2 (

1 + 3ρ + ρ2
)

(1 + ρ)
3
n2

+ O
(

1

n3

)
.

Now we specialize to the case ` = 1 to get the mean.

Plugging into E1, we obtain

Bn−ke

(n−k)!
=

exp(E1k)H2k√
2π
√

1 + 1/ρ̃k
,

where

E1k := k ln (ρ) −
1

2
L−

1

2
ln (ρ) −

1

2

k (−ρ + k − 2)
(1 + ρ)n

+ O
(

1

n2

)
,

and

H2k := 1 −
1

24

2ρ4 + 9ρ3 + 16ρ2 + 6ρ + 2

(1 + ρ)
3
n

+ O
(

1

n2

)
.

We need Bn−k
Bn

. This leads to conclude

Bn−k
Bn

=
(n−k)!
n!

H6ρ
k,

with

H6 := H3H4H5 = 1 −
1

2

k
(
−ρ2 + k(1 + ρ) − 3ρ− 1

)
(1 + ρ)

2
n

+ O
(

1

n2

)
,

where

H3 :=

√
1 + 1/ρ√
1 + 1/ρ̃k

= 1 −
1

2

k

(1 + ρ)
2
n
−

1

8

k2
(
8ρ + 2ρ2 + 1

)
(1 + ρ)

4
n2

+ O
(

1

n3

)
,

and

H4 :=
H2k
H2

= 1 −
1

24

k
(
11ρ5 + 28ρ4 + 36ρ3 + 10ρ2 + 10ρ + 2ρ6 + 2

)
(1 + ρ)

5
n2

+ O
(

1

n3

)
,

and where H5 is computed as follows:

E1k −E1 = k ln(ρ) −
1

2

k (−ρ + k − 2)
(1 + ρ)n

+ O
(

1

n2

)
,

80



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

and

exp(E1k −E1) = ρkH5,

so

H5 = 1 −
1

2

k (−ρ + k − 2)
n (1 + ρ)

+
1

24

(
9ρ3 + 39ρ2 − 10ρ2k + 60ρ + 3k2(1 + ρ) − 30ρk + 24 − 16k

)
k2

(1 + ρ)
3
n2

+ O
(

1

n3

)
.

The mean M of Jn is given by

M =
Bn−kn!

Bn(n−k)!k!
=
ρk

k!
H6.

Similarly (we omit the details)

E(Jn(Jn − 1)) =
ρ2k

(k!)2
H7,

where

H7 := 1 −
k
(
−ρ2 + 2k(1 + ρ) − 3ρ− 1

)
(1 + ρ)

2
n

+ O
(

1

n2

)
.

Hence the variance σ2 of Jn is given by

σ2 = E(Jn(Jn − 1)) + M −M2,

and

σ =

√
ρk

k!
H8,

with

H8 := 1 −
2k2 (ρ + 2) ρk + kk!

(
−3ρ + k(1 + ρ) −ρ2 − 1

)
4k! (1 + ρ)

2
n

+ O
(

1

n2

)
.

More generally, the `th falling moment is given by

n!

(n−k`)!(k!)`
Bn−k`
Bn

=
ρk`

(k!)`
H7,`,

H7,` = 1 −
1

2

k`
(
−ρ2 + k`(1 + ρ) − 3ρ− 1

)
(1 + ρ)

2
n

+ O
(

1

n2

)
.

2.2. Distribution of Jn

Fristedt [5] proved that the distribution of Jn is asymptotically Gaussian. This can also be obtained
with Hwang’s techniques: see [8]. We want here to re-derive this property with more precision. The
corresponding GF f5(z) is derived from f3(z):

f5(z) = exp

(
ez −

zk

k!
+ km ln(z) − ln(m!) −m ln (k!)

)
,

81



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

with

m = M + xσ, x = Θ(1).

The saddle point equation is now

ρke
ρk −

ρk
kk

k!
+ km−n = 0. (7)

It is easily seen that we have

ρk ∼ ρ + δ,

with

δ =

∞∑
j=1

αj
nj
.

When we write ρk ∼ ρ + δ, this is simply a statement that ρk −ρ can be written as a Taylor series
in terms of powers of n−1, and then α1 is just the first coefficient in this Taylor series.

Solving (7) gives, for instance,

α1 := −kx
√
ρk

k!
ρ (1 + ρ)

−1
.

Also, we have the classical result that

ln(m!) = −m + m ln (m) +
1

2
ln (2πm) +

1

12
m−1 + O

(
1

m2

)
.

We must analyze

P(Jn = m) =
n!

eBn
[zn]f5(z).

First of all, we must compute the dominant term of n!f5(ρk)
eBnρ

n
k
. We have

n!f5(ρk)

eBnρ
n
k

= exp(T1)
1

H2

with H2 given by (6) and, with (5),

T1 =
neδ

ρ
−
ρk
k

k!
+ km ln (ρk ) −n ln (ρk ) − ln(m!) −m ln (k!)

−
(
n

ρ
−

1

2
L−n ln (ρ) −

1

2
ln (ρ) −

1

2
ln
(
1 + ρ−1

)
−

1

2
ln (2π)

)
.

We compute

T1 = T0 +
T4
n

+ O
(

1

n2

)
.

The dominant term of T0 is computed as

T2 :=
1

2

[
L + ln (1 + ρ) −x2 −k ln (ρ) + ln (k!)

]
.

82



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

Set now the next term of T0 as T3 := T0 −T2. We have

n!f5(ρk)

eBnρ
n
k

= exp(T1)
1

H2

= e−x
2/2

√
k!√
ρk

√
1 + ρ

√
n exp

(
T3 + T4/n + O

(
1

n2

))(
1 +

T5
n

+ O
(

1

n2

))
, (8)

and

T3 :=
1/6x

(
x2 − 3

)√
k!

ρk/2
−

1

12

k!
(
−3x2 + x4 + 1

)
ρk

+
1

60

x
(
3x4 + 5 − 10x2

)
(k!)

3/2

ρ3k/2
+ O

(
1

ρ2k

)
.

Later on, we will need

T6 := exp(T3) = 1 +
1/6x

(
x2 − 3

)√
k!

ρk/2
+

1

72

(
27x2 − 12x4 − 6 + x6

)
k!

ρk
+ O

(
1

ρ3k/2

)
.

Also

T5 :=
1

24

2ρ4 + 9ρ3 + 16ρ2 + 6ρ + 2

(1 + ρ)
3

.

We now turn to the coefficient of 1/n in T1.

T4 =
1

2

k3x

√
(k!)

−1
ln (ρ)

k! (1 + ρ)
ρ3k/2

+
1

2
k2 ln(ρ)

(
−ρ2 +

x2ρ

ln (ρ)
− 3ρ +

x2

ln (ρ)
+ k(1 + ρ) − 1

)
ρk (k!)

−1
(1 + ρ)

−2

and

exp

(
T4
n

)
= 1 +

T7
n

+ O
(

1

n2

)
,

and

T7 ≡ T4.

To compute the integral, we obtain, for instance,

κ2 = (1 + ρ)n +


−k2ρk

k!
−
x

√
(k!)

−1 (
1 + 3ρ + ρ2

)
kρk/2

(1 + ρ)
+ O

(
1

ρk/2

) + O( 1
n

)
,

and the integral leads to

I =
1

√
n
√

2π
√

1 + ρ

(
1 +

T8
n

+ O
(

1

n2

))
,

with

T8 :=
1

24

(
24k2ρ2 + 12k2ρ3 + 12k2ρ

)
ρk

(1 + ρ)
3
ρk!

+ O
(
ρk/2

)
.

We compute now

T9 := T5 + T7 + T8 = T91ρ
3k/2 + T92ρ

k + O
(
ρk/2

)
,

83



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

with

T91 :=
1

2

k3x ln (ρ)

(k!)
3/2

(1 + ρ)
,

and

T92 :=
1

2

k2
(
ρ + x2(1 + ρ) + 1

)
(1 + ρ)

2
k!

+
1

2

k2
(
−ρ2 + k(1 + ρ) − 3ρ− 1

)
ln (ρ)

(1 + ρ)
2
k!

.

Combining the integral I with (8) gives the local limit theorem:

Theorem 2.1. The asymptotic distribution of Jn is given by the local limit theorem:

P(Jn = m) = e−x
2/2

√
k!√

ρk
√

2π
T6

(
1 +

T9
n

+ O
(

1

n2

))
. (9)

Of course more terms can be mechanically computed, but the expressions become much more intri-
cate.

To check the quality of our asymptotics, we have chosen k = 2,n = 1000, the range of interest for

m is given by m ∈
(
ρk

k!
+ 2
√

ρk

k!
, ρ

k

k!
− 2
√

ρk

k!

)
= (6, 21). To numerically compute T(m,n), we use (3),

which gives

T(m,n)

n!
=
[
zn−km

]
exp

(
ez − 1 −

zk

k!

)
1

m!(k!)m
.

Figure 1 shows T(m,n) (circle), the asymptotics e−x
2/2

√
k!√

ρk
√

2π
(line, of course we use here ρ

k

k!
as mean

and variance) and Equ. (9) (box).

Figure 2 gives the quotient of Equ. (9) and T(m,n).

Figure 3 gives the quotient of Equ. (9) and T(m,n) (box) and the quotient of e−x
2/2

√
k!√

ρk
√

2π
and

T(m,n) (line).

Note that the same technique would lead to the joint distribution of Jn(k1), Jn(k2) for two (or more)
different values of k.

3. Large deviation m = n/k −nα, 1 > α > 1/2

We have a maximum of n/k blocks of size k in a partition. So we use

m =
n

k
−nα.

This can be written as

m =
n

k
(1 −ε),

with ε := knα−1.

In this section, we choose α ≥ 1
2
, but the other case is similarly analyzed. The saddle point equation,

from (7) becomes

ρ∗eρ
∗
−
ρ∗kk

k!
+ km−n = ρ∗eρ

∗
−
ρ∗kk

k!
− ñ = 0

84



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

0

0.02

0.04

0.06

0.08

0.1

5 10 15 20 25

j

Figure 1. T(m,n) (circle), the asymptotics e−x
2/2

√
k!√

ρk
√
2π

(line) and Equ. (9) (box)

0.9

0.95

1

1.05

1.1

1.15

5 10 15 20 25

j

Figure 2. Quotient of Equ. (9) and T(m,n)

85



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

0.6

0.8

1

1.2

1.4

5 10 15 20 25

j

Figure 3. Quotient of Equ. (9) and T(m,n) (box), quotient of e−x
2/2

√
k!√

ρk
√
2π

and T(m,n) (line)

with ñ := knα. The multiseries’ scale is here n � ñ � 1
ε
� L. The solution of ρeρ = ñ is asymptotically

given by

ρ = αL + ln (k) − ln (α) − ln (L) +
(
−

ln (k)

α
+

ln (α) + ln (L)

α

)
L−1 + O

(
1

L2

)
.

As previously, we have

ρ∗ = ρ + δ,

with, here,

δ =
ρkkρ

k! (1 + ρ) ñ
+

1

2

(
ρk
)2
k2
(
−2ρ−ρ2 + 2k + 2ρk

)
ρ

(k!)
2

(1 + ρ)
3
ñ2

+ O
(

1

ñ3

)
.

First of all, we have

n!f5(ρ
∗)

eρ∗n
=
n!

e
exp(R0),

with

R0 =
eδñ

ρ
−
ρ∗k

k!
+ km ln (ρ∗) −n ln (ρ∗) − ln (m!) −m ln (k!) .

We have, successively,

R0 = nR1 + R2 + O
(

1

n

)
,

86



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

R1 := R10 +
R11
ñ

+
R12
ñ2

+ O
(

1

ñ3

)
,

R2 :=
ñ

ρ
+ R20 +

R21
ñ

+ O
(

1

ñ2

)
,

with

R10 :=
1

2

2 − 2 ln (k!) + 2 ln (k) − 2L
k

+
1

2

−2 ln (k) + 2L− 2k ln (ρ) + 2 ln (k!)
k

ε−
1

2
k−1ε2 + O(ε3),

R11 := −
ρkk

k! (1 + ρ)
ε,

R12 := −
1

2

ρ2k
(
−ρ2 + 2k(1 + ρ) − 3ρ− 1

)
k2

(k!)
2

(1 + ρ)
3

ε,

and

R20 = −
ρk

k!
−

1

2
L +

ρkk

k! (1 + ρ)
−

1

2
ln
(

2
π

k

)
+

1

2
ε + O(ε2),

and

R21 =
1

2

ρ2k
(
−2 − 5ρ− 2ρ2 + 2k(1 + ρ)

)
(1 + ρ)

3
(k − 1)!2

.

Computing the integral, we have, for instance,

κ2 := (1 + ρ) ñ −
ρkk

(
−ρ2 + k(1 + ρ) − 3ρ− 1

)
k! (1 + ρ)

+ O
(

1

ñ

)
,

and the integral leads to

I =
1

√
1 + ρ

√
2π

1
√
ñ

(
1 +

R5
ñ

+ O
(

1

ñ2

))
,

and

R5 :=
R3
R4

,

with

R3 := 12k
2ρk+1(1 + ρ) − 36ρk+1k(1 + ρ) + 12ρkk2(1 + ρ) − 12ρk+2k(1 + ρ)

− 12ρkk(1 + ρ) − 2k!ρ4 − 9k!ρ3 − 16k!ρ2 − 6k!ρ− 2k!,

where

R4 := 24 (1 + ρ)
3
k!.

Finally, we obtain the following asymptotic result

87



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

Theorem 3.1. The asymptotic expression of the T(m,n) for large deviation is given by

T(m,n) =
n!

e
exp(R0)

1
√

1 + ρ
√

2π

1
√
ñ

(
1 +

R5
ñ

+ O
(

1

ñ2

))
. (10)

Let us analyze the importance of our terms. We have two sets: the set A of dominant terms, which
stay in the exponent and the set B of small terms, leading to a coefficient of type (1 + ∆), with ∆ small.
The property of each term may depend on α. For instance, in R10, the first term leads to an O(nL) term,
the ε term leads to an nα term, the ε2 term leads to an n2α−1 term, which are all ∈ A. the ε3 term leads
to an n3α−2 term which is ∈ A if α ≥ 2/3 and ∈ B otherwize. In R11 the ε term leads to a term ∈ A. In
R12 all terms are ∈ B. In R2, the ñ term is ∈ A , in R20 the first term is ∈ A, all other terms are ∈ B,
in R21, all terms are ∈ B.

We finally mention that our non-central range is not sacred: other types of ranges can be analyzed
with similar methods.

To check the quality of our asymptotics, we have first chosen k = 2,α = .52, a range n ∈
[10000, 70000] and m = bn

k
− nαc. Figure 4 shows the quotient Equ. (10)/T(m,n). The fluctuations

are due to the fact that m is integer, so the value of α we need is actually the root of m− (n
k
−nα) = 0.

1.005

1.006

1.007

1.008

1.009

1.01

1.011

10000 20000 30000 40000 50000 60000 70000

Figure 4. Quotient Equ. (10)/T(m,n), α = .52,n ∈ [10000,70000]

For α = .65, we choose n ∈ [100, 2300], this leads to Figure 5. The quality of the asymptotics
decreases for α ≥ .7, more terms would be necessary.

Another way is to fix n. We have chosen k = 2,n = 10000 and a range α ∈ (.52, .65) hence
m ∈ [4600, 4900]. Again α is chosen as the root of m − (n

k
− nα) = 0. Figure 6 shows the quotient

Equ. (10)/T(m,n).

Acknowledgment: We would like to thank two referees for many useful suggestions that improved
the paper.

88



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

1.7

1.8

1.9

2

500 1000 1500 2000

Figure 5. Quotient Equ. (10)/T(m,n), α = .65,n ∈ [100,2300]

1

1.1

1.2

1.3

1.4

1.5

4600 4650 4700 4750 4800 4850 4900

Figure 6. Quotient Equ. (10)/T(m,n), n = 10000,α ∈ (.52, .65),m ∈ [4600,4900]

89



G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

References

[1] B. Chern, P. Diaconis, D. M. Kane, R. C. Rhoades, Closed expressions for set partition statistics,
Res. Math. Sci. 1(2) (2014) 1–32.

[2] B. Chern, P. Diaconis, D. M. Kane, R. C. Rhoades, Central limit theorems for some set partitions,
Adv. Appl. Math. 70 (2015) 92–105.

[3] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, D. E. Knuth, On the LambertW function,
Adv. Comput. Math. 5 (1996) 329–359.

[4] P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.
[5] B. Fristedt, The structure of random partitions of large sets, Technical report, University of Min-

nesota, 1987.
[6] I. J. Good, Saddle–point methods for the multinomial distribution, Ann. Math. Statist. 28(4) (1957)

861–881.
[7] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Second Edition, Addison Wesley,

1994.
[8] H. K. Hwang, On convergence rates in the central limit theorems for combinatorial structures,

European J. Combin. 19(3) (1998) 329–343.
[9] D. E. Knuth, The Art of Computer Programming, vol. 4a: Combinatorial Algorithms. Part I,

Addison–Wesley, Upper Saddle River, New Jersey, 2011.
[10] G. Louchard, Asymptotics of the Stirling numbers of the first kind revisited: A saddle point approach,

Discrete Math. Theor. Comput. Sci. 12(2) (2010) 167–184.
[11] G. Louchard, Asymptotics of the Stirling numbers of the second kind revisited: A saddle point

approach, Appl. Anal. Discrete Math. 7(2) (2013) 193–210.
[12] G. Louchard, Asymptotics of the Eulerian numbers revisited: A large deviation analysis, Online J.

Anal. Comb. 10 (2015) 1–11.
[13] T. Mansour, Combinatorics of Set Partitions, Discrete Mathematics and Its Applications Series,

CRC Press, Boca Raton, FL, 2013.
[14] B. Salvy, J. Shackell, Symbolic asymptotics: Multiseries of inverse functions, J. Symbolic Comput.

20(6) (1999) 543–563.
[15] R. P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edn, Cambridge Studies in Advanced

Mathematics, Vol. 49. Cambridge University Press, Cambridge, 2012.

90

http://dx.doi.org/10.1186/2197-9847-1-2
http://dx.doi.org/10.1186/2197-9847-1-2
http://dx.doi.org/10.1016/j.aam.2015.06.008
http://dx.doi.org/10.1016/j.aam.2015.06.008
http://dx.doi.org/10.1007/BF02124750 
http://dx.doi.org/10.1007/BF02124750 
http://dx.doi.org/10.1214/aoms/1177706790
http://dx.doi.org/10.1214/aoms/1177706790
http://dx.doi.org/10.1006/eujc.1997.0179 
http://dx.doi.org/10.1006/eujc.1997.0179 
http://www.ams.org/mathscinet-getitem?mr=2676669
http://www.ams.org/mathscinet-getitem?mr=2676669
http://dx.doi.org/10.2298/AADM130612011L 
http://dx.doi.org/10.2298/AADM130612011L 
http://web.math.rochester.edu/ojac/vol10/117.pdf
http://web.math.rochester.edu/ojac/vol10/117.pdf
http://dx.doi.org/10.1006/jsco.1999.0281
http://dx.doi.org/10.1006/jsco.1999.0281


G. Louchard / J. Algebra Comb. Discrete Appl. 4(1) (2017) 75–91

Appendix: Justification of the integration procedure

For the Bn case, we must analyze

<(ln(f4(ρeiθ) −niθ).

Let us first notice that niθ does not contribute to the analysis. Next, we have

<
(
eρe

iθ
)

= eρ cos(θ) cos(ρ sin(θ))

which has a dominant peak at 0.

For the Gaussian case, we use f5(z). We must analyze

<
(
eρe

iθ

−
(ρeiθ)k

k!

)
= eρ cos(θ) cos(ρ sin(θ)) −

ρk

k!
cos(kθ)

which has a dominant peak at 0.

The non-central region leads to the same analysis.

91


	Introduction
	Central region
	Large deviation m=n/k-n, 1>>1/2
	References
	Appendix: Justification of the integration procedure