# Asymptotic Enumeration and Limit Laws for Multisets: the Subexponential Case

Konstantinos Panagiotou and Leon Ramzews Department of Mathematics, Ludwig-
Maximilians-Universität München. E-mail<EMAIL_ADDRESS>of
Mathematics, Ludwig-Maximilians-Universität München. E-mail:
<EMAIL_ADDRESS>Funded by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation), Project PA 2080/3-1.

###### Abstract

For a given combinatorial class ${\mathcal{C}}$ we study the class
${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$ satisfying the multiset
construction, that is, any object in ${\mathcal{G}}$ is uniquely determined by
a set of ${\mathcal{C}}$-objects paired with their multiplicities. For
example, $\text{{Mset}}(\mathbb{N})$ is (isomorphic to) the class of number
partitions of positive integers, a prominent and well-studied case. The
multiset construction appears naturally in the study of unlabelled objects,
for example graphs or various structures related to number partitions. Our
main result establishes the asymptotic size of the set ${\mathcal{G}}_{n,N}$
that contains all multisets in ${\mathcal{G}}$ having size $n$ and being
comprised of $N$ objects from ${\mathcal{C}}$, as $n$ _and_ $N$ tend to
infinity and when the counting sequence of ${\mathcal{C}}$ is governed by
subexponential growth; this is a particularly important setting in
combinatorial applications. Moreover, we study the component distribution of
random objects from ${\mathcal{G}}_{n,N}$ and we discover a phenomenon that we
baptise _extreme condensation_ : taking away the largest component as well as
all the components of the smallest possible size, we are left with an object
which converges in distribution as $n,N\to\infty$. The distribution of the
limiting object is also retrieved. Moreover and rather surprisingly, in stark
contrast to analogous results for labelled objects, the results here hold
uniformly in $N$.

##  1 Introduction & Main Results

Let ${\mathcal{C}}$ be a combinatorial class, that is, a countable set endowed
with a size function $\lvert\cdot\rvert:{\mathcal{C}}\to\mathbb{N}$ such that
${\mathcal{C}}_{n}:=\\{C\in{\mathcal{C}}:\lvert C\rvert=n\\}$ contains only
finitely many objects for all $n\in\mathbb{N}$. Then the class of
${\mathcal{C}}$-multisets ${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$
consists of all objects of the form

$\big{\\{}(C_{1},d_{1}),\dots,(C_{k},d_{k})\big{\\}},\quad
k\in\mathbb{N},\leavevmode\nobreak\ \leavevmode\nobreak\
C_{i}\in{\mathcal{C}},d_{i}\in\mathbb{N}\text{ for all }1\leq i\leq k,$

where $(C_{i})_{1\leq i\leq k}$ are pairwise distinct and $d_{i}$ is the
multiplicity of the object $C_{i}$ in the multiset. In simple words, a
${\mathcal{C}}$-multiset is a finite unordered collection of elements from
${\mathcal{C}}$ such that multiple occurrences of each element are admissible.
For example, if ${\mathcal{C}}=\mathbb{N}$, then
$\text{{Mset}}({\mathcal{C}})$ contains all partitions of natural numbers, a
prominent object. The multiset construction is omnipresent in combinatorial
settings, for example when ${\mathcal{C}}$ is some class of connected
unlabelled graphs; this makes ${\mathcal{G}}$ the class of unlabelled graphs
having connected components in ${\mathcal{C}}$. For many historical references
and examples we refer the reader to the excellent books [18, 30]. An
alternative and instructive way to describe multisets of size $n\in\mathbb{N}$
is to make the connection to number partitions explicit as follows. First,
choose a number partition of $n$. Then, assign to each of the parts an element
of that size from ${\mathcal{C}}$. Hence, multisets are also called _weighted
integer partitions_ , frequently encountered in the context of statistical
physics of ideal gas. There, $c_{k}:=\lvert\\{C\in{\mathcal{C}}:\lvert
C\rvert=k\\}\rvert$ describes the different possible states of a particle at
energy level $k\in\mathbb{N}$, see [49] for a thorough overview.

Given $G=\\{(C_{1},d_{1}),\dots,(C_{k},d_{k})\\}\in{\mathcal{G}}$ we denote by
$\lvert G\rvert:=\sum_{1\leq i\leq k}d_{i}\lvert C_{i}\rvert$ the _size_ and
by $\kappa(G):=\sum_{1\leq i\leq k}d_{i}$ the number of _components_ of $G$.
We further set

${\mathcal{G}}_{n}:=\\{G\in{\mathcal{G}}:\lvert
G\rvert=n\\}\quad\text{and}\quad{\mathcal{G}}_{n,N}:=\\{G\in{\mathcal{G}}_{n}:\kappa(G)=N\\},\qquad
n,N\in\mathbb{N}.$

Additionally, we define $\mathsf{G}_{n}$ and $\mathsf{G}_{n,N}$ to be
multisets drawn uniformly at random from ${\mathcal{G}}_{n}$ and
${\mathcal{G}}_{n,N}$, respectively.

A vast amount of literature is dedicated to the enumerative problem of
determining $g_{n}:=\lvert{\mathcal{G}}_{n}\rvert$, and sometimes also
$g_{n,N}:=\lvert{\mathcal{G}}_{n,N}\rvert$, under various general assumptions
or for specific examples such as integer partitions, plane partitions or
unlabelled (un-)rooted forests, see e.g. [23, 24, 22, 37, 32, 25] for $g_{n}$
and [26, 29] for $g_{n,N}$. Note that determining $g_{n}$ and $g_{n,N}$ is
directly related to the limiting distribution and local limit theorems for the
number of components in $\mathsf{G}_{n}$, for example investigated in [34, 27,
5, 17]. Another closely related topic that has received a lot of attention is
devoted to finding the asymptotic behaviour of the global shape of
$\mathsf{G}_{n}$ and $\mathsf{G}_{n,N}$ in terms of phenomena like
condensation or gelation, cf. [48, 35, 4, 3, 33, 17]. Section 1.1 highlights
some of these results in more detail and makes the connection to this work
explicit.

We associate to ${\mathcal{C}}$ and ${\mathcal{G}}$ the (ordinary) generating
series in two formal variables $x$ and $y$

$C(x):=\sum_{k\in\mathbb{N}}\lvert{\mathcal{C}}_{k}\rvert x^{k}\quad\text{ and
}\quad G(x,y):=\sum_{k,\ell\in\mathbb{N}}\lvert{\mathcal{G}}_{k,\ell}\rvert
x^{k}y^{\ell},$

and we use the standard notation
$g_{n,N}=\lvert{\mathcal{G}}_{n,N}\rvert=[x^{n}y^{N}]G(x,y)$ for all
$n,N\in\mathbb{N}$. These two power series are known to fulfil the fundamental
relation, see for example [18, 30],

$\displaystyle G(x,y)=\exp\left(\sum_{j\geq 1}y^{j}\frac{C(x^{j})}{j}\right).$
(1.1)

In this paper we consider the prominent and broad case in which the counting
sequence $(c_{n})_{n\in\mathbb{N}}$ is _subexponential_ , and our aim is to
study the class ${\mathcal{G}}_{n,N}$ – what is $g_{n,N}$, how do typical
objects look like? – as $n\to\infty$ _and for all $1\leq N\leq n$_.
Subexponential sequences appear naturally in combinatorial contexts, the main
reason being the presence of square-root singularities in the analysis of
associated generating functions. Here is an example for a prototypical
application.

##### Example.

_Let ${\mathcal{T}}$ be the class of unlabelled trees, that is, isomorphism
classes of connected and acyclic graphs. Then
$\mathcal{F}=\text{{Mset}}({\mathcal{T}})$ is the class of unlabelled forests.
Moreover, see [36], the number of unlabelled trees satisfies_

$|{\mathcal{T}}_{n}|\sim c\cdot n^{-5/2}\cdot\rho^{-n}$

_for some $c>0$ and $0<\rho<1$. What can we say about $\mathcal{F}_{n,N}$?_

Similar counting sequences, in particular with a polynomial term $n^{-\alpha}$
for some $\alpha>1$, appear in a variety of contexts in graph enumeration; so-
called subcritical graph classes [12] that include trees, outerplanar and
series-parallel graphs are prominent examples. All these counting sequences –
and many more – are _subexponential_. Let us proceed with a formal definition.
In order to do so, we step back from our combinatorial setting and let
$(c_{k})_{k\in\mathbb{N}}$ be a real-valued non-negative sequence. Then we say
that $C(x)=\sum_{k\geq 1}c_{k}x^{k}$, or $(c_{k})_{k\geq 1}$ respectively, is
_subexponential_ with radius of convergence $\rho>0$, if

$\frac{c_{n-1}}{c_{n}}\sim\rho\quad\text{and}\quad c_{n}^{-1}\sum_{1\leq k\leq
n}c_{k}c_{n-k}\sim 2C(\rho)<\infty,\quad n\to\infty.$

Important examples for subexponential sequences are of the form
$c_{n}\sim\lambda(n)\cdot n^{-\alpha}\cdot\rho^{-n}$ for $\alpha>1$ and
$\lambda(n)$ any slowly varying function, see [16].

Let us now return to the question investigated in this paper. Given a
subexponential $C(x)$ we want to study for $n\in\mathbb{N}$ and all $1\leq
N\leq n$ the number $g_{n,N}=[x^{n}y^{N}]G(x,y)$, and moreover, if $C(x)$ is
the generating series of some combinatorial class (that is,
$(c_{k})_{k\in\mathbb{N}}$ is an integer sequence), typical properties of the
random multiset $\mathsf{G}_{n,N}$. A directly related result in this context
is [5], where the authors show that the (limiting) distribution of the number
of components in a random $\cal C$-multiset $\mathsf{G}_{n}$ is given by a
weighted sum of independent Poisson random variables. Equivalently, this means
that $g_{n,N}$ can be determined asymptotically for _fixed_ of $N$ as
$n\to\infty$; thus the enumeration problem is well understood for a bounded
number of components. On the other end of the spectrum, let $m\equiv
m(C)\in\mathbb{N}$ be such that $c_{m}>0$ and $c_{1}=\cdots=c_{m-1}=0$. When
$C(x)$ is the generating function of a combinatorial class, this means that
the size of the smallest possible object in ${\mathcal{C}}$ is $m$, and so,
any $\cal C$-multiset in ${\cal G}_{n}$ has at most $n/m$ components. In
particular, $n-mN\geq 0$, and if $n-mN=O(1)$ then the structure of _any_ $\cal
C$-multiset of size $n$ with $N$ components is rather simple: except for a
bounded number of components of bounded size, all other components are of the
smallest possible size $m$. Our first main result adresses the enumeration
problem in all other remaining cases, namely when $N,n-mN\to\infty$.

######  Theorem 1.1.

Suppose that $C(x)$ is subexponential and $0<\rho<1$. Let
$m=\min\\{k\in\mathbb{N}:c_{m}>0\\}$. Then, as $n,N,n-mN\to\infty$,

$[x^{n}y^{N}]G(x,y)\sim A\cdot N^{c_{m}-1}\cdot c_{n-m(N-1)},$ (1.2)

where

$A=\frac{1}{\Gamma(c_{m})}\exp\left(\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\right).$

The proof is in Section 3.2. Some discussion and remarks are in place. First,
by considering real-valued sequences $(c_{k})_{k\in\mathbb{N}}$ the formula in
Theorem 1.1 gives us the asymptotic behaviour of the coefficients of $G(x,y)$
with a priori no combinatorial interpretation. However, if the sequence is
integer-valued and corresponds to the counting sequence of a combinatorial
class $\cal C$, then Theorem 1.1 is an enumeration result: it provides us with
the number of $\cal C$-multisets of size $n$ and $N$ components, where
$N,n-mN\to\infty$. Second, in combinatorial applications, note that we
_always_ have that $\rho<1$, as otherwise the subexponentiality of $C(x)$
would imply that $c_{k}\to 0$ as $k\to\infty$. That is, the assumption
$0<\rho<1$ imposes no restriction in the combinatorial setting.

Let us make a third remark that will pave the way to the following results.
From here on we solely consider the combinatorial setting. Note the right hand
side of (1.2): this formula establishes an explicit connection between
$g_{n,N}$ and $c_{n-m(N-1)}$, that is, we do not need the actual counting
sequence of $\cal C$ to make statements about $g_{n,N}$. Moreover, a closer
look at this formula reveals an unexpected fact. The number of possible ways
to choose a multiset of $N$ objects from ${\mathcal{C}}_{m}$ is given by
$\binom{c_{m}+N-1}{N}\sim N^{c_{m}-1}/\Gamma(c_{m})$ (this is just a number
partition of $N$ in $c_{m}$ parts). Hence the right hand side of (1.2) is
proportional to the number of possibilities to choose $N$ objects from
${\mathcal{C}}_{m}$ and one object from ${\mathcal{C}}_{n-m(N-1)}$; that is, a
“typical” object from ${\mathcal{G}}_{n,N}$ should essentially consist of a
big component with more or less $n-m(N-1)$ vertices and $N-1$ components of
the smallest possible size $m$. This is rather extreme, as the size of a
component of an object in ${\mathcal{G}}_{n,N}$ is bounded from above by
$n-m(N-1)$.

Our next result formalizes this intuition. For
$G=\\{(C_{1},d_{1}),\dots,(C_{k},d_{k})\\}\in{\mathcal{G}}$ denote by
${\mathcal{L}}(G):=\max_{1\leq i\leq k}\lvert C_{i}\rvert$ the size of one of
its largest components. We show that except for a term $\mathcal{O}_{p}(1)$,
that is, a quantity that is bounded in probability, the largest component in a
uniformly drawn object $\mathsf{G}_{n,N}$ from ${\mathcal{G}}_{n,N}$ has
indeed size very close to $n-mN$.

######  Theorem 1.2.

Suppose that $C(x)$ is subexponential. Then, as $n,N,n-mN\to\infty$,

${\mathcal{L}}(\mathsf{G}_{n,N})=n-mN+{\cal O}_{p}(1).$

The proof can be found in Section 3.3. We call the phenomenon established in
Theorem 1.2 _extreme condensation_ : we observe that typically our objects
have a giant component that is _essentially as large as possible_ ; its size
is close to the largest possible size $n-m(N-1)$. In particular, virtually all
other components are of smallest possible size $m$. We are not aware of any
other object with a comparable behaviour, at least not in the analytical
$(\rho>0$) setting considered here.111For example, it is known that a
factorial weight sequence induces extreme condensation in the balls-in-boxes
model, see [28, Example 19.36]. In such situations the respective generating
series has radius of convergence 0. Moreover, this behaviour is surprising for
one more reason: if we consider the labelled counterparts of our unlabelled
objects, in our running example trees, then the typical structure is well
known to undergo various phase transitions (from subcritical to condensation)
depending on the number of components, but it never becomes as extreme as
observed here. See [28, 38] and Section 1.2 for a more detailed discussion.

Our final main result addresses the last remaining bit and describes the shape
of a typical object from $\mathsf{G}_{n,N}$ when we remove a component of
largest size and all components of the smallest possible size $m$. This
_remainder_ is a multiset of stochastically bounded size and number of
components, and we determine the limiting distribution. To formulate our
statement we need some additional notation. Define the class
${\mathcal{C}}_{>m}=\bigcup_{k>m}{\mathcal{C}}_{k}$ equipped with the modified
size function $\lvert C\rvert_{>m}:=\lvert C\rvert-m$ for
$C\in{\mathcal{C}}_{>m}$. The associated generating function $C_{>m}(x)$ thus
equals $(C(x)-c_{m}x^{m})/x^{m}$; here subtracting $c_{m}x^{m}$ accounts for
the fact that we remove objects of (the smallest) size $m$ and dividing
through $x^{m}$ all objects in ${\mathcal{C}}_{k}$, $k>m$, are treated as
objects with size $k-m$. Similar to the formula in (1.1) (setting $y=1$) the
class of all multisets ${\mathcal{G}}_{>m}:=\text{{Mset}}({\mathcal{C}}_{>m})$
therefore has generating series

$G_{>m}(x):=\exp\left(\sum_{j\geq
1}\frac{C(x^{j})-c_{m}x^{j}}{jx^{jm}}\right).$

Further, the size of an object $G$ in ${\mathcal{G}}_{>m}$ is given by $\lvert
G\rvert_{>m}:=\lvert G\rvert-m\kappa(G)$. As the coefficients of $C_{>m}(x)$
are given by $(c_{k+m})_{k\in\mathbb{N}}$ we deduce that $C_{>m}(x)$ is also
subexponential with radius of convergence $\rho$ and $G_{>m}(\rho)<\infty$.
Define a random variable $\Gamma G_{>m}(\rho)$ on ${\mathcal{G}}_{>m}$
specified by

$\mathrm{Pr}\left[\Gamma G_{>m}(\rho)=G\right]=\frac{\rho^{\lvert
G\rvert_{>m}}}{G_{>m}(\rho)}=\exp\left(-\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{j}}{j\rho^{jm}}\right)\rho^{\lvert
G\rvert-m\kappa(G)},\quad G\in{\mathcal{G}}_{>m}.$ (1.3)

We remark in passing that this is the – well-known – Boltzmann distribution
(on ${\cal G}_{>m}$) about which we will talk later extensively. For
$G\in{\mathcal{G}}$ let the remainder ${\mathcal{R}}(G)$ be the multiset
obtained after removing all tuples $(C,d)\in G$ with $C\in{\mathcal{C}}_{m}$
and one object of largest size from $G$ (this choice can be done in a
canonical way by numbering all elements in ${\mathcal{C}}$). That means, if
the object of largest size has multiplicity $d>1$ replace $d$ by $d-1$,
otherwise remove the object and its multiplicity $1$ completely from the set.
Then the distribution in (1.3) is the limit of the remainder
${\mathcal{R}}(\mathsf{G}_{n,N})$, see Section 3.4 for the proof.

######  Theorem 1.3.

Suppose that $C(x)$ is subexponential. Then, as $n,N,n-mN\to\infty$, in
distribution ${\mathcal{R}}(\mathsf{G}_{n,N})\to\Gamma G_{>m}(\rho).$

We close this introduction and the presentation of the main results by
catching up with our previous example regarding the class ${\mathcal{T}}$ of
unlabelled trees and ${\cal F}=\text{{Mset}}({{\mathcal{T}}})$ the unlabelled
forests.

##### Example (continued)

_Theorem 1.1 is directly applicable to the class of unlabelled trees. We
readily obtain that the number of unlabelled forests of size $n$ with $N$
components satisfies_

$f_{n,N}\sim A\cdot\lvert{\mathcal{T}}_{n-N+1}\rvert\sim
A^{\prime}\cdot(n-N)^{-5/2}\rho^{-n+N},\quad\text{for }n,N,n-N\to\infty$

_and for some constants $A,A^{\prime}>0$. Moreover, for this range of $N$, we
obtain that with high probability, a random unlabelled forest contains a huge
tree with $n-N+\mathcal{O}\left(1\right)$ vertices, and
$N+\mathcal{O}\left(1\right)$ “trivial” trees that consist of a single vertex.
This is in stark contrast to the known behaviour of random labelled forests,
see Section 1.2 for a detailed discussion, but also from unlabelled models
such as random unrooted ordered forests, cf. [8]. _

We proceed with an application of our results to Benjamini-Schramm convergence
of unlabelled graphs with many components. The Benjamini-Schramm limit of a
sequence of graphs describes what a uniformly at random chosen vertex
typically sees in its neighbourhood and is a special instance of local weak
convergence, see also [2, 6]. Given a graph $G=(V,E)$ we form the _rooted_
graph $(G,o)$ by distinguishing a vertex $o\in V$. Let ${\mathcal{B}}$ be the
collection of all these rooted graphs. Then two graphs $(G,o)$ and
$(G^{\prime},o^{\prime})$ in ${\mathcal{B}}$ are called isomorphic,
$(G,o)\simeq(G^{\prime},o^{\prime})$, if there exists an edge-preserving
bijection $\Phi$ on the vertex sets of $G$ and $G^{\prime}$ such that
$\Phi(o)=o^{\prime}$. Hence, the collection
${\mathcal{B}}_{*}={\mathcal{B}}/{\simeq}$ of equivalence classes in
${\mathcal{B}}$ under the relation $\simeq$ contains all unlabelled rooted
graphs.

Set $B_{k}(G,o)$ to be the induced subgraph of $(G,o)\in{\mathcal{B}}_{*}$
containing all vertices within graph distance $k$ from the root $o$. Then we
say that a sequence of (labelled or unlabelled) simple connected locally
finite graphs $(\mathsf{G}_{n})_{n\geq 1}$ (possibly random) converges in the
_Benjamini-Schramm_ (BS) sense to a limiting object
$(\mathbbmss{G},\mathbbmss{o})\in{\mathcal{B}}_{*}$ if for a vertex $o_{n}$
being selected uniformly at random from $\mathsf{G}_{n}$

$\displaystyle\lim_{n\to\infty}\mathrm{Pr}\left[B_{k}(\mathsf{G}_{n},o_{n})\simeq(G,o)\right]=\mathrm{Pr}\left[B_{k}(\mathbbmss{G},\mathbbmss{o})\simeq(G,o)\right],\quad
k\in\mathbb{N},(G,o)\in{\mathcal{B}}_{*}.$ (1.4)

Back to our setting, we consider ${\mathcal{C}}$ to be a class of unlabelled
finite connected graphs (with subexponential counting sequence and
$m\in\mathbb{N}$ denotes the size of the smallest possible graph in
${\mathcal{C}}$) such that ${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$ is the
class of unlabelled graphs with connected components in ${\mathcal{C}}$. Let
as before $\mathsf{G}_{n,N}$ be drawn uniformly at random from
${\mathcal{G}}_{n,N}$. In order to adapt to the setting above we let
$(\mathsf{G}_{n,N},o_{n})$ denote the connected component around a uniformly
at random chosen root $o_{n}$ in $\mathsf{G}_{n,N}$. Let $\mathsf{C}_{n}$ be
drawn uniformly at random from ${\mathcal{C}}_{n}:=\\{C\in{\mathcal{C}}:\lvert
C\rvert=n\\}$. With this at hand, the extension of BS convergence to non-
connected graphs is evident and we obtain the following result.

######  Proposition 1.4.

Suppose that $C(x)$ is subexponential. Assume that $mN/n\to\lambda\in[0,1)$ as
$n,N\to\infty$. If the sequence $(\mathsf{C}_{n})_{n\geq 1}$ converges to a
limit object $(\mathbbmss{C},\mathbbmss{o})$ in the BS sense, then
$\mathsf{G}_{n,N}$ converges as $n,N\to\infty$ to a limit object
$(\mathbbmss{G},\mathbbmss{o})$ in the BS sense given by the law

$(1-\lambda)\delta_{(\mathbbmss{C},\mathbbmss{o})}+\lambda\delta_{(C_{m},o_{m})},$

where $o_{m}$ is a vertex chosen uniformly at random among the $m$ vertices in
$\mathsf{C}_{m}$. In particular, if $N=o(n)$ we have that
$(\mathbbmss{G},\mathbbmss{o})=(\mathbbmss{C},\mathbbmss{o})$.

The proof is found in Section 3.5. The authors of [21] show that any
subcritical class ${\mathcal{C}}$ of connected unlabelled graphs fulfils the
conditions of Proposition 1.4. In the subcritical setting the BS limit of
connected unlabelled rooted graphs is also the BS limit of the respective
unrooted graphs as shown in [44]. In particular, prior to these works it was
shown in [47, 46] that the BS limits of unlabelled unrooted trees and of
unlabelled rooted trees, also called Pólya trees, both exist and coincide.
Additionally, this limit, say $(\mathbbmss{T},\mathbbmss{o})$, is made
explicit in these publications.

##### Example (further continued)

_We obtain with Proposition 1.4 that the BS limit
$(\mathbbmss{F},\mathbbmss{o})$ of $\mathsf{F}_{n,N}$ drawn uniformly at
random from all unlabelled forests of size $n$ and being composed of $N$ trees
has law, assuming that $N/n\to\lambda\in[0,1)$ as $n,N\to\infty$,_

$(1-\lambda)\delta_{(\mathbbmss{T},\mathbbmss{o})}+\lambda\delta_{{\mathcal{X}}},$

_where ${\mathcal{X}}$ is a single rooted vertex. In other words, with
probability $1-\lambda$ the neighbourhood of a uniformly at random chosen
vertex from $\mathsf{F}_{n,N}$ looks like the infinite tree $\mathbbmss{T}$
and with probability $\lambda$ the neighbourhood is empty. _

##### Proof Strategy

The main idea in the proof is to consider a randomized algorithm/stochastic
process that generates $\cal C$-multisets. As it turns out, such an algorithm
that outputs elements from ${\mathcal{G}}$ (with a priori _no control_ on the
size or the number of components!) can be designed by defining the so-called
Boltzmann distribution on ${\mathcal{G}}$, see Section 3.1 for all details.
The crucial property of this algorithm is that all choices it makes are
_independent_. Our first contribution is to establish explicitly the
connection between the choices of the algorithm and its output; hence the
probability that the output is in ${\mathcal{G}}_{n,N}$ can be linked to an
event regarding the actual choices of the algorithm. Our second and main
contribution is to actually compute the probability of this event; as we will
see, this is not at all an easy task, since the involved random variables are
not identically distributed and interfere in a complex way with the parameters
of the generated object.

In contrast to this work, most proofs in the literature about enumeration of
multisets are either conducted from a purely analytical generating function
perspective or involve somehow the _conditioning relation_ representing the
(heavily dependent) number of component frequencies in $\mathsf{G}_{n}$ of a
particular size by independent random variables with negative binomial
distributions. This is related to the alternative (and equivalent)
representation of the generating function for $\cal C$-multisets (1.1) given
by

$G(x,y)=\prod_{k\geq 1}(1-yx^{k})^{-c_{k}}.$ (1.5)

As opposed to analysing the component spectrum in [34, 22, 4, 3], our
arguments are in the style of [48, 41, 45, 46, 39]: we use the Pólya-Boltzmann
model representing $\mathsf{G}_{n}$ as random ${\mathcal{C}}$-objects attached
to cycles of a random permutation, which is helpful to get rid of cumbersome
appearances of symmetries and which gives rise to Poisson distributions
instead of negative binomials; this difference is reflected by the two
different representations (1.1) and (1.5). Then we show that the size
associated to fixpoints is dominant and the subexponentiality-feature often
referred to as “single big jump” guarantees that in fact only one object
receives the entire possible size.

##### Plan of the Paper

Subsequently, we embed our results in the corpus of existing literature in
Section 1.1. In Section 1.2 we compare the labelled and the unlabelled setting
in light of our results. Then we collect and prove some results about
subexponential power series tailored to our needs in Section 2. In Section 3
all proofs are presented, where each of the main results is treated in an
extra subsection, such that Theorem 1.1 is proven in Section 3.2, Theorem 1.2
in Section 3.3 and Theorem 1.3 in Section 3.4.

##### Notation

We shall use the following (standard) notation. Given two real-valued
sequences $(a_{k})_{k\in\mathbb{N}}$ and $(b_{k})_{k\in\mathbb{N}}$ with
$b_{k}\neq 0$ for all $k\geq k_{0}$ for some $k_{0}\in\mathbb{N}$, we write,
as $n\to\infty$,

  * i)

$a_{n}\sim b_{n}$ (“$a_{n}$ is asymptotically equal to $b_{n}$”) if
$\lim_{n\to\infty}a_{n}/b_{n}=1$,

  * ii)

$a_{n}\propto b_{n}$ (“$a_{n}$ is asymptotically proportional to $b_{n}$”) if
there exist $0<A_{1}\leq A_{2}$ such that

$A_{1}\leq\liminf_{n\to\infty}\bigl{\lvert}\frac{a_{n}}{b_{n}}\bigr{\rvert}\leq\limsup_{n\to\infty}\bigl{\lvert}\frac{a_{n}}{b_{n}}\bigr{\rvert}\leq
A_{2},$

  * iii)

$a_{n}=o(b_{n})$ if $\lim_{n\to\infty}a_{n}/b_{n}=0$.

For a sequence of real-valued random variables $(X_{k})_{k\in\mathbb{N}}$ and
a non-negative sequence $(a_{k})_{k\in\mathbb{N}}$ we write
$X_{n}=\mathcal{O}_{p}(a_{n})$ (“$X_{n}$ is stochastically bounded by
$a_{n}$”) if for all $\varepsilon>0$ there exists $K>0$ such that
$\limsup_{n\to\infty}\mathrm{Pr}\left[\lvert X_{n}\rvert\geq
Ka_{n}\right]\leq\varepsilon$. In the case $a_{k}\equiv 1$ we simply say
“$X_{n}$ is stochastically bounded”.

We will use the following notation for formal power series. For a
$k$-dimensional vector of formal variables $\mathbf{x}=(x_{1},\dots,x_{k})$
and $\mathbf{d}=(d_{1},\dots,d_{k})\in\mathbb{N}_{0}^{k}$ we write
$\mathbf{x}^{\mathbf{d}}$ for the monomial $x^{d_{1}}_{1}\cdots
x^{d_{k}}_{k}$. A multivariate power series with real-valued coefficients is
given by
$A(\mathbf{x})=\sum_{\mathbf{d}\in\mathbb{N}_{0}^{k}}a_{\mathbf{d}}\mathbf{x}^{\mathbf{d}}$,
where the $a_{\mathbf{d}}$’s are in $\mathbb{R}$. For
$\mathbf{d}\in\mathbb{N}_{0}^{k}$ we write
$[\mathbf{x}^{\mathbf{d}}]A(\mathbf{x})=a_{\mathbf{d}}$ for the coefficient of
$\mathbf{x}^{\mathbf{d}}$.

###  1.1 (More) Related Work

In this section we put our results in the broader context of (asymptotic)
enumeration of multisets/weighted integer partitions. The most prominent
assumption is that the counting sequence of ${\mathcal{C}}$ fulfils
$c_{n}\sim\lambda(n)\cdot n^{-\alpha}\cdot\rho^{-n}$ as $n\to\infty$ for some
slowly varying function $\lambda(\cdot)$ and parameters
$\alpha\in\mathbb{R},0<\rho\leq 1$. Then there emerge three cases depending on
the parameter $\alpha$ determining the behaviour of $C(x)=\sum_{k\geq
1}c_{k}x^{k}$ at or near its radius of convergence $\rho$, each giving rise to
a fundamentally different picture.

In the _expansive_ case $\alpha<1$, which in particular includes the classical
and prominent setting $c_{k}\equiv 1$ of integer partitions, the number of
$\cal C$-multisets $g_{n}=|{\cal G}_{n}|$ is well-understood [22]. However,
general results about the uniformly drawn element $\mathsf{G}_{n}$ – in
particular the distribution of the number of components that is of interest
here – are not known without any extra conditions. For example, under the
assumption of _Meinardus_ scheme of conditions, a set of analytic assumptions
that in particular imply that $\rho=1$, the number of components of
$\mathsf{G}_{n}$ fulfils various local limit theorems, see [34]. The authors
of [24] state that expansive multisets with counting sequence
$c_{k}=Ck^{-\alpha}$ for some $C>0$ fulfil Meinardus conditions. For example,
integer partitions $(c_{k}=1)$ and plane partitions $(c_{k}=k)$ are
encapsulated by this approach. Hence, they call the Meinardus case _quasi-
expansive_. For quasi-expansive sequences it is established in [35] that the
size of the largest component of $\mathsf{G}_{n}$ is with high probability of
size $\Theta(1)\cdot n^{1/(2-\alpha)}\log n$. The broader picture here is that
the number of components in $\mathsf{G}_{n}$ is typically unbounded and the
size of the largest component is sublinear in $n$. On the other hand, much
less is known for the number of $\cal C$-multisets with $N$ components
$g_{n,N}=|{\cal G}_{n,N}|$ and the typical shape of $\mathsf{G}_{n,N}$ for
arbitrary $1\leq N\leq n$. Nevertheless, there is one important exception,
namely the case of integer partitions. There, depending on whether $N$ is
$\mathcal{O}(n^{1/2})$ or $\omega(n^{1/2})$ the asymptotic behaviour of the
number of partitions of $n$ into $N$ parts is given by different formulas, see
[29]. For $N\geq(1+\varepsilon)/(\sqrt{2/3}\pi)\sqrt{n}\log n$ for any
$0<\varepsilon<1$ it is even true that $g_{n,N}\sim g_{n-N}$ [26]. In general,
it is reasonable to conjecture that the shape of $\mathsf{G}_{n,N}$ depends on
the asymptotic regime of $N$; this, however, is a topic for a completely
different paper.

The _logarithmic_ case, where $\alpha=1$ and $\lambda\equiv\lambda(\cdot)$
constant, is concomitant with similar effects. The number of components in
$\mathsf{G}_{n}$ is typically of order $\lambda\log n$ [3, Thm. 8.21] and,
denoting by $(L_{1},\dots,L_{N})$ the $N$ largest component sizes of
$\mathsf{G}_{n}$, then $n^{-1}(L_{1},\dots,L_{N})$ has a limiting distribution
that is Poisson-Dirichlet [3, Thm. 6.8] implying that $\mathsf{G}_{n}$ is
composed of several “large” objects. The same is true for $\mathsf{G}_{n,N}$
with $N\in\mathbb{N}$ fixed, where the $N-1$ smallest components have with
high probability sizes $(n^{U_{i}})_{1\leq i\leq N-1}$ for iid uniformly
distributed random variables $(U_{i})_{1\leq i\leq N-1}$ [3, Thm. 6.9]. To our
knowledge, there are no results (regarding asymptotic enumeration or
structural properties) for all other $N$.

In contrast to all previous cases, the phenomenon of condensation is observed
in the _convergent_ case, where $\alpha>1$: the single largest component of
$\mathsf{G}_{n}$ is of size $n-\mathcal{O}_{p}(1)$ and its number of
components converges in distribution, see [4]. In accordance with the results
observed for the convergent case the number of components in $\mathsf{G}_{n}$
in the subexponential setting has a limiting distribution given by a weighted
sum of independent Poisson random variables [5]. Equivalently, this means that
$g_{n,N}$ can be determined asymptotically for _fixed_ values of
$N\in\mathbb{N}$. As for the global shape of $\mathsf{G}_{n}$, the results in
[48] imply that the remainder obtained after removing the largest component
converges in distribution to a limit given by the so-called Pólya-Boltzmann
distribution, see [9].

###  1.2 Discussion - The Unlabelled vs. the Labelled Setting

In what follows we will have a closer look at the resemblances and surprising
disparities between multisets, which are typically associated to _unlabelled_
structures, and sets of _labelled_ combinatorial structures. We refer the
reader to the books [18, 30] for an excellent exposition to combinatorial
classes. Another vast source of references and examples is the tour-de-force
paper [28] entailing many results about the _balls-in-boxes_ model (Section
11), which by choosing the weight sequence $(c_{k}/k!)_{k\in\mathbb{N}}$
implies the labelled set-construction.

Given a labelled class ${\mathcal{C}}^{\iota}$ we may form the analogon to the
multiset construction discussed in this work. Initially we pick
$C_{1},\dots,C_{k}$ from ${\mathcal{C}}^{\iota}$ and let $n$ be the total
size. Then we partition $\\{1,\dots,n\\}$ into sets $L_{1},\dots,L_{k}$ such
that $L_{i}=\lvert C_{i}\rvert$ for all $i$. Subsequently, we canonically
assign the labels in $L_{i}$ to $C_{i}$ for all $i$. The outcome of this
procedure is a labelled set, where each of the labels in $\\{1,\dots,n\\}$
appears exactly once. The notion of size and number of components carries over
from the multiset construction. Let us call the collection of all such
labelled sets ${\mathcal{G}}^{\iota}=\text{{Set}}({\mathcal{C}}^{\iota})$ and
introduce the sets ${\mathcal{G}}^{\iota}_{n}$ and
${\mathcal{G}}^{\iota}_{n,N}$ of objects in ${\mathcal{G}}^{\iota}$ of size
$n$ and of size $n$ having $N$ components, respectively. Further, let
$c^{\iota}_{k}:=\lvert\\{C\in{\mathcal{C}}^{\iota}:\lvert C\rvert=k\\}\rvert$
for $k\in\mathbb{N}$. Similarly to (1.1) the bivariate (exponential)
generating series related to this case is known ([18, 30]) to be

$G^{\iota}(x,y)=\exp\left(yC^{\iota}(x)\right),\quad\text{where
}C^{\iota}(x)=\sum_{k\geq 1}c_{k}^{\iota}\frac{x^{k}}{k!}.$

In complete analogy to the unlabelled case we are here intrerested in the
number $g^{\iota}_{n,N}=\lvert{\mathcal{G}}^{\iota}_{n,N}\rvert$ of sets of
size $n$ and $N$ components, and for properties of the uniform random elements
$\mathsf{G}^{\iota}_{n}$ and $\mathsf{G}^{\iota}_{n,N}$ from ${\cal
G}^{\iota}_{n}$ and ${\cal G}^{\iota}_{n,N}$, respectively.

First of all, the case $N=\mathcal{O}\left(1\right)$ is treated (together with
the unlabelled case) in [5]. There it is shown that in the subexponential
setting both $\kappa(\mathsf{G}_{n})$ and $\kappa(\mathsf{G}^{\iota}_{n})$
converge in distribution; hence, for a fixed number of components the labelled
and unlabelled cases behave qualitatively the same. Also the global structure
of the associated random variables $\mathsf{G}_{n}$ and
$\mathsf{G}^{\iota}_{n}$ is in both cases governed by the same condensation
effect, see [45, 48]. However, the situation changes as $N\to\infty$. The
works [38, 28] treat this topic extensively222In particular we want to
highlight [28, Theorems 18.12, 18.14, 19.34, 19.49].: under the condition that
$c_{n}^{\iota}\sim bn^{-(1+\alpha)}\rho^{-n}n!$ for $b>0$ and $\alpha>1$ as
$n\to\infty$ there emerges a “trichotomy” ($1<\alpha\leq 2$) and in some cases
a “dichotomy” ($\alpha>2$) depending on the asymptotic regime of $N$. To
illustrate the nature of these results, let us consider the class of labelled
trees ${\mathcal{T}}^{\iota}$ such that
${\mathcal{F}}^{\iota}=\text{{Set}}({\mathcal{T}}^{\iota})$ is the class of
labelled forests. The well-known formula by Cayley states that
$t^{\iota}_{n}=n^{n-2}\sim(2\pi)^{-1/2}n^{-5/2}\mathrm{e}^{n}n!$, so that
$\alpha=3/2$. Abbreviating by $f^{\iota}_{n,N}$ the number of forests on $n$
nodes and $N$ trees, the following detailed result exposing two phase
transitions is known. Let $N:=\lfloor\lambda n\rfloor$, then

$\displaystyle\frac{N!}{n!}\cdot
f^{\iota}_{n,N}\sim\begin{cases}c_{-}(\lambda)n^{-3/2}\mathrm{e}^{n}2^{-N},&\lambda\in(0,1/2)\\\
cn^{-2/3}\mathrm{e}^{n}2^{-N},&\lambda=1/2\\\
c_{+}(\lambda)n^{-1/2}f(\lambda)^{n},&\lambda\in(1/2,1)\end{cases},\quad
n\to\infty,$

for positive real-valued continuous functions $c_{-/+}(\lambda),f(\lambda)$
and a constant $c$; note that the critical exponent jumps form $3/2$ to $2/3$
and then to $1/2$. All in all, the main results of the present paper reveal
substantial differences between the labelled and the unlabelled case already
at the level of the counting sequences: as we stated before in our example,
the number of unlabelled forests of size $n$ with $N=\lfloor\lambda n\rfloor$
components is asymptotically equal to
$A\cdot(1-\lambda)^{-5/2}n^{-5/2}\rho^{n-N}$; in particular, the critical
exponent does not vary.

The aforementioned variation in the critical exponent has also important
consequences for the global structure of a labelled forest
$\mathsf{F}^{\iota}_{n,N}$ drawn uniformly at random from the set of labelled
forests of size $n$ composed of $N$ trees. Three different cases emerge as $n$
approaches infinity:

  1. 1.

In the case where there are “few” components ($0<\lambda<1/2$), most of the
mass is concentrated in one large tree containing a linear fraction (that is
$1-2\lambda$) of all nodes and the remaining $N-1$ trees all have size
$\mathcal{O}_{p}(n^{2/3})$.

  2. 2.

In the case where the ratio between components and total size is “balanced”
($\lambda=1/2$) all trees have size $\mathcal{O}_{p}(n^{2/3})$.

  3. 3.

Whenever there are “many” components with respect to the total number of nodes
($1/2<\lambda<1$), all trees are small in the sense that their size is
stochastically bounded by $\log n$.

For a detailed discussion for what happens near the critical point
$\lambda=1/2$ see also [31]. This is again substiantially different to the
unlabelled case, where we showed that extreme condensation dominates the
picture for all values of $N$.

##  2 Subexponential Power Series

In this section we collect (and prove) some properties of subexponential power
series that will be quite handy in the rest of paper. Many of the definitions
and statements shown here are taken from Embrechts and Omey [16] or Foss,
Korshunov, and Zachary [20] and adapted to the discrete case, see also Stufler
[48].

######  Definition 2.1.

A power series $C(x)=\sum_{k\geq 0}c_{k}x^{k}$ with non-negative coefficients
and radius of convergence $0<\rho<\infty$ is called _subexponential_ if

$\displaystyle\frac{1}{c_{n}}\sum_{0\leq k\leq n}c_{n-k}c_{k}$
$\displaystyle\sim 2C(\rho)<\infty\quad\text{and}$ ($S_{1}$)
$\displaystyle\frac{c_{n-1}}{c_{n}}$ $\displaystyle\sim\rho,\quad n\to\infty.$
($S_{2}$)

Note that the radius of convergence of a power series $C(x)$ satisfying
($S_{2}$) (in particular of any subexponential power series) is $\rho$ and
that eventually $[x^{n}]C(x)>0$, where as usual, $[x^{n}]C(x)=c_{n}$ denotes
the coefficient of $x^{n}$ in $C(x)$. Any arbitrary subexponential power
series $C(x)$ with radius of convergence $\rho$ induces the probability
generating series of a $\mathbb{N}_{0}$-valued random variable by setting

$d_{k}:=\frac{c_{k}\rho^{k}}{C(\rho)},\quad n\in\mathbb{N}_{0}.$

Then $D(x)=\sum_{k\geq 0}d_{k}x^{k}$ is subexponential with $\rho=1$ and
$D(\rho)=1$. There are several results about the asymptotic behaviour of sums
of random variables with such a subexponential generating series. Here we will
need Lemma 2.2 (i) below, which corresponds to determining the probability
that a randomly stopped sum of random variables with distribution
$(d_{k})_{k\geq 0}$ attains a large value. Moreover, Lemma 2.2 (ii) will be
particularly useful, since it provides bounds holding uniformly in the given
parameters. In Lemma 2.2 (iii) we present and prove a statement often referred
to – with various interpretations – as “principle of a single big jump”. The
dominant contribution to a large sum of subexponential random variables stems
typically from one single summand.

######  Lemma 2.2.

Let $(D_{i})_{i\in\mathbb{N}}$ be iid $\mathbb{N}_{0}$-valued random variables
with probability generating function $D(x)$. Assume that $D(x)$ is
subexponential with radius of convergence $1$. For $p\in\mathbb{N}$ let
$S_{p}:=\sum_{1\leq i\leq p}D_{i}$ and $M_{p}:=\max\\{D_{1},\dots,D_{p}\\}$.
Then the following statements are true.

  1. (i)

[20, Theorem 4.30] Let $\tau$ be a $\mathbb{N}_{0}$-valued random variable
independent of $(D_{i})_{i\in\mathbb{N}}$. Further, assume that the
probability generating function of $\tau$ is analytic at $1$. Then

$\mathrm{Pr}\left[S_{\tau}=n\right]\sim\mathbb{E}\left[\tau\right]\mathrm{Pr}\left[D_{1}=n\right],\quad
n\to\infty.$

  2. (ii)

[20, Theorem 4.11] For every $\delta>0$ there exists $n_{0}\in\mathbb{N}$ and
a $C>0$ such that

$\mathrm{Pr}\left[S_{p}=n\right]\leq
C(1+\delta)^{p}\mathrm{Pr}\left[D_{1}=n\right],\quad\text{for all }n\geq
n_{0},\leavevmode\nobreak\ p\in\mathbb{N}.$

  3. (iii)

For any $p\geq 2$

$(M_{p}\mid S_{p}=n)=n+\mathcal{O}_{p}(1),\quad n\to\infty.$

###### Proof of Lemma 2.2 (iii).

Let $\varepsilon>0$ be arbitrary. To prove the claim we will establish the
existence of $K\in\mathbb{N}$ such that

$\lim_{n\to\infty}\mathrm{Pr}\left[\lvert M_{p}-n\rvert\geq K\mid
S_{p}=n\right]<\varepsilon.$

Clearly under the condition $S_{p}=n$ we have $M_{p}\leq n$. Thus

$\displaystyle\mathrm{Pr}\left[\lvert M_{p}-n\rvert\geq K\mid
S_{p}=n\right]=\sum_{k\geq K}\mathrm{Pr}\left[M_{p}=n-k\mid S_{p}=n\right].$
(2.1)

Since $D_{1},\dots,D_{p}$ are iid we obtain for any $k\geq K$

$\mathrm{Pr}\left[M_{p}=n-k\mid
S_{p}=n\right]\leq\mathrm{Pr}\left[\bigcup_{1\leq i\leq p}\\{D_{i}=n-k\\}\mid
S_{p}=n\right]=p\frac{\mathrm{Pr}\left[D_{1}=n-k\right]\mathrm{Pr}\left[S_{p-1}=k\right]}{\mathrm{Pr}\left[S_{p}=n\right]}.$

Together with Lemma 2.2 (ii) we find some constant $C>0$ such that for $k\geq
K$ sufficiently large

$\mathrm{Pr}\left[S_{p-1}=k\right]\leq
C(1+\varepsilon)^{p-1}\mathrm{Pr}\left[D_{1}=k\right].$

Part (i) justifies for $n$ sufficiently large that
$\mathrm{Pr}\left[S_{p}=n\right]\geq(1-\varepsilon)p\mathrm{Pr}\left[D_{1}=n\right].$
All in all, for a suitably chosen constant $C(p)$ the expression in (2.1) can
be estimated by

$\mathrm{Pr}\left[\lvert M_{p}-n\rvert\geq K\mid S_{p}=n\right]\leq
C(p)\sum_{k\geq
K}\frac{\mathrm{Pr}\left[D_{1}=n-k\right]\mathrm{Pr}\left[D_{1}=k\right]}{\mathrm{Pr}\left[D_{1}=n\right]}.$

Due to property ($S_{1}$) we conclude that this is smaller than $\varepsilon$
choosing $K$ large enough and the proof is finished. ∎

The following lemma establishes asymptotics for the coefficients of the
product of two power series.

######  Lemma 2.3.

[10, Thm. 3.42] or [43, Ex. 178] Let $A(x),B(x)$ be power series such that $A$
satisfies ($S_{2}$). Assume that the radii of convergence $\rho_{A}$ and
$\rho_{B}$ of $A$ and $B$, respectively, satisfy $0<\rho_{A}<\rho_{B}$ and
$B(\rho_{A})\neq 0$. Then

$[x^{n}]A(x)B(x)\sim B(\rho_{A})\cdot[x^{n}]A(x),\quad n\to\infty.$

Note that Lemma 2.3 does not require $A$ to be subexponential, neither does it
require that $B$ has non-negative coefficients only. We will later apply the
lemma with (powers of)

$A(x):=\frac{1}{1-\rho_{A}^{-1}x}=\sum_{k\geq 0}(\rho_{A}^{-1}x)^{k}$

for some $\rho_{A}>0$. Then $A(x)$ has $\eqref{eq:subexp2}$ with radius of
convergence $\rho_{A}$ but $A(\rho_{A})=\infty$; in particular, property
$\eqref{eq:subexp1}$ is not satisfied and $A$ is not subexponential.

As a final remark in this section we make the following observation, which we
shall use mostly without further reference. Suppose that for two sequences
$(a_{n})_{n\in\mathbb{N}_{0}},(b_{n})_{n\in\mathbb{N}_{0}}$ in $\mathbb{R}$ we
know that $a_{n}\sim b_{n}$ as $n\to\infty$. Then the ratio $a_{n}/b_{n}$ is
bounded unless $b_{n}=0$, that is,

$a_{n}\sim b_{n}\implies\text{there is $A>0$ such that }a_{n}\leq
A|b_{n}|\text{ for all $n\in\mathbb{N}_{0}$ such that $b_{n}\neq 0$}.$ (2.2)

##  3 Proofs

We briefly (re-)collect all assumptions and fix the notation needed in this
section. Note that Theorem 1.1 is valid for real-valued sequences
$(c_{k})_{k\in\mathbb{N}}$ whereas the remaining theorems are only reasonable
in a combinatorial setting. We will hence put everything into a combinatorial
context and outsource the few modifications needed for the general real-valued
setting into Section 3.1.1.

For a combinatorial class ${\mathcal{C}}$ let $C(x)=\sum_{k\geq 1}c_{k}x^{k}$
denote a power series with coefficients
$c_{k}:=\lvert\\{C\in{\mathcal{C}}:\lvert C\rvert=k\\}\rvert$,
$k\in\mathbb{N}$. Further, let

$m=m_{C}:=\min\\{k\in\mathbb{N}\leavevmode\nobreak\ :\leavevmode\nobreak\
c_{k}>0\\}$ (3.1)

be the index of the first coefficient that does not equal zero. We also assume
that $C(x)$ is subexponential, which implies that the radius of convergence
fulfils $0<\rho<1$. However, the subexponentiality feature is only needed in
the very last step of the proof, cf. Lemma 3.10; all other statements
preceding this lemma are valid even without this asssumption as long as
$0<\rho<1$. Further we define $G(x,y):=\exp\left(\sum_{j\geq
1}C(x^{j})y^{j}/j\right)$ and $G(x):=G(x,1)$. We begin with two auxiliary
statements. The first one is about the radius of convergence of $G(x)$.

######  Lemma 3.1.

Assume that $C(x)$ is a power series with non-negative real-valued
coefficients and radius of convergence $0<\rho<1$ and $C(0)=0$,
$C(\rho)<\infty$. Then $G(x)$ has radius of convergence $\rho$ and
$G(\rho)<\infty$.

###### Proof.

From the definition of $G$ we obtain that $G(x)=e^{C(x)}H(x)$, where $\log
H(x)=\sum_{j\geq 2}C(x^{j})/j$. Since $\rho\in(0,1)$ we obtain for any
$\varepsilon>0$ such that $(1+\varepsilon)\rho^{2}<\rho$ and any $j\geq 2$

$C\big{(}(1+\varepsilon)\rho^{j}\big{)}=\sum_{k\geq
1}c_{k}(1+\varepsilon)^{k}\rho^{jk}=(1+\varepsilon)\rho^{j}\sum_{k\geq
1}c_{k}((1+\varepsilon)\rho^{j})^{k-1}<(1+\varepsilon)\rho^{j-1}C(\rho).$

In particular, $H((1+\varepsilon)\rho)<\infty$ and the radius of convergence
of $H$ is larger than $\rho$. Thus, the radius of convergence of $G$ is
$\rho$, and $G(\rho)=e^{C(\rho)}H(\rho)<\infty$. ∎

The second statement is a purely technical result that we will be handy.

######  Lemma 3.2.

[18, Theorem VI.1] Let $\alpha,\beta\in\mathbb{R}_{+}$. Then

$[x^{n}](1-\beta
x)^{-\alpha}\sim\frac{n^{\alpha-1}}{\Gamma(\alpha)}\beta^{n},\quad
n\to\infty.$

In the remaining part of this section we introduce the Boltzmann model as
helpful tool to reduce our problems to the investigation of iid random
variables in Section 3.1. Subsequently, we present the proofs of our three
main theorems in Sections 3.2-3.4. At last we prove Proposition 1.4 in Section
3.5.

###  3.1 Setup and Notation

In this section we will introduce the _Boltzmann model_ from the pioneering
paper [15], which has found various applications in the study of the typical
shape of combinatorial structures, see for example [14, 1, 45, 42, 13, 11, 7,
40]. With the help of this model we translate the initial problem of
extracting coefficients of the multiset ogf of unlabelled classes into a
probabilistic question. This gives us the proper idea for the general approach
for arbitrary functions of the form (1.1), i.e. when the coefficients are not
necessarily integers. Further, the formalisation via this model will allow us
to prove the extreme condensation phenomenon.

Assume that $z\in\mathbb{R}_{+}$ is chosen such that $C(z)>0$ is finite. The
unlabelled Boltzmann model defines a random variable $\Gamma C(z)$ taking
values in the entire space ${\mathcal{C}}$ through

$\mathrm{Pr}\left[\Gamma C(z)=C\right]=\frac{z^{\left|C\right|}}{C(z)},\quad
C\in{\mathcal{C}}.$

In complete analogy the random variable $\Gamma G(z)$ is defined on
${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$ of multisets containing
${\mathcal{C}}$-objects, where in this case the parameter $z>0$ is such that
$G(z):=G(z,1)<\infty$ in (1.1). In the rest of this section we fix $z=\rho$
recalling that $0<\rho<1$ is the radius of convergence of $C$. Then, in virtue
of Lemma 3.1, $G$ has radius of convergence $\rho$ and $G(\rho)<\infty$, so
that both $\Gamma C(\rho),\Gamma G(\rho)$ are well-defined, and we just write
$\Gamma C,\Gamma G$.

Let $g_{n}$ be the number of objects of size $n$ in ${\mathcal{G}}$ and
$g_{n,N}$ those of size $n$ comprised of $N$ components. By using Bayes’
Theorem and that the Boltzmann model induces a uniform distribution on objects
of the same size, we immediately obtain

$\frac{g_{n,N}}{g_{n}}=\mathrm{Pr}\left[\kappa(\Gamma G)=N\mid\left|\Gamma
G\right|=n\right]=\mathrm{Pr}\left[\left|\Gamma G\right|=n\mid\kappa(\Gamma
G)=N\right]\frac{\mathrm{Pr}\left[\kappa(\Gamma
G)=N\right]}{\mathrm{Pr}\left[\left|\Gamma
G\right|=n\right]},\leavevmode\nobreak\ \leavevmode\nobreak\
n,N\in\mathbb{N}.$ (3.2)

To get a handle on this expression we exploit a powerful description of the
distribution of $\Gamma G(z)$ in terms of $\Gamma C(\cdot)$, derived in [19].
In the next steps, the notation $\bigsqcup_{j\in J}A_{j}$ is used to denote a
multiset of elements $A_{j}$ from a set $\mathcal{A}$, $j\in J$ being indices
in some countable set $J$. That is, multiple occurrences of identical elements
are allowed and $\bigsqcup_{j\in J}A_{j}$ is completely determined by the
different elements it contains and their multiplicities.

  1. (1)

Let $(P_{j})_{j\geq 1}$ be independent random variables, where
$P_{j}\sim\mathrm{Po}\left(C(\rho^{j})/j\right)$.

  2. (2)

Let $(\gamma_{j,i})_{j,i\geq 1}$ be independent random variables with
$\gamma_{j,i}\sim\Gamma C(\rho^{j})$ for $j,i\geq 1$.

  3. (3)

For $j,i\geq 1$ and $1\leq k\leq j$ set $\gamma_{j,i}^{(k)}=\gamma_{j,i}$,
that is, make $j$ copies of $\gamma_{j,i}$. Let $\Lambda G:=\bigsqcup_{j\geq
1}\bigsqcup_{1\leq i\leq P_{j}}\bigsqcup_{1\leq k\leq j}\gamma_{j,i}^{(k)}$.

Intuitively, we interpret $P_{j}$ as the number of $j$-cycles in some not
further specified permutation and to each cycle of length $j$ we attach $j$
times an identical copy of a $\Gamma C(\rho^{j})$-distributed
${\mathcal{C}}$-object. Afterwards we discard the permutation and the cycles
and keep the multiset of the generated ${\mathcal{C}}$-objects. This
construction is also made explicit in [9, Prop. 37].

######  Lemma 3.3.

[19, Prop. 2.1] The distributions of $\Gamma G$ and $\Lambda G$ are identical.

This statement paves the way to study $\Gamma G$. In particular, if we write
$C_{j,i}=|\gamma_{j,i}|$, note that the definition of $\Lambda G$ guarantees
that in distribution

$\kappa(\Gamma G)=\sum_{j\geq 1}jP_{j}\quad\text{and}\quad|\Gamma
G|=\sum_{j\geq 1}j\sum_{1\leq i\leq P_{j}}C_{j,i}.$

So, let us for $n,N\in\mathbb{N}$ define the events

$\displaystyle{\mathcal{P}}_{N}:=\left\\{\sum_{j\geq
1}jP_{j}=N\right\\}\quad\text{and}\quad{\mathcal{E}}_{n}:=\left\\{\sum_{j\geq
1}j\sum_{1\leq i\leq P_{j}}C_{j,i}=n\right\\}.$ (3.3)

With $\mathrm{Pr}\left[{\mathcal{E}}_{n}\right]=\mathrm{Pr}\left[\left|\Lambda
G\right|=n\right]=g_{n}\rho^{n}/G(\rho)$ at hand, Lemma 3.3 and (3.2) then
guarantee that

$\displaystyle
g_{n,N}=G(\rho)\rho^{-n}\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]\mathrm{Pr}\left[{\mathcal{P}}_{N}\right].$
(3.4)

Note that for all $1\leq i\leq P_{j}$ and $j\in\mathbb{N}$, we have

$\displaystyle\mathrm{Pr}\left[C_{j,i}=k\right]=\frac{c_{k}\rho^{jk}}{C(\rho^{j})},\quad
k\in\mathbb{N}.$ (3.5)

Equation (3.4) enables us to reduce the problem of determining
$g_{n,N}=[x^{n}y^{N}]G(x,y)$ to the problem of determining the probability of
the events ${\mathcal{P}}_{N}$ and ${\mathcal{E}}_{n}$ conditioned on
${\mathcal{P}}_{N}$.

####  3.1.1 Remarks to Theorem 1.1

In Theorem 1.1 we consider $(c_{k})_{k\in\mathbb{N}}$ to be a real-valued non-
negative sequence and assume $0<\rho<1$. In complete analogy to the discussion
prior to this subsection let $P_{j}\sim\mathrm{Po}\left(C(\rho^{j})/j\right)$
for $j\in\mathbb{N}$, $(C_{j,1},\dots,C_{j,P_{j}})_{j\in\mathbb{N}}$ be as in
(3.5), and assume that all these variables are independent. As a matter of
fact, also in this (more general) case we obtain exactly the same
representation of $[x^{n}y^{N}]G(x,y)$ in terms of ${\mathcal{E}}_{n}$ and
${\mathcal{P}}_{N}$ defined in (3.3) without using the combinatorial Boltzmann
model.

######  Lemma 3.4.

Let $C(x)$ be a power series with non-negative real-valued coefficients and
radius of convergence $0<\rho<1$ at which $C(\rho)<\infty$. Then

$[x^{n}y^{N}]G(x,y)=G(\rho)\rho^{-n}\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]\mathrm{Pr}\left[{\mathcal{P}}_{N}\right],\quad
n,N\in\mathbb{N}.$

###### Proof.

We begin with the simple observation

$\begin{split}\mathrm{Pr}\left[{\mathcal{P}}_{N},{\mathcal{E}}_{n}\right]&=[x^{n}y^{N}]\sum_{k\geq
0}\sum_{\ell\geq
0}\mathrm{Pr}\left[{\mathcal{P}}_{k},{\mathcal{E}}_{\ell}\right]x^{\ell}y^{k}\\\
&=[x^{n}y^{N}]\sum_{k\geq 0}y^{k}\sum_{\sum_{j\geq 1}jp_{j}=k}\prod_{j\geq
1}\mathrm{Pr}\left[P_{j}=p_{j}\right]\sum_{\ell\geq
0}\mathrm{Pr}\left[\sum_{j\geq 1}j\sum_{1\leq i\leq
p_{j}}C_{j,i}=\ell\right]x^{\ell}.\end{split}$ (3.6)

We will study this expresion by first simplifying the sum over $\ell$, then
the sum over all $p_{j}$’s, and eventually the sum over $k$. We begin with the
sum over $\ell$. For a $\mathbb{N}_{0}$-valued random variable $A$ let
$A(x):=\sum_{\ell\geq 0}\mathrm{Pr}\left[A_{j}=\ell\right]x^{\ell}$ denote its
probability generating series. Then, if $(A_{j})_{j\in\mathbb{N}}$ is a
sequence of independent $\mathbb{N}_{0}$-valued random variables,

$\displaystyle(A_{1}+\dots+A_{m})(x)=\prod_{1\leq j\leq m}A_{j}(x),\quad
m\in\mathbb{N}.$ (3.7)

Let us write $C_{j}(x)$ for the probability generating series of $jC_{j,i}$;
note that the actual value of $i$ is not important, since the
$(C_{j,i})_{i\in\mathbb{N}}$ are iid. Then, whenever $\sum_{j\geq 1}p_{j}$ is
finite, (3.7) implies

$\sum_{\ell\geq 0}\mathrm{Pr}\left[\sum_{j\geq 1}j\sum_{1\leq i\leq
p_{j}}C_{j,i}=\ell\right]x^{\ell}=\prod_{j\geq 1}C_{j}(x)^{p_{j}}.$

Noting that $jC_{j,1}$ takes only values in the lattice $j\mathbb{N}_{0}$, we
obtain

$C_{j}(x)=\sum_{\ell\geq
0}\mathrm{Pr}\left[jC_{j,1}=\ell\right]x^{\ell}=\sum_{\ell\geq
0}\mathrm{Pr}\left[C_{j,1}=\ell\right]x^{j\ell}=\frac{1}{C(\rho^{j})}\sum_{\ell\geq
0}c_{\ell}\rho^{\ell}x^{j\ell}=\frac{C((\rho x)^{j})}{C(\rho^{j})}.$

We deduce

$\sum_{\ell\geq 0}\mathrm{Pr}\left[\sum_{j\geq 1}j\sum_{1\leq i\leq
p_{j}}C_{j,i}=\ell\right]x^{\ell}=\prod_{j\geq 1}\left(\frac{C((\rho
x)^{j})}{C(\rho^{j})}\right)^{p_{j}}.$

This puts the sum over $\ell$ in (3.6) in compact form. To simplify the sum
over the $p_{j}$’s in (3.6) define independent random variables
$(H_{j})_{j\geq 1}$ with $H_{j}\sim\mathrm{Po}\left(C((\rho x)^{j})/j\right)$.
Then

$\sum_{\sum_{j\geq 1}jp_{j}=k}\prod_{j\geq
1}\mathrm{Pr}\left[P_{j}=p_{j}\right]\left(\frac{C((\rho
x)^{j})}{C(\rho^{j})}\right)^{p_{j}}=\frac{G(\rho
x,1)}{G(\rho,1)}\mathrm{Pr}\left[\sum_{j\geq 1}jH_{j}=k\right].$

By similar reasoning as before the probability generating function of $jH_{j}$
is given by

$\sum_{\ell\geq
0}\mathrm{Pr}\left[H_{j}=\ell\right]y^{j\ell}=\exp\left(-C((\rho
x)^{j})/j\right)\sum_{\ell\geq 0}\frac{(C((\rho
x)^{j})y^{j}/j)^{\ell}}{\ell!}=\frac{\exp\left(C((\rho
x)^{j})y^{j}/j\right)}{\exp\left(C((\rho x)^{j})/j\right)}.$

Applying (3.7), where we set $A_{j}:=jH_{j}$, in combination with this
identity and plugging everything into (3.6) yields

$\sum_{k\geq 0}\mathrm{Pr}\left[\sum_{j\geq
1}jH_{j}=k\right]y^{k}=\frac{G(\rho x,y)}{G(\rho)}.$

All in all, we have shown that
$\mathrm{Pr}\left[{\mathcal{P}}_{N},{\mathcal{E}}_{n}\right]=G(\rho)^{-1}[x^{n}y^{N}]G(\rho
x,y)$. With $[x^{n}]F(ax)=a^{n}[x^{n}]F(x)$ for any power series $F$ and
$a\in\mathbb{R}$ we finish the proof. ∎

###  3.2 Proof of Theorem 1.1

Let ${\mathcal{P}}_{N}$, ${\mathcal{E}}_{n}$ be as in the previous section,
see (3.3), where $P_{j}\sim\mathrm{Po}\left(C(\rho^{j})/j\right)$ and
$C_{j,1},\dots,C_{j,P_{j}}$ for ${j\in\mathbb{N}}$ have the distribution
specified in (3.5). Moreover, we assume that all these random variables are
independent. Equipped with Lemma 3.4 from the previous section, the proof of
Theorem 1.1 boils down to estimating
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]$ and
$\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]$. Before we actually do so, let us
introduce some more auxiliary quantities. Set

$P:=\sum_{j\geq 1}jP_{j}\quad\text{and}\quad
P^{(\ell)}:=\sum_{j>\ell}jP_{j},\quad\ell\in\mathbb{N}_{0}.$

With this notation, ${\mathcal{P}}_{N}$ is the same as $\\{P=N\\}$ and
$\\{P^{(0)}=N\\}$. Moreover, recall (3.1) and set

$\displaystyle L:=\sum_{1\leq i\leq P_{1}}(C_{1,i}-m)\quad\text{and}\quad
R:=\sum_{j\geq 2}j\sum_{1\leq i\leq P_{j}}(C_{j,i}-m).$ (3.8)

With this notation

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]=\mathrm{Pr}\left[L+R=n-mN\mid{\mathcal{P}}_{N}\right].$
(3.9)

The driving idea behind these definitions is that the random variables
$C_{j,i}-m$, for $j\geq 2$, have exponential tails, and these tails get
thinner as we increase $j$; in particular, the probability that $C_{j,i}-m=0$
approaches one exponentially fast as we increase $j$. However, things are not
so easy, since we always condition on ${\mathcal{P}}_{N}$, and in this space
some of the $P_{j}$’s might be large. This brings us to our general proof
strategy. First of all, we will study our probability space conditioned on
${\mathcal{P}}_{N}$; in particular, in Corollary 3.7 and Lemma 3.8 below we
describe the joint distribution of $P_{1},\dots,P_{N}$ given
${\mathcal{P}}_{N}$. More specifically, these results show that the $P_{j}$’s
are (more or less) distributed like Poisson random variables with bounded
expectations. This will allow us then in Lemma 3.9 to show that $L$ dominates
the sum $L+R$ in the sense that
$\mathrm{Pr}\left[L+R=n-mN\mid{\mathcal{P}}_{N}\right]\sim\mathrm{Pr}\left[L=n-mN\mid{\mathcal{P}}_{N}\right]$
as $n,N,n-N\to\infty$. Subsequently, in Lemma 3.10 we expoit the
subexponentiality and establish that this last probability is essentially a
multiple of $\mathrm{Pr}\left[C_{1,1}=n-mN\right]$. Just as a side remark and
so as to make the notation more accessible: it is instructive to think of the
random variable $L$ as something (that will turn out to be) large, and $R$ as
some remainder (that will turn out to be small with exponential tails).

Our first aim is to study the distribution – in particular the tails – of $P$
and $P^{(\ell)}$, that is, we want to estimate the probability of
${\mathcal{P}}_{N}$. To this end, consider the probability generating series
$F(x)$ and $F^{(\ell)}(x)$ of $P$ and $P^{(\ell)}$, respectively, that is

$F^{(\ell)}(x)=\frac{1}{G^{(\ell)}(\rho)}\cdot\exp\left(\sum_{j>\ell}\frac{C(\rho^{j})}{j}x^{j}\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
G^{(\ell)}(\rho):=\exp\left(\sum_{j>\ell}\frac{C(\rho^{j})}{j}\right)$

and $F(x)=F^{(0)}(x)$, $G^{(0)}(\rho)=G(\rho)$. Hence, the distribution of
$P^{(\ell)}$ (and $P$) is given by $(\mathrm{Pr}[P^{(\ell)}=N])_{N\geq
0}=([x^{N}]F^{(\ell)}(x))_{N\geq 0}$. In Lemma 3.6 we determine the precise
asymptotic behaviour of these probabilities. But first, we need a simple
auxiliary statement.

######  Proposition 3.5.

There exists $A>0$ such that, for all $0<z\leq\rho$ and $j\in\mathbb{N}$

$1\leq\frac{C(z^{j})}{c_{m}z^{jm}}\leq 1+Az^{j}.$

###### Proof.

The first inequality follows directly from the definition of $C$ and $m$. Note
that

$\frac{C(z^{j})}{c_{m}z^{jm}}\leq
1+z^{j}\frac{1}{c_{m}}\sum_{k>m}c_{k}\rho^{jk-j(m+1)}=1+z^{j}\frac{\rho^{-2m}}{c_{m}}\sum_{k>m}c_{k}\rho^{jk-j(m+1)+2m}.$
(3.10)

Since $m\geq 1$ and $k\geq m+1$ we obtain that

$jk-j(m+1)+2m=j(k-m-1)+2m\geq(k-m-1)+2m=k+m-1\geq k.$

Thus, as $\rho<1$, we obtain from (3.10) the claimed bound with
$A=C(\rho)\rho^{-2m}/c_{m}$. ∎

######  Lemma 3.6.

There exist constants $(B^{(\ell)})_{\ell\in\mathbb{N}_{0}}>0$ such that, as
$N\to\infty$

$[x^{N}]F(x)\sim B^{(0)}\cdot
N^{c_{m}-1}\rho^{mN}\quad\text{and}\quad[x^{N}]F^{(\ell)}(x)\sim
B^{(\ell)}\cdot N^{c_{m}-1}\rho^{mN},\leavevmode\nobreak\ \leavevmode\nobreak\
\ell\in\mathbb{N},$

where

$\frac{B^{(\ell)}}{B^{(0)}}=\exp\left(\sum_{1\leq
j\leq\ell}\frac{C(\rho^{j})}{j}\right)\exp\left(-\sum_{1\leq
j\leq\ell}\frac{C(\rho^{j})}{j}\rho^{-jm}\right).$

###### Proof.

We split up

$F(x)=\frac{1}{G(\rho)}\cdot\exp\left(\sum_{j\geq
1}\frac{c_{m}\rho^{jm}}{j}x^{j}\right)\cdot\exp\left(\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j}x^{j}\right)=:\frac{1}{G(\rho)}\cdot
A(x)\cdot B(x).$

Proposition 3.5 asserts that $B(x)$ has radius of convergence
$\rho_{B}\geq\rho^{-(m+1)}$. Further,

$A(x)=(1-\rho^{m}x)^{-c_{m}},$

and the radius of convergence of $A(x)$ is
$\rho_{A}=\rho^{-m}<\rho^{-(m+1)}\leq\rho_{B}$ (since $\rho<1$). Using Lemma
3.2 we obtain that $[x^{N}]A(x)\sim{N^{c_{m}-1}}\rho^{mN}/{\Gamma(c_{m})}$ and
thus $A(x)$ has property ($S_{2}$). From Lemma 2.3 we then obtain that

$\mathrm{Pr}\left[P=N\right]=[x^{N}]F(x)\sim\frac{1}{G(\rho)}B(\rho_{A})[x^{N}]A(x)\sim\frac{B(\rho^{-m})}{G(\rho)\Gamma(c_{m})}\cdot{N^{c_{m}-1}}{}\rho^{mN},\quad
N\to\infty,$ (3.11)

Similarly, for $\ell\in\mathbb{N}$

$F^{(\ell)}(x)=\frac{A(x)}{G^{(\ell)}(\rho)}\cdot\exp\left(\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j}x^{j}\right)\exp\left(-\sum_{1\leq
j\leq\ell}\frac{C(\rho^{j})}{j}x^{j}\right)=:\frac{A(x)}{G^{(\ell)}(\rho)}\cdot
B^{(\ell)}(x).$

Since the radius of convergence of $B^{(\ell)}(x)$ is again (at least)
$\rho^{-(m+1)}$

$[x^{N}]F^{(\ell)}(x)\sim\frac{B^{(\ell)}(\rho^{-m})}{G^{(\ell)}(\rho)\Gamma(c_{m})}\cdot{N^{c_{m}-1}}\rho^{mN}.$

∎

As an immediate consequence of Lemma 3.6 we establish the asymptotic
distribution of the random vector $(P_{1},\dots,P_{\ell})$ conditioned on the
event ${\mathcal{P}}_{N}$ for fixed $\ell\in\mathbb{N}$; this will be useful
later when we consider the distribution of $L$, cf. (3.8). Clearly, the
condition ${\mathcal{P}}_{N}$ makes $P_{1},\dots,P_{\ell}$ dependent, but the
corollary says that this effect vanishes for large $N$. Moreover, we study the
moments of $P_{1}$ given ${\mathcal{P}}_{N}$.

######  Corollary 3.7.

Let $\ell\in\mathbb{N}$ and $(p_{1},\dots,p_{\ell})\in\mathbb{N}_{0}^{\ell}$.
Then

$\mathrm{Pr}\left[\bigcap_{1\leq
j\leq\ell}\left\\{P_{j}=p_{j}\right\\}\mid{\mathcal{P}}_{N}\right]\to\prod_{1\leq
j\leq\ell}\mathrm{Pr}\left[\mathrm{Po}\left(\frac{C(\rho^{j})}{j\rho^{jm}}\right)=p_{j}\right],\quad
N\to\infty.$ (3.12)

Moreover, for any $z\in\mathbb{R}$, as $N\to\infty$

$\mathbb{E}\left[z^{P_{1}}\mid{\mathcal{P}}_{N}\right]\to\mathbb{E}\left[z^{\mathrm{Po}\left(\frac{C(\rho)}{\rho^{m}}\right)}\right]=\mathrm{e}^{\frac{C(\rho)}{\rho^{m}}(z-1)},\quad\mathbb{E}\left[P_{1}\mid{\mathcal{P}}_{N}\right]\to\mathbb{E}\left[\mathrm{Po}\left(\frac{C(\rho)}{\rho^{m}}\right)\right]={C(\rho)}{\rho^{-m}}.$

###### Proof.

Let $s=\sum_{1\leq j\leq\ell}jp_{j}$. Using the definition of conditional
probability we obtain readily

$\mathrm{Pr}\left[\bigcap_{1\leq
j\leq\ell}\left\\{P_{j}=p_{j}\right\\}\mid{\mathcal{P}}_{N}\right]=\frac{\mathrm{Pr}\left[\bigcap_{1\leq
j\leq\ell}\left\\{P_{j}=p_{j}\right\\}\cap\\{P^{(\ell)}=N-s\\}\right]}{\mathrm{Pr}\left[P=N\right]}.$

Since $P_{1},\dots P_{\ell},P^{(\ell)}$ are independent, the right-hand size
equals

$\prod_{1\leq
j\leq\ell}\mathrm{Pr}\left[P_{j}=p_{j}\right]\cdot[x^{N-s}]F^{(\ell)}(x)/[x^{N}]F(x),$
(3.13)

and (3.12) follows by applying Lemma 3.6. We will next show $P_{1}$ given
${\mathcal{P}}_{N}$ has exponential moments. Abbreviate $B:=C(\rho)\rho^{-m}$.
Note that (3.12) (where we use $\ell=1$) yields for any fixed $K\in\mathbb{N}$

$\sum_{0\leq k\leq
K}z^{k}\mathrm{Pr}\left[P_{1}=k\mid{\mathcal{P}}_{N}\right]\sim\sum_{0\leq
k\leq K}z^{k}\mathrm{Pr}\left[\mathrm{Po}\left(B\right)=k\right],\quad
N\to\infty.$

Let $\varepsilon>0$. Note that we can choose $K$ large enough such that the
right hand side differs at most $\varepsilon$ from
$\mathbb{E}\left[z^{\mathrm{Po}\left(B\right)}\right]=e^{B(z-1)}$. In order
finish the proof we will argue that if $K$ and $N$ are large enough, then
$\sum_{K\leq k\leq
N}z^{k}\mathrm{Pr}\left[P_{1}=k\mid{\mathcal{P}}_{N}\right]<\varepsilon$ as
well. First, by Lemma 3.6

$z^{N}\mathrm{Pr}\left[P_{1}=N\mid{\mathcal{P}}_{N}\right]\leq
z^{N}\frac{\mathrm{Pr}\left[P_{1}=N\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]}\sim\frac{1}{A}N^{-c_{m}+1}\frac{(zB)^{N}}{N!}\to
0,\quad N\to\infty.$

Moreover, according to Lemma 3.6 there exists $A_{1}>0$ such that
$[x^{N-k}]F^{(1)}(x)/[x^{N}]F(x)\leq A_{1}\cdot(1-k/N)^{c_{m}-1}\rho^{-mk}$
for all $0\leq k\leq N-1$. Then with (3.13) we obtain

$\displaystyle\sum_{K\leq k\leq
N-1}z^{k}\mathrm{Pr}\left[P_{1}=k\mid{\mathcal{P}}_{N}\right]\leq
A_{1}\sum_{K\leq k\leq N-1}t_{k},\leavevmode\nobreak\ \leavevmode\nobreak\
\text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
t_{k}:=(1-k/N)^{c_{m}-1}\frac{(zB)^{k}}{k!}.$ (3.14)

Note that we can choose $K$ large enough such that, say, $t_{k+1}\leq t_{k}/2$
for all $K\leq k<N-1$. Then the sum is bounded by $2t_{K}$, and choosing $K$
once more large enough gives $2t_{K}<\varepsilon$. ∎

Note that Corollary 3.7 (only) holds for a fixed $\ell\in\mathbb{N}$; it does
not tell us anything about $(P_{1},\dots,P_{\ell})$ in the case where $\ell$
is not fixed, or, more importantly, when $\ell=N$ (note that
$P_{N^{\prime}}=0$ for all $N^{\prime}>N$ if we condition on
${\mathcal{P}}_{N}$). Regarding this general case, the following statement
gives an upper bound for the probability of the event $\bigcap_{1\leq j\leq
N}\\{P_{j}=p_{j}\\}$ that is not too far from the right-hand side in Corollary
3.7. For the remainder of this section it is convenient to define

$\Omega_{N}:=\Bigl{\\{}(p_{1},\dots,p_{N})\in\mathbb{N}_{0}^{N}\leavevmode\nobreak\
:\leavevmode\nobreak\ \sum_{1\leq j\leq N}jp_{j}=N\Bigr{\\}},\quad N\geq 2.$

In what follows we derive a stochastic upper bound for the distribution of
$(P_{1},\dots,P_{N})$ conditioned on ${\mathcal{P}}_{N}$.

######  Lemma 3.8.

There exists an $A>0$ such that for all $N$ and all
$(p_{1},\dots,p_{N})\in\Omega_{N}$

$\mathrm{Pr}\left[\bigcap_{1\leq j\leq
N}\\{P_{j}=p_{j}\\}\mid{\mathcal{P}}_{N}\right]\leq A\cdot N\cdot\prod_{1\leq
j\leq
N}\mathrm{Pr}\left[\mathrm{Po}\left(\frac{C(\rho^{j})}{j\rho^{jm}}\right)=p_{j}\right].$

###### Proof.

Using the definition of conditional probability and recalling that the
$P_{j}$’s are independent and $P_{j}\sim\mathrm{Po}\left(C(\rho^{j})/j\right)$

$\displaystyle\textrm{Pr}\Biggl{[}\bigcap_{1\leq j\leq N}$
$\displaystyle\\{P_{j}=p_{j}\\}\mid{\mathcal{P}}_{N}\Biggr{]}\leq\frac{1}{\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]}\cdot\prod_{1\leq
j\leq N}\left(\frac{C(\rho^{j})}{j}\right)^{p_{j}}\frac{1}{p_{j}!}$
$\displaystyle=\frac{1}{\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]}\cdot\exp\left(\sum_{1\leq
j\leq N}\frac{C(\rho^{j})}{j\rho^{jm}}\right)\rho^{mN}\cdot\prod_{1\leq j\leq
N}\mathrm{Pr}\left[\mathrm{Po}\left(\frac{C(\rho^{j})}{j\rho^{jm}}\right)=p_{j}\right].$

With Lemma 3.6 we obtain the existence of $B_{1}>0$ such that for $N$ large
enough

$\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]^{-1}\leq
B_{1}\rho^{-mN}N^{1-c_{m}}.$

By Proposition 3.5 there exists a constant $B_{2}>0$ such that
$C(\rho^{j})/\rho^{jm}\leq c_{m}+B_{2}c_{m}\rho^{j}$. Consequently, since
$\rho\in(0,1)$ there exists $B_{3}>0$ such that

$\exp\left(\sum_{1\leq j\leq N}\frac{C(\rho^{j})}{j\rho^{jm}}\right)\leq
B_{3}N^{c_{m}},$

which concludes the proof. ∎

With this result at hand we are ready to study the distribution of $R$, cf.
(3.8). As it will be necessary later, we show uniform tails bounds that hold
for the joint distribution of $P_{1}$ and $R$ conditioned on
${\mathcal{P}}_{N}$.

######  Lemma 3.9.

There exist $A>0$ and $0<a<1$ such that

$\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N}\right]\leq A\cdot
a^{p+r},\quad p,r,N\in\mathbb{N}.$

###### Proof.

We will prove the claimed bound by showing appropriate bounds for the moment
generating function $\mathbb{E}\left[e^{\lambda
R}\mid{\mathcal{P}}_{N}\right]$. Let us fix any $0<\lambda<-\log(\rho)/2$ such
that $\rho e^{\lambda}<1$. Then $\rho^{j}\mathrm{e}^{\lambda j}<\rho$ for all
$j\geq 2$. Recall that
$\mathrm{Pr}\left[C_{j,i}=k\right]={c_{k}\rho^{jk}}/{C(\rho^{j})},k\in\mathbb{N},j\geq
2,i\geq 1$, see (3.5). We obtain that

$\mathbb{E}\left[\mathrm{e}^{\lambda(j(C_{j,i}-m))}\right]=\sum_{s\geq
0}\mathrm{Pr}\left[C_{j,i}=s+m\right]\mathrm{e}^{\lambda
js}=\mathrm{e}^{-\lambda jm}\frac{C(\rho^{j}\mathrm{e}^{\lambda
j})}{C(\rho^{j})},\quad i\geq 1,j\geq 2.$

Let $\Omega_{N,p}$ be the set of all
$\mathrm{p}=(p_{2},\dots,p_{N})\in\mathbb{N}_{0}^{N-1}$ such that
$(p,p_{2},\dots,p_{N})\in\Omega_{N}$, i.e. $p=N-\sum_{2\leq j\leq N}jp_{j}$,
and let ${\mathcal{E}}_{\mathrm{p}}$ be the event

${\mathcal{E}}_{\mathrm{p}}:=\\{P_{1}=p\\}\cap\bigcap_{2\leq j\leq
N}\\{P_{j}=p_{j}\\}.$

Then by Markov’s inequality and the independence of the $C_{j,i}$’s and the
$P_{j}$’s, for any $\mathrm{p}\in\Omega_{N,p}$

$\mathrm{Pr}\left[P_{1}=p,R\geq
r\mid{\mathcal{E}}_{\mathrm{p}}\right]=\mathrm{Pr}\left[\mathrm{e}^{\lambda{R}}\geq\mathrm{e}^{\lambda
r}\mid{\mathcal{E}}_{\mathrm{p}}\right]\leq\mathrm{e}^{-\lambda
r}\mathbb{E}\left[\mathrm{e}^{\lambda{R}}\mid{\mathcal{E}}_{\mathrm{p}}\right]=\mathrm{e}^{-\lambda
r}\prod_{j=2}^{N}\left(\frac{C(\rho^{j}\mathrm{e}^{\lambda
j})}{C(\rho^{j})\mathrm{e}^{\lambda jm}}\right)^{p_{j}}.$

Abbreviate
$\tau_{j}:=C((\rho\mathrm{e}^{\lambda})^{j})/(\rho\mathrm{e}^{\lambda})^{jm}$
for $j\in\mathbb{N}$. By Lemma 3.8 there exists $A_{1}>0$ such that

$\begin{split}\text{Pr}[P_{1}=p,\leavevmode\nobreak\ &R\geq
r\mid{\mathcal{P}}_{N}]=\sum_{\mathrm{p}\in\Omega_{N,p}}\mathrm{Pr}\left[R\geq
r\mid{\mathcal{E}}_{\mathrm{p}}\right]\mathrm{Pr}\left[{\mathcal{E}}_{\mathrm{p}}\mid{\mathcal{P}}_{N}\right]\\\
&\leq A_{1}\mathrm{e}^{-\lambda r}N\exp\left(-\sum_{2\leq j\leq
N}\frac{C(\rho^{j})}{j\rho^{jm}}\right)\frac{(C(\rho)/\rho^{m})^{p}}{p!}\sum_{\mathrm{p}\in\Omega_{N,p}}\prod_{2\leq
j\leq N}\frac{(\tau_{j}/j)^{p_{j}}}{p_{j}!}.\end{split}$ (3.15)

With Proposition 3.5 we find $A_{2}>0$ with

$\exp\left(-\sum_{2\leq j\leq
N}\frac{C(\rho^{j})}{j\rho^{jm}}\right)\leq\exp\left(-c_{m}\sum_{2\leq j\leq
N}\frac{1}{j}\right)\leq A_{2}N^{-c_{m}}.$

Let $H_{j}\sim\mathrm{Po}\left(\tau_{j}/j\right)$ be independent for
$j=2,\dots,N$ and set $\tau:=\text{exp}(\sum_{2\leq j\leq N}\tau_{j}/j)$.
Moreover, abbreviate $B:=C(\rho)/\rho^{m}$. From (3.15) we obtain that there
is an $A_{3}>0$ such that

$\begin{split}\mathrm{Pr}\left[P_{1}=p,R\geq
r\mid{\mathcal{P}}_{N}\right]&\leq A_{3}\mathrm{e}^{-\lambda
r}N^{1-c_{m}}\cdot\tau\cdot\frac{B^{p}}{p!}\sum_{\mathrm{p}\in\Omega_{N,p}}\prod_{j=2}^{N}\mathrm{Pr}\left[H_{j}=p_{j}\right].\end{split}$
(3.16)

Note that

$\sum_{\mathrm{p}\in\Omega_{N,p}}\prod_{j=2}^{N}\mathrm{Pr}\left[H_{j}=p_{j}\right]=\mathrm{Pr}\left[\sum_{j=2}^{N}jH_{j}=N-p\right]=\tau^{-1}\cdot[x^{N-p}]\exp\left(\sum_{j\geq
2}\frac{\tau_{j}}{j}x^{j}\right).$

Observe that in the last expression we actually have to restrict the summation
to the interval $2\leq j\leq N$; however, $[x^{M}]\text{exp}(\sum_{j\geq
2}{\tau_{j}}x^{j}/j)=[x^{M}]\text{exp}(\sum_{2\leq j\leq M}{\tau_{j}}x^{j}/j)$
for all $M\in\mathbb{N}$. Then

$\displaystyle\exp\left(\sum_{j\geq 2}\frac{\tau_{j}}{j}x^{j}\right)$
$\displaystyle=\exp\left(c_{m}\sum_{j\geq
1}\frac{x^{j}}{j}\right)\cdot\exp\left(-c_{m}x+\sum_{j\geq
2}\frac{x^{j}}{j}(\tau_{j}-c_{m})\right)=:G(x)\cdot H(x).$

By Proposition 3.5 there exists a constant $A_{4}>0$ such that $\tau_{j}\leq
c_{m}(1+A_{4}(\rho\mathrm{e}^{\lambda})^{j}).$ With this at hand we deduce
that $H(x)$ has radius of convergence (at least)
$(\rho\mathrm{e}^{\lambda})^{-1}$, which by our choice of $\lambda$ is $>1$.
Note that $G(x)=(1-x)^{-c_{m}}$, which shows together with Lemma 3.2 that $G$
has property ($S_{2}$) with radius of convergence $1$. As $G(x)$ only has
positive coefficients, by Lemma 2.3 and the remark in (2.2) there is an
$A_{5}>0$ such that

$[x^{N-p}]G(x)H(x)\leq A_{5}(N-p)^{c_{m}-1},\quad p=0,\dots,N-1.$

All in all,

$\displaystyle\mathrm{Pr}\left[\sum_{2\leq j\leq N}jH_{j}=N-p\right]\leq
A_{5}\tau^{-1}(N-p)^{c_{m}-1},\quad p=0,\dots,N-1.$ (3.17)

For the case $p=N$ note that the probability that $\sum_{2\leq j\leq
N}jH_{j}=0$ equals $\tau^{-1}$. Putting the pieces together, we get from
(3.16) that there is an $A_{6}>0$ such that

$\mathrm{Pr}\left[P_{1}=p,R\geq r\mid{\mathcal{P}}_{N}\right]\leq
A_{6}\mathrm{e}^{-\lambda
r}N^{1-c_{m}}\left(\frac{B^{N}}{N!}+\frac{B^{p}}{p!}(N-p)^{c_{m}-1}\cdot\mathbf{1}[p\neq
N]\right).$ (3.18)

Observe that $N^{1-c_{m}}B^{N}/N!\leq e^{-\lambda N}$ for $N$ large enough.
Additionally, if $N/2\leq p<N$, then for $N$ large enough

$N^{1-c_{m}}\frac{(e^{\lambda}B)^{p}}{p!}(N-p)^{c_{m}-1}=(1-p/N)^{c_{m}-1}\frac{(e^{\lambda}B)^{p}}{p!}\leq
N^{1-c_{m}}\cdot\frac{(e^{\lambda}B)^{p}}{p!}\leq 1$

and for $0\leq p\leq N/2$

$N^{1-c_{m}}\frac{(e^{\lambda}B)^{p}}{p!}(N-p)^{c_{m}-1}\leq\max\\{2^{1-c_{m}},1\\}\cdot
e^{e^{\lambda}B}\mathrm{Pr}\left[\mathrm{Po}\left(e^{\lambda}B\right)=p\right]\leq\max\\{2^{1-c_{m}},1\\}\cdot
e^{e^{\lambda}B}$

is also bounded. Plugging these bounds into (3.18) completes the proof. ∎

We have just proven that $P_{1},R$ have (joint) exponential tails when
conditioned on ${\mathcal{P}}_{N}$. The next lemma is the last essential step
towards the proof of Theorem 1.1, where we estimate
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]$. Recall from
(3.9) that

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]=\mathrm{Pr}\left[L+R=n-mN\mid{\mathcal{P}}_{N}\right],\quad\text{where}\quad
L=\sum_{1\leq i\leq P_{1}}(C_{1,i}-m).$

######  Lemma 3.10.

Let $C(x)$ be subexponential. Then

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]\sim
c_{n-m(N-1)}\rho^{n-mN},\quad n,N,n-mN\to\infty.$

###### Proof.

For the entire proof we abbreviate $\widetilde{N}:=n-mN$. Then

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]=\sum_{p\geq
0}\sum_{r\geq
0}\mathrm{Pr}\left[L=\widetilde{N}-r\mid{\mathcal{P}}_{N},P_{1}=p,R=r\right]\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N}\right].$
(3.19)

For brevity, let us write in the remainder

${\cal D}_{N,p,r}={\cal
P}_{N}\cap\\{P_{1}=p\\}\cap\\{R=r\\}\quad\text{and}\quad
Q_{\widetilde{N}}:=\text{Pr}\big{[}C_{1,1}=\widetilde{N}+m\big{]}=\frac{c_{n-m(N-1)}\rho^{n-m(N-1)}}{C(\rho)}.$

We will show that

$\text{Pr}\big{[}L=\widetilde{N}-r\leavevmode\nobreak\ |\leavevmode\nobreak\
{\cal D}_{N,p,r}\big{]}\sim p\cdot Q_{\widetilde{N}}\quad\text{for}\quad
p,r\in\mathbb{N}_{0},\text{ as }\widetilde{N}\to\infty.$ (3.20)

Let $a\in(0,1)$ be the constant guaranteed to exist from Lemma 3.9, and choose
$\delta>0$ such that $(1+\delta)a<1$. We will also show that there are
$C>0,N_{0}\in\mathbb{N}$ such that

$\text{Pr}\big{[}L=\widetilde{N}-r\leavevmode\nobreak\ |\leavevmode\nobreak\
{\cal D}_{N,p,r}\big{]}\leq C(1+\delta)^{p+r}\cdot
Q_{\widetilde{N}}\leavevmode\nobreak\ \leavevmode\nobreak\ \text{for
all}\leavevmode\nobreak\ \leavevmode\nobreak\
p,r\in\mathbb{N}_{0},\widetilde{N}\geq N_{0}.$ (3.21)

From the two facts (3.20) and (3.21) the statement in the lemma can be
obtained as follows. We will assume throughout that $\delta$ is fixed as
described above, say for concreteness $\delta=(a^{-1}-1)/2$, and choose an
$0<\varepsilon<1$ arbitrarily. Moreover, we will fix $K\in\mathbb{N}$ in
dependence of $\varepsilon$ only, and we will split the double sum in (3.19)
in three parts with $(p,r)$ in the sets

$B_{\leq}=\\{(p,r):0\leq p,r\leq K\\},\quad
B_{>,\cdot}=\\{(p,r):p>K,r\in\mathbb{N}_{0}\\},\quad
B_{\cdot,>}=\\{(p,r):p\in\mathbb{N}_{0},r>K\\}.$

We will show that the main contribution to
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\leavevmode\nobreak\ |\leavevmode\nobreak\
{\cal P}_{N}\right]$ stems from $B_{\leq}$, while the other two parts
contribute rather insignificantly. Let us begin with treating the latter
parts. Observe that using Lemma 3.9 and (3.21) we obtain that there is a
constant $C^{\prime}>0$ such that for all $r\in\mathbb{N}_{0}$ and $K\geq
K_{0}(\varepsilon)$

$\begin{split}\sum_{p\geq
K}\mathrm{Pr}\left[L=\widetilde{N}-r\leavevmode\nobreak\ |\leavevmode\nobreak\
{\cal D}_{N,p,r}\right]\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]&\leq C^{\prime}\sum_{p\geq
K}(1+\delta)^{p+r}\cdot a^{p+r}\cdot Q\\\
&\leq\varepsilon\cdot((1+\delta)a)^{r}\cdot Q_{\widetilde{N}}.\end{split}$

Since $(1+\delta)a<1$, summing this over all $r$ readily yields for
$c=(1-(1+\delta)a)^{-1}$ that

$\sum_{(p,r)\in
B_{>,\cdot}}\mathrm{Pr}\left[L=\widetilde{N}-r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\cal
D}_{N,p,r}\right]\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]\leq c\varepsilon\cdot
Q_{\widetilde{N}}.$ (3.22)

Completely analogously with the roles of $p,r$ interchanged we obtain that
also

$\sum_{(p,r)\in
B_{\cdot,>}}\mathrm{Pr}\left[L=\widetilde{N}-r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\cal
D}_{N,p,r}\right]\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]\leq c\varepsilon\cdot
Q_{\widetilde{N}}.$ (3.23)

It remains to handle the part of the sum in (3.19) with $p,r\in B_{\leq}$.
Using (3.20) we infer that

$\sum_{(p,r)\in
B_{\leq}}\mathrm{Pr}\left[L=\widetilde{N}-r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\cal
D}_{N,p,r}\right]\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]\sim\sum_{(p,r)\in
B_{\leq}}p\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]\cdot Q_{\widetilde{N}}.$

Using Lemma 3.9 once again note that we can choose $K$ large enough such that

$\sum_{0\leq p\leq K}\sum_{r\geq
K}p\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\ |\leavevmode\nobreak\
{\mathcal{P}}_{N}\right]\leq A\sum_{0\leq p\leq K}\sum_{r\geq
K}pa^{p+r}\leq\varepsilon$

and that

$\left|\sum_{p\geq 0}p\mathrm{Pr}\left[P_{1}=p\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]-\sum_{0\leq p\leq
K}p\mathrm{Pr}\left[P_{1}=p\leavevmode\nobreak\ |\leavevmode\nobreak\
{\mathcal{P}}_{N}\right]\right|=\left|\sum_{p>K}p\mathrm{Pr}\left[P_{1}=p\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]\right|\leq\varepsilon.$

Altogether this establishes that

$\left|\sum_{(p,r)\in
B_{\leq}}\mathrm{Pr}\left[L=\widetilde{N}-r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\cal
D}_{N,p,r}\right]\mathrm{Pr}\left[P_{1}=p,R=r\leavevmode\nobreak\
|\leavevmode\nobreak\ {\mathcal{P}}_{N}\right]-\mathbb{E}\left[P_{1}\mid{\cal
P}_{N}\right]Q_{\widetilde{N}}\right|\leq 2\varepsilon Q_{\widetilde{N}}.$

Corollary 3.7 asserts that $\mathbb{E}\left[P_{1}\mid{\cal P}_{N}\right]\to
C(\rho)\rho^{-m}$. Since $\varepsilon>0$ was arbitrary, combining this with
(3.22) and (3.23) we obtain from (3.19) that
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\cal P}_{N}\right]\sim
C(\rho)\rho^{-m}\cdot Q_{\widetilde{N}}$, which is the claim of the lemma.

In order to complete the proof it remains to show the two claims (3.20) and
(3.21). We begin with (3.20). Note that for $p,r\in\mathbb{N}_{0}$

$\text{Pr}\big{[}L=\widetilde{N}-r\mid{\mathcal{P}}_{N},P_{1}=p,R=r\big{]}=\mathrm{Pr}\left[\sum_{1\leq
i\leq p}C_{1,i}=\widetilde{N}-r+pm\right].$ (3.24)

Recall that $\text{Pr}[C_{1,1}=k]=c_{k}\rho^{k}/C(\rho)$, where $\rho$ is the
radius of convergence of $C$. Since $C$ is subexponential, $c_{k-1}\sim\rho
c_{k}$ and thus the distribution of the $C_{1,i}$’s is also subexponential
with $\text{Pr}[C_{1,1}=k-1]\sim\text{Pr}[C_{1,1}=k]$. We obtain with Lemma
2.2 (i) that the latter probability is $\sim
p\text{Pr}[C_{1,1}=\widetilde{N}-r+pm]$, as $\widetilde{N}\to\infty$.
Moreover, as $\widetilde{N}\to\infty$,
$\text{Pr}[C_{1,1}=\widetilde{N}-r+pm]\sim Q_{\widetilde{N}}$, and (3.20) is
established.

We finally show (3.21). Our starting point is again (3.24). Note that with
Lemma 2.2 (ii) there are $C>0$ and $N_{0}\in\mathbb{N}$ such that the sought
probability is at most $C(1+\delta)^{p}\text{Pr}[C_{1,1}=\widetilde{N}-r+pm]$
for all $\widetilde{N}-r+pm\geq N_{0}$. Moreover, as we have argued in the
previous paragraph, the distribution of $C_{1,1}$ is subexponential with
$\text{Pr}[C_{1,1}=k-1]\sim\text{Pr}[C_{1,1}=k]$; we thus may choose $C$ and
$N_{0}$ large enough such that in addition
$\text{Pr}[C_{1,1}=\widetilde{N}-r+pm]\leq C(1+\delta)^{r}Q_{\widetilde{N}}$.
This establishes (3.21) if $\widetilde{N}-r+pm\geq N_{0}$. To treat the
remaining cases, note that in this situation we have $r>\widetilde{N}-N_{0}$.
Since the probability generating series of $C_{1,1}$ is subexponential with
radius of convergence 1, we obtain that $C(1+\delta)^{r}Q_{\widetilde{N}}>1$
for sufficiently large $\widetilde{N}$; thus (3.21) is trivially true in this
case. ∎

With all these facts at hand the proof of Theorem 1.1 is straightforward. With
Lemma 3.4 and 3.6 (in particular, Equation (3.11)) we obtain as
$n,N,n-mN\to\infty$,

$\displaystyle[x^{n}y^{N}]G(x,y)$
$\displaystyle=\frac{1}{G(\rho)}\rho^{-n}\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]$
$\displaystyle\sim\frac{1}{\Gamma(c_{m})}\exp\left(\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j}\rho^{-jm}\right)N^{c_{m}-1}c_{n-m(N-1)}.$

###  3.3 Proof of Theorem 1.2

Let us begin with (re-)collecting all basic definitions that will be needed in
the proof. Suppose that $C(x)$ is subexponential with radius of convergence
$0<\rho<1$ and set $m:=\min\\{k\in\mathbb{N}:c_{k}>0\\}$, see also (3.1).
Moreover, let $P_{j}\sim\mathrm{Po}\left(C(\rho^{j})/j\right),j\in\mathbb{N}$
and $C_{j,1},\dots,C_{j,P_{j}},{j\in\mathbb{N}}$ have the distribution
specified in (3.5), that is,
$\mathrm{Pr}\left[C_{j,i}=k\right]={c_{k}\rho^{jk}}/{C(\rho^{j})},k,i,j\in\mathbb{N}$.
We assume that all these random variables are independent. Let
${\mathcal{P}}_{N}$, ${\mathcal{E}}_{n}$ be as in (3.3), that is, with

$P=\sum_{j\geq 1}jP_{j},\quad L=\sum_{1\leq i\leq P_{1}}(C_{j,i}-m),\quad
R=\sum_{j\geq 2}j\sum_{1\leq i\leq P_{j}}(C_{j,i}-m)$

we have that ${\mathcal{P}}_{N}=\\{P=N\\}$ and
${\mathcal{E}}_{n}=\\{L+R=n-mP\\}$.

With this notation at hand, let $\mathsf{G}_{n,N}$ be a uniformly drawn random
object from ${\cal G}_{n,N}$, meaning that the number of atoms is $n$ and the
number of components $N$. According to Lemma 3.3 and using that the Boltzmann
model induces the uniform distribution on objects of the same size, we infer
that

$\mathrm{Pr}\left[\mathsf{G}_{n,N}=G\right]=\frac{1}{|{\cal
G}_{n,N}|}=\frac{\rho^{n}/C(\rho)}{|{\cal
G}_{n,N}|\rho^{n}/C(\rho)}=\frac{\mathrm{Pr}\left[\Lambda
G=G\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N},{\mathcal{E}}_{n}\right]}=\mathrm{Pr}\left[\Lambda
G=G\mid{\mathcal{P}}_{N},{\mathcal{E}}_{n}\right],\quad G\in{\cal G}_{n,N},$

that is, studying the distribution of $\mathsf{G}_{n,N}$ boils down to
considering the distribution of $\Lambda G$ conditional on both
${\mathcal{P}}_{N},{\mathcal{E}}_{n}$. This is the starting point of our
investigations. In particular, $\mathsf{G}_{n,N}$ has $N$ components with
sizes given by the vector $(C_{j,i}:1\leq j\leq N,1\leq i\leq P_{j})$. Our aim
is here to study the properties of that vector in the conditional space given
by ${\mathcal{P}}_{N},{\mathcal{E}}_{n}$. To this end, set

$M^{*}:=\max_{j\geq 1,1\leq i\leq P_{j}}C_{j,i}\quad\text{ and }\quad
C^{*}_{p}:=\max\\{C_{1,1},\dots,C_{1,p}\\}\quad\text{for $p\in\mathbb{N}$}.$
(3.25)

Then the statement of the theorem is that, conditional on
${\mathcal{P}}_{N},{\mathcal{E}}_{n}$, we have that
$M^{*}=n-mN+\mathcal{O}_{p}(1)$; since the total number of atoms is $n$, the
number of components is $N$, and the smallest component contains $m$ atoms,
this immediately implies that there are $N+\mathcal{O}_{p}(1)$ components with
exactly $m$ atoms, and all remaining components have a total size of
$\mathcal{O}_{p}(1)$ as well.

The general proof strategy in the remaining section is as follows. We first
show in Lemma 3.11 that both $P_{1},R$ are “small” in the conditioned space;
this makes sure that only a bounded number of entries in the vector
$(C_{j,i})_{j\geq 2,1\leq i\leq P_{j}}$ are larger than $m$, and that this
total excess is bounded. Hence, the remaining number of
$n-(N-P_{1})m+\mathcal{O}_{p}(1)$ atoms is to be found in the components with
sizes in $(C_{1,i})_{1\leq i\leq P_{1}}$. In Lemma 3.11 we exclude that
$P_{1}$ grows too large conditioned on ${\mathcal{E}}_{n},{\mathcal{P}}_{N}$;
indeed, we show that it is stochastically bounded. Then the property of
subexponentiality guarantees that only the maximum of the $C_{1,i}$’s
dominates the entire sum, cf. Lemma 2.2 (iii), and Theorem 1.2 follows.

Let us now fill this overview with details. Recall Lemma 3.9, which says that
$P_{1},R$ have (joint) exponential tails given ${\mathcal{P}}_{N}$. We show
that conditioning in addition to ${\mathcal{E}}_{n}$ does not change the
behaviour qualitatively. The proof can be found at the end of the section.

######  Lemma 3.11.

There exist constants $A>0$ and $0<a<1$ such that

$\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]\leq
A\cdot a^{p+r},\quad p,r,n,N\in\mathbb{N}.$

With this lemma the proof of the theorem can be completed as follows. Let
$\varepsilon>0$ be arbitrary. Abbreviate $\widetilde{N}=n-mN$. With $M^{*}$ as
in (3.25) we will show that there is $K\in\mathbb{N}$ such that

$\mathrm{Pr}\left[|M^{*}-\widetilde{N}|\geq
K\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]<\varepsilon$

for $n,N,\widetilde{N}$ sufficiently large, which is the statement of the
theorem. According to Lemma 3.11 there exist constants
$C_{R},C_{P}\in\mathbb{N}$ such that

$\mathrm{Pr}\left[R\geq C_{R},P_{1}\geq
C_{P}\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]<\varepsilon/2,\quad
n,N,\widetilde{N}\in\mathbb{N}.$

We deduce

$\mathrm{Pr}\left[|M^{*}-\widetilde{N}|\geq
K\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]\leq\frac{\varepsilon}{2}+\sum_{0\leq
r\leq C_{R}}\sum_{1\leq p\leq
C_{P}}\mathrm{Pr}\left[{|M^{*}-\widetilde{N}|}\geq
K\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N},R=r,P_{1}=p\right].$ (3.26)

Note that we only need to consider values of $p$ which are larger than $1$ as
$p=0$ excludes $R=r\leq C_{R}<\widetilde{N}$. The event
“${\mathcal{E}}_{n},{\mathcal{P}}_{N},R=r,P_{1}=p$” implies that
$\left|C_{j,i}\right|\leq m+r$ for all $j\geq 2,1\leq i\leq P_{j},$ and
$S_{p}:=\sum_{1\leq i\leq p}C_{1,i}=\widetilde{N}-r+pm$. Recall the definition
of $C^{*}$ from (3.25). Assume that $C^{*}_{p}\leq m+r$, then we get the
contradiction $\widetilde{N}-r+pm=S_{p}\leq p(m+r)<\widetilde{N}-r+pm$ for
$\widetilde{N}$ large enough. It follows that $C^{*}_{p}>m+r$ and hence we are
allowed to interchange $C^{*}_{p}$ and $M^{*}$ in this conditioned space. That
yields

$\mathrm{Pr}\left[|M^{*}-\widetilde{N}|\geq
K\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N},R=r,P_{1}=p\right]=\mathrm{Pr}\left[|C^{*}_{p}-\widetilde{N}|\geq
K\mid S_{p}=\widetilde{N}-r+pm\right],$

for $1\leq p\leq C_{P},0\leq r\leq C_{R}$. As $C^{*}_{p}$ is at most
$\widetilde{N}-r+pm$ under this condition, we particularly obtain that
$\\{C^{*}_{p}\geq\widetilde{N}+K\\}=\emptyset$ for $K\geq mC_{P}$ as long as
$0\leq p\leq C_{P}$ and $r\geq 0$. Consequently, for $1\leq p\leq C_{P},0\leq
r\leq C_{R}$,

$\mathrm{Pr}\left[\lvert C^{*}_{p}-\widetilde{N}\rvert\geq K\mid
S_{p}=\widetilde{N}-r+pm\right]=\mathrm{Pr}\left[C^{*}_{p}\leq\widetilde{N}-K\mid
S_{p}=\widetilde{N}-r+pm\right].$

Now Lemma 2.2 (iii) is applicable as $C_{1,i}$ has subexponential distribution
for $1\leq i\leq p$ and hence for $1\leq p\leq C_{P},0\leq r\leq C_{R}$ we
have $(C^{*}_{p}\mid
S_{p}=\widetilde{N}+r-pm)=\widetilde{N}+r-pm+\mathcal{O}_{p}(1)$ as
$\tilde{N}\to\infty$. Consequently, choosing $K$ large enough,

$\mathrm{Pr}\left[C^{*}_{p}\leq\widetilde{N}-K\mid
S_{p}=\widetilde{N}-r+pm\right]<\frac{\varepsilon}{2C_{R}C_{P}},\quad 1\leq
p\leq C_{P},0\leq r\leq C_{R}.$

We conclude from (3.26)

$\displaystyle\mathrm{Pr}\left[|M^{*}-\widetilde{N}|\geq
K\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]\leq\frac{\varepsilon}{2}+\sum_{0\leq
r\leq C_{R}}\sum_{1\leq p\leq
C_{P}}\mathrm{Pr}\left[C^{*}_{p}\leq\widetilde{N}-K\mid
S_{p}=\widetilde{N}-r+pm\right]<\varepsilon.$

Since $\varepsilon>0$ was arbitrary we have just proven that the largest
component satisfies
$(M^{*}\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N})=\widetilde{N}+\mathcal{O}_{p}(1)$,
and the proof is completed.

###### Proof of Lemma 3.11.

We start with the observation

$\displaystyle\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right]=\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid
P_{1}=p,R=r,{\mathcal{P}}_{N}\right]\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N}\right]\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]^{-1}.$
(3.27)

Set $\widetilde{N}:=n-mN$ and $L_{p}:=\sum_{1\leq i\leq p}(C_{1,i}-m)$ for
$p\in\mathbb{N}_{0}$ as well as
$Q_{\widetilde{N}}=\text{Pr}[C_{1,1}-m=\widetilde{N}]$. Let $0<a<1$ be the
constant from Lemma 3.9 and let $\delta>0$ be such that $(1+\delta)a<1$. With
(3.21) we obtain that there exists $A_{1}>0$ with

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid
P_{1}=p,R=r,{\mathcal{P}}_{N}\right]=\mathrm{Pr}\left[L_{p}=\widetilde{N}-r\mid{\mathcal{P}}_{N}\right]\leq
A_{1}(1+\delta)^{p+r}Q_{\widetilde{N}},\quad p,r,n,N\in\mathbb{N}.$

Lemma 3.9 tells us that we find $A_{2}>0$ with

$\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N}\right]\leq
A_{2}a^{p+r},\quad p,r,N\in\mathbb{N}.$

Finally, according to Lemma 3.10 there is a constant $A_{3}$ such that

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]\geq
A_{3}Q_{\widetilde{N}},\quad n,N\in\mathbb{N},$

and the claim follows with $a$ replaced by $(1+\delta)a<1$ by plugging
everything into (3.27). ∎

###  3.4 Proof of Theorem 1.3

For the proof of this theorem we use the equivalent definition of multisets in
which all objects not occurring in $G\in{\mathcal{G}}$ are counted with
multiplicity $d=0$. Let
$G=\\{(C,d_{C}):C\in{\mathcal{C}}_{>m}\\}\cup\\{(C,0):C\in{\mathcal{C}}_{m}\\}\in{\mathcal{G}}$
and assume that $N(n)\equiv N$ is such that $N(n),n-mN(n)\to\infty$ as
$n\to\infty$. Let us write $R_{n,N}$ for the object obtained after removing
(i.e. setting the multiplicity to $0$) all objects of size $m$ and a largest
component (i.e. subtracting the multiplicity by one) from $\mathsf{G}_{n,N}$.
The statement of the theorem is equivalent to showing that

$\mathrm{Pr}\left[R_{n,N}=G\right]\to\exp\left(-\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\right)\rho^{\lvert
G\rvert-m\kappa(G)},\quad n\to\infty,$

see also (1.3). Defining the family of multiplicity counting functions
$(d_{C}(\cdot))_{C\in{\mathcal{C}}}$ by
$(d_{C}(G))_{C\in{\mathcal{C}}}=(d_{C})_{C\in{\mathcal{C}}}$ for
$G=\\{(C,d_{C}):C\in{\mathcal{C}}\\}\in{\mathcal{G}}$ we immediately obtain
that

$\mathrm{Pr}\left[R_{n,N}=G\right]=\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{>m}:d_{C}(R_{n,N})=d_{C}\right].$

Let $S>\max\\{m,\lvert G\rvert\\}$ be some arbitrary integer to be specified
later. We infer that

$\mathrm{Pr}\left[R_{n,N}=G\right]\leq\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\right].$

To obtain a lower bound, since $S>\lvert G\rvert$, we observe that $\\{\forall
C\in{\mathcal{C}}_{>m}:d_{C}(R_{n,N})=d_{C}\\}$ is the same as $\\{\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\\}\cap\\{\forall
C\in{\mathcal{C}}_{>S}:d_{C}(R_{n,N})=0\\}$. Moreover, note that $\lvert
R_{n,N}\rvert\leq S$ implies $d_{C}(R_{n,N})=0$ for all
$C\in{\mathcal{C}}_{>S}$. Thus

$\displaystyle\mathrm{Pr}\left[R_{n,N}=G\right]$
$\displaystyle\geq\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C},\lvert R_{n,N}\rvert\leq
S\right]$ $\displaystyle\geq\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\right]-\mathrm{Pr}\left[\lvert
R_{n,N}\rvert>S\right].$

Let $\varepsilon>0$. According to Theorem 1.2 there is $S_{1}>\max\\{m,\lvert
G\rvert\\}$ so that $\mathrm{Pr}\left[\lvert
R_{n,N}\rvert>S_{1}\right]<\varepsilon$. Hence
$\mathrm{Pr}\left[R_{n,N}=G\right]$ differs by at most $\varepsilon$ from
$\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\right]$ for all $S>S_{1}$. Let
us write $L_{n,N}$ for the size of a largest component in $\mathsf{G}_{n,N}$.
Theorem 1.2 guarantees that $L_{n,N}$ is unbounded whp, and so we obtain for
any $S\in\mathbb{N}$

$\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\right]=\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C},\lvert
L_{n,N}\rvert>S\right]+o(1).$

However, the event $\\{\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C},\lvert L_{n,N}\rvert>S\\}$ is
equivalent to the event $\\{\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C},\lvert
L_{n,N}\rvert>S\\}$, since we obtain $R_{n,N}$ by removing all components with
size $m$ and a largest component (of size $>S$) from $\mathsf{G}_{n,N}$. Now
we add and subtract $\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,s}:d_{C}(\mathsf{G}_{n,N})=d_{C},\lvert
L_{n,N}\rvert\leq S\right]=o(1)$ in order to get rid of the event $\lvert
L_{n,N}\rvert>S$ and arrive at the fact

$\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(R_{n,N})=d_{C}\right]=\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]+o(1).$

Combining all previous facts yields that for $n$ sufficiently large

$\big{|}\mathrm{Pr}\left[R_{n,N}=G\right]-\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]\big{|}\leq
2\varepsilon$ (3.28)

and thus we are left with estimating $\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]$. For
$\boldsymbol{\mathrm{v}}_{S}:=(v_{C})_{C\in{\mathcal{C}}_{m+1,S}}$ denote by
$G(x,y,\boldsymbol{\mathrm{v}}_{S})$ the generating series of ${\mathcal{G}}$
such that $x$ marks the size, $y$ the number of components and
$\boldsymbol{\mathrm{v}}_{S}=(v_{C})_{C\in{\mathcal{C}}_{m+1,S}}$ the
multiplicities of $(C)_{C\in{\mathcal{C}}_{m+1,S}}$, or in other words: for
$\ell,k\in\mathbb{N}_{0},\boldsymbol{\mathrm{t}}_{S}:=(t_{C})_{C\in{\mathcal{C}}_{m+1,S}}\in\mathbb{N}_{0}^{\lvert{\mathcal{C}}_{m+1,S}\rvert}$
the coefficients are given by

$g_{\ell,k,\boldsymbol{\mathrm{t}}_{S}}=\lvert\\{G\in{\mathcal{G}}:\lvert
G\rvert=\ell,\kappa(G)=k,\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(G)=t_{C}\\}\rvert.$

Setting $v_{C}=1$ for all $C\in{\mathcal{C}}_{m+1,S}$ we obtain the generating
series $G(x,y)$ counting only size and number of components by $x$ and $y$
respectively. As $\mathsf{G}_{n,N}$ is drawn uniformly at random from
${\mathcal{G}}_{n,N}$ the proof reduces to determining

$\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]=\frac{[x^{n}y^{N}\boldsymbol{\mathrm{v}}_{s}^{\boldsymbol{\mathrm{d}}_{S}}]G(x,y,\boldsymbol{\mathrm{v}}_{S})}{[x^{n}y^{N}]G(x,y)}.$

The following lemma, whose proof is shifted to the end of this section,
accomplishes this task.

######  Lemma 3.12.

Let $\boldsymbol{\mathrm{d}}=(d_{C})_{C\in{\mathcal{C}}_{m+1,S}}$ with
$D:=\sum_{C\in{\mathcal{C}}_{m+1,S}}\lvert C\rvert d_{C}$ and
$D^{\prime}:=\sum_{C\in{\mathcal{C}}_{m+1,S}}d_{C}$. Then

$\frac{[x^{n}y^{N}\boldsymbol{\mathrm{v}}_{s}^{\boldsymbol{\mathrm{d}}_{S}}]G(x,y,\boldsymbol{\mathrm{v}}_{S})}{[x^{n}y^{N}]G(x,y)}\to\rho^{D-mD^{\prime}}\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-\rho^{\lvert
C\rvert-m}),\quad n\to\infty.$

Lemma 3.12 yields directly for sufficiently large $n$

$\biggl{\lvert}\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]-\rho^{\lvert
G\rvert-m\kappa(G)}\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-\rho^{\lvert
C\rvert-m})\biggr{\rvert}<\varepsilon.$

Now observe that with defining $C_{m+1,S}(x):=\sum_{m<\ell\leq
S}\lvert{\mathcal{C}}_{\ell}\rvert x^{\ell}$ we obtain

$\lim_{S\to\infty}\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-\rho^{\lvert
C\rvert-m})=\lim_{S\to\infty}\prod_{m<\ell\leq
S}\exp\left(|{\mathcal{C}}_{\ell}|\log(1-\rho^{\ell-m})\right)=\lim_{S\to\infty}\exp\left(-\sum_{j\geq
1}\frac{C_{m+1,S}(\rho^{j})}{j\rho^{jm}}\right).$

By the continuity of $\exp\left(\cdot\right)$ and monotone convergence this
equals $G_{>m}(\rho)^{-1}$. Choose $S_{2}>\max\\{m,\lvert G\rvert\\}$ large
enough such that $\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-\rho^{\lvert
C\rvert-m})$ differs at most by $\varepsilon$ from $G_{>m}(\rho)^{-1}$ for all
$S>S_{2}$. Summarizing, fixing $S\geq\max\\{S_{1},S_{2}\\}$ we obtain for
sufficiently large $n$

$\big{|}\mathrm{Pr}\left[\forall
C\in{\mathcal{C}}_{m+1,S}:d_{C}(\mathsf{G}_{n,N})=d_{C}\right]-\rho^{\lvert
G\rvert-m\kappa(G)}G_{>m}(\rho)^{-1}\big{|}\leq 2\varepsilon.$

Since $\varepsilon>0$ was arbitrary the proof of the theorem is finished with
(3.28).

###### Proof of Lemma 3.12.

First we determine $G(x,y,\boldsymbol{\mathrm{v}}_{S})$ explicitly. Define the
multivariate generating series

$C(x,y,\boldsymbol{\mathrm{v}}_{S})=y\left(C(x)+\sum_{C\in{\mathcal{C}}_{m+1,S}}(v_{C}-1)x^{\lvert
C\rvert}\right),$

where as usual $x$ marks the size, $y$ the number of components (which by
convention is always $1$ for $C\in{\mathcal{C}}$) and
$\boldsymbol{\mathrm{v}}_{S}$ objects in ${\mathcal{C}}_{m+1,S}$. Note that
these parameters are clearly additive when forming multisets. Hence, according
to [18, Theorem III.1] the formula (1.1) extends to the multivariate version

$\displaystyle G(x,y,\boldsymbol{\mathrm{v}}_{S})=\exp\left(\sum_{j\geq
1}\frac{C(x^{j},x^{j},\boldsymbol{\mathrm{v}}_{S}^{j})}{j}\right),$ (3.29)

where
$\boldsymbol{\mathrm{v}}_{S}^{j}=(v_{C}^{j})_{C\in{\mathcal{C}}_{m+1,S}}$.
Setting $v_{C}=1$ for all $C\in{\mathcal{C}}_{m+1,S}$ we see that
$G(x,y,\boldsymbol{\mathrm{1}})\equiv G(x,y)$ such that
$[x^{n}y^{N}]G(x,y)=\lvert{\mathcal{G}}_{n,N}\rvert$. By elementary algebraic
manipulations we reformulate (3.29) to

$\displaystyle\begin{split}G(x,y,\boldsymbol{\mathrm{v}}_{S})&=G(x,y)\exp\left(\sum_{C\in{\mathcal{C}}_{m+1,S}}\left(\sum_{j\geq
1}\frac{(x^{\lvert C\rvert}yv_{C})^{j}}{j}-\sum_{j\geq 1}\frac{(x^{\lvert
C\rvert}y)^{j}}{j}\right)\right)\\\
&=G(x,y)\prod_{C\in{\mathcal{C}}_{m+1,S}}\frac{1-x^{\lvert
C\rvert}y}{1-x^{\lvert C\rvert}yv_{C}}.\end{split}$ (3.30)

Let us now turn to the initial claim in Lemma 3.12. We obtain that

$\displaystyle[x^{n}y^{N}\boldsymbol{\mathrm{v}}_{S}^{\boldsymbol{\mathrm{d}}_{S}}]G(x,y,\boldsymbol{\mathrm{v}}_{S})$
$\displaystyle=[x^{n}y^{N}]G(x,y)\prod_{C\in{\mathcal{C}}_{m+1,S}}[v_{C}^{d_{C}}]\frac{1-x^{\lvert
C\rvert}y}{1-x^{\lvert C\rvert}v_{C}y}$
$\displaystyle=[x^{n-D}y^{N-D^{\prime}}]G(x,y)\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-x^{\lvert
C\rvert}y).$

Since ${\mathcal{C}}_{m+1,S}$ does only have finitely many elements, there
exist $L,K\in\mathbb{N}$ such that
$[x^{\ell}y^{k}]\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-x^{\lvert C\rvert}y)=0$
for all $\ell\geq L,k\geq K$. Recall that, using Theorem 1.1,

$[x^{n}y^{N}]G(x,y)\sim\exp\left(\sum_{j\geq
1}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\right)\frac{N^{c_{m}-1}}{\Gamma(c_{m})}\lvert{\mathcal{C}}_{n-m(N-1)}\rvert,\quad
n\to\infty,$

and so $[x^{n-a}y^{N-b}]G(x,y)\sim[x^{n}y^{N}]G(x,y)\rho^{a-mb}$ for fixed
$a,b\in\mathbb{N}$ as ${\mathcal{C}}$ is subexponential. Hence, as
$n\to\infty$,

$\displaystyle[x^{n}y^{N}\boldsymbol{\mathrm{v}}_{S}^{\boldsymbol{\mathrm{d}}_{S}}]G(x,y,\boldsymbol{\mathrm{v}}_{S})$
$\displaystyle=\sum_{\ell\in[L],k\in[K]}[x^{n-D-\ell}y^{N-D^{\prime}-k}]G(x,y)[x^{\ell}y^{k}]\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-x^{\lvert
C\rvert}y)$
$\displaystyle\sim[x^{n}y^{N}]G(x,y)\cdot\rho^{D-mD^{\prime}}\sum_{\ell\in[L],k\in[K]}\rho^{\ell-
mk}[x^{\ell}y^{k}]\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-x^{\lvert C\rvert}y)$
$\displaystyle=[x^{n}y^{N}]G(x,y)\cdot\rho^{D-mD^{\prime}}\prod_{C\in{\mathcal{C}}_{m+1,S}}(1-\rho^{\lvert
C\rvert-m}),$

which finishes the proof. ∎

###  3.5 Proof of Proposition 1.4

###### Proof of Proposition 1.4.

It is a well-known fact that the weak convergence of $(\mathsf{G}_{n},o_{n})$
to $(\mathbbmss{G},\mathbbmss{o})$ in (1.4) is equivalent to showing that for
any bounded and continuous function $f:{\mathcal{B}}_{*}\to\mathbb{R}$

$\lim_{n\to\infty}\mathbb{E}\left[f(\mathsf{G}_{n},o_{n})\right]=\mathbb{E}\left[f(\mathbbmss{G},\mathbbmss{o})\right].$

For any finite graph $G$ denote by $o_{G}$ a vertex chosen uniformly at random
from its vertex set. Let ${\mathcal{M}}(\mathsf{G}_{n,N})$ denote a
(canonically chosen) largest component of $\mathsf{G}_{n,N}$ and
${\mathcal{R}}(\mathsf{G}_{n,N})$ the remainder after removing all objects of
size $m$ and ${\mathcal{M}}(\mathsf{G}_{n,N})$. Let
$f:{\mathcal{B}}_{*}\to\mathbb{R}$ be an arbitrary bounded and continuous
function. Then

$\displaystyle\mathbb{E}\left[f(\mathsf{G}_{n,N},o_{n})\right]=$
$\displaystyle\mathbb{E}\left[f({\mathcal{M}}(\mathsf{G}_{n,N}),o_{{\mathcal{M}}(\mathsf{G}_{n,N})})\right]\mathrm{Pr}\left[o_{n}\in{\mathcal{M}}(\mathsf{G}_{n,N})\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[f({\mathcal{R}}(\mathsf{G}_{n,N}),o_{{\mathcal{R}}(\mathsf{G}_{n,N})})\right]\mathrm{Pr}\left[o_{n}\in{\mathcal{R}}(\mathsf{G}_{n,N})\right]$
$\displaystyle+$
$\displaystyle\mathbb{E}\left[f(\mathsf{C}_{m},o_{m})\right]\mathrm{Pr}\left[o_{n}\notin{\mathcal{R}}(\mathsf{G}_{n,N})\cup{\mathcal{M}}(\mathsf{G}_{n,N})\right].$

According to Theorem 1.2 we have that
$\lvert{\mathcal{M}}(\mathsf{G}_{n,N})\rvert=n-mN+\mathcal{O}_{p}(1)$ implying
$\mathrm{Pr}\left[o_{n}\in{\mathcal{M}}(\mathsf{G}_{n,N})\right]\sim(n-mN)/n\to
1-\lambda$. As the size of ${\mathcal{M}}(\mathsf{G}_{n,N})\in{\mathcal{C}}$
tends to infinity and $(\mathsf{C}_{n})_{n\geq 1}$ converges in the BS sense
to $(\mathbbmss{C},\mathbbmss{o})$ we have that

$\mathbb{E}\left[f({\mathcal{M}}(\mathsf{G}_{n,N}),o_{{\mathcal{M}}(\mathsf{G}_{n,N})})\right]\mathrm{Pr}\left[o_{n}\in{\mathcal{M}}(\mathsf{G}_{n,N})\right]\to(1-\lambda)\mathbb{E}\left[f(\mathbbmss{C},\mathbbmss{o})\right],\quad
n,N\to\infty.$

Theorem 1.3 entails that ${\mathcal{R}}(\mathsf{G}_{n,N})$ has a limiting
distribution and hence
$\mathrm{Pr}\left[o_{n}\in{\mathcal{R}}(\mathsf{G}_{n,N})\right]\to 0$. As $f$
is bounded

$\mathbb{E}\left[f({\mathcal{R}}(\mathsf{G}_{n,N}),o_{{\mathcal{R}}(\mathsf{G}_{n,N})})\right]\mathrm{Pr}\left[o_{n}\in{\mathcal{R}}(\mathsf{G}_{n,N})\right]\to
0,\quad n\to\infty.$

Finally, we obtain by combining Theorems 1.2 and 1.3 that
$n-\lvert{\mathcal{R}}(\mathsf{G}_{n,N})\cup{\mathcal{M}}(\mathsf{G}_{n,N})\rvert=mN+\mathcal{O}_{p}(1)$
and hence
$\mathrm{Pr}\left[o_{n}\notin{\mathcal{R}}(\mathsf{G}_{n,N})\cup{\mathcal{M}}(\mathsf{G}_{n,N})\right]\sim
mN/n\to\lambda$. Thus,

$\lim_{n,N\to\infty}\mathbb{E}\left[f(\mathsf{G}_{n,N},o_{n})\right]=(1-\lambda)\mathbb{E}\left[f(\mathbbmss{C},\mathbbmss{o})\right]+\lambda\mathbb{E}\left[f(\mathsf{C}_{m},o_{m})\right].$

∎

## Acknowledgements

The authors thank Benedikt Stufler for fruitful discussions and valuable input
to the proof of Theorem 1.2.

## References

  * Addario-Berry [2019] L. Addario-Berry.  A Probabilistic Approach to Block Sizes in Random Maps.  _ALEA Lat. Am. J. Probab. Math. Stat._ , 16(1):1–13, 2019.  URL https://doi.org/10.30757/alea.v16-01.
  * Aldous and Steele [2004] D. Aldous and J. M. Steele.  The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence.  In _Probability on Discrete Structures_ , volume 110 of _Encyclopaedia Math. Sci._ , pages 1–72. Springer, Berlin, 2004.  doi: 10.1007/978-3-662-09444-0˙1.  URL https://doi.org/10.1007/978-3-662-09444-0_1.
  * Arratia et al. [2003] R. Arratia, A. Barbour, and S. Tavaré.  _Logarithmic Combinatorial Structures: A Probabilistic Approach_.  EMS monographs in mathematics. European Mathematical Society, 2003.  ISBN 9783037190005.  URL https://books.google.de/books?id=oBPvAAAAMAAJ.
  * Barbour and Granovsky [2005] A. Barbour and B. L. Granovsky.  Random Combinatorial Structures: the Convergent Case.  _Journal of Combinatorial Theory, Series A_ , 109(2):203–220, 2005.  ISSN 0097-3165.  doi: 10.1016/j.jcta.2004.09.001.  URL http://www.sciencedirect.com/science/article/pii/S0097316504001347.
  * Bell et al. [2000] J. P. Bell, E. A. Bender, P. J. Cameron, and L. B. Richmond.  Asymptotics for the Probability of Connectedness and the Distribution of Number of Components.  _Electron. J. Combin._ , 7:Research Paper 33, 22, 2000.  URL https://doi.org/10.37236/1511.
  * Benjamini and Schramm [2001] I. Benjamini and O. Schramm.  Recurrence of Distributional Limits of Finite Planar Graphs.  _Electron. J. Probab._ , 6:no. 23, 13, 2001.  ISSN 1083-6489.  doi: 10.1214/EJP.v6-96.  URL https://doi.org/10.1214/EJP.v6-96.
  * Bernasconi et al. [2010] N. Bernasconi, K. Panagiotou, and A. Steger.  On Properties of Random Dissections and Triangulations.  _Combinatorica_ , 30(6):627–654, 2010.  ISSN 1439-6912.  doi: 10.1007/s00493-010-2464-8.  URL https://doi.org/10.1007/s00493-010-2464-8.
  * Bernikovich and Pavlov [2011] E. S. Bernikovich and Y. L. Pavlov.  On the Maximum Size of a Tree in a Random Unlabelled Unrooted Forest.  _Diskret. Mat._ , 23(1):3–20, 2011.  ISSN 0234-0860.  doi: 10.1515/DMA.2011.001.  URL https://doi.org/10.1515/DMA.2011.001.
  * Bodirsky et al. [2011] M. Bodirsky, É. Fusy, M. Kang, and S. Vigerske.  Boltzmann Samplers, Pólya Theory, and Cycle Pointing.  _SIAM Journal on Computing_ , 40(3):721–769, 2011\.  ISSN 0097-5397.  doi: 10.1137/100790082.  URL http://dx.doi.org/10.1137/100790082.
  * Burris [2001] S. N. Burris.  _Number Theoretic Density and Logical Limit Laws_ , volume 86 of _Mathematical Surveys and Monographs_.  American Mathematical Society, Providence, RI, 2001.  ISBN 0-8218-2666-2.  doi: 10.1090/surv/086.  URL https://doi.org/10.1090/surv/086.
  * Curien and Kortchemski [2014] N. Curien and I. Kortchemski.  Random Non‐-Crossing Plane Configurations: A Conditioned Galton-‐Watson Tree Approach.  _Random Structures & Algorithms_, 45(2):236–260, 2014.  doi: 10.1002/rsa.20481.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20481.
  * Drmota et al. [2011] M. Drmota, É. Fusy, M. Kang, V. Kraus, and J. Rué.  Asymptotic Study of Subcritical Graph Classes.  _SIAM J. Discrete Math._ , 25(4):1615–1651, 2011\.  ISSN 0895-4801.  doi: 10.1137/100790161.  URL https://doi.org/10.1137/100790161.
  * Drmota et al. [2014] M. Drmota, O. Giménez, M. Noy, K. Panagiotou, and A. Steger.  The Maximum Degree of Random Planar Graphs.  _Proceedings of the London Mathematical Society_ , 109(4):892–920, 2014.  ISSN 1460-244X.  doi: 10.1112/plms/pdu024.  URL http://dx.doi.org/10.1112/plms/pdu024.
  * Drmota et al. [2019] M. Drmota, E. Y. Jin, and B. Stufler.  Graph Limits of Random Graphs From a Subset of Connected $k$–Trees.  _Random Structures & Algorithms_, 55(1):125–152, 2019.  ISSN 1042-9832.  doi: 10.1002/rsa.20802.  URL https://doi.org/10.1002/rsa.20802.
  * Duchon et al. [2004] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer.  Boltzmann Samplers for the Random Generation of Combinatorial Structures.  _Combin. Probab. Comput._ , 13(4-5):577–625, 2004\.  ISSN 0963-5483.  doi: 10.1017/S0963548304006315.  URL https://doi.org/10.1017/S0963548304006315.
  * Embrechts and Omey [1984] P. Embrechts and E. Omey.  Functions of Power Series.  _Yokohama Math. J._ , 32(1-2):77–88, 1984.  ISSN 0044-0523.
  * Erdös and Lehner [1941] P. Erdös and J. Lehner.  The Distribution of the Number of Summands in the Partitions of a Positive Integer.  _Duke Math. J._ , 8:335–345, 1941.  ISSN 0012-7094.  URL http://projecteuclid.org/euclid.dmj/1077492649.
  * Flajolet and Sedgewick [2009] P. Flajolet and R. Sedgewick.  _Analytic Combinatorics_.  Cambridge University Press, Cambridge, 2009.  ISBN 978-0-521-89806-5.  doi: 10.1017/CBO9780511801655.  URL https://doi.org/10.1017/CBO9780511801655.
  * Flajolet et al. [2007] P. Flajolet, É. Fusy, and C. Pivoteau.  Boltzmann Sampling of Unlabelled Structures.  In _2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)_ , pages 201–211. 2007.  doi: 10.1137/1.9781611972979.5.  URL http://epubs.siam.org/doi/abs/10.1137/1.9781611972979.5.
  * Foss et al. [2013] S. Foss, D. Korshunov, and S. Zachary.  _An Introduction to Heavy-tailed and Subexponential Distributions_.  Springer Series in Operations Research and Financial Engineering. Springer, New York, second edition, 2013.  ISBN 978-1-4614-7100-4; 978-1-4614-7101-1.  doi: 10.1007/978-1-4614-7101-1.  URL https://doi.org/10.1007/978-1-4614-7101-1.
  * Georgakopoulos and Wagner [2016] A. Georgakopoulos and S. Wagner.  Limits of Subcritical Random Graphs and Random Graphs with Excluded Minors.  _ArXiv e-prints_ , 2016.  URL https://arxiv.org/abs/1512.03572v2.
  * Granovsky and Stark [2006] B. L. Granovsky and D. Stark.  Asymptotic Enumeration and Logical Limit Laws for Expansive Multisets and Selections.  _J. London Math. Soc. (2)_ , 73(1):252–272, 2006\.  ISSN 0024-6107.  doi: 10.1112/S0024610705022477.  URL https://doi.org/10.1112/S0024610705022477.
  * Granovsky and Stark [2015] B. L. Granovsky and D. Stark.  Developments in the Khintchine-Meinardus Probabilistic Method for Asymptotic Enumeration.  _Electron. J. Combin._ , 22(4):Paper 4.32, 26, 2015.  URL https://doi.org/10.37236/4581.
  * Granovsky et al. [2008] B. L. Granovsky, D. Stark, and M. Erlihson.  Meinardus’ Theorem on Weighted Partitions: Extensions and a Probabilistic Proof.  _Adv. in Appl. Math._ , 41(3):307–328, 2008.  ISSN 0196-8858.  doi: 10.1016/j.aam.2007.11.001.  URL https://doi.org/10.1016/j.aam.2007.11.001.
  * Hardy and Ramanujan [1918] G. H. Hardy and S. Ramanujan.  Asymptotic Formulae in Combinatory Analysis.  _Proc. London Math. Soc. (2)_ , 17:75–115, 1918.  ISSN 0024-6115.  doi: 10.1112/plms/s2-17.1.75.  URL https://doi.org/10.1112/plms/s2-17.1.75.
  * Hwang [1997] H.-K. Hwang.  Distribution of Integer Partitions with Large Number of Summands.  _Acta Arith._ , 78(4):351–365, 1997.  ISSN 0065-1036.  doi: 10.4064/aa-78-4-351-365.  URL https://doi.org/10.4064/aa-78-4-351-365.
  * Hwang [2001] H.-K. Hwang.  Limit Theorems for the Number of Summands in Integer Partitions.  _J. Combin. Theory Ser. A_ , 96(1):89–126, 2001\.  ISSN 0097-3165.  doi: 10.1006/jcta.2000.3170.  URL https://doi.org/10.1006/jcta.2000.3170.
  * Janson [2012] S. Janson.  Simply Generated Trees, Conditioned Galton-Watson Trees, Random Allocations and Condensation.  _Probab. Surv._ , 9:103–252, 2012.  doi: 10.1214/11-PS188.  URL https://doi.org/10.1214/11-PS188.
  * Knessl and Keller [1990] C. Knessl and J. B. Keller.  Partition Asymptotics from Recursion Equations.  _SIAM J. Appl. Math._ , 50(2):323–338, 1990.  ISSN 0036-1399.  doi: 10.1137/0150020.  URL https://doi.org/10.1137/0150020.
  * Leroux et al. [1997] P. Leroux, F. Bergeron, and G. Labelle.  _Combinatorial Species and Tree-Like Structures_ , volume 67 of _Encyclopedia of Mathematics and its Applications_.  Cambridge University Press, Cambridge, 1997.  URL http://www.bibsonomy.org/bibtex/216d18979a45d1a17ca0db4e5f58d3f47/brouder.
  * Łuczak and Pittel [1992] T. Łuczak and B. Pittel.  Components of Random Forests.  _Combin. Probab. Comput._ , 1(1):35–52, 1992\.  ISSN 0963-5483.  doi: 10.1017/S0963548300000067.  URL https://doi.org/10.1017/S0963548300000067.
  * Meinardus [1954] G. Meinardus.  Asymptotische Aussagen über Partitionen.  _Math. Z._ , 59:388–398, 1954.  ISSN 0025-5874.  doi: 10.1007/BF01180268.  URL https://doi.org/10.1007/BF01180268.
  * Mutafchiev [1998] L. Mutafchiev.  The Largest Tree in Certain Models of Random Forests.  _Random Structures & Algorithms_, 13(3‐4):211–228, 1998.  doi: 10.1002/(SICI)1098-2418(199810/12)13:3/4¡211::AID-RSA2¿3.0.CO;2-Y.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291098-2418%28199810/12%2913%3A3/4%3C211%3A%3AAID-RSA2%3E3.0.CO%3B2-Y.
  * Mutafchiev [2011] L. Mutafchiev.  Limit Theorems for the Number of Parts in a Random Weighted Partition.  _Electron. J. Combin._ , 18(1):Paper 206, 27, 2011\.  ISSN 1077-8926.  URL https://doi.org/10.37236/693.
  * Mutafchiev [2013] L. Mutafchiev.  The Size of the Largest Part of Random Weighted Partitions of Large Integers.  _Combin. Probab. Comput._ , 22(3):433–454, 2013\.  ISSN 0963-5483.  doi: 10.1017/S0963548313000047.  URL https://doi.org/10.1017/S0963548313000047.
  * Otter [1948] R. Otter.  The Number of Trees.  _Ann. of Math. (2)_ , 49:583–599, 1948.  ISSN 0003-486X.  doi: 10.2307/1969046.  URL https://doi.org/10.2307/1969046.
  * Palmer and Schwenk [1979] E. M. Palmer and A. J. Schwenk.  On the Number of Trees in a Random Forest.  _J. Combin. Theory Ser. B_ , 27(2):109–121, 1979\.  ISSN 0095-8956.  doi: 10.1016/0095-8956(79)90073-X.  URL https://doi.org/10.1016/0095-8956(79)90073-X.
  * Panagiotou and Ramzews [2018] K. Panagiotou and L. Ramzews.  Asymptotic Enumeration of Graph Classes with Many Components.  In _2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)_ , pages 133–142. SIAM, Philadelphia, PA, 2018.  doi: 10.1137/1.9781611975062.12.  URL https://doi.org/10.1137/1.9781611975062.12.
  * Panagiotou and Sinha [2012] K. Panagiotou and M. Sinha.  Vertices of Degree $k$ in Random Unlabeled Trees.  _J. Graph Theory_ , 69:114–130, 2012.  ISSN 0364-9024.  doi: 10.1002/jgt.20567.  URL https://doi.org/10.1002/jgt.20567.
  * Panagiotou and Steger [2010] K. Panagiotou and A. Steger.  Maximal Biconnected Subgraphs of Random Planar Graphs.  _ACM Trans. Algorithms_ , 6(2):31:1–31:21, 2010\.  ISSN 1549-6325.  doi: 10.1145/1721837.1721847.  URL http://doi.acm.org/10.1145/1721837.1721847.
  * Panagiotou and Stufler [2018] K. Panagiotou and B. Stufler.  Scaling Limits of Random Pólya Trees.  _Probability Theory and Related Fields_ , 170(3):801–820, 2018.  URL https://doi.org/10.1007/s00440-017-0770-4.
  * Panagiotou et al. [2016] K. Panagiotou, B. Stufler, and K. Weller.  Scaling Limits of Random Graphs from Subcritical Classes.  _The Annals of Probability_ , 44(5):3291–3334, 2016.  doi: 10.1214/15-AOP1048.  URL http://dx.doi.org/10.1214/15-AOP1048.
  * Pólya and Szegő [1970] G. Pólya and G. Szegő.  _Aufgaben und Lehrsätze aus der Analysis. Band I: Reihen, Integralrechnung, Funktionentheorie_.  Vierte Auflage. Heidelberger Taschenbücher, Band 73. Springer-Verlag, Berlin-New York, 1970.
  * Stufler [2017] B. Stufler.  Asymptotic Properties of Random Unlabelled Block-weighted Graphs.  _ArXiv e-prints_ , 2017.  URL https://arxiv.org/abs/1712.01301v1.
  * Stufler [2018a] B. Stufler.  Gibbs Partitions: the Convergent Case.  _Random Structures Algorithms_ , 53(3):537–558, 2018a.  ISSN 1042-9832.  URL https://doi.org/10.1002/rsa.20771.
  * Stufler [2018b] B. Stufler.  Random Enriched Trees with Applications to Random Graphs.  _Electron. J. Combin._ , 25(3):Paper 3.11, 81, 2018b.  ISSN 1077-8926.  URL https://doi.org/10.37236/7328.
  * Stufler [2019] B. Stufler.  The Continuum Random Tree is the Scaling Limit of Unlabeled Unrooted Trees.  _Random Structures & Algorithms_, 55(2):496–528, 2019.  ISSN 1042-9832.  doi: 10.1002/rsa.20833.  URL https://doi.org/10.1002/rsa.20833.
  * Stufler [2020] B. Stufler.  Unlabelled Gibbs Partitions.  _Combin. Probab. Comput._ , 29(2):293–309, 2020\.  ISSN 0963-5483.  doi: 10.1017/s0963548319000336.  URL https://doi.org/10.1017/s0963548319000336.
  * Vershik [1996] A. M. Vershik.  Statistical Mechanics of Combinatorial Partitions, and their Limit Configurations.  _Funktsional. Anal. i Prilozhen._ , 30(2):19–39, 96, 1996.  ISSN 0374-1990.  doi: 10.1007/BF02509449.  URL https://doi.org/10.1007/BF02509449.