# Expansive Multisets: Asymptotic Enumeration

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

(August 27, 2024)

###### Abstract

Consider a non-negative sequence $c_{n}=h(n)\cdot n^{\alpha-1}\cdot\rho^{-n}$,
where $h$ is slowly varying, $\alpha>0$, $0<\rho<1$ and $n\in\mathbb{N}$. We
investigate the coefficients of $G(x,y)=\prod_{k\geq 1}(1-x^{k}y)^{-c_{k}}$,
which is the bivariate generating series of the multiset construction of
combinatorial objects. By a powerful blend of probabilistic methods based on
the Boltzmann model and analytic techniques exploiting the well-known saddle-
point method we determine the number of multisets of total size $n$ with $N$
components, that is, the coefficient of $x^{n}y^{N}$ in $G(x,y)$,
asymptotically as $n\to\infty$ and for all ranges of $N$. Our results reveal a
phase transition in the structure of the counting formula that depends on the
ratio $n/N$ and that demonstrates a prototypical passage from a bivariate
local limit to an univariate one.

###### Contents

  1. 1 Introduction and Main Results
    1. 1.1 Main Results
    2. 1.2 Notes on the Proof & Perspective
    3. 1.3 Plan of the Paper
  2. 2 Preparations
    1. 2.1 Existence, Uniqueness and Properties of $N^{*}_{n}$ and $({x}_{n},y_{n})$
    2. 2.2 Probabilistic Estimates
    3. 2.3 Estimates for Power Series
    4. 2.4 Euler-Maclaurin Summation
  3. 3 General Proof Strategy
    1. 3.1 Proof Setup: the Boltzmann Model
    2. 3.2 Proof of the Main Results
  4. 4 Proofs
    1. 4.1 Proof of Lemma 3.1
    2. 4.2 Proof of Lemma
      1. 4.2.1 Proof of Lemma 3.3(I)
      2. 4.2.2 Proof of Lemma 3.3(II)
    3. 4.3 Proof of Lemma 3.3(II)
    4. 4.4 Proof of Lemma 3.4(II)
    5. 4.5 Proof of Lemma 3.6
    6. 4.6 Proof of Lemma 3.7
    7. 4.7 Proof of Corollaries 3.8 and 3.9
    8. 4.8 Proof of Lemma 3.9
      1. 4.8.1 Proof of Lemma 3.10(I)
      2. 4.8.2 Proof of Lemma 3.10(II)
    9. 4.9 Proof of Lemma 3.10(II)
    10. 4.10 Proof of Theorem 1.1
  5. A Appendix: Slowly Varying Functions

##  1 Introduction and Main Results

##### Multisets

The focus of this work is on a simple, yet powerful and ubiquitous
construction. Given a set ${\mathcal{C}}$, we define the class
${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$ of _${\mathcal{C}}$ -multisets_
or _partitions weighted by ${\mathcal{C}}$_ to be the collection of all
elements of the form

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

The tuple $(C,d)$ (informally) means that the object $C\in{\mathcal{C}}$
occurs $d$ times in the multiset. The asymptotic study – enumeration,
properties, limit laws – of multisets has a long and rich history. One of the
very first and monumental results in this context was achieved by Hardy and
Ramanujan [23], who studied number partitions, which are nothing else than
multisets of natural numbers, i.e., ${\mathcal{C}}=\mathbb{N}$ in our
notation. They discovered the beautiful asymptotic formula

$|{\cal
P}_{n}|\sim\frac{1}{4\sqrt{3}n}\exp\left\\{\pi\sqrt{\frac{2}{3}n}\right\\},\quad\textrm{as
}n\to\infty,$

where ${\cal P}_{n}$ contains all number partitions of $n\in\mathbb{N}$. In
their paper they made the simple, though substantial, observation that a very
general class of enumeration problems can be solved by applying Cauchy’s
formula and performing an appropriate analysis of the resulting complex
integral. This powerful idea, which is nowadays known as the _saddle-point
method_ or _method of steepest descent_ and which is (much) older than [23],
has seen tremendous extensions, has been rediscovered numerous times, and has
seen widespread applications in various fields inside and outside of
mathematics, particularly in physics. The field is far too broad so that we
could review it here; we refer to the classical textbook [11], the modern
exposition [34], and to the excellent treatments in [15, 41], which also put a
particular emphasis on the combinatorial perspective.

Another predominant idea in this area is to reformulate the counting problem
into a probabilistic question, so as to profit from probability theory’s huge
toolbox. A central result was established by Arratia and Tavaré [1], who
showed that many random combinatorial objects possess a component structure
whose joint distribution is equal to that of random variables that are
conditioned to have a specific (weighted) sum and are otherwise _independent_.
This, of course, rings the bell of every probabilist and calls for local limit
theorems. Moreover, it lies at the core of  _Khinchin’s probabilistic method_
that originated in [28], see [16] for some historical perspective, and that
makes the relation of counting and probability a general and guiding
principle.

In this paper we are concerned with the asymptotic enumeration of multisets,
and the two fundamentally different methods/principles will play an important
role in what is to come. To be precise, assume for the moment that
${\mathcal{C}}$ is a combinatorial class, that is, it is equipped 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 $n\in\mathbb{N}$. Then we associate to elements in
${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$ in a natural way a (total) size
and a number of components, that is,

$\lvert G\rvert:=\sum_{1\leq i\leq k}d_{i}\lvert
C_{i}\rvert,\quad\kappa(G):=\sum_{1\leq i\leq
k}d_{i},\qquad\textrm{where}\qquad
G=\big{\\{}(C_{1},d_{1}),\dots,(C_{k},d_{k})\big{\\}}\in{\mathcal{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}.$

We write $C(x):=\sum_{k\geq 1}\lvert{\mathcal{C}}_{k}\rvert x^{k}$ for the
generating series of ${\mathcal{C}}$. Then it is well-known, see [15, 32],
that the bivariate generating series for the class ${\mathcal{G}}$ fulfills
the fundamental relations

$G(x,y):=\sum_{k,\ell\geq 1}\lvert{\mathcal{G}}_{k,\ell}\rvert
x^{k}y^{\ell}=\prod_{k\geq
1}(1-x^{k}y)^{-c_{k}}=\mathrm{exp}\bigg{\\{}\sum_{j\geq
1}C(x^{j})y^{j}/j\bigg{\\}}.$

For a generating series $F(x)$ we will write $[x^{n}]F(x)$ for the coefficient
of $x^{n}$ in $F(x)$, and for a bivariate series $F(x,y)$ we will denote by
$[x^{n}y^{N}]F(x,y)$ the coefficient of $x^{n}y^{N}$ in $F(x,y)$. As already
mentioned, if ${\mathcal{C}}=\mathbb{N}$, then we obtain the class of number
partitions ${\mathcal{P}}=\text{{Mset}}(\mathbb{N})$ and
$\lvert{\mathcal{P}}_{n}\rvert=[x^{n}]G(x,1)$, which is the starting point for
the analytical methods employed in [23]. Naturally, the determination of
$g_{n}:=[x^{n}]G(x,1)$ for general $C(x)$, respectively
$(|{\mathcal{C}}_{n}|)_{n\geq 1}$, has become a very active research topic.
From today’s viewpoint, the asymptotic value of $g_{n}$ is very well-
understood and was determined under various general conditions and for several
specific classes. A particularly prominent and broad setting, and the one
considered here, is when

$\displaystyle c_{n}:=|{\mathcal{C}}_{n}|=h(n)\cdot
n^{\alpha-1}\cdot\rho^{-n},\quad\leavevmode\nobreak\
\alpha\in\mathbb{R},\leavevmode\nobreak\ 0<\rho\leq 1,$ (1.1)

where $h:[1,\infty)\to[0,\infty)$ is an eventually positive, continuous and
slowly varying, which means that

$\lim_{x\to\infty}\frac{h(\lambda x)}{h(x)}=1\leavevmode\nobreak\ \text{ for
all }\leavevmode\nobreak\ \lambda>0.$

As it turns out, depending on the value of $\alpha$ the models have fairly
different features. The state-of-the-art results for multiset enumeration,
i.e., the (asymptotic) determination of $g_{n}=[x^{n}]G(x,1)$ in the so-called
_expansive_ case $\alpha>0$ are by Granovsky and Stark [20], whereas the
_logarithmic_ case $\alpha=0$ is treated in the excellent book by Arratia et
al. [2] and the _convergent_ case $\alpha<0$ is studied in Stufler [43]. There
are many other treatises that also highlight several other aspects, like the
typical structure of multisets, and that provide explicit formulas [21, 36,
35, 22, 16, 3, 5, 33], the methods ranging from purely analytic to
probabilistic as previously described.

##### Our Contribution

While the enumeration problem is fairly well-studied, the fundamental question
about the distribution of the number of components in a (uniformly random)
multiset, and in particular the asymptotic determination of
$g_{n,N}:=|{\mathcal{G}}_{n,N}|$, is far less understood and actually much
more complex. Indeed, both the saddle-point method and the probabilistic
method hit a barrier. In the saddle point method, we are faced with an
integral over $\mathbb{C}^{2}$ and obtaining control over the integration
contour is – as the orders of magnitude of $n$ and $N$ may be vastly
incompatible – extremely challenging from a technical viewpoint; in the
probabilistic method, on the other hand, we have to deal with bivariate local
limit theorems for random variables with a specific dependency structure.
Although there are many general and notable results that address the
multivariate setting in both the analytic and probabilistic settings, see for
example the extensive treatment in [41], they are not sufficient for the
desired level of generality considered here.

In this paper we study the expansive case $\alpha>0$ in (1.1) and we
demonstrate that a _combination_ of both methods is very effective for
determining $g_{n,N}$ (and not only …) in all relevant cases, that is, when
$n\to\infty$ and $N$ is not too close to one or to the maximum possible number
of components. Indeed, we first set up an appropriate probabilistic framework,
which differs substantially from the “classical” aforementioned ones used in
enumeration of multisets; to wit, the previous approaches, that are directly
or indirectly based on [28], use a description with negative binomials, while
our approach, which is inspired by modern Boltzmann sampling techniques in
combinatorics [7], makes use of Poisson variables. A thorough discussion and
comparison is made in Section 1.2. Having achieved this, we use probabilistic
methods to reduce the determination of $g_{n,N}$ to an one dimensional
problem, which then, in turn, is tackled with the saddle-point method. At this
point it seems unavoidable to resort to probabilistic methods only, as the
problem involves a genuine triangle array of random variables for which we
need a local limit theorem.

Before we build up the theory and present the results in the following
sections we review some previous work that addresses the determination of
$g_{n,N}$ in specific settings. In the context of number partitions ${\cal
P}=\textsc{Mset}(\mathbb{N})$ the picture is quite clear. In [29] the
asymptotic order of $|{\cal P}_{n,N}|$ for $n,N,n-N\to\infty$ is determined
and a phase transition, depending on whether $N$ is $\mathcal{O}(n^{1/2})$ or
$\omega(n^{1/2})$, in the structure of the counting sequence is observed. For
$N\geq d\sqrt{n}\ln n$ and $d>d_{0}$ for some $d_{0}>0$ it is even true that
$g_{n,N}\sim|{\cal P}|_{n-N}$, as shown in [24]. Another setting in which the
picture is fully described is the subexponential case in (1.1), that is, when
$\alpha<0$. For example, if $c_{1}=1$, the authors showed that there is an
$A>0$ such that $g_{n,N}\sim Ac_{n-N}$ for all $n,N,n-N\to\infty$, that is,
the number of $N$-component ${\mathcal{C}}$-multisets is proportional to
$c_{n-N}$ for all ranges of $n-N$. The result was shown with the help of a
probabilistic method, but as the result itself suggests, this bivariate
problem is actually and in essence a univariate one. Finally, in the expansive
case ${\mathcal{G}}=\textsc{Mset}({\mathcal{C}})$, under the stronger
assumptions $c_{n}\sim Cn^{\alpha-1}$ for $C>0$, $\alpha>0$ and additional
analytical assumptions, $g_{n,N}$ was determined asymptotically for
$N=\omega(\ln^{3}n)$ and $N=o(n^{\alpha/(\alpha+1)})$ in Stark [42]. Actually,
in that paper the author accomplishes the herculean task of performing a
bivariate saddle-point integration, though only for a limited range of the
parameters. In any case, the results of [42] give reason to conjecture that
$g_{n,N}$, as in the case of number partitions, undergoes a phase transition
depending on the ratio of $N$ and $n^{\alpha/(\alpha+1)}$ in this general
setting as well. We will confirm in this paper that such transitions are
prototypical for the considered counting problems.

###  1.1 Main Results

Let us fix the setting that we consider. Let $h:[1,\infty)\to[0,\infty)$ be an
eventually positive, continuous and slowly varying function. Consider the
real-valued sequence $(c_{n})_{n\in\mathbb{N}}$ given by

$\displaystyle c_{n}=h(n)\cdot n^{\alpha-1}\cdot\rho^{-n}\quad\text{where
}\alpha>0,0<\rho<1\text{ and }n\in\mathbb{N}.$ (1.2)

Note that there are two differences to (1.1). First, the sequence here does
not have to be a counting sequence, since the $c_{n}$’s may not be integral.
Second, we assume $\rho<1$ and exclude the single case $\rho=1$, as our
methods necessitate this. Following [20], we call sequences
$(c_{k})_{k\in\mathbb{N}}$ fulfilling (1.2) _expansive_. We also say that the
corresponding generating series $C(x):=\sum_{k\geq 1}c_{k}x^{k}$ is expansive.

Further, define $m=m(C)\in\mathbb{N}$ to be the smallest integer such that
$c_{m}\neq 0$, that is, $c_{1}=\cdots=c_{m-1}=0$ and $c_{m}>0$.
Recall/consider the power series

$\displaystyle G(x,y):=\exp\left\\{\sum_{j\geq
1}\frac{C(x^{j})}{j}y^{j}\right\\}\quad\text{and}\quad G^{\geq
2}(x,y):=\exp\left\\{\sum_{j\geq 2}\frac{C(x^{j})}{j}y^{j}\right\\}.$ (1.3)

Note that since we defined $(c_{n})_{n\in\mathbb{N}}$ to be real-valued the
series $G(x,y)$ has a priori no combinatorial meaning. However, if
$(c_{n})_{n\in\mathbb{N}}$ is the counting sequence of a combinatorial class
${\mathcal{C}}$, then, as we saw previously, $G(x,y)$ is the generating series
of ${\mathcal{G}}=\text{{Mset}}({\mathcal{C}})$, where $x$ tags the size and
$y$ the number of components. Nonetheless, we study $G(x,y)$ as a series
having possibly non-integral coefficients for the rest of this work unless
stated otherwise. The series $G^{\geq 2}(x,y)$ is an auxiliary object that we
will need later.

As already mentioned, the quantity $g_{n}=[x^{n}]G(x,1)$ is a well-researched
object. The authors of [20] investigated, among other cases, $g_{n}$ in the
expansive case. We present the following theorem that is a straightforward
consequence from the results and their proofs in [20, Thm. 1 and Cor. 1].
However, as we use a different notation and the connection to [20] is not
immediately obvious, we will give a short self-contained two-page proof that
also demonstrates our methodology quite well in Section 4.10.

######  Theorem 1.1.

Suppose that $C(x)$ is expansive as in (1.2). Let $z_{n}$ be the unique
solution to $z_{n}C^{\prime}(z_{n})=n$. Then, as $n\to\infty$,

$z_{n}\sim\rho\quad\textrm{and}\quad[x^{n}]G(x,1)\sim G^{\geq
2}(\rho,1)\cdot\frac{\exp\left\\{C(z_{n})\right\\}}{\sqrt{2\pi
z_{n}^{2}C^{\prime\prime}(z_{n})}}\cdot z_{n}^{-n}.$ (LLT)

The form of the enumeration result (LLT) is prototypical: there is a saddle-
point ($z_{n}$), an exponential term ($z_{n}^{-n}$), a term in which the power
series is evaluated ($G^{\geq 2}(\rho,1)\exp{C(z_{n})}\sim G(z_{n},1)$), and a
polynomial term $(2\pi z_{n}^{2}C^{\prime\prime}(z_{n}))^{-1/2}$. The latter
is the result of an appropriate integration around the saddle point, or, in a
terminology that we prefer here, the result of a local limit theorem, i.e.,
the probability that a sum of specific independent and identically distributed
random variables equals its mean. We will see much more of that later. Let us
remark, however, that in the generality considered here, we cannot expect to
be able to say much more than (LLT): in general, it is not possible to derive
a more explicit asymptotic expression for $\exp\\{C(z_{n})\\}$ (though it is
possible to do so for $C(z_{n})$ and for its derivatives), and the actual
order of magnitude depends very much on the micro-structure of $h$.

We now move on the main mission of this work, namely the study of
$g_{n,N}=[x^{n}y^{N}]G(x,y)$. We need some preparations. For
$(n,N)\in\mathbb{N}^{2}$ consider the system of equations in the variables
$x,y$

$\displaystyle xyC^{\prime}(x)+mc_{m}\frac{x^{m}y}{1-x^{m}y}=n,\enspace
yC(x)+c_{m}\frac{x^{m}y}{1-x^{m}y}=N,\enspace x,y>0\enspace\text{and}\enspace
x^{m}y<1.$ (1.4)

We will explain later in detail where these equations come from and only tease
for now that the left-hand sides are (more or less) the expected value of the
size and the number of components, which we “tune” to $n$ and $N$,
respectively, in a specifically designed random multiset. Equations (1.4) are
– in some sense – the bivariate equivalent of the saddle-point equation in
Theorem 1.1. Further, for $v\in\mathbb{R}^{+}$ consider the equation in the
single variable $u$

$\displaystyle u\cdot h(u)^{1/(\alpha+1)}=v^{1/(\alpha+1)}\quad\text{and}\quad
1\leq u\leq v.$ (1.5)

Our first auxiliary result is that the previous systems of equations have
unique solutions.

######  Lemma 1.2.

The following statements are true.

  1. (i)

Suppose that $C(x)$ is expansive. For $n,N$ and $n-mN$ sufficiently large
there is a unique solution $(x_{n,N},y_{n,N})$ to (1.4).

  2. (ii)

For $v$ sufficiently large there is a unique solution $u_{v}$ to (1.5) given
by $u_{v}=v^{1/(\alpha+1)}/g(v)$, where $g:\mathbb{R}^{+}\to\mathbb{R}^{+}$ is
slowly varying.

With the slowly varying function $g$ from Lemma 1.2(ii) at hand, define the
“magic” value

$\displaystyle N_{n}^{*}:=C_{0}\cdot g(n)\cdot
n^{\alpha/(\alpha+1)},\quad\text{where}\quad
C_{0}:=\alpha^{-1}{(\rho^{-m}\Gamma(\alpha+1))^{{1}/(\alpha+1)}}.$ (1.6)

As we will see shortly, the quantity $N^{*}_{n}$ marks a phase transition in
the structure of the counting sequence $[x^{n}y^{N}]G(x,y)$ (and much more …)
dependent on whether $N/N^{*}_{n}<1$ or $N/N^{*}_{n}>1$. More precisely,
assume that we are given a real-valued positive sequence
$(\lambda_{n})_{n\in\mathbb{N}}$ such that, as $n\to\infty$,

$\displaystyle N_{n}=\lambda_{n}N^{*}_{n}\in\mathbb{N},\quad
N_{n}\to\infty\quad\text{and}\quad n-mN_{n}\to\infty.$ (1.7)

Note that by these definitions $N_{n}$ becomes a function of $n$ and the
solutions $({x}_{n},y_{n})\equiv(x_{n,N_{n}},y_{n,N_{n}})$ to (1.4) and
$N^{*}_{n}$ from (1.6) are all well defined for sufficiently large $n$ due to
Lemma 1.2. We will from now on distinguish the two cases

$(I):\limsup_{n\to\infty}\lambda_{n}<1\qquad\text{and}\qquad(II):\liminf_{n\to\infty}\lambda_{n}>1.$

Our first main result determines the asymptotic growth (in several equivalent
forms that have their own merits) of $[x^{n}y^{N_{n}}]G(x,y)$ as $n\to\infty$
in case $(I)$.

######  Theorem 1(I).

Suppose that $C(x)$ is expansive. In case $(I)$, that is, if
$\limsup_{n\to\infty}\lambda_{n}<1$,

$\displaystyle[x^{n}y^{N_{n}}]G(x,y)$ $\displaystyle\sim G^{\geq
2}(\rho,y_{n})\cdot\frac{\exp\left\\{y_{n}C({x}_{n})\right\\}}{2\pi\sqrt{N_{n}y_{n}{x}_{n}^{2}C^{\prime\prime}({x}_{n})/(\alpha+1)}}\cdot{x}_{n}^{-n}y_{n}^{-N_{n}}$
(LLT-I) $\displaystyle\sim G^{\geq
2}(\rho,y_{n})\cdot\frac{\sqrt{\alpha}}{2\pi}\cdot\exp\bigg{\\{}-\frac{c_{m}\rho^{m}y_{n}}{1-\rho^{m}y_{n}}\bigg{\\}}\cdot\frac{1}{n}\cdot{x}_{n}^{-n}(y_{n}/\mathrm{e})^{-N_{n}}$
(Explicit-I) $\displaystyle\sim G^{\geq
2}(\rho,y_{n})\cdot\frac{1}{N_{n}!}[x^{n}]C(x)^{N_{n}}.$ (Comb-I)

Some remarks are in place. First, (LLT-I) is the prototypical form of the
result that very much resembles (LLT) in a bivariate setting. The second form
(Explicit-I) is handy and most convenient to work with, as it includes no
evaluation of derivatives and – crucially – powers of $C$ at the saddle point.
We feel lucky that we were able to derive such a form of the sequence, and
this is mostly owed to the structure of the Equations (1.4) that have a very
special property in case $(I)$ (just to look ahead a bit, in that case
$x^{m}y$ stays bounded away from one, so that $1/(1-x^{m}y)$ remains bounded).
The last identity (Comb-I) hints at an interesting fact when $G(x,y)$ is
viewed in the combinatorial setting, i.e., as the generating series of
multisets of a class $\cal C$. Indeed, $C(x)^{N}$ is the generating series for
_sequences_ $(C_{1},\dots,C_{N})$ that are composed of $N$ objects from $\cal
C$. Then $C(x)^{N}/N!$ enumerates _sets_ $\\{C_{1},\dots,C_{N}\\}$, _provided
that all elements are distinct_ ; otherwise there is no reasonable
interpretation. So, (Comb-I) may let us speculate that a typical $\cal
C$-multiset in ${\mathcal{G}}_{n,N_{n}}$ has only distinct components, and
moreover, that we can accurately describe a typical/random element in
${\mathcal{G}}_{n,N_{n}}$ by a sequence of $N_{n}$ objects from $\cal C$ that
are conditioned to have total size $n$ and are otherwise independent. All this
and actually much more is somehow true as we show in the companion paper [38],
where we study limit laws of random multisets in ${\mathcal{G}}_{n,N_{n}}$.

Let us finish the discussion about Theorem 1(I) with the following remark. If
$\lambda:=\lim_{n\to\infty}\lambda_{n}\in[0,1)$ exists, then, as we shall see
in Lemma 4.1 below, $\lim_{n\to\infty}y_{n}=\rho^{-m}\lambda^{\alpha+1}$.
Consequently, by writing $d(\lambda)=G^{\geq
2}(\rho,\rho^{-m}\lambda^{\alpha+1})$, the counting sequence has the
simple(-r) form

$[x^{n}y^{N_{n}}]G(x,y)\sim
d(\lambda)\cdot\frac{1}{N_{n}!}[x^{n}]C(x)^{N_{n}}\sim
d(\lambda)\cdot\frac{\sqrt{\alpha}}{2\pi}\cdot\exp\bigg{\\{}-\frac{c_{m}\lambda^{\alpha+1}}{1-\lambda^{\alpha+1}}\bigg{\\}}\cdot\frac{1}{n}\cdot{x}_{n}^{-n}(y_{n}/\mathrm{e})^{-N_{n}}.$

In order to treat $g_{n,N}$ in the second case $(II)$ we define

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

Let us give a quick explanation for the choice of notation. Consider the class
${\mathcal{C}}_{>m}$ of all elements in ${\mathcal{C}}$ of size greater than
$m$ together with the modified size function $\lvert C\rvert_{>m}:=\lvert
C\rvert-m>0$ for all $C\in{\mathcal{C}}_{>m}$. We obtain that the generating
series of ${\mathcal{C}}_{>m}$ is given by
$C_{>m}(x)=(C(x)-c_{m}x^{m})/x^{m}$. Then the generating series of
${\mathcal{G}}_{>m}:=\text{{Mset}}({\mathcal{C}}_{>m})$ is given by
$G_{>m}(x)=\textrm{exp}\\{\sum_{j\geq 1}C_{>m}(x^{j})/j\\}$. The superscript
in $G_{>m}^{\geq 2}$ accounts for the fact that we only sum up starting at
$j=2$.

######  Theorem 1(II).

Suppose that $C(x)$ is expansive. In case $(II)$, that is, if
$\liminf_{n\to\infty}\lambda_{n}>1$, there is a non-negative sequence
$(a_{n})_{n\in\mathbb{N}}$ given by

$a_{n}:=\lambda_{n}^{-1}\cdot\frac{g(n-mN_{n})}{g(n)}\cdot\left(\frac{n-mN_{n}}{n}\right)^{\alpha/(\alpha+1)}$

such that

$\displaystyle[x^{n}y^{N_{n}}]G(x,y)$ $\displaystyle\sim G_{>m}^{\geq
2}(\rho)\cdot\frac{\exp\left\\{C_{>m}({x}_{n})\right\\}}{\sqrt{2\pi\rho^{-m}{x}_{n}^{2}C^{\prime\prime}({x}_{n})}}\cdot{x}_{n}^{-(n-mN_{n})}$
(LLT-II) $\displaystyle\sim G_{>m}^{\geq
2}(\rho)\cdot\frac{\big{(}(1-a_{n})N_{n}\big{)}^{c_{m}-1}}{\Gamma(c_{m})}\cdot[x^{n-mN_{n}}]\mathrm{e}^{C_{>m}(x)},\quad
n\to\infty.$ (Comb-II)

We have again remarks. First, (LLT-II) is the classical form that looks like
(LLT-I) and (LLT). Note that, however, (LLT-II) looks much more like (LLT) in
the sense that it resembles a _uni_ variate local limit theorem – $y_{n}$ does
not appear in the formulation at all! This simplification is quite surprising,
as we would expect a bivariate law like in Theorem 1(I). Here the alternative
form (Comb-II) comes to help and gives – as before – a hint about what may be
going on. When $G(x,y)$ is the generating series of ${\mathcal{C}}$-multisets,
then $[x^{n}y^{N}]G(x,y)$ is the number of such multisets with $N$ components
and size $n$. But the factor

$((1-a_{n})N)^{c_{m}-1}/\Gamma(c_{m})\sim\binom{(1-a_{n})N+c_{m}-1}{c_{m}-1}$

in (Comb-II) counts the number of ways to create a multiset with
$\sim(1-a_{n})N$ objects from ${\mathcal{C}}_{m}$. Where are the remaining
$a_{n}N$ components? For the other term note that
$\exp\left\\{C_{>m}(x)\right\\}=\sum_{k\geq 0}C_{>m}(x)^{k}/k!$. Then, as
before, $C_{>m}(x)^{k}$ is the generating series of sequences of
${\mathcal{C}}_{>m}$-objects of length $k$ and, provided all elements in the
sequence are distinct, $C_{>m}(x)^{k}/k!$ counts sets of $k$ objects. Then
$[x^{n-mN}]\exp\left\\{C_{>m}(x)\right\\}$ enumerates _sets_ of distinct
${\mathcal{C}}_{>m}$-objects with a varying number of components, which,
however, concentrates around $a_{n}N$, and thus with (actual) size $\sim
n-mN_{n}(1-a_{n})$. Concluding, we may speculate that a typical
${\mathcal{C}}$-multiset in ${\mathcal{G}}_{n,N}$ contains a random set of
$N^{\prime}$ (that typically is $\sim a_{n}N$) components with size $>m$, and
the remaining $N-N^{\prime}$ components are of size $m$. So, since there is no
restriction for the component count for objects of size $>m$, we arrive at a
univariate limit law as in (LLT-II). Finally, let us note that in case $(II)$
an explicit form as in (Explicit-I) is in general out of reach due to the
reasons outlined after Theorem 1.1 – although it is possible to establish the
first order of $C_{>m}(x_{n})$ (and its derivatives), achieving a similar
statement for $\exp\left\\{C_{>m}(x_{n})\right\\}$ seems intractable in the
general setting considered here.

Let us finish the discussion about Theorem 1(II) with the following remark. As
we will see in Lemma 4.2 below, if the limit
$\lambda:=\lim_{n\to\infty}\lambda_{n}$ exists, then $a_{n}\sim\lambda^{-1}$
so that defining $d(\lambda):=G_{>m}^{\geq
2}(\rho)(1-\lambda^{-1})^{c_{m}-1}$, Theorem 1(II) yields the slightly simpler
form

$[x^{n}y^{N_{n}}]G(x,y)\sim
d(\lambda)\cdot\frac{N^{c_{m}-1}}{\Gamma(c_{m})}\cdot[x^{n-mN_{n}}]\mathrm{e}^{C_{>m}(x)}.$

Let us close this section with a final remark. We, unfortunately, cannot offer
a Theorem $(I\textrm{\textonehalf})$ that describes what happens when
$\lambda_{n}\to 1$. The point is that the answer actually depends on how this
limit is approached and at what speed. In this context we leave it as an open
problem to describe the scaling window and the exact behavior in- and outside
of it.

###  1.2 Notes on the Proof & Perspective

Let us consider the combinatorial setting in which $C(x)$ is the generating
series of a combinatorial class ${\mathcal{C}}$ and $G(x,y)$ is the
(bivariate) generating series of ${\mathcal{G}}$, the class of all
${\mathcal{C}}$-multisets. The main idea of the proof is to translate the task
of determining $g_{n,N}=[x^{n}y^{N}]G(x,y)$ into a probabilistic problem by
considering a multiset $\mathsf{G}_{n}$ drawn uniformly at random from
${\mathcal{G}}_{n}$. Let us first discuss the quantity $g_{n}:=[x^{n}]G(x,1)$
– the _total_ number of multisets of size $n$ with no restrictions on the
number of components – for which this kind of analysis has already been
carried out successfully in several cases. Assume that we have at our disposal
a randomized algorithm/stochastic process $\mathsf{G}$ that outputs elements
from ${\mathcal{G}}$ with _a priori_ no control on the size or the number of
components, but with the guarantee that all objects of the same size are
equiprobable. Then

$\displaystyle\frac{1}{g_{n}}=\mathrm{Pr}\left[\mathsf{G}_{n}=G\right]=\frac{\mathrm{Pr}\left[\mathsf{G}=G\right]}{\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n\right]}\quad\text{for
any }G\in{\mathcal{G}}_{n}.$ (1.8)

The goal is to find an algorithm such that we can determine/estimate the terms
in the latter expression, namely $\mathrm{Pr}\left[\mathsf{G}=G\right]$ (that
is usually easy, by design of the algorithm) and
$\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n\right]$ (the hard one). As it turns
out, such algorithms exist and two different approaches stand out in the
literature.

The first and classical approach, based on Khinchin’s probabilistic method and
also referred to as _conditioning relation_ , generates $\mathsf{G}$ by
(first) sampling for each $k\in\mathbb{N}$ independently a random number
$X_{k}$ of components of size $k$; thus $|\mathsf{G}|=\sum_{k\geq 1}kX_{k}$.
The “right” choice for $X_{k}$ is a negative binomial distribution with
parameters $(c_{k},{x}_{n}^{k})$ for a control value ${x}_{n}$. This is
related to the alternative (and equivalent) representation of the generating
function (1.3) for $\cal C$-multisets given by

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

for $y=1$, see [15, 32]. Then, by “tuning” ${x}_{n}$ such that
$\mathbb{E}\left[\lvert\mathsf{G}\rvert\right]=n$ a local limit theorem for
$\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n\right]$ can be shown to be true in
certain cases. For example, if $c_{n}=\Theta(n^{\alpha-1}\rho^{-n})$ with
$\alpha>0,0<\rho\leq 1$ the authors of [20] proceed as described to determine
$g_{n}$ asymptotically. This tuning procedure is in general a feasible method
for expansive multisets, as $\mathbb{E}\left[\lvert\mathsf{G}\rvert\right]$ is
proportional to $C^{\prime}({x}_{n})/C({x}_{n})$ and
$\lim_{{x}_{n}\to\rho}C^{\prime}({x}_{n})=\infty$ for $\alpha>0$; in other
cases, in particular when $\alpha<0$, tuning is not possible. The conditioning
relation is also used by other authors for solving various related problems,
see for example the aforementioned works [21, 35, 22, 3, 2, 17]. Some
historical remarks about Khinchin’s probabilistic method [28] are made in
[16].

On the other hand, and this is the method that we choose and develop further
in this work, the _Pólya-Boltzmann model_ [8] is used to find a decomposition
of $\mathsf{G}$ into random ${\mathcal{C}}$-objects attached to cycles of a
random permutation, which is helpful to get rid of cumbersome appearances of
symmetries and that gives rise to Poisson distributions instead of negative
binomials; this difference is reflected by the two different representations
(1.3) and (1.9). Again we obtain independent random variables tuned by a
control parameter ${x}_{n}$ that can be used to describe
$\lvert\mathsf{G}\rvert$ in a better-to-handle manner. For a precise
description of the involved random variables have a peek at Section 3, where
we present (a _bi_ variate extension of) the framework in full detail. The
crucial property of the corresponding variables is that all objects attached
to cycles of length $j\geq 2$ in the permutation are drawn according to a
probability distribution with mean proportional to $C({x}_{n}^{j})$. Since
$0<{x}_{n}\leq\rho$ we infer that $C({x}_{n}^{j})$ is decreasing exponentially
fast in $j$ for $0<\rho<1$. Hence, objects associated to fixpoints, that is,
for $j=1$, are dominant in the structure of $\mathsf{G}$; this essentially
reduces the analysis to the study of iid random variables, rendering this
method particularly useful whenever $0<\rho<1$. For example, [43] determines
(among other more general things) $g_{n}$ with this technique in the prominent
setting where $c_{n}$ is subexponential, which corresponds to our setting with
$\alpha<0$. For other applications of the Pólya-Boltzmann model regarding
random multisets, see for instance [40, 39].

Let us return to our actual problem, where we want to find an asymptotic
expression for $g_{n,N}$ as $n\to\infty$ and for essentially all $N\to\infty$.
As in (1.8) we obtain

$\displaystyle\frac{g_{n,N}}{g_{n}}=\mathrm{Pr}\left[\kappa(\mathsf{G}_{n})=N\right]=\frac{\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n,\kappa(\mathsf{G})=N\right]}{\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n\right]}.$
(1.10)

Here we see a major difficulty that suddenly may appear: the one-parametric
models have the property $\mathbb{E}\left[\lvert\mathsf{G}\rvert\right]=n$
that we obtained by tuning ${x}_{n}$, but at the same time
$\mathbb{\kappa(\mathsf{G})}$ can possibly be far away from $N$. This,
however, is not always a problem, and the one-parameteric models can also be
useful, as demonstrated in [37] in the aforementioned subexponential case. On
the other hand, in the expansive case a two-parametric description of
$\mathsf{G}$ must be found in order to tune the expectation of
$\kappa(\mathsf{G})$ to be (close to) $N$. Then the problem of determining
$g_{n,N}$ boils down to finding a two-dimensional local limit law for
$K_{n,N}:=\mathrm{Pr}\left[\lvert\mathsf{G}\rvert=n,\kappa(\mathsf{G})=N\right]$.
Achieving this is a difficult problem, since there is a significant interplay
between $\lvert\mathsf{G}\rvert$ and $\kappa(\mathsf{G})$. The author of [42]
solved this problem under the assumption that $c_{n}\sim Cn^{\alpha-1}$ for
$C,\alpha>0$ and the restrictions $N=o(n^{\alpha/(\alpha+1)})$ and
$N=\omega(\ln^{3}n)$ by using the conditioning relation and a bivariate
saddle-point integration. Other parameter ranges have not been studied as far
as we are aware of.

In this work we consider the general setting (1.2). To get a grip on $K_{n,N}$
we conduct a novel application of a bivariate Boltzmann model with the
parameters ${x}_{n,N}$ and $y_{n,N}$ solving (1.4). This solution asserts
(more or less) that $\mathbb{E}\left[\lvert\mathsf{G}\rvert\right]=n$ and
$\mathbb{E}\left[\kappa(\mathsf{G})\right]=N$. As the two parameters interact
in a complex way such that depending on the ratio of $n$ and $N$ the main
contribution to $\lvert\mathsf{G}\rvert$ or $\kappa(\mathsf{G})$ is not
necessarily given only by the fixpoints anymore, we come to the conclusion
that there is a phase transition in $N$ at which the behaviour of $g_{n,N}$
changes significantly. This can be recognized in the different natures of
Theorems 1(I) and 1(II).

###  1.3 Plan of the Paper

The preparations for the proofs of the main theorems are contained in Section
2, which is a collection of many auxiliary results and technical statements.
In particular, properties of ${x}_{n},y_{n},N^{*}_{n}$ and more general
results regarding coefficients of products of certain power series tailored to
our needs are derived. In Section 3.1 we begin with the proof and introduce
the Boltzmann model. Subsequently, we present the proof of our main theorems
in a layered structure starting with the statement of more general important
lemmas in Section 3.2, where we also describe how they can be combined such as
to arrive at the assertions of Theorems 1(I) and 1(II). The respective proofs
of these lemmas can be then found in Section 4. Finally, some general
(textbook) results about slowly varying functions are placed in the self-
contained Appendix A.

##### Acknowledgements

The authors are grateful to Michael Drmota who gave valuable insights into the
saddle-point method.

##  2 Preparations

In this section we start by exposing some general results that are relevant
for all forthcoming proofs in the paper: in Section 2.1 we prove Lemma 1.2
establishing the existence and uniqueness of the solutions to (1.4) and (1.5).
Then, in Section 2.2 we recall some well-known probabilistic estimates about
Poisson distributed random variables. Subsequently, Section 2.3 contains
statements about large coefficients of products of power series. Finally, the
Euler-Maclaurin-formula that will help us to approximate sums by integrals is
presented in Section 2.4.

###  2.1 Existence, Uniqueness and Properties of $N^{*}_{n}$ and
$({x}_{n},y_{n})$

In this section we prove Lemma 1.2 and find some further properties of
${x}_{n},y_{n}$ and $N^{*}_{n}$.

###### Proof of Lemma 1.2(i).

Define the power series $S:\mathbb{R}_{+}\to\mathbb{R}\cup\\{\infty\\}$,
$z\mapsto\sum_{k\geq 1}z^{k}$ and consider the system of equations

$\displaystyle xyC^{\prime}(x)+mc_{m}S(x^{m}y)$ $\displaystyle=n,$ (2.1)
$\displaystyle yC(x)+c_{m}S(x^{m}y)$ $\displaystyle=N.$ (2.2)

If we find a pair $({x}_{n,N},y_{n,N})\in\mathbb{R}_{+}^{2}$ satisfying (2.1)
and (2.2), then this pair is also a solution to our system (1.4).
$S({x}_{n,N}^{m}y_{n,N})$ diverges for ${x}_{n,N}^{m}y_{n,N}\geq 1$, so that
${x}_{n,N}^{m}y_{n,N}<1$ and
$S({x}_{n,N}^{m}y_{n,N})={x}_{n,N}^{m}y_{n,N}/(1-{x}_{n,N}^{m}y_{n,N})$. Vice
versa, any solution to (1.4) satisfies (2.1), (2.2). Thus it suffices to find
a pair $({x}_{n,N},y_{n,N})\in\mathbb{R}_{+}^{2}$ satisfying (2.1), (2.2).
Subtracting $m$ times (2.2) from (2.1) we obtain

$\displaystyle
y=(n-mN)\left(\frac{xC^{\prime}(x)}{C(x)}-m\right)^{-1}C(x)^{-1}=:a(x)\cdot
C(x)^{-1}.$ (2.3)

Plugging this into (2.2) and reformulating yields the one-variable equation

$\displaystyle f(x):=a(x)+c_{m}S\left(b(x)\right)=N,\quad\text{where}\quad
b(x):=x^{m}\cdot a(x){C(x)^{-1}}.$ (2.4)

Before we solve this equation let us have a closer look at the expression
$xC^{\prime}(x)/C(x)$. Since $(c_{k})_{k\geq 1}$ is a non-negative and non-
zero sequence and since $C$ has radius of convergence $\rho$ we know that
$xC^{\prime}(x)/C(x)$ is continuous and strictly increasing on the (open)
interval $(0,\rho)$. Moreover, as $m$ is the first index such that $c_{m}>0$
and as $c_{n}=h(n)n^{\alpha-1}\rho^{-n}$ for some $\alpha>0$

$\lim_{x\to
0}\frac{xC^{\prime}(x)}{C(x)}=m\quad\textrm{and}\quad\lim_{x\to\rho}\frac{xC^{\prime}(x)}{C(x)}=\infty.$

With these facts at hand we study $a$ and $b$. The monotonicity properties of
$xC^{\prime}(x)/C(x)$ imply that $a(x)$ is strictly decreasing in $(0,\rho)$
with

$\lim_{x\to 0}a(x)=\infty\quad\textrm{and}\quad\lim_{x\to\rho}a(x)=0.$

Moreover, $b(x)$ is also strictly decreasing on $(0,\rho)$ as the product of
two strictly decreasing positive functions $a(x)$ and
$x^{m}/C(x)=1/\sum_{k\geq m}c_{k}x^{k-m}$ and satisfies

$\lim_{x\to 0}b(x)=\infty\quad\textrm{and}\quad\lim_{x\to\rho}b(x)=0.$

Let $\delta\in(0,\rho)$ be the unique number such that $b(\rho-\delta)=1$ and
so $b(x)\in(0,1)$ for $x\in(\rho-\delta,\rho)$. We immediately obtain that any
solution to (2.4), that is, any $x$ solving $f(x)=N$ must be in
$(\rho-\delta,\rho)$ and we look only in this interval for solutions.

Note that if there is any solution, then it must be unique. Indeed, $a,b$ are
both strictly decreasing, and $S(b(x))$ too, since $S$ has only non-negative
coefficients. Thus, $f$ is strictly decreasing in $(\rho-\delta,\rho)$.

Finally, we argue that there exists a solution to $f(x)=N$. From our
considerations we obtain that the function $S(b(x))$, defined on
$(\rho-\varepsilon,\rho)$, takes any value in $(0,\infty)$. On the other hand,
we know that $a(x)\to 0$ for $x\to\rho$. We conclude that $f(x)\to 0$ as
$x\to\rho$ and $f(x)\to\infty$ as $x\to\rho-\delta$. This implies the
existence of (a unique value) ${x}_{n,N}$ such that $f({x}_{n,N})=N$. With
this at hand we determine $y_{n,N}$ by (2.3), and the proof is completed. ∎

###### Proof of Lemma 1.2(ii).

Let $0<\varepsilon<1/(\alpha+1)$. We first show that there is a solution in
the interval $(u_{-},u_{+})$, where $u_{-}:=v^{1/(\alpha+1)-\varepsilon}$ and
$u_{+}:=v^{1/(\alpha+1)+\varepsilon}$, and that there are no solutions in
$[1,v]\setminus(u_{-},u_{+})$. Set

$F_{v}(x):=xh(x)^{1/(\alpha+1)}-v^{1/(\alpha+1)}.$

Then
$F_{v}(u_{-})=v^{1/(\alpha+1)-\varepsilon}h(v^{1/(\alpha+1)-\varepsilon})-v^{1/(\alpha+1)}<0$
for $v$ sufficiently large, since $h$ being expansive guarantees that
$h(t)=t^{o(1)}$ as $t\to\infty$, see also (A.2). Analogously we obtain that
$F_{v}(u_{+})>0$ for large $v$. Since $h$ is continuous by assumption, also
$F_{v}$ is continuous and there is $u_{v}\in(u_{-},u_{+})$ with
$F_{v}(u_{v})=0$ for $v$ large enough.

Now consider $1\leq u\leq u_{-}$. Let $\delta>0$ be such that
$(1/(\alpha+1)-\varepsilon)(1+\delta)<1/(\alpha+1)$. Due to (A.2), for $v$
large enough

$F_{v}(u)=uh(u)^{1/(\alpha+1)}-v^{1/(\alpha+1)}\leq
u_{-}^{1+\delta}-v^{1/(\alpha+1)}=v^{(1/(\alpha+1)-\varepsilon)(1+\delta)}-v^{1/(\alpha+1)}<0.$

So, there is no solution in $[1,u_{-}]$. Next consider $u_{+}\leq u\leq v$.
Then with room to spare (A.2) guarantees
$h(u)^{1/(\alpha+1)}>u^{-\varepsilon/2}\geq v^{-\varepsilon/2}$ for $v$
sufficiently large. Hence

$F_{v}(u)=uh(u)^{1/(\alpha+1)}-v^{1/(\alpha+1)}>v^{1/(\alpha+1)+\varepsilon}v^{-\varepsilon/2}-v^{1/(\alpha+1)}>0.$

which proves that there is no solution in $[u_{+},v]$.

Next, let us show that the solution $u_{v}\in(u_{-},u_{+})$ is unique. Assume
that $u_{-}<u_{-}^{*}<u_{+}^{*}<u_{+}$ are two distinct solutions. Then due to
(A.2) we obtain for $0<\delta<1$ and $v$ sufficiently large

$\frac{u_{-}^{*}}{u_{+}^{*}}=\frac{h(u_{+}^{*})^{1/(\alpha+1)}}{h(u_{-}^{*})^{1/(\alpha+1)}}\geq\left(\frac{u_{-}^{*}}{u_{+}^{*}}\right)^{\delta}$

implying that $u_{-}^{*}/u_{+}^{*}\geq 1$, a contradiction.

Finally, we show that $g(v)=h(u_{v})^{1/(\alpha+1)}$ is slowly varying; since
$u_{v}=g(v)^{-1}v^{1/(\alpha+1)}$ the proof is finished. Let $\lambda>0$ be
arbitrary. Denote by $u_{\lambda v}$ the solution to $u_{\lambda
v}h(u_{\lambda v})^{1/(\alpha+1)}=(\lambda v)^{1/(\alpha+1)}$ which, as we
have just shown, exists and is unique for $\lambda v$ sufficiently large. Then

$\left(\frac{g(v)}{g(\lambda
v)}\right)^{\alpha+1}=\frac{h(u_{v})}{h(u_{\lambda
v})}=\frac{h\big{(}h(u_{v})^{-1/(\alpha+1)}v^{1/(\alpha+1)}\big{)}}{h\big{(}h(u_{\lambda
v})^{-1/(\alpha+1)}(\lambda v)^{1/(\alpha+1)}\big{)}}.$

Abbreviate $t={h(u_{v})}/{h(u_{\lambda v})}$. By applying (A.2) to the last
expression in the previous display we obtain for any $0<\delta<1$ and
sufficiently large $v$

$\min\left\\{(\lambda t)^{\delta},(\lambda t)^{-\delta}\right\\}\leq
t\leq\max\left\\{(\lambda t)^{\delta},(\lambda t)^{-\delta}\right\\}.$

Note that $\lambda^{\delta},\lambda^{-\delta}$ get arbitrarily close to $1$ if
we let $\delta\to 0$. So, since $\delta<1$ we have proven that $g$ is slowly
varying, i.e., $g(v)/g(\lambda v)\to 1$ as $n\to\infty$. ∎

In the rest of the section we retrieve useful asymptotic properties of
$({x}_{n},y_{n})\equiv(x_{n,N_{n}},y_{n,N_{n}})$, where it is instructive to
write ${x}_{n}=\rho e^{-\chi_{n}}$. This will allow us to determine the values
of $y_{n}C({x}_{n})$ in the different regimes of $N_{n}$.

######  Lemma 2.1.

Let $N_{n}=\lambda_{n}N^{*}_{n}$, $n\in\mathbb{N}$ be a sequence as in (1.7)
and set $\chi_{n}=\ln(\rho/{x}_{n})$. Let $g$ be the slowly varying function
from Lemma 1.2(ii). Then, as $n\to\infty$,

$\chi_{n}\sim
g\left(\frac{n-mN_{n}}{y_{n}}\right)\cdot\left(\frac{n-mN_{n}}{\Gamma(\alpha+1)y_{n}}\right)^{-1/(\alpha+1)}\sim
o(1),$ (2.5)

and further, for $k\in\mathbb{N}_{0}$ as $n\to\infty$,

$\displaystyle{x}_{n}^{k}C^{(k)}({x}_{n})\sim\Gamma(\alpha+k)\cdot
h(\chi_{n}^{-1})\cdot\chi_{n}^{-\alpha-k}\sim\Gamma(\alpha+k)\cdot
g\left(\frac{n-mN_{n}}{y_{n}}\right)^{1-k}\cdot\left(\frac{n-mN_{n}}{\Gamma(\alpha+1)y_{n}}\right)^{\frac{\alpha+k}{\alpha+1}}$
(2.6)

and moreover $x_{n}y_{n}C^{\prime}(x_{n})\sim n-mN_{n}$.

###### Proof.

First we show that $y_{n}$ is bounded from above. For the sake of
contradiction, assume that there is an increasing $\mathbb{N}$-valued sequence
$(n_{\ell})_{\ell\in\mathbb{N}}$ such that $y_{n_{\ell}}\to\infty$. Since
$x_{n_{\ell}}^{m}y_{n_{\ell}}<1$ due to (1.4) we have $x_{n_{\ell}}\to 0$ as
$\ell\to\infty$. As $C(x)\sim c_{m}x^{m}$ and $C^{\prime}(x)\sim
mc_{n}x^{m-1}$ as $x\to 0$ we get as $\ell\to\infty$

$y_{n_{\ell}}C(x_{n_{\ell}})=\mathcal{O}\left(1\right)\quad\textrm{and}\quad
x_{n_{\ell}}y_{n_{\ell}}C^{\prime}(x_{n_{\ell}})=\mathcal{O}\left(1\right).$

But
$x_{n_{\ell}}y_{n_{\ell}}C^{\prime}(x_{n_{\ell}})-my_{n_{\ell}}C(x_{n_{\ell}})=n_{\ell}-mN_{n_{\ell}}\to\infty$,
contradicting (1.4).

Next we show that $\chi_{n}\to 0$. For the sake of contradiction, assume that
there is a strictly increasing $\mathbb{N}$-valued sequence
$(n_{\ell})_{\ell\in\mathbb{N}}$ and an $\varepsilon>0$ such that
$\chi_{n_{\ell}}:=\ln(\rho/x_{n_{\ell}})\geq\varepsilon$ for all
$\ell\in\mathbb{N}$. Since both $C,C^{\prime}$ have radius of convergence
$\rho$ we infer that there is a $\Delta>0$ such that
$C(x_{n_{\ell}}),x_{n_{\ell}}C^{\prime}(x_{n_{\ell}})\leq\Delta$ for all
$\ell\in\mathbb{N}$. From (1.4) and the fact that $y_{n}$ is bounded we then
obtain that, as $\ell\to\infty$,

$c_{m}S_{n_{\ell}}:=c_{m}x_{n_{\ell}}^{m}y_{n_{\ell}}/(1-x_{n_{\ell}}^{m}y_{n_{\ell}})=N_{n_{\ell}}+\mathcal{O}\left(1\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \textrm{and}\leavevmode\nobreak\ \leavevmode\nobreak\
mc_{m}S_{n_{\ell}}=n_{\ell}+\mathcal{O}\left(1\right).$

Since $n_{\ell}-mN_{n_{\ell}}\to\infty$ this is a contradiction, and we have
established that $\chi_{n}\to 0$.

The proof can now be finished rather routinely. By applying a well-known
result for slowly varying functions, see [6, Thm. 1.7.1] and also Theorem A.4,
we immediately obtain

$\displaystyle
x_{n}^{k}C^{(k)}(x_{n})\sim\Gamma(\alpha+k)h(\chi_{n}^{-1})\chi_{n}^{-\alpha-k},\quad\textrm{$k\in\mathbb{N}_{0}$,
$n\to\infty$}.$ (2.7)

From this we readily obtain that
${x}_{n}C^{\prime}({x}_{n})=\omega(C({x}_{n}))$, and then, since
${x}_{n}y_{n}C^{\prime}({x}_{n})-my_{n}C({x}_{n})=n-mN_{n}$ according to (1.4)
we infer that ${x}_{n}y_{n}C^{\prime}({x}_{n})\sim n-mN_{n}$. Plugging (2.7)
into ${x}_{n}y_{n}C^{\prime}({x}_{n})\sim n-mN_{n}$ and rearranging the terms
yields

$\chi_{n}^{-1}h(\chi_{n}^{-1})^{1/(\alpha+1)}=\left(\frac{n-mN_{n}}{\Gamma(\alpha+1)y_{n}}\right)^{1/(\alpha+1)}(1+o(1)).$
(2.8)

As $y_{n}>0$ is bounded from above it follows that
$t:=(n-mN_{n})/(\Gamma(\alpha+1)y_{n})\cdot(1+o(1))\to\infty$. Consequently,
Lemma 1.2(ii) asserts that there is a unique solution
$\chi_{n}^{-1}=t^{1/(\alpha+1)}/g(t)$. As $g$ is slowly varying we obtain
(2.5). Further, plugging (2.5) into (2.7) yields the last remaining statement
(2.6). ∎

###  2.2 Probabilistic Estimates

The following well-known statement gives estimates for Poisson distributed
random variables. A proof can be easily conducted by using Stirling’s formula.

######  Proposition 2.2.

Let $X$ be a $\mathrm{Po}\left(\lambda\right)$-distributed random variable.
Then there exists $a>0$ such that uniformly for $x,\lambda>0$

$\displaystyle\mathrm{Pr}\left[\lvert X-\lambda\rvert\geq
x\sqrt{\lambda}\right]\leq\mathrm{e}^{-ax\min\\{x,\sqrt{\lambda}\\}}.$ (2.9)

Further, for $x=o(\lambda^{1/6})$

$\displaystyle\mathrm{Pr}\left[X=\lfloor\lambda+x\sqrt{\lambda}\rfloor\right]\sim(2\pi\lambda)^{-1/2}\mathrm{e}^{-{x^{2}}/{2}}\qquad\text{as
}\lambda\to\infty.$ (2.10)

###  2.3 Estimates for Power Series

In the proofs of our main results we will often find ourselves in the
situation where we have to retrieve coefficients of the product of two power
series. In this basic setting the coefficient of the product is proportional
to the coefficient of the series with the smaller radius of convergence as
shown in the next classical lemma.

######  Lemma 2.3.

[9, Thm. 3.42] Let $A(x),R(x)$ be power series with radii of convergence
$\rho_{A},\rho_{R}>0$. Suppose that
$[x^{n-1}]A(x)/[x^{n}]A(x)\sim\rho_{A}^{-1}$. Moreover, assume that
$\rho_{R}>\rho_{A}$ and $R(\rho_{A})\neq 0$. Then

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

In our forthcoming arguments the involved series $A,R$ will also depend on
$n$; there we will use the following (rather technical) statement, which we
tried to simplify as much as possible; it seems that the conditions cannot be
weakened to obtain the desired conclusion that mimics Lemma 2.3.

######  Lemma 2.4.

Let $\big{(}A_{n}(x)\big{)}_{n\in\mathbb{N}}$ be a sequence of power series
and $(\rho_{n})_{n\in\mathbb{N}}$ a real-valued positive sequence with
$\overline{\rho}=\limsup_{n\to\infty}\rho_{n}\in\mathbb{R}$ such that

$\displaystyle\frac{[x^{n-k}]A_{n}(x)}{[x^{n}]A_{n}(x)}$
$\displaystyle\sim\rho_{n}^{k}\quad\text{for }k\in\mathbb{N}_{0}\text{ and as
}n\to\infty.$ (2.11)

Moreover, assume that there exist $\varepsilon>0$ and
$n_{0},k_{0}\in\mathbb{N}$ such that

$\displaystyle\left\lvert\frac{[x^{n-k}]A_{n}(x)}{[x^{n}]A_{n}(x)}\right\rvert$
$\displaystyle\leq(1+\varepsilon)^{k}\rho_{n}^{k}\quad\text{for }k_{0}\leq
k\leq n\text{ and }n\geq n_{0}.$ (2.12)

Let $(R_{n}(x))_{n\in\mathbb{N}}$ be a sequence of power series with radii of
convergence at least $a:=(1+\varepsilon)\overline{\rho}$. Moreover, suppose
that there is a sequence $(d_{k})_{k\in\mathbb{N}}$ such that
$\lvert[x^{k}]R_{n}(x)\rvert\leq d_{k}$ for all $k,n\in\mathbb{N}$ and
$\sum_{k\geq 1}d_{k}a^{k}<\infty$. In addition, let $Q:[0,a]\to\mathbb{R}$ be
such that $R_{n}$ converges uniformly to $Q$ on $[0,a]$. If $\inf_{n\geq
n_{0}}Q(\rho_{n})>0$, then

$[x^{n}]A_{n}(x)R_{n}(x)\sim Q(\rho_{n})\cdot[x^{n}]A_{n}(x)\quad\text{as
}n\to\infty.$

###### Proof.

We abbreviate $a_{k,n}:=[x^{k}]A_{n}(x)$ and $r_{k,n}:=[x^{k}]R_{n}(x)$ for
$k,n\in\mathbb{N}$. Write for $K\in\mathbb{N}$

$\frac{1}{a_{n,n}}[x^{n}]A_{n}(x)R_{n}(x)=I(0,K)+I(K,n),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{where}\leavevmode\nobreak\ \leavevmode\nobreak\
I(i,j):=\sum_{i\leq k<j}\frac{a_{n-k,n}}{a_{n,n}}r_{k,n}.$

Let $\varepsilon^{\prime}>0$. Let $K_{0}$ be such that for all $K\geq K_{0}$

$\Big{|}\sum_{0\leq
k<K}r_{k,n}\rho_{n}^{k}-Q(\rho_{n})\Big{|}\leq|R_{n}(\rho_{n})-Q(\rho_{n})|+\Big{|}\sum_{k>K}r_{k,n}\rho_{n}^{k}\Big{|}<\varepsilon^{\prime};$

such a $K_{0}$ exists since $R_{n}\to Q$ uniformly on $[0,a]$, $\rho_{n}\leq
a$ for all $n$, and since
$|\sum_{k>K}r_{k,n}\rho_{n}^{k}|\leq\sum_{k>K}d_{k}a^{k}$ gets arbitrarily
small by the assumption that $\sum_{k\geq 1}d_{k}a^{k}$ converges.

Note further that for any $K\geq K_{0}$ the property (2.11) entails for
sufficiently large $n$

$\Big{|}I(0,K)-\sum_{0\leq
k<K}r_{k,n}\rho_{n}^{k}\Big{|}<\varepsilon^{\prime}.$

The triangle inequality readily implies that $\lvert
I(0,K)-Q(\rho_{n})\rvert<2\varepsilon^{\prime}$ for all $K\geq K_{0}$ and $n$
sufficiently large. Further, (2.12) guarantees that there is $\varepsilon>0$
such that $0<a_{n-k,n}/a_{n,n}\leq(1+\varepsilon)^{k}\rho_{n}^{k}$ for all
$k,n$ sufficiently large. From that we conclude that there is a
$K_{1}\in\mathbb{N}$ such that for all $K\geq K_{1}$

$\lvert I(K,n)\rvert\leq\sum_{k\geq
K}\left|r_{k,n}\right|(1+\varepsilon)^{k}\rho_{n}^{k}\leq\sum_{k\geq
K}d_{k}(1+\varepsilon)^{k}\overline{\rho}^{k}<\varepsilon^{\prime}.$

All together, fixing $K\geq\max\\{K_{0},K_{1}\\}$, we proved that there is an
error term $|E|<3\varepsilon^{\prime}$ such that
$a_{n,n}^{-1}\cdot[x^{n}]A_{n}(x)R_{n}(x)=Q(\rho_{n})+E$ for $n$ sufficiently
large. Since $\varepsilon^{\prime}>0$ was arbitrary and $Q(\rho_{n})$ is
bounded away from zero, the claim follows. ∎

The next statement applies Lemma 2.4 to the special case
$A_{n}(x)=\exp\left\\{h_{n}x\right\\}$ and $Q(x)=R_{n}(x)=(1-x)^{-\gamma}$,
where $\gamma>0$ and $h_{n}$ is approaching infinity. In particular, we
observe what the effect of $Q$ is on $[x^{k}]A_{n}(x)=h_{n}^{k}/k!$.

######  Lemma 2.5.

Let $\gamma>0$ and for a (eventually) positive sequence
$(\alpha_{n})_{n\in\mathbb{N}}$ define $h_{n}:=\alpha_{n}n$.

  1. (i)

For $k\in\mathbb{N}$ and $\alpha_{n}$ such that $h_{n}\to\infty$

$\displaystyle[x^{k}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}\sim[x^{k}]\mathrm{e}^{h_{n}x}\sim\frac{h_{n}^{k}}{k!}\qquad
n\to\infty.$ (2.13)

  2. (ii)

If $\liminf_{n\to\infty}\alpha_{n}>1$

$\displaystyle[x^{n}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}\sim\left(\frac{1}{1-\alpha_{n}^{-1}}\right)^{\gamma}\cdot\frac{h_{n}^{n}}{n!},\qquad
n\to\infty.$ (2.14)

  3. (iii)

If $\limsup_{n\to\infty}\alpha_{n}<1$ and $h_{n}\to\infty$ then

$\displaystyle[x^{n}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}\sim\frac{\big{(}(1-\alpha_{n})n\big{)}^{\gamma-1}}{\Gamma(\gamma)}\mathrm{e}^{h_{n}},\qquad
n\to\infty.$ (2.15)

###### Proof.

Statement (i) is easily verified, as for _fixed_ $k$

$[x^{k}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}=\sum_{0\leq\ell\leq
k}\binom{k-\ell+\gamma-1}{\gamma-1}\frac{h_{n}^{\ell}}{\ell!}\sim\frac{h_{n}^{k}}{k!}.$

We proceed to Part (ii). Set $R_{n}(x):=Q(x):=(1-x)^{-\gamma}$ for all
$n\in\mathbb{N}$ and $A_{n}(x):=\mathrm{e}^{h_{n}\cdot x}$. We want to apply
Lemma 2.4 and verify its conditions one by one. First,

$\frac{[x^{n-k-1}]A_{n}(x)}{[x^{n-k}]A_{n}(x)}=\frac{n-k}{h_{n}}\sim\frac{1}{\alpha_{n}}:=\rho_{n},\qquad
k\in\mathbb{N}_{0},n\to\infty$

that is, (2.11) is established. Next we see that (2.12) is valid since

$\frac{[x^{N_{n}-k}]A_{n}(x)}{[x^{n}]A_{n}(x)}=\frac{n(n-1)\cdots(n-k-1)}{h_{n}^{k}}\leq\rho_{n}^{k},\qquad
0\leq k\leq N_{n}\in\mathbb{N}.$

Since $\liminf_{n\to\infty}\alpha_{n}>1$ we have that
$\overline{\rho}=\limsup_{n\to\infty}\rho_{n}<1$. Let $\varepsilon>0$ be such
that $a:=(1+\varepsilon)\overline{\rho}<1$. Establishing uniform convergence
of $R_{n}\to Q$ on $[0,a]$ and estimating the coefficients of $R_{n}(x)$ is
trivial, as $R_{n}=Q$ for all $n\in\mathbb{N}$ and $Q$ is absolute convergent
on $[0,a]$. Lastly, $Q(\rho_{n})$ is bounded from below away from zero as
$0<\rho_{n}\leq\overline{\rho}<1$ for all $n\in\mathbb{N}$. Hence Lemma 2.4
entails

$[x^{n}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}\sim\frac{1}{(1-\alpha_{n}^{-1})^{\gamma}}[x^{n}]\mathrm{e}^{h_{n}x}=\frac{1}{(1-\alpha_{n}^{-1})^{\gamma}}\frac{h_{n}^{n}}{n!}.$

Finally, we show (iii). Let $X\sim\mathrm{Po}(h_{n})$. We split up the sum

$\displaystyle[x^{n}]\frac{1}{(1-x)^{\gamma}}\mathrm{e}^{h_{n}x}$
$\displaystyle=\sum_{0\leq k\leq
n}\binom{n-k+\gamma-1}{\gamma-1}\frac{h_{n}^{k}}{k!}$
$\displaystyle=\mathrm{e}^{h_{n}}\left(\sum_{\lvert
k-h_{n}\rvert\leq\sqrt{h_{n}}\ln n}+\sum_{\lvert k-h_{n}\rvert>\sqrt{h_{n}}\ln
n}\right)\binom{n-k+\gamma-1}{\gamma-1}\mathrm{Pr}\left[X=k\right]=:\mathrm{e}^{h_{n}}(S_{1}+S_{2}).$

For $h_{n}=\alpha_{n}n$ we have $n-k\sim(1-\alpha_{n})n=\omega(1)$ for all
$\lvert k-h_{n}\rvert\leq\sqrt{h_{n}}\ln n$. Hence

$S_{1}\sim\frac{\big{(}(1-\alpha_{n})n\big{)}^{\gamma-1}}{\Gamma(k)}\mathrm{Pr}\left[\lvert
X-h_{n}\rvert\leq\sqrt{h_{n}}\ln n\right].$

By applying (2.9) we obtain for some $d>0$ that $\text{Pr}[\lvert
X-h_{n}\rvert>\sqrt{h_{n}}\ln n]\leq\mathrm{e}^{-d\ln^{2}n}$, so that $\lvert
X-h_{n}\rvert\leq\sqrt{h_{n}}\ln n$ with probability $\sim 1$. Moreover, it is
easy to see that $S_{2}$ is negligible: note that

$S_{2}\leq\mathrm{e}^{-d\ln^{2}n}\sum_{0\leq k\leq
n}\binom{n-k+\gamma-1}{\gamma-1}=\mathrm{e}^{-d\ln^{2}n}\binom{n+\gamma}{\gamma}=\Theta\left(\mathrm{e}^{-d\ln^{2}n}n^{\gamma}\right)=o(S_{1}).$

∎

The following simple and well-known saddle-point estimate for the coefficients
of a power series will be useful several times.

######  Lemma 2.6.

Let $F(x)=\sum_{k\geq 0}f_{k}x^{k}$ be a power series with non-negative
coefficients. Then, for any $n\in\mathbb{N}$ and $z>0$

$\displaystyle f_{n}=[x^{n}]F(x)\leq F(z){z^{-n}}.$ (2.16)

Finally, we present a simple estimate which holds for any power series with
non-negative coefficients and positive radius of convergence.

######  Lemma 2.7.

Let $m\in\mathbb{N}$. Let $F(x)=\sum_{k\geq m}f_{k}x^{k}$ be a power series
with non-negative coefficients such that $f_{m}>0$ and radius of convergence
$\rho>0$. Let $0<\varepsilon<1$. Then there exists $A>0$ such that for all
$0\leq z\leq(1-\varepsilon)\rho$

$1\leq\frac{F(z)}{f_{m}z^{m}}\leq 1+Az.$

###### Proof.

The first inequality follows directly from the definition of $F$ and $m$.
Abbreviate $a:=(1-\varepsilon)\rho$ and note that since $\rho<1$ also
$a<\rho<1$. Then

$\frac{F(z)}{f_{m}z^{m}}\leq
1+z\frac{1}{f_{m}}\sum_{k>m}f_{k}a^{k-m-1}=1+z\frac{a^{-m-1}}{f_{m}}\sum_{k>m}f_{k}a^{k}.$
(2.17)

Thus, as $a<\rho<1$, we obtain from (2.17) the claimed bound with
$A=F(a)a^{-m-1}/f_{m}$. ∎

###  2.4 Euler-Maclaurin Summation

For a function $g$ we will need several times to compute the sum
$\sum_{k=a}^{b}g(k)$ for some $a<b$. The Euler-Maclaurin summation formula,
discussed for example in [19, Ch. 9.5], relates the sum to an integral, which
is sometimes easier to compute.

######  Lemma 2.8.

Let $g:\mathbb{R}\to\mathbb{R}$ be differentiable and $P_{1}(x):=x-\lfloor
x\rfloor-1/2$. Then for any $a<b$

$\sum_{k=a}^{b}g(k)=\int_{a}^{b}g(x)dx+\frac{g(a)+g(b)}{2}+\int_{a}^{b}g^{\prime}(x)P_{1}(x)dx.$

We will apply this to functions of the form $g(x)=\mathrm{e}^{-dx^{2}}$ for
some $d>0$. Note that $\lvert P_{1}(x)\rvert\leq 1$ and $\lvert
g^{\prime}(x)\rvert$ equals $g^{\prime}(x)$ for $x<0$ and $-g^{\prime}(x)$ for
$x>0$. Accordingly,

$\displaystyle\sum_{k=a}^{b}g(k)=\int_{a}^{b}g(x)dx+Q,\quad\text{where}\quad\lvert
Q\rvert\leq\frac{g(a)+g(b)}{2}+\int_{-\infty}^{\infty}|g^{\prime}(x)|dx\leq
3.$ (2.18)

This will simplify the computation of $\sum g(k)$ considerably, as it will
turn out that the remainder $Q$ is negligible compared to $\int g(x)dx$ which,
in turn, is well-studied.

##  3 General Proof Strategy

In this section we describe the general proof strategy. On the way, several
important intermediate statements are stated and we explain how to assemble
them in order to prove Theorems 1(I) and 1(II). Then all is left to show is
that these intermediate statements are valid, the proof of which is deferred
to Section 4.

###  3.1 Proof Setup: the Boltzmann Model

We begin with the definition of the Boltzmann model that will be central in
the forthcoming considerations. Given a non-negative real-valued sequence
$(c_{n})_{n\in\mathbb{N}}$, the associated power series $C(x)$, and a positive
real $x_{0}$ such that $C(x_{0})<\infty$, we define the random variable
$\Gamma C(x_{0})$ by

$\mathrm{Pr}\left[\Gamma
C(x_{0})=n\right]=c_{n}\frac{x_{0}^{n}}{C(x_{0})},\qquad n\in\mathbb{N}.$

We will refer to this distribution as the _Boltzmann distribution_ or the
_Boltzmann model_ for $C(x)$ or for $(c_{n})_{n\in\mathbb{N}}$ at $x_{0}$. The
Boltzmann model has a natural interpretation, if $(c_{n})_{n\in\mathbb{N}}$ is
the counting sequence of some combinatorial class $\cal C$; this is actually
where this terminology originates, see the seminal paper [14]. Indeed, imagine
in that case that we put a “weight” of $x_{0}^{n}$ to any object of size $n$
in $\cal C$, so that the total weight $C(x_{0})$ is finite. If we then draw an
object from $\cal C$ with a probability that is proportional to its weight,
then we get precisely the Boltzmann distribution. Since we are going to need
that later several times without explicitly referencing it, note that

$\mathbb{E}[\Gamma
C(x_{0})]=\frac{x_{0}C^{\prime}(x_{0})}{C(x_{0})}\quad\textrm{and}\quad\mathbb{E}\big{[}\Gamma
C(x_{0})^{2}\big{]}=\frac{x_{0}^{2}C^{\prime\prime}(x_{0})}{C(x_{0})}+\frac{x_{0}C^{\prime}(x_{0})}{C(x_{0})}.$

In a completely analogous way we can define a bivariate variant of the
Boltzmann model. Suppose that we are given a sequence of non-negative
sequences $((g_{n,N})_{N\in\mathbb{N}})_{n\in\mathbb{N}}$ with associated
power series $G(x,y)$ and positive reals $x_{0},y_{0}$ such that
$G(x_{0},y_{0})<\infty$. Then we consider the $\mathbb{N}^{2}$-valued random
variable $\Gamma G(x_{0},y_{0})$ with distribution

$\mathrm{Pr}\left[\Gamma
G(x_{0},y_{0})=(n,N)\right]=g_{n,N}\frac{x_{0}^{n}y_{0}^{N}}{G(x_{0},y_{0})},\qquad
n,N\in\mathbb{N},$ (3.1)

that we also call a Boltzmann distribution/model for $G$ at $(x_{0},y_{0})$.

The crucial point behind the previous definitions is that we can exploit them
to actually determine $c_{n}$ and $g_{n,N}$. Indeed, if we could determine the
probability on the left-hand side of (3.1), then would also know $g_{n,N}$.
This consideration is of course only useful if we had an appropriate hands-on
description of $\Gamma G(x_{0},y_{0})$ that we could study appropriately. Here
the Boltzmann models come into play: a particularly useful property of them –
and one that made them so successful in combinatorics – is that they _compose
well_ , see also [14, 8]. For example, suppose that $C(x)=A(x)B(x)$ and
$x_{0}$ be such that $A(x_{0}),B(x_{0})<\infty$. Then we can relate the
Boltzmann models $\Gamma C(x_{0})$ and $\Gamma A(x_{0}),\Gamma B(x_{0})$ as
follows. Consider the following simple random process, that first draws
independently from $\Gamma A(x_{0}),\Gamma B(x_{0})$ and then creates the sum:

  1. (P)

Let independently $A=\Gamma A(x_{0})$ and $B=\Gamma B(x_{0})$ and set $C=A+B$.

Then it is quite easy to see that $C$ is distributed like $\Gamma C(x_{0})$;
we do not show that here, since we do not need it, but we keep the guiding
principle in mind: the _product of power series corresponds to independent
components in the Boltzmann model_. Let us study a second example. Suppose
that we are given $C(x)$ and $D(x)=\exp\\{C(x)\\}$111In combinatorial terms
this corresponds to the set-construction, that is, $[x^{n}]D(x)$ is the number
of objects of size $n$ that are unordered collections of elements in $\cal C$,
cf. [15]. Assume that $x_{0}$ is such that $C(x_{0})<\infty$, so that
$D(x_{0})<\infty$ as well. Then we can relate the models $\Gamma C(x_{0})$ and
$\Gamma D(x_{0})$ by first drawing a Poisson random variable and then summing
up independent $\Gamma C(x_{0})$’s:

  1. (S1)

Let $P$ be a Poisson distributed random variable with parameter $C(x_{0})$.

  2. (S2)

Let $C_{1},\dots,C_{P}$ independent random variables distributed like $\Gamma
C(x_{0})$.

  3. (S3)

Set $D=C_{1}+\dots+C_{P}$.

Then it is quite easy to see that $D$ is distributed like $\Gamma D(x_{0})$;
again, we do not show that, but keep in mind: _exponentation on the power
series level corresponds to a Poisson distribution on the Boltzmann level_.
Moreover, we can say that $\Gamma D(x_{0})$ has a number of $C$-components
distributed like Po$(C(x_{0}))$. Let us look at a last example. Suppose that
$H(x)=C(x^{j})$ for some $j\in\mathbb{N}$ and $x_{0}$ be such that
$H(x_{0})<\infty$. Consider the process

  1. (E)

Let $C=\Gamma C(x_{0}^{j})$ and set $H=jC$.

Then we obtain that $H$ is distributed like $\Gamma H(x_{0})$, so that
_potentiation of the argument on the power series level corresponds to
multiplication on the Boltzmann level_ , and we can say that $\Gamma H(x_{0})$
has $j$ components.

Here we are interested in the Boltzmann model on

$G(x,y)=\exp\left\\{\sum_{j\geq 1}C(x^{j})y^{j}/j\right\\}=\prod_{j\geq
1}\exp\left\\{C(x^{j})y^{j}/j\right\\},\quad\text{where
}[x^{n}]C(x)=c_{n}\text{ satisfies\leavevmode\nobreak\ \eqref{eq:c_n}}$

at some $(x_{0},y_{0})\in(\mathbb{R}^{+})^{2}$ such that
$G(x_{0},y_{0})<\infty$. Guided by the general principles (product $\to$
independent components, exponentation $\to$ Poisson, potentiation $\to$
multiplication) we consider the following process:

  1. 1.

Let $(P_{j})_{j\geq 1}$ be independent Poisson random variables with
parameters $(C({x}_{0}^{j})y_{0}^{j}/j)_{j\geq 1}$.

  2. 2.

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

  3. 3.

Set $\Lambda({x}_{0},y_{0}):=\big{(}\sum_{j\geq 1}j\sum_{1\leq i\leq
P_{j}}C_{j,i},\,\sum_{j\geq 1}jP_{j}\big{)}$.

Then, rather unsurprisingly, we obtain the following statement, whose proof is
in Section 4.1.

######  Lemma 3.1.

The distributions of $\Gamma G({x}_{0},y_{0})$ and $\Lambda({x}_{0},y_{0})$
are identical.

However, we can extract more from the aforementioned description of $\Lambda$.
Let us write – motivated from the combinatorial background – for short for a
pair $P=(n,N)$ (like $\Lambda(x_{0},y_{0})$) $\kappa(P)=N$ for the “number of
components” and $|P|=n$ for the “size”. Define the events

$\displaystyle{\mathcal{P}}_{N}:=\left\\{\kappa(\Lambda(x_{0},y_{0}))=N\right\\}=\left\\{\sum_{j\geq
1}jP_{j}=N\right\\},\leavevmode\nobreak\
{\mathcal{E}}_{n}:=\left\\{|\Lambda(x_{0},y_{0})|=n\right\\}=\left\\{\sum_{j\geq
1}j\sum_{1\leq i\leq P_{j}}C_{j,i}=n\right\\}.$ (3.2)

Then Lemma 3.1 reveals that

$[x^{n}y^{N}]G(x,y)\frac{x_{0}^{n}y_{0}^{N}}{G(x_{0},y_{0})}=\mathrm{Pr}\left[\Gamma
G(x_{0},y_{0})=(n,N)\right]=\mathrm{Pr}\left[\Lambda(x_{0},y_{0})=(n,N)\right]=\mathrm{Pr}\left[{\mathcal{E}}_{n},{\mathcal{P}}_{N}\right].$

Rewriting this yields an alternative representation of $[x^{n}y^{N}]G(x,y)$ in
terms of iid random variables.

######  Corollary 3.2.

Let ${x}_{0},y_{0}>0$ be such that $G({x}_{0},y_{0})<\infty$. For any
$n,N\in\mathbb{N}$ such that $[x^{n}y^{N}]G(x,y)>0$

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

In other words, if we can compute $G(x_{0},y_{0})$,
$\mathrm{Pr}\left[{\mathcal{P}}_{N}\right]$ and
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N}\right]$ then we also
obtain the desired quantity $[x^{n}y^{N}]G(x,y)$ and we are done. How this can
achieved is the topic of the next section.

###  3.2 Proof of the Main Results

In order to prove Theorems 1(I) and 1(II) we will apply Corollary 3.2. Let us
begin with a remark. Although Corollary 3.2 is true for all $n,N\in\mathbb{N}$
and $x_{0},y_{0}>0$ such that $G(x_{0},y_{0})<\infty$, we certainly cannot
expect that it is _useful_ for all choices of the parameters. Here, where we
want to prove Theorems 1(I) and 1(II), we consider (large) sizes
$n\in\mathbb{N}$ and a corresponding sequence $N_{n}$ satisfying (1.7) and
(1.6), that is,

$N_{n}=\lambda_{n}N_{n}^{*}\quad\textrm{such that}\quad
N_{n},n-mN_{n}\to\infty.$

Then $x_{0},y_{0}$ should be chosen is such a way that the events
${\mathcal{P}}_{N_{n}}$ and ${\mathcal{E}}_{n}$ are ’typical’. Note that the
expectations satisfy

$\displaystyle\mathbb{E}\left[\lvert\Lambda(x_{0},y_{0})\rvert\right]=\mathbb{E}\left[\sum_{j\geq
1}j\sum_{1\leq i\leq P_{j}}C_{j,i}\right]=\sum_{j\geq
1}\mathbb{E}\left[P_{j}\right]j\mathbb{E}\left[C_{j,i}\right]=\sum_{j\geq
1}x_{0}^{j}y_{0}^{j}C^{\prime}(x_{0}^{j}).$

and

$\displaystyle\mathbb{E}\left[\kappa(\Lambda(x_{0},y_{0}))\right]=\mathbb{E}\left[\sum_{j\geq
1}j\mathbb{E}\left[P_{j}\right]\right]=\sum_{j\geq 1}y_{0}^{j}C(x_{0}^{j}).$

So, in order to get the most out of Corollary 3.2, it seems reasonable to
choose $x_{0},y_{0}$ such that

$\displaystyle\sum_{j\geq
1}{x}_{0}^{j}y_{0}^{j}C^{\prime}({x}_{0}^{j})=n\quad\text{and}\quad\sum_{j\geq
1}y_{0}^{j}C({x}_{0}^{j})=N_{n}.$ (3.3)

Note, however, that actually we will _not_ (quite) do that. Instead, we will
choose $({x}_{0},y_{0})$ to be the unique solution $(x_{n},y_{n})$ of (1.4);
to wit, (1.4) reads here

$\displaystyle{x}_{n}y_{n}C^{\prime}({x}_{n})+mc_{m}\frac{{x}_{n}^{m}y_{n}}{1-{x}_{n}^{m}y_{n}}=n,\leavevmode\nobreak\
\leavevmode\nobreak\
y_{n}C({x}_{n})+c_{m}\frac{{x}_{n}^{m}y_{n}}{1-{x}_{n}^{m}y_{n}}=N_{n},\leavevmode\nobreak\
\leavevmode\nobreak\ x_{n},y_{n}>0,\leavevmode\nobreak\ \leavevmode\nobreak\
x_{n}^{m}y_{n}<1.$ (3.4)

To justify – informally, at this point – the “switch” to the set of simpler
equations let us look closer at the second equation in (3.3):

$N_{n}=\sum_{j\geq 1}y_{0}^{j}C({x}_{0}^{j})=y_{0}C(x_{0})+c_{m}\sum_{j\geq
1}(x_{0}^{m}y_{0})^{j}+\sum_{j\geq
2}y_{0}^{j}(C(x_{0}^{j})-c_{m}x_{0}^{jm})-c_{m}x_{0}^{m}y_{0}.$

(Note that, somehow arbitrarily, we pulled out the term $c_{m}x_{0}^{m}y_{0}$
so that the we got a geometric series starting at $1$. This will turn out
convinient later, but actually it makes no difference.) Then we must certainly
have that $x_{0}<\rho$ and $0<x_{0}^{m}y_{0}<1$, and so the first sum on the
right-hand side equals $(x_{0}^{m}y_{0})/(1-x_{0}^{m}y_{m})$ and the second
one is bounded (since uniformly $C(x_{0}^{j})-c_{m}x_{0}^{jm}={\cal
O}(x_{0}^{j(m+1)})$ by Lemma 2.7 and $\rho<1$). So,

$N_{n}=y_{0}C(x_{0})+c_{m}\frac{x_{0}^{m}y_{0}}{1-x_{0}^{m}y_{0}}+\mathcal{O}\left(y_{0}\right)$
(3.5)

and by ignoring the additive error term we arrive at the second equation in
(3.4). Similarly we can justify the switch to the first equation.

To wrap up, in all of the following we will work with $\Lambda(x_{n},y_{n})$,
where $(x_{n},y_{n})$ is the unique solution to (3.4) and
$N_{n}=\lambda_{n}N^{*}_{n}$ satisfies (1.6) and (1.7). In particular, we will
consider independent random variables $(P_{j})_{j\geq 1}$ and
$(C_{j,i})_{j,i\geq 1}$ such that

$\displaystyle
P_{j}\sim\mathrm{Po}\left(C(x_{n}^{j})y_{n}^{j}/j\right),\leavevmode\nobreak\
\leavevmode\nobreak\
j\in\mathbb{N},\quad\textrm{and}\quad\mathrm{Pr}\left[C_{j,i}=k\right]=c_{k}\frac{x_{n}^{jk}}{C(x_{n}^{j})},\leavevmode\nobreak\
\leavevmode\nobreak\ j,i,k\in\mathbb{N}.$ (3.6)

By applying Corollary 3.2 we see that for the proof of Theorems 1(I) and 1(II)
it suffices to determine

$G({x}_{n},y_{n}),\quad\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\quad\text{and}\quad\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]$

for ${\mathcal{P}}_{N_{n}}$ and ${\mathcal{E}}_{n}$ defined in (3.2). This
will be performed in versions $(I)$ and $(II)$ of Lemmas 3.3(II), 3.4(II) and
3.9. Along the way some more (intermediate) statements will be needed. We will
also abbreviate throughout without further reference

$S_{n}:=\frac{{x}_{n}^{m}y_{n}}{1-{x}_{n}^{m}y_{n}}.$

Up to this point there is nothing special about the relation of $n$ and
$N_{n}$. However, towards the proof of Theorems 1(I) and 1(II) we establish in
the next lemma the key role of the value $N^{*}_{n}$. In particular, if we
write $x_{n}=\rho e^{-\chi_{n}}$, then Lemma 2.1 reveals that $\chi_{n}=o(1)$
so that $x_{n}\sim\rho$. If we now consider
$S_{n}=x_{n}^{m}y_{n}/(1-x_{n}^{m}y_{n})$, then it is obvious that $y_{n}$
plays a crucial role: if $y_{n}$ stays well below $\rho^{-m}$, then $S_{n}$ is
bounded, otherwise it becomes large. This transition happens precisely at
$N_{n}^{*}$, as established in the following lemma, and it has far reaching
consequences in the remainder; depending on whether
$\limsup_{n\to\infty}<\rho^{-m}$ or $y_{n}\sim\rho^{-m}$ there isn’t/there is
a crucial interplay between the terms $x_{n}y_{n}C^{\prime}(x_{n})$ (and
$y_{n}C(x_{n})$) and $S_{n}$ in (3.4).

######  Lemma 3.3(I).

In case $(I)$, that is, when $\limsup_{n\to\infty}\lambda_{n}<1$,

$\displaystyle\limsup_{n\to\infty}y_{n}<\rho^{-n}\qquad\text{and
consequently}\qquad y_{n}C({x}_{n})=N_{n}+\Theta(y_{n}),\quad
S_{n}=\Theta(y_{n}).$

######  Lemma 3.3(II).

In case $(II)$, that is, when $\liminf_{n\to\infty}\lambda_{n}>1$,

$\displaystyle y_{n}\sim\rho^{-m}\qquad\text{and consequently}\qquad
y_{n}C({x}_{n})\sim a_{n}\cdot N_{n},\quad S_{n}\sim\frac{1-a_{n}}{c_{m}}\cdot
N_{n}$

for some non-negative sequence $(a_{n})_{n\in\mathbb{N}}$ such that
$\limsup_{n\to\infty}a_{n}<1$ and

$a_{n}:=\lambda_{n}^{-1}\cdot\frac{g(n-mN_{n})}{g(n)}\left(\frac{n-mN_{n}}{n}\right)^{\alpha/(\alpha+1)}.$

The proofs can be found in Section 4.2. These statements have an decisive
impact on the quantities discussed in this section. Recall the definitions of
$G^{\geq 2}$ and $G^{\geq 2}_{>m}$ from Section 1.1. We start with
$G({x}_{n},y_{n})$, where we already observe a qualitative difference in the
asymptotic behavior.

######  Lemma 3.4(I).

In case $(I)$

$G({x}_{n},y_{n})\sim G^{\geq
2}(\rho,y_{n})\cdot\exp\left\\{y_{n}C(x_{n})\right\\}\sim G^{\geq
2}(\rho,y_{n})\cdot\exp\left\\{-c_{m}\frac{\rho^{m}y_{n}}{1-\rho^{m}y_{n}}\right\\}\cdot\exp\left\\{N_{n}\right\\}.$

######  Lemma 3.4(II).

Let $(a_{n})_{n\in\mathbb{N}}$ be the sequence from Lemma 3.3(II). In case
$(II)$

$G({x}_{n},y_{n})\sim(ec_{m})^{-c_{m}}\cdot G^{\geq
2}_{>m}(\rho)\cdot\left(\left(1-a_{n}\right)N_{n}\right)^{c_{m}}\cdot\exp\left\\{y_{n}C({x}_{n})\right\\}.$

The proofs are in Section 4.3. Next we consider
$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]$. Recall that
$P_{j}\sim\mathrm{Po}(y_{n}^{j}C({x}_{n}^{j})/j)$ for $j\in\mathbb{N}$. We saw
in the discussion around (3.3)-(3.5) that $\sum_{j\geq
2}y_{n}^{j}C({x}_{n}^{j})$ is comparable to
$S_{n}+\mathcal{O}\left(y_{n}\right)$. Hence, by Lemma 3.3(I), in case $(I)$
$P_{1}$ has mean $N_{n}+\mathcal{O}\left(1\right)$, and moreover, the mean of
the sum $\sum_{j\geq 2}jP_{j}$ is $\mathcal{O}\left(1\right)$. Thus, we
suspect that
$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\approx\mathrm{Pr}\left[P_{1}=N_{n}\right]$,
that is, the whole “mass” condenses into $P_{1}$. This is established in the
following lemma.

######  Lemma 3.5(I).

In case $(I)$

$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim\mathrm{Pr}\left[P_{1}=N_{n}\right]\sim(2\pi
N_{n})^{-1/2}.$

Further, there exist $A>0,0<a<1$ such that

$\displaystyle\mathrm{Pr}\left[\sum_{j\geq 2}jP_{j}=K\right]\leq
A\cdot\min\\{a,y_{n}\\}^{K},\qquad K\in\mathbb{N}.$ (3.7)

The proof is in Section 4.4. In case $(II)$ the behavior is quite different
from that. We observe that $y_{n}^{j}C({x}_{n}^{j})$ is essentially
$c_{m}({x}_{n}^{m}y_{n})^{j}$ as $j$ grows bigger, so that in a first
approximation $\sum_{j\geq 1}jP_{j}$ should behave like

$P_{1}+\sum_{j\geq
1}j\mathrm{Po}\left(c_{m}{({x}_{n}^{m}y_{n})^{j}}/{j}\right).$

Here Lemma 3.3(II) reveals that the mean of this sum is large, actually linear
in $N_{n}$. By comparing the characteristic functions by an
$\exp$-$\ln$-transformation we have for any $k\in\mathbb{N}$ and $0<\beta<1$
that the sum of independent Poisson random variables $\sum_{j\geq
1}j\mathrm{Po}\left(k\beta^{j}/j\right)$ is equal in distribution to the sum
of iid geometric distributed random variables $\sum_{1\leq i\leq
k}\mathrm{Geom}_{i}(1-\beta)$. But this is nothing else than a multinomial
distribution with parameters $1-\beta$ and $k$, so that

$\text{Pr}\Bigg{[}\sum_{1\leq i\leq
k}\mathrm{Geom}_{i}(1-\beta)=N_{n}\Bigg{]}=\binom{N_{n}-1}{k-1}(1-\beta)^{k}\beta^{N_{n}-k}.$

Plugging back $\beta={x}_{n}^{m}y_{n}$ and $k=c_{m}$ as well as using
$(1-{x}_{n}^{m}y_{n})\sim S_{n}^{-1}\sim c_{m}((1-a_{n})N_{n})^{-1}$ due to
Lemma 3.3(II) we obtain that

$\text{Pr}\Bigg{[}\sum_{j\geq
1}j\mathrm{Po}\left(c_{m}\frac{({x}_{n}^{m}y_{n})^{j}}{j}\right)=N_{n}\Bigg{]}\sim\frac{c_{m}^{c_{m}}}{\Gamma(c_{m})(1-a_{n})^{c_{m}}}\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{N_{n}}.$

Since $P_{1}$ is either negligible compared to $\sum_{j\geq 2}jP_{j}$ or at
most of the same order ($a_{n}N_{n}$ vs. $(1-a_{n})N_{n}$ by Lemma 3.3(II)),
this should be qualitatively the actual result. It turns out that this is
true.

######  Lemma 3.5(II).

Let $(a_{n})_{n\in\mathbb{N}}$ be the sequence from Lemma 3.3(II). In case
$(II)$,

$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim\frac{c_{m}^{c_{m}}\exp\left\\{c_{m}\frac{a_{n}}{1-a_{n}}\right\\}}{\Gamma(c_{m})}\cdot\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{(1-a_{n})N_{n}}.$

Let $(K_{n})_{n\in\mathbb{N}}$ be sequence in $\mathbb{N}$ such that
$K_{n}\to\infty$ as $n\to\infty$. Then, for all $\ell\in\mathbb{N}$ as
$n\to\infty$

$\mathrm{Pr}\left[\sum_{j>\ell}jP_{j}=K_{n}\right]\sim\frac{c_{m}^{c_{m}}}{(1-a_{n})^{c_{m}}\Gamma(c_{m})}\cdot\frac{({x}_{n}^{m}y_{n})^{K_{n}}}{K_{n}}\cdot\left(\frac{K_{n}}{N_{n}}\right)^{c_{m}}.$
(3.8)

The proof is in Section 4.4. Having studied the event ${\mathcal{P}}_{N_{n}}$
itself we continue by investigating the effect on the probability space when
conditioning on ${\mathcal{P}}_{N_{n}}$ in order to determine
$\mathrm{Pr}\left[{\cal E}_{n}\leavevmode\nobreak\ |\leavevmode\nobreak\
{\mathcal{P}}_{N_{n}}\right]$. For this purpose, we introduce some auxiliary
notation. Define

$L_{p}:=\sum_{1\leq i\leq p}(C_{1,i}-m),\leavevmode\nobreak\
\leavevmode\nobreak\ p\in\mathbb{N},\quad\text{and}\quad
L:=L_{P_{1}},\quad\text{and}\quad R:=\sum_{j\geq 2}j\sum_{1\leq i\leq
P_{j}}(C_{j,i}-m).$

With this at hand we reformulate

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

The driving idea behind these definitions is to split up $\sum_{j\geq
1}j\sum_{1\leq i\leq P_{j}}(C_{j,i}-m)$ into a “dominant” large part $L$ and
“negligible” remainder $R$. We observe that the random variables $C_{j,i}$
have exponential tails for $j\geq 2$ since ${x}_{n}\leq\rho<1$. In addition,
$\mathbb{E}\left[C_{j,i}\right]={x}_{n}C^{\prime}({x}_{n}^{j})/C({x}_{n}^{j})$
tends to $m$ exponentially fast in $j$ so that the probability of
$\\{C_{j,i}-m=0\\}$ should tend exponentially fast to $1$ in $j$. However, as
we are conditioning on the event ${\mathcal{P}}_{N_{n}}$, where some of the
$P_{j}$’s might be large, it is not obvious that $R$ will be also small. The
next lemma clarifies the picture.

######  Lemma 3.6.

In both cases $(I)$ and $(II)$ there are $0<a<1,A>0$ such that

$\mathrm{Pr}\left[R=r\mid{\mathcal{P}}_{N_{n}}\right]\leq A\cdot a^{r},\qquad
r,n\in\mathbb{N}.$

The proof is in Section 4.5. With this at hand, we try to get a handle on
(3.9) by conditioning on $R$ and $P_{1}$ having certain values, i.e.

$\displaystyle\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]=\sum_{p,r\geq
0}\mathrm{Pr}\left[L_{p}=n-mN_{n}-r\right]\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N_{n}}\right].$

Then the exponential tails of $R$ conditioned on ${\mathcal{P}}_{N_{n}}$
established in Lemma 3.6 guarantee that we can omit all terms where $r$ is
large; further, all terms where $p$ deviates “too much” from
$\mathbb{E}\left[P_{1}\right]=y_{n}C({x}_{n})$ should be negligible as well,
since $P_{1}$ is very much concentrated around its mean. This leads to

$\displaystyle\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]\approx\sum_{r\text{
``small'', }p\text{ ``close to''
}\mathbb{E}\left[P_{1}\right]}\mathrm{Pr}\left[L_{p}=n-mN_{n}-r\right]\mathrm{Pr}\left[P_{1}=p,R=r\mid{\mathcal{P}}_{N_{n}}\right].$
(3.10)

To finish we will use the fact that the mean of $L_{p}$ is close to
$n-mN_{n}-r$ for small $r$ and $p$ in the vicinity of
$\mathbb{E}\left[P_{1}\right]$. In the next lemma we actually show that
$L_{p}$ follows a local central limit theorem, which will allow us to obtain a
very fine-grained unterstanding of (3.10). The mean and variance of $L_{p}$
are given by

$\displaystyle\mu_{p}$
$\displaystyle:=\mathbb{E}\left[L_{p}\right]=p\left(\frac{{x}_{n}C^{\prime}({x}_{n})}{C({x}_{n})}-m\right)\quad\text{and}$
(3.11) $\displaystyle\sigma_{p}^{2}$
$\displaystyle:=\mathrm{Var}\left(L_{p}\right)=p\left(\frac{{x}_{n}^{2}C^{\prime\prime}({x}_{n})+{x}_{n}C^{\prime}({x}_{n})}{C({x}_{n})}-\left(\frac{{x}_{n}C^{\prime}({x}_{n})}{C({x}_{n})}\right)^{2}\right).$
(3.12)

According to Lemma 2.1 the asymptotic behaviour of these expressions is

$\displaystyle\mu_{p}\sim\alpha
p\chi_{n}^{-1}\qquad\text{and}\qquad\sigma_{p}^{2}\sim\alpha p\chi_{n}^{-2}.$
(3.13)

To prove the local limit theorem we will reformulate
$\mathrm{Pr}\left[L_{p}=s\right]=C({x}_{n})^{-p}[x^{s}]C({x}_{n}x)^{p}$ for
$s=\mu_{p}+t\sigma_{p}$ and $t\in\mathbb{R}$. Although there are many results
in the literature on how to determine large coefficients of $H(x)^{p}$/how to
obtain local limit theorems, none of these are applicable in the generality
considered here. To wit, in [12, 13] or [15, Thm. IX.16] the function $H$ is
assumed to be either logarithmic or to allow for a singular expansion; and in
[15, Thms. VIII.8 and 9] as well as several applications in [41] the ratio
$n/p$ needs to be in $\Theta(1)$ to be able to determine $[x^{n}]H(x)^{p}$.
Clearly this is not the case here as $\mu_{p}/p=\omega(1)$. In [10] a local
limit theorem is derived, provided that a central limit theorem and additional
assumptions, that in particular imply
$\sigma_{p}^{2}/p=\mathcal{O}\left(1\right)$, are true; but note that
$\sigma_{p}^{2}/p=\omega(1)$ in our setting. Indeed, we have to deal here with
a _genuine_ triangle array of independent random variables and thus we conduct
a detailed saddle-point analysis from scratch on our own.

######  Lemma 3.7.

Let $p=p_{n}\to\infty$ as $n\to\infty$. Then for $t=o(p^{1/6})$, as
$n\to\infty$,

$\displaystyle\mathrm{Pr}\left[L_{p}=\mu_{p}+t\sigma_{p}\right]\sim\mathrm{e}^{-t^{2}/2}\cdot\mathrm{Pr}\left[L_{p}=\mu_{p}\right]\sim\mathrm{e}^{-t^{2}/2}\frac{1}{\sqrt{2\pi}\,\sigma_{p}}\sim\mathrm{e}^{-t^{2}/2}\frac{1}{\sqrt{2\pi}}\frac{\chi_{n}}{\sqrt{p\alpha}}.$

The proof is in Section 4.6. Assisted by this lemma we obtain from (3.10)

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]\approx\sum_{p\text{
``close to''
}\mathbb{E}\left[P_{1}\right]}\mathrm{Pr}\left[L_{p}=n-mN_{n}\right]\mathrm{Pr}\left[P_{1}=p\mid{\mathcal{P}}_{N_{n}}\right].$

In the final step of the proof we determine
$\mathrm{Pr}\left[L_{p}=n-mN_{n}\right]$. Here we observe for a last time the
effect of cases (I)/(II). In particular, in case $(I)$ it seems reasonable
that it is enough to consider the case $P_{1}=N_{n}$, see also Lemma 3.5(I);
we obtain the following statements that are a direct consequence of Lemma 3.7.

######  Corollary 3.8.

In case $(I)$

$\mathrm{Pr}\left[L_{N_{n}}=n-mN_{n}\right]=\mathrm{Pr}\left[\sum_{1\leq i\leq
N_{n}}C_{1,i}=n\right]\sim\sqrt{\frac{\alpha+1}{2\pi
y_{n}x_{n}^{2}C^{\prime\prime}(x_{n})}}\sim\sqrt{\frac{\alpha}{2\pi}}\frac{\sqrt{N_{n}}}{n}.$

The proof is in Section 4.7. In case $(II)$ we expect in light of
$\mathbb{E}[P_{1}]\sim a_{n}N_{n}$ is (much) smaller than $N_{n}$ a different
behavior; here we do not stick to a particular value of $P_{1}$.

######  Corollary 3.9.

In case $(II)$

$\mathrm{Pr}\left[L=n-mN_{n}\right]\sim\frac{1}{\sqrt{2\pi\rho^{-m}x_{n}^{2}C^{\prime\prime}(x_{n})}}\sim\sqrt{\frac{\alpha
C_{0}}{2\pi(\alpha+1)}\cdot
g(n-mN_{n})\cdot(n-mN_{n})^{-(\alpha+2)/(\alpha+1)}}.$

Backed by this this groundwork we are able to determine
$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]$. The
proofs are in Section 4.8.

######  Lemma 3.10(I).

In case $(I)$

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]\sim\mathrm{Pr}\left[\sum_{1\leq
i\leq N_{n}}C_{1,i}=n\right].$

######  Lemma 3.10(II).

In case $(II)$

$\mathrm{Pr}\left[{\mathcal{E}}_{n}\mid{\mathcal{P}}_{N_{n}}\right]\sim\mathrm{Pr}\left[L=n-mN_{n}\right].$

The proofs are almost completed. It is straightforward to obtain the
asymptotic order of $[x^{n}y^{N_{n}}]G(x,y)$ in Theorems 1(I) and 1(II) by
combining the respective versions $(I)$ and $(II)$ of Lemmas 3.3(II), 3.4(II)
and 3.9 and applying Corollary 3.2. We conclude this section by summarizing
all the auxiliary statements that allow us to infer the “combinatorial” forms
in Theorems 1(I) and 1(II). The proofs are in Section 4.9.

######  Lemma 3.11(I).

In case $(I)$

$\mathrm{Pr}\left[\sum_{1\leq i\leq N_{n}}C_{1,i}=n\right]\sim\sqrt{2\pi
N_{n}}\cdot{x}_{n}^{n}y_{n}^{N_{n}}\cdot\exp\left\\{c_{m}\frac{\rho^{m}y_{n}}{1-\rho^{m}y_{n}}\right\\}\cdot\mathrm{e}^{-N_{n}}\cdot\frac{1}{N_{n}!}[x^{n}]C(x)^{N_{n}}.$

######  Lemma 3.11(II).

Let $(a_{n})_{n\in\mathbb{N}}$ be the sequence from Lemma 3.3(II). In case
$(II)$

$\mathrm{Pr}\left[L=n-mN_{n}\right]\sim\mathrm{e}^{c_{m}}\cdot{x}_{n}^{n-mN_{n}}\cdot\exp\left\\{-\frac{C({x}_{n})}{{x}_{n}^{m}}\right\\}\cdot[x^{n-mN_{n}}]\exp\left\\{\frac{C(x)-c_{m}x^{m}}{x^{m}}\right\\}.$

Further

$y_{n}C({x}_{n})-\frac{C({x}_{n})}{{x}_{n}^{m}}\sim-
c_{m}\frac{a_{n}}{1-a_{n}}.$

##  4 Proofs

In this section we prove all lemmas and corollaries from Section 3, together
with some auxiliary statements.

###  4.1 Proof of Lemma 3.1

###### Proof of Lemma 3.1.

Let $n,N$ be such that $[x^{n}y^{N}]G(x,y)>0$ and $x_{0},y_{0}>0$ such that
$G(x_{0},y_{0})<\infty$. For $k\in\mathbb{N}$ define the set
$\Omega_{k}:=\\{(p_{1},p_{2},\dots)\in\mathbb{N}_{0}^{\infty}:\sum_{j\geq
1}jp_{j}=k\\}$. Then per definition

$\displaystyle\mathrm{Pr}\left[\Lambda(x_{0},y_{0})=(n,N)\right]$
$\displaystyle=\mathrm{Pr}\left[\sum_{j\geq 1}j\sum_{1\leq i\leq
P_{j}}C_{j,i}=n,\sum_{j\geq 1}jP_{j}=N\right]$
$\displaystyle=\frac{y_{0}^{N}}{G(x_{0},y_{0})}\sum_{\mathrm{p}\in\Omega_{N}}\mathrm{Pr}\left[\sum_{j\geq
1}j\sum_{1\leq i\leq p_{j}}C_{j,i}=n\right]\prod_{j\geq
1}\frac{(C(x_{0}^{j})/j)^{p_{j}}}{p_{j}!}.$ (4.1)

Next we reformulate

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

Plugging this back into (4.1) yields

$\displaystyle\mathrm{Pr}\left[\Lambda(x_{0},y_{0})=(n,N)\right]$
$\displaystyle=\frac{x_{0}^{n}y_{0}^{N}}{G(x_{0},y_{0})}\cdot[x^{n}]\sum_{\mathrm{p}\in\Omega_{N}}\prod_{j\geq
1}\frac{(C(x^{j})/j)^{p_{j}}}{p_{j}!}$
$\displaystyle=\frac{x_{0}^{n}y_{0}^{N}}{G(x_{0},y_{0})}[x^{n}y^{N}]\sum_{k\geq
0}\sum_{\mathrm{p}\in\Omega_{k}}\prod_{j\geq
1}\frac{(C(x^{j})y^{j}/j)^{p_{j}}}{p_{j}!}.$ (4.2)

Define by $(P_{j}(x,y))_{j\geq 1}$ independent Poisson variables with
parameters $(C(x^{j})y^{j}/j)_{j\geq 1}$. Then

$\displaystyle[x^{n}y^{N}]\sum_{k\geq
0}\sum_{\mathrm{p}\in\Omega_{k}}\prod_{j\geq
1}\frac{(C(x^{j})y^{j}/j)^{p_{j}}}{p_{j}!}=[x^{n}y^{N}]G(x,y)\sum_{k\geq
0}\mathrm{Pr}\left[\sum_{j\geq 1}jP_{j}(x,y)=k\right]=[x^{n}y^{N}]G(x,y)$

and inserting this into (4.2) yields
$\mathrm{Pr}\left[\Lambda(x_{0},y_{0})=(n,N)\right]=[x^{n}y^{N}]G(x,y)x_{0}^{n}y_{0}^{N}/G(x_{0},y_{0})$,
which equals $\mathrm{Pr}\left[\Gamma G(x_{0},y_{0})=(n,N)\right]$, as
claimed. ∎

###  4.2 Proof of Lemma 3.2

####  4.2.1 Proof of Lemma 3.3(I)

As we will need that later, we prove the following more general statement,
form which Lemma 3.3(I) follows immediately.

######  Lemma 4.1.

Let $\chi_{n}=\ln(\rho/{x}_{n})$. In case $(I)$

$\displaystyle\chi_{n}\sim\alpha\frac{N_{n}}{n},\qquad
y_{n}\sim\rho^{-m}\cdot\frac{h(n/N^{*}_{n})}{h(n/N_{n})}\cdot\lambda_{n}^{\alpha+1}\qquad\text{and}\qquad\limsup_{n\to\infty}y_{n}<\rho^{-m}.$

Further, if $\lambda_{n}=o(1)$ then $y_{n}=o(1)$ and if
$\lambda_{n}=\Theta(1)$ then
$y_{n}\sim\rho^{-m}\lambda_{n}^{\alpha+1}=\Theta(1)$. Moreover,

$\displaystyle y_{n}C({x}_{n})=N_{n}+c_{m}S_{n}\qquad\text{and}\qquad
S_{n}=\Theta(y_{n}).$

###### Proof.

We first show that $y_{n}C({x}_{n})=\Theta(N_{n})$. Since
$S_{n}=x_{n}^{m}y_{n}/(1-x_{n}^{m}y_{n})>0$ we infer from (3.4) that
$y_{n}C({x}_{n})<N_{n}$. For the sake of contradiction assume that there is a
sequence $(n_{\ell})_{\ell\in\mathbb{N}}$ such that
$y_{n_{\ell}}C(x_{n_{\ell}})=o(N_{n_{\ell}})$. This implies that
$S_{n_{\ell}}\sim N_{n_{\ell}}$ due to (3.4), which is only possible if
$y_{n}\sim\rho^{-m}$, as we know that $x_{n}\sim\rho^{m}$ from Lemma 2.1. By
applying (2.6) for $k=0$ and since $n_{\ell}-mN_{n_{\ell}}\sim n_{\ell}$ in
case $(I)$ we thus infer that
$y_{n_{\ell}}C(x_{n_{\ell}})=\Theta(g(n_{\ell})n_{\ell}^{\alpha/(\alpha+1)})=\Theta(N^{*}_{n_{\ell}})=\Omega(N_{n_{\ell}})$,
the desired contradiction. We showed that $y_{n}C(x_{n})=\Theta(N_{n})$. We
also immediately obtain from this fact that $\chi_{n}=\Theta(n/N_{n})$, since
$\chi_{n}^{-1}=\Theta(x_{n}C^{\prime}(x_{n})/C(x_{n}))$ due to Lemma 2.1.

Next we show that $S_{n}=\mathcal{O}\left(1\right)$, again by contradiction.
Assume that there is a sequence $(n_{\ell})_{\ell\in\mathbb{N}}$ such that
$S_{n_{\ell}}=\omega(1)$. Then again $y_{n_{\ell}}\sim\rho^{-m}$ so that we
get with Lemma 2.1 and the definition of $N^{*}_{n_{\ell}}$ from (1.6) that,
as $\ell\to\infty$,

$\displaystyle y_{n_{\ell}}C(x_{n_{\ell}})\sim
C_{0}g(n_{\ell})n_{\ell}^{\alpha/(\alpha+1)}=N_{n_{\ell}}^{*}.$ (4.3)

But in case $(I)$ we have that
$\limsup_{\ell\to\infty}y_{n_{\ell}}C(x_{n_{\ell}})/N^{*}_{n_{\ell}}\leq\limsup_{\ell\to\infty}N_{n_{\ell}}/N^{*}_{n_{\ell}}<1$,
a contradiction. We just showed that $S_{n}=\mathcal{O}\left(1\right)$. It
immediately follows that $y_{n}C(x_{n})\sim N_{n}$ and
$\alpha\chi_{n}^{-1}\sim x_{n}C^{\prime}(x_{n})/C(x_{n})\sim n/N_{n}$ from
(3.4).

From $S_{n}=\mathcal{O}\left(1\right)$ we also conclude that $\limsup
y_{n}<\rho^{-m}$, as ${x}_{n}\sim\rho^{m}$ due to Lemma 2.1. This, in turn,
also implies $S_{n}=\Theta(y_{n})$, as claimed. It remains to show the
validity of the asymptotic expression of $y_{n}$. By applying Lemma 2.1, in
particular (2.8),

$\chi_{n}^{-1}h(\chi_{n}^{-1})^{1/(\alpha+1)}\sim\left(\frac{n}{\Gamma(\alpha+1)y_{n}}\right)^{1/(\alpha+1)}.$

Solving for $y_{n}$ yields $y_{n}\sim
n\chi_{n}^{\alpha+1}/(h(\chi^{-1})\Gamma(\alpha+1))$. We plug in
$\chi_{n}\sim\alpha N_{n}/n$ as well as the definitions of
$C_{0}=\alpha^{-1}(\rho^{-m}\Gamma(\alpha+1))^{1/(\alpha+1)}$ and $N^{*}_{n}$
from (1.6) and $N=\lambda_{n}N^{*}_{n}=\lambda_{n}g(n)n^{\alpha/(\alpha+1)}$
to obtain that

$y_{n}\sim\rho^{-m}\cdot\frac{g(n)^{\alpha+1}}{h(n/N_{n})}\cdot\lambda_{n}^{\alpha+1}.$

Since $g(n)=h(n/N^{*}_{n})^{1/(\alpha+1)}$, which can be seen directly from
(1.5) for $u=n/N^{*}_{n}$ and $v=n$, we are done. If $\lambda_{n}=o(1)$ we
have with (A.2) that there is a $0<\delta<\alpha+1$ such that
$\lambda_{n}^{\alpha+1}\cdot
h(n/N^{*}_{n})/h(n/N_{n})\leq(N^{*}_{n}/N_{n})^{\delta}=\lambda_{n}^{\alpha+1-\delta}=o(1)$.
If $\lambda_{n}=\Theta(1)$ then $h(n/N^{*}_{n})/h(n/N_{n})\sim 1$ finishing
the proof. ∎

####  4.2.2 Proof of Lemma 3.3(II)

We later need the following statement which contains Lemma 3.3(II) together
with asymptotic properties of the solution $({x}_{n},y_{n})$ to (3.4) in case
$(II)$.

######  Lemma 4.2.

Let $\chi_{n}=\ln(\rho/{x}_{n})$. Consider the non-negative sequence

$a_{n}:=\lambda_{n}^{-1}\cdot\frac{g(n-mN_{n})}{g(n)}\cdot\left(\frac{n-mN_{n}}{n}\right)^{\alpha/(\alpha+1)},\quad
n\in\mathbb{N}$ (4.4)

that fulfills

$a_{n}\leq\lambda_{n}^{-1}\text{ for }n\in\mathbb{N}\text{ sufficiently
large}\quad\text{and}\quad a_{n}\sim\lambda_{n}^{-1}\text{ for }N_{n}=o(n).$

Then, in case $(II)$,

$\displaystyle y_{n}\sim\rho^{-m}\quad\textrm{and}\quad\chi_{n}\sim\alpha\cdot
a_{n}\cdot\frac{N_{n}}{n-mN_{n}}\sim\alpha C_{0}\cdot
g(n-mN_{n})\cdot(n-mN_{n})^{-1/(\alpha+1)},$ $\displaystyle
y_{n}C({x}_{n})\sim a_{n}\cdot N_{n}\sim C_{0}\cdot
g(n-mN_{n})\cdot(n-mN_{n})^{\alpha/(\alpha+1)}\quad\text{and}\quad
S_{n}\sim\frac{1-a_{n}}{c_{m}}\cdot N_{n}.$

###### Proof.

Since $x_{n}^{m}y_{n}<1$ and $x_{n}\sim\rho$ according to Lemma 2.1, it is
clear that $y_{n}\leq(1+\varepsilon)\rho^{-m}$ for all $\varepsilon>0$ and all
sufficiently large $n$. First of all, we show that $y_{n}\sim\rho^{-m}$ by
establishing that even $S_{n}=\Theta(N_{n})$. We know that $S_{n}\leq N_{n}$,
as $y_{n}C({x}_{n})\geq 0$ in (3.4). We show $S_{n}=\Omega(N_{n})$ by
contradiction. Assume there is a sequence $(n_{\ell})_{\ell\in\mathbb{N}}$
such that $S_{n_{\ell}}=o(N_{n_{\ell}})$. From (3.4) and by applying Lemma 2.1
and
$N_{n_{\ell}}=\lambda_{n_{\ell}}N^{*}_{n_{\ell}}=\lambda_{n_{\ell}}C_{0}g(n_{\ell})n_{\ell}^{\alpha/(\alpha+1)}$,
where $C_{0}=\alpha^{-1}(\rho^{-m}\Gamma(\alpha+1))^{1/(\alpha+1)}$, we obtain

$\displaystyle
1\sim\frac{y_{n_{\ell}}C(x_{n_{\ell}})}{N_{n_{\ell}}}\sim\rho^{m/(\alpha+1)}y_{n_{\ell}}\lambda_{n_{\ell}}^{-1}\frac{g\big{(}(n_{\ell}-mN_{n_{\ell}})/y_{n_{\ell}}\big{)}}{g({n_{\ell}})}\left(\frac{n_{\ell}-mN_{n_{\ell}}}{n_{\ell}y_{n_{\ell}}}\right)^{\alpha/(\alpha+1)}.$
(4.5)

Since $g$ is slowly varying we obtain from (A.2) for $0<\delta<1/(\alpha+1)$
and sufficiently large $\ell$

$\frac{g\big{(}(n_{\ell}-mN_{n_{\ell}})/y_{n_{\ell}}\big{)}}{g({n_{\ell}})}\leq\max\left\\{\left(\frac{n_{\ell}-mN_{n_{\ell}}}{n_{\ell}y_{n_{\ell}}}\right)^{\delta},\left(\frac{n_{\ell}-mN_{n_{\ell}}}{n_{\ell}y_{n_{\ell}}}\right)^{-\delta}\right\\}.$

Together with (4.5) and the simple fact
$(n_{\ell}-mN_{n_{\ell}})/(n_{\ell}y_{n_{\ell}})\leq y_{n_{\ell}}^{-1}$ we
obtain

$\displaystyle\frac{y_{n_{\ell}}C(x_{n_{\ell}})}{N_{n_{\ell}}}$
$\displaystyle\leq\rho^{m/(\alpha+1)}y_{n_{\ell}}\lambda_{n_{\ell}}^{-1}\max\\{y_{n_{\ell}}^{-\alpha/(\alpha+1)-\delta},y_{n_{\ell}}^{-\alpha/(\alpha+1)+\delta}\\}\leq(1+\varepsilon)^{1/(\alpha+1)}\lambda_{n_{\ell}}^{-1}((1+\varepsilon)\rho)^{\delta}.$

As $\liminf_{\ell\to\infty}\lambda_{n_{\ell}}>1$, this can be made $<1$ by
choosing $\varepsilon,\delta>0$ sufficiently small. This contradicts (4.5) so
that we have shown that $S_{n}=\Theta(N_{n})$ also implying
$y_{n}\sim\rho^{-m}$.

With this at hand and plugging $y_{n}\sim\rho^{-m}$ into the expressions for
$C({x}_{n})$ and $\chi_{n}$ from Lemma 2.1 as well as recalling
$C_{0}:=\alpha^{-1}(\rho^{-m}\Gamma(\alpha+1))^{1/(\alpha+1)}$ we obtain

$\displaystyle y_{n}C({x}_{n})\sim C_{0}\cdot
g(n-mN_{n})\cdot(n-mN_{n})^{\alpha/(\alpha+1)}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \chi_{n}\sim\alpha C_{0}\cdot
g(n-mN_{n})\cdot(n-mN)^{-1/(\alpha+1)}.$

Multiplying both right-hand sides by
$1=N^{*}_{n}/N^{*}_{n}=\lambda_{n}^{-1}N_{n}/(C_{0}g(n)n^{\alpha/(\alpha+1)})$
we obtain the claimed representations $y_{n}C(x_{n})\sim a_{n}\cdot N_{n}$ and
$\chi_{n}\sim\alpha\cdot a_{n}\cdot N_{n}/(n-mN_{n})$ for

$\displaystyle
a_{n}:=\lambda_{n}^{-1}\cdot\frac{g(n-mN_{n})}{g(n)}\cdot\left(\frac{n-mN_{n}}{n}\right)^{\alpha/(\alpha+1)}.$

The properties of $a_{n}$ are readily obtained by noting that $g$ is slowly
varying and the simple fact $(n-mN_{n})/n\leq 1$. Finally, since $a_{n}$ is
bounded away from one, we also obtain from (3.4) that
$S_{n}=(N_{n}-y_{n}C(x_{n}))/c_{m}\sim(1-a_{n})/c_{m}\cdot N_{n}$.

∎

###  4.3 Proof of Lemma 3.3(II)

###### Proof of Lemma 3.4(I).

Due to (3.4) and Lemma 4.1 we know that
$y_{n}C({x}_{n})=N_{n}-c_{m}{x}_{n}^{m}y_{n}/(1-{x}_{n}^{m}y_{n})=N_{n}-c_{m}\rho^{m}y_{n}/(1-\rho^{m}y_{n})+o(1)$.
Further, Lemma 2.7 entails that there is $A>0$ such that

$\sum_{j\geq 2}\frac{C({x}_{n}^{j})}{j}y_{n}^{j}=\sum_{j\geq
2}({x}_{n}^{m}y_{n})^{j}\frac{C({x}_{n}^{j})}{j{x}_{n}^{jm}}\leq
c_{m}\sum_{j\geq 2}({x}_{n}^{m}y_{n})^{j}(1+A{x}_{n}^{j}).$

This is bounded from above: due to Lemma 4.1 we know that $\limsup
y_{n}<\rho^{-m}$ and $x_{n}\leq\rho$, which in turn implies that
${x}_{n}^{m}y_{n}$ is bounded from above by something strictly smaller than
$1$. Hence, using that $G(x,y)$ is continuous in $x$ and $x_{n}\sim\rho$ we
obtain by dominated convergence

$G({x}_{n},y_{n})=\exp\left\\{y_{n}C({x}_{n})+\sum_{j\geq
2}\frac{C({x}_{n}^{j})}{j}y_{n}^{j}\right\\}\sim\exp\left\\{N_{n}-c_{m}\frac{\rho^{m}y_{n}}{1-\rho^{m}y_{n}}\right\\}\exp\left\\{\sum_{j\geq
2}\frac{C(\rho^{j})}{j}y_{n}^{j}\right\\}.$

∎

###### Proof of Lemma 3.4(II).

Let $(a_{n})_{n\in\mathbb{N}}$ be the sequence from Lemma 4.2. Since
${x}_{n}^{m}y_{n}\to 1$ and $(1-{x}_{n}^{m}y_{n})^{-1}\sim(1-a_{n})/c_{m}\cdot
N_{n}$ due to Lemma 4.2 we obtain that

$\displaystyle G({x}_{n},y_{n})$
$\displaystyle=\exp\left\\{y_{n}C({x}_{n})+c_{m}\sum_{j\geq
1}\frac{({x}_{n}^{m}y_{n})^{j}}{j}-c_{m}{x}_{n}^{m}y_{n}+\sum_{j\geq
2}\frac{C({x}_{n}^{j})y_{n}^{j}-c_{m}{x}_{n}^{jm}y_{n}^{j}}{j}\right\\}$
$\displaystyle\sim\exp\left\\{y_{n}C({x}_{n})\right\\}\cdot\frac{1}{c_{m}^{c_{m}}}\cdot\left(\left(1-a_{n}\right)N_{n}\right)^{c_{m}}\cdot\exp\left\\{-c_{m}+\sum_{j\geq
2}\frac{C({x}_{n}^{j})y_{n}^{j}-c_{m}{x}_{n}^{jm}y_{n}^{j}}{j}\right\\}.$

With Lemma 2.7 there is some $A>0$ such that for all $j\geq 2$

$\big{(}C({x}_{n}^{j})y_{n}^{j}-c_{m}{x}_{n}^{jm}y_{n}^{j}\big{)}/j\leq
A(x_{n}^{m}y_{n})^{j}x_{n}^{j}.$

Since $\limsup x_{n}^{m+1}y_{n}=\rho<1$ the expression in the previous display
is summable and by dominated convergence we obtain that

$\exp\left\\{\sum_{j\geq
2}(C({x}_{n}^{j})y_{n}^{j}-c_{m}{x}_{n}^{jm}y_{n}^{j})/{j}\right\\}\to\exp\left\\{\sum_{j\geq
2}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\right\\}=G_{>m}^{\geq
2}(\rho).$

∎

###  4.4 Proof of Lemma 3.4(II)

We will use the probability generating function (pgf)
$F^{(\ell)}(x)=\mathbb{E}[{x^{P^{(\ell)}}}]$ of the sum of Poisson random
variables $P^{(\ell)}:=\sum_{j>\ell}jP_{j}$ for $\ell\in\mathbb{N}_{0}$.
Define the auxiliary series

$G^{(\ell)}(x,y):=\exp\left\\{\sum_{j>\ell}\frac{C(x^{j})}{j}y^{j}\right\\}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
R^{(\ell)}(x):=\exp\left\\{-c_{m}\sum_{1\leq
j\leq\ell}\frac{x^{j}}{j}+\sum_{j>\ell}\frac{C({x}_{n}^{j})-c_{m}{x}_{n}^{jm}}{j{x}_{n}^{jm}}x^{j}\right\\}.$

The pgf of a $\mathrm{Po}\left(\lambda\right)$ random variable equals
$\mathrm{e}^{\lambda(x-1)}$. By the independence of the $P_{j}$’s,

$F^{(\ell)}(x)=\frac{1}{G^{(\ell)}({x}_{n},y_{n})}\exp\left\\{\sum_{j>\ell}\frac{C({x}_{n}^{j})y_{n}^{j}}{j}x^{j}\right\\}.$

We want to determine $[x^{N_{n}}]F^{(0)}(x)$ that is precisely the probability
of ${\mathcal{P}}_{N_{n}}=\\{P^{(0)}=N_{n}\\}$. In general, when computing
coefficients of these pgfs we will factorize $F^{(\ell)}(x)$ in such a way
that Lemma 2.5 is applicable. More precisely, we split up for any
$K\in\mathbb{N}$ and $\ell\in\mathbb{N}_{0}$

$\displaystyle[x^{K}]F^{(\ell)}(x)$
$\displaystyle=\frac{({x}_{n}^{m}y_{n})^{K}}{G^{(\ell)}({x}_{n},y_{n})}\cdot[x^{K}]\frac{1}{(1-x)^{c_{m}}}\cdot
R^{(\ell)}(x).$ (4.6)

When investigating (4.6) great care has to be taken. In $R^{(0)}(x)$ the term
$C({x}_{n})/{x}_{n}^{m}$, which tends to infinity due to Lemma 2.1, appears.
Setting $R(x):=R^{(1)}(x)$ and $F(x):=F^{(0)}(x)$ we rewrite

$\displaystyle[x^{N_{n}}]F(x)$
$\displaystyle=\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\cdot[x^{N_{n}}]\frac{1}{(1-x)^{c_{m}}}\cdot\exp\left\\{\frac{C({x}_{n})}{{x}_{n}^{m}}x\right\\}\cdot
R(x).$ (4.7)

In order to apply Lemma 2.5 we get rid of the term $R(x)$. This is achieved by
using Lemma 2.4, where we need to establish uniform convergence of $R$ as $n$
gets large. Note that the coefficients of $F^{(\ell)}(x)$ are much easier to
compute for $\ell>1$ as the term involving $C({x}_{n})/{x}_{n}^{m}$ is absent.
Nevertheless, we need uniform convergence for $R^{(\ell)}$ in this case as
well.

######  Lemma 4.3.

Let $\ell\in\mathbb{N}_{0}$ and set

$Q^{(\ell)}(x):=\exp\left\\{-c_{m}\sum_{1\leq
j\leq\ell}\frac{x^{j}}{j}+\sum_{j>\ell}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}x^{j}\right\\}.$

Let $0<\varepsilon<\rho^{-1}$. Then $R^{(\ell)}$ converges uniformly to
$Q^{(\ell)}$ on $[0,\rho^{-1}-\varepsilon]$ and the radius of convergence of
$Q^{(\ell)}$ is at least $\rho^{-1}>1$. Further, there exists a sequence
$(d_{n})_{n\in\mathbb{N}_{0}}$ such that $\lvert[x^{k}]R^{(\ell)}(x)\rvert\leq
d_{k}$ for all $k,n\in\mathbb{N}_{0}$ such that $\sum_{k\geq
0}d_{k}x^{k}<\infty$ for any $x\in[0,\rho^{-1}-\varepsilon]$.

###### Proof.

We will use the following standard result in real analysis. Let
$(f_{n})_{n\in\mathbb{N}}$ be real-valued functions all defined on some closed
interval $[a,b]$. Suppose that $f_{n}$ is strictly monotone for each
$n\in\mathbb{N}$ and that $(f_{n})_{n\in\mathbb{N}}$ converges pointwise to a
continuous function $f$. Then the convergence is uniform. In our setting, we
have that

$R^{(\ell)}(x)=\exp\left\\{-c_{m}\sum_{1\leq
j\leq\ell}\frac{x^{j}}{j}\right\\}\cdot\exp\left\\{\sum_{j>\ell}\frac{C(x_{n}^{j})-c_{m}x_{n}^{jm}}{jx_{n}^{jm}}\cdot
x^{j}\right\\}=:e(x)\cdot f_{n}(x).$

Clearly, if we show that $f_{n}(x)$ converges uniformly to some $f(x)$, then
$R^{(\ell)}(x)$ converges uniformly to $e(x)f(x)$. A direct application of
Lemma 2.7 yields that there exists some $A>0$ such that

$\displaystyle\log f_{n}(x)\leq A\sum_{j>\ell}\frac{x_{n}^{j}}{j}\leq
A\sum_{j>\ell}\frac{\rho^{j}}{j}.$ (4.8)

Hence the radius of convergence of $f_{n}(x)$ is at least $\rho^{-1}$,
implying that $f_{n}(x)$ is defined on $[0,\rho^{-1}-\varepsilon]$ for any
$0<\varepsilon<\rho^{-1}$ and $n\in\mathbb{N}$. Moreover, $f_{n}$ has only
non-negative coefficients, so it is strictly increasing. Finally, (4.8) shows
that by dominated convergence $f_{n}$ converges pointwise to
$f(x):=Q^{(\ell)}(x)/e(x)$. Since $f$ is continuous we have proven that the
convergence is uniform and the claim that $R^{(\ell)}(x)$ converges uniformly
to $e(x)f(x)=Q^{(\ell)}(x)$ follows immediately.

We proceed with estimating $\lvert[x^{k}]R^{(\ell)}(x)\rvert$. Let us first
note that $\lvert[x^{k}]\mathrm{e}^{-px^{q}}\rvert=[x^{k}]\mathrm{e}^{px^{q}}$
for any $p>0$ and $k,q\in\mathbb{N}$. Further the second sum in $\ln
R^{(\ell)}(x)$ involves only non-negative terms, so that

$\lvert[x^{k}]R^{(\ell)}(x)\rvert=[x^{k}]R_{+}^{(\ell)}(x),\leavevmode\nobreak\
\textrm{where }\leavevmode\nobreak\
R_{+}^{(\ell)}:=\textrm{exp}\Big{\\{}c_{m}\sum_{1\leq
j\leq\ell}\frac{x^{j}}{j}+\sum_{j>\ell}\frac{C({x}_{n}^{j})-c_{m}{x}_{n}^{jm}}{j{x}_{n}^{jm}}x^{j}\Big{\\}}.$

Since $R_{+}^{(\ell)}(x)$ has only non-negative coefficients, we deduce from
(2.16) that for all $0<k\in\mathbb{N}_{0}$ and setting
$y=\rho^{-1}-{\varepsilon}/{2}$

$\lvert[x^{k}]R^{(\ell)}(x)\rvert\leq R_{+}^{(\ell)}(y)\cdot y^{-k}.$

Since ${x}_{n}\sim\rho$ due to Lemma 2.1 we obtain analogous to (4.8) that
there is some $A_{3}>0$ such that $R_{+}^{(\ell)}(y)\leq A_{3}$. Setting
$d_{k}:=A_{3}y^{-k}$ for $k\in\mathbb{N}_{0}$ the claim is verified since
$d_{k}(\rho^{-1}-\varepsilon)^{k}=A_{3}(\rho^{-1}-\varepsilon)^{k}/(\rho^{-1}-\varepsilon/2)^{k}$
is summable. ∎

With these ingredients at hand we are able to prove Lemmas 3.5(I) and 3.5(II).

###### Proof of Lemma 3.5(I).

Abbreviate $h_{n}:=C({x}_{n})/{x}_{n}^{m}$ and set

$A(x):=\frac{1}{(1-x)^{c_{m}}}\cdot\exp\left\\{h_{n}x\right\\}\quad\text{and}\quad
R(x):=\exp\left\\{-c_{m}x+\sum_{j\geq
2}\frac{C({x}_{n}^{j})-c_{m}{x}_{n}^{jm}}{j{x}_{n}^{jm}}x^{j}\right\\}.$

With this at hand, we use (4.7) to reformulate

$\displaystyle\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]$
$\displaystyle=\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\cdot[x^{N_{n}}]A(x)R(x).$

We will apply Lemma 2.4 to $A(x)R(x)$ and verify conditions (2.11) and (2.12)
first. Set $\alpha_{n}:=h_{n}/N_{n}$ and $\alpha_{n,k}:=h_{n}/(N_{n}-k)$ for
$0\leq k<N_{n}$. We obtain from Lemma 4.1

$\displaystyle\alpha_{n}=\frac{y_{n}C({x}_{n})}{y_{n}x_{n}^{m}}\frac{1}{N_{n}}\sim\frac{1}{y_{n}x_{n}^{m}}\sim\frac{h(n/N_{n})}{h(n/N^{*}_{n})}\cdot\lambda_{n}^{-(\alpha+1)},$
(4.9)

so that, again by Lemma 4.1, $\liminf\alpha_{n}=\rho^{-m}/\limsup y_{n}>1$ and
$\liminf\alpha_{n,k}>1$, too, uniformly for $0\leq k<N_{n}$. Hence, Lemma
2.5(ii) is applicable and we obtain for all $k$ such that $N_{n}-k\to\infty$

$\displaystyle[x^{N_{n}-k}]A(x)=[x^{N_{n}-k}]\frac{1}{(1-x)^{c_{m}}}\mathrm{e}^{\alpha_{n,k}(N_{n}-k)x}\sim\left(\frac{1}{1-\alpha_{n,k}^{-1}}\right)^{c_{m}}\cdot\frac{h_{n}^{N_{n}-k}}{(N_{n}-k)!}.$
(4.10)

This implies (2.11), i.e., for $k\in\mathbb{N}_{0}$ and as $n\to\infty$

$\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}-k+1}]A(x)}\sim\left(\frac{1-\alpha_{n,k}^{-1}}{1-\alpha_{n,k-1}^{-1}}\right)^{c_{m}}\frac{N_{n}}{h_{n}}\stackrel{{\scriptstyle\eqref{eq:delta_N_l<d}}}{{\sim}}\frac{h(n/N^{*}_{n})}{h(n/N_{n})}\cdot\lambda_{n}^{\alpha+1}=:\rho_{n}.$

Set $\overline{\rho}:=\limsup\rho_{n}<1$. Due to (4.10) we have for any $k$
such that $N_{n}-k\to\infty$

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}$
$\displaystyle\sim\left(\frac{1-\alpha_{n}^{-1}}{1-\alpha_{n,k}^{-1}}\right)^{c_{m}}\frac{N_{n}!}{(N_{n}-k)!}N_{n}^{-k}\left(\frac{N_{n}}{h_{n}}\right)^{k}\sim\left(\frac{1-\alpha_{n}^{-1}}{1-\alpha_{n,k}^{-1}}\right)^{c_{m}}\frac{N_{n}!}{(N_{n}-k)!}N_{n}^{-k}\rho_{n}^{k}.$

Since $\alpha_{n,k}\geq\alpha_{n}$ and $N_{n}!/(N_{n}-k)!N_{n}^{-k}\leq 1$ we
obtain for any $\varepsilon>0$

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}\leq(1+\varepsilon)^{k}\rho_{n}^{k},\quad
N_{n}-k\text{ sufficiently large.}$ (4.11)

Lemma 2.5(i) and (4.10) imply that for any $k$ such that
$N_{n}-k=\mathcal{O}\left(1\right)$

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}$
$\displaystyle\sim(1-\alpha_{n}^{-1})^{c_{m}}\frac{N_{n}!}{(N_{n}-k)!}h_{n}^{-k}\sim(1-\alpha_{n}^{-1})^{c_{m}}\frac{N_{n}!}{(N_{n}-k)!}N_{n}^{-k}\rho_{n}^{k}\leq\rho_{n}^{k}.$

Again this entails that for any $\varepsilon>0$ and $N_{n}$ sufficiently large

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}\leq(1+\varepsilon)^{k}\rho_{n}^{k}\quad\text{for
}N_{n}-k=\mathcal{O}\left(1\right).$ (4.12)

Together with (4.11) this shows that condition (2.12) is fulfilled for any
$\varepsilon>0$ as long as $n$ is sufficiently large. Let us proceed with
checking the remaining conditions of Lemma 2.4. Choose $\varepsilon>0$ in
(4.11) and (4.12) such that $a:=(1+\varepsilon)\overline{\rho}<\rho^{-1}$;
this is possible, since $\overline{\rho}<1$ and $\rho>1$. Then the series
$R(x)$ are all analytic at $a$ by Lemma 4.3. Moreover, by the same lemma,
$R(x)$ converges uniformly to

$Q(x):=\exp\left\\{-c_{m}x+\sum_{j\geq
2}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\cdot x^{j}\right\\}$

in any closed subinterval of $[0,\rho^{-1})$. In particular, as $\rho^{-1}>1$,
we obtain uniform convergence on $[0,a]$. Moreover, Lemma 4.3 guarantees the
existence of a sequence $(d_{n})_{n\in\mathbb{N}_{0}}$ such that
$\lvert[x^{k}]R(x)\rvert\leq d_{k}$ and $\sum_{k\geq 1}d_{k}a^{k}<\infty$.
Finally $Q(\rho_{n})\geq\exp\left\\{-c_{m}\overline{\rho}\right\\}>0$ for all
$n\in\mathbb{N}$ so that all conditions of Lemma 2.4 are met. We deduce with a
combination of (4.9) and (4.10)

$[x^{N_{n}}]A(x)\cdot R(x)\sim Q(\rho_{n})\cdot[x^{N_{n}}]A(x)\sim
Q(\rho_{n})\cdot\left(\frac{1}{1-\rho_{n}}\right)^{c_{m}}\cdot\frac{h_{n}^{N_{n}}}{N_{n}!}.$

Recalling (4.7) we have shown so far

$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim
Q(\rho_{n})\cdot\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\left(\frac{1}{1-\rho_{n}}\right)^{c_{m}}\cdot\frac{h_{n}^{N_{n}}}{N_{n}!}.$

In what follows, we simplify this term. First note that $\rho^{-m}\rho_{n}\sim
y_{n}$ by Lemma 4.1. Thus

$\left(\frac{1}{1-\rho_{n}}\right)^{c_{m}}\sim\exp\left\\{c_{m}\sum_{j\geq
1}\frac{(\rho^{m}y_{n})^{j}}{j}\right\\}.$

Further, recalling that $h_{n}:=C({x}_{n})/{x}_{n}^{m}$, we obtain

$\displaystyle({x}_{n}^{m}y_{n})^{N_{n}}h_{n}^{N_{n}}=(y_{n}C(x_{n}))^{N_{n}}\stackrel{{\scriptstyle\eqref{eq:saddle_point_digest}}}{{=}}\left(N_{n}-c_{m}\frac{{x}_{n}^{m}y_{n}}{1-{x}_{n}^{m}y_{n}}\right)^{N_{n}}\sim
N_{n}^{N_{n}}\exp\left\\{-c_{m}\frac{\rho^{m}y_{n}}{1-\rho^{m}y_{n}}\right\\}.$

Together with Lemma 3.4(I) this establishes the limit law

$\displaystyle\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim
Q\big{(}\rho^{m}y_{n}\big{)}\cdot\exp\left\\{c_{m}\sum_{j\geq
1}\frac{(\rho^{m}y_{n})^{j}}{j}\right\\}\cdot\exp\left\\{-\sum_{j\geq
2}\frac{C(\rho^{j})}{j}{y}_{n}^{j}\right\\}\cdot\mathrm{e}^{-N_{n}}\frac{N_{n}^{N_{n}}}{N_{n}!}\sim\frac{1}{\sqrt{2\pi
N_{n}}},$

as claimed. To show the second statement (3.7) we first estimate

$\mathrm{Pr}\left[\sum_{j\geq
2}jP_{j}=K\right]\leq[x^{K}]\exp\left\\{\sum_{j\geq
2}\frac{C({x}_{n}^{j})y_{n}^{j}}{j}x^{j}\right\\}.$

Applying (2.16) yields

$\displaystyle\mathrm{Pr}\left[\sum_{j\geq
2}jP_{j}=K\right]\leq\exp\left\\{\sum_{j\geq
2}\frac{C({x}_{n}^{j})}{j}\right\\}y_{n}^{K}.$ (4.13)

Further $\sum_{j\geq 2}C({x}_{n}^{j})/j\leq\sum_{j\geq
2}C(\rho^{j})/j<\infty$. At the same time we observe with Lemma 2.7 that there
is some $A>0$ such that

$\sum_{j\geq 2}\frac{C({x}_{n}^{j})y_{n}^{j}}{j}x^{j}\leq A\cdot\sum_{j\geq
2}\frac{({x}_{n}^{m}y_{n})^{j}}{j}x^{j}.$

Since according to Lemma 4.1 we have that $\limsup{x}_{n}^{m}y_{n}\leq
1-\varepsilon$ for some $0<\varepsilon<1$ we deduce that there is some $a>1$
with $(1-\varepsilon)a<1$ such that by (2.16) we obtain

$\mathrm{Pr}\left[\sum_{j\geq
2}jP_{j}=K\right]\leq\exp\left\\{A\cdot\sum_{j\geq
2}\frac{((1-\varepsilon)a)^{j}}{j}\right\\}a^{-K},$

finishing the proof together with (4.13). ∎

###### Proof of Lemma 3.5(II).

Abbreviate $h_{n}:=C({x}_{n})/{x}_{n}^{m}$ and set

$A(x):=\frac{1}{(1-x)^{c_{m}}}\cdot\exp\left\\{h_{n}x\right\\}\quad\text{and}\quad
R(x):=\exp\left\\{-c_{m}x+\sum_{j\geq
2}\frac{C({x}_{n}^{j})-c_{m}{x}_{n}^{jm}}{j{x}_{n}^{jm}}x^{j}\right\\}.$

Then, from (4.7) we obtain that

$\displaystyle\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]$
$\displaystyle=\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\cdot[x^{N_{n}}]A(x)\cdot
R(x).$

We will apply Lemma 2.4 to $A(x)R(x)$. Let us first verify the conditions
(2.11), (2.12). Set $\alpha_{n}:=h_{n}/N_{n}$ and
$\alpha_{n,k}:=h_{n}/(N_{n}-k)$. Let $(a_{n})_{n\in\mathbb{N}}$ be the
sequence from (4.4). Then, as stated in Lemma 4.2,

$\displaystyle\alpha_{n}=\frac{y_{n}C({x}_{n})}{{x}_{n}^{m}y_{n}}\frac{1}{N_{n}}\sim
a_{n}$

and

$\displaystyle[x^{N_{n}-k}]A(x)=[x^{N_{n}-k}]\frac{1}{(1-x)^{c_{m}}}\mathrm{e}^{\alpha_{n,k}(N_{n}-k)x},\quad
p\in\mathbb{N}_{0}.$ (4.14)

For (fixed) $k\in\mathbb{N}_{0}$ and using (4.4) we obtain that
$\limsup\alpha_{n,k}=\limsup\alpha_{n}\leq\limsup\lambda_{n}^{-1}<1$. Thus
Lemma 2.5(iii) yields

$[x^{N_{n}-p}]A(x)\sim\frac{\big{(}(1-\alpha_{n})N_{n}\big{)}^{c_{m}-1}}{\Gamma(c_{m})}\mathrm{e}^{h_{n}},\quad
k\in\mathbb{N}_{0},n\to\infty.$ (4.15)

Hence condition (2.11) is fulfilled with $\rho_{n}\sim 1$ and
$\overline{\rho}=\limsup\rho_{n}=1$. We verify condition (2.12) as well. Let
$\delta>0$ be such that $(1+\delta)\limsup h_{n}/N_{n}<1$. Such a $\delta$
exists, since $\limsup h_{n}/N_{n}=\limsup\alpha_{n}<1$, as we already saw
before. With this at hand we split up $\\{0,\dots,N_{n}\\}$ into

$B_{1}:=\\{0,\dots,N_{n}-(1+\delta)h_{n}-1\\}\quad\text{and}\quad
B_{2}:=\\{N_{n}-(1+\delta)h_{n},\dots,N_{n}\\}.$

Consider $k\in B_{1}$. Then
$\limsup\alpha_{n,k}\leq\limsup\alpha_{n}N_{n}/((1+\delta)h_{n})=(1+\delta)^{-1}<1$.
Further $N_{n}-k\to\infty$ in this case, so that we obtain from (4.14) and
Lemma 2.5(iii)

$[x^{N_{n}-k}]A(x)\sim\frac{\big{(}(1-\alpha_{n,k})(N_{n}-k)\big{)}^{c_{m}-1}}{\Gamma(c_{m})}\mathrm{e}^{h_{n}}.$

This leads to

$\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}\sim\left(\frac{1-\alpha_{n,N_{n}-k}}{1-\alpha_{n}}\right)^{c_{m}-1}\left(1-\frac{k}{N_{n}}\right)^{c_{m}-1}=\left(1-\frac{k}{N_{n}(1-\alpha_{n})}\right)^{c_{m}-1},\quad
k\in B_{1}.$

If $c_{m}-1\geq 0$, then this is at most 1. If $c_{m}-1\in(-1,0)$, then it is
at most $(1-{k}/{N_{n}(1-\alpha_{n})})^{-1}=1+k/(N_{n}(1-\alpha_{n})-k)\leq
e^{k/(N_{n}(1-\alpha_{n})-k)}$. By assumption
$N_{n}(1-\alpha_{n})-k\to\infty$, and so for any $\varepsilon>0$,

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}\leq(1+\varepsilon)^{k},\quad
k\in B_{1}.$ (4.16)

Next consider $k\in B_{2}$. Set $z:=1-h_{n}^{-1/2}$. Then the bound (2.16)
together with (4.15) yield

$\displaystyle\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}\leq\frac{(1-z)^{-c_{m}}\exp\left\\{h_{n}z\right\\}z^{-(N_{n}-k)}}{[x^{N_{n}}]A(x)}=\mathcal{O}\left(N_{n}\left(\frac{\sqrt{h_{n}}}{N_{n}}\right)^{c_{m}}\exp\\{-\sqrt{h_{n}}\\}z^{k-N_{n}}\right).$
(4.17)

We further get that for any $k\in B_{2}$ that there exists $-h_{n}\leq
t\leq\delta h_{n}$ with $N_{n}-k=h_{n}+t$ so that

$z^{k-N_{n}}\leq\exp\left\\{-h_{n}^{-1/2}(k-N_{n})\right\\}=\exp\left\\{\sqrt{h_{n}}+{t}/{\sqrt{h_{n}}}\right\\}.$

Since $\sqrt{h_{n}}=o(N_{n})$ we get from (4.17)

$\frac{[x^{N_{n}-k}]A(x)}{[x^{N_{n}}]A(x)}=o\left(N_{n}\exp\left\\{{t}/{\sqrt{h_{n}}}\right\\}\right)=o\left(N_{n}\exp\left\\{\delta\sqrt{N_{n}}\right\\}\right)\quad\text{for
all }k\in B_{2}.$

However, since any $k\in B_{2}$ satisfies $k=\Omega(N_{n})$, this bound is
also $\leq(1+\varepsilon)^{k}$ for any $\varepsilon>0$ and $n$ sufficiently
large. Together with (4.16) this finally verifies condition (2.12) of Lemma
2.4 (recall that $\rho_{n}\sim 1$).

We show that the remaining conditions of Lemma 2.4 are satisfied as well. By
applying Lemma 4.3 we obtain that $R(x)$ converges uniformly to

$Q(x):=\exp\Bigg{\\{}-c_{m}x+\sum_{j\geq
2}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}\cdot x^{j}\Bigg{\\}}$

on any interval $[0,a]$ with $a<\rho^{-1}$. Since $\rho^{-1}>1$ we may even
choose $\varepsilon>0$ such that $a=(1+\varepsilon)\overline{\rho}$ and
$1=\overline{\rho}<a<\rho^{-1}$. Then Lemma 4.3 gives us the existence of the
sequence $(d_{n})_{n\in\mathbb{N}_{0}}$ with $\lvert[x^{k}]R(x)\rvert\leq
d_{k}$ and $\sum_{k\geq 1}d_{k}a^{k}<\infty$. Finally $Q(\rho_{n})\sim Q(1)>0$
for all $n\in\mathbb{N}$ so that all conditions of Lemma 2.4 are met and we
deduce from (4.15)

$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\cdot
Q(1)\cdot[x^{N_{n}}]A(x)\sim\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{G({x}_{n},y_{n})}\cdot
Q(1)\cdot\frac{\left(\left(1-a_{n}\right)N_{n}\right)^{c_{m}-1}}{\Gamma(c_{m})}\mathrm{e}^{h_{n}}.$

Lemma 3.4(II) gives us (the asymptotics of) $G({x}_{n},y_{n})$ and we obtain

$\displaystyle\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\sim\frac{c_{m}^{c_{m}}}{(1-a_{n})\Gamma(c_{m})}\cdot\frac{({x}_{n}^{m}y_{n})^{N_{n}}}{N_{n}}\cdot\mathrm{e}^{h_{n}-y_{n}C({x}_{n})}.$

To conclude we observe by appyling Lemma 4.2

$\displaystyle
h_{n}-y_{n}C({x}_{n})=\frac{C(x_{n})}{x_{n}^{m}}-y_{n}C(x_{n})=y_{n}C({x}_{n})\cdot\frac{1-{x}_{n}^{m}y_{n}}{{x}_{n}^{m}y_{n}}=\frac{y_{n}C({x}_{n})}{S_{n}}\sim
c_{m}\frac{a_{n}}{1-a_{n}}.$ (4.18)

This shows the first statement of the lemma. Next we prove the second
statement (3.8). Recall that $K\equiv K_{n}$ is such that $K_{n}\to\infty$ as
$n\to\infty$. From (4.6) we obtain

$\displaystyle\mathrm{Pr}\left[\sum_{j>\ell}jP_{j}=K\right]=\frac{({x}_{n}^{m}y_{n})^{K}}{G^{(\ell)}({x}_{n},y_{n})}\cdot[x^{K}]\frac{1}{(1-x)^{c_{m}}}\cdot
R^{(\ell)}(x).$

Similar to the case $\ell=0$ we want to apply Lemma 2.4 to
$(1-x)^{-c_{m}}R^{(\ell)}(x)$, but this time it is much easier as
$(1-x)^{-c_{m}}$ does not depend on $n$. It is elementary to verify that

$\displaystyle[x^{K}]\frac{1}{(1-x)^{c_{m}}}=\binom{K+c_{m}-1}{K}\sim\frac{K^{c_{m}-1}}{\Gamma(c_{m})},\quad\text{as
}K\to\infty.$ (4.19)

Hence (2.11) is fulfilled with $\rho_{n}=1$ and
$\overline{\rho}:=\limsup\rho_{n}=1$, and the explicit form readily allows us
to establish condition (2.12) as well. Moreover, Lemma 4.3 asserts that
$R^{(\ell)}(x)$ converges to

$Q^{(\ell)}(x):=\exp\left\\{-c_{m}\sum_{1\leq
i\leq\ell}\frac{x^{j}}{j}+\sum_{j>\ell}\frac{C(\rho^{j})-c_{m}\rho^{jm}}{j\rho^{jm}}x^{j}\right\\}$

uniformly on any closed interval in $[0,\rho^{-m})$. Completely analogous to
the case $\ell=0$ all the remaining conditions of Lemma 2.4 are also fulfilled
and we obtain that

$\mathrm{Pr}\left[\sum_{j>\ell}jP_{j}=K\right]\sim\frac{({x}_{n}^{m}y_{n})^{K}}{G^{(\ell)}({x}_{n},y_{n})}\cdot
Q^{(\ell)}(1)\cdot\frac{K^{c_{m}-1}}{\Gamma(c_{m})}.$ (4.20)

By a similar reformulation as in the proof of Lemma 3.4(II) we derive with
Lemma 4.3

$G^{(\ell)}({x}_{n},y_{n})\sim{c_{m}^{-c_{m}}}\cdot\left(\left(1-a_{n}\right)N_{n}\right)^{c_{m}}\cdot
Q^{(\ell)}(1),$

and plugging this into (4.20) finally establishes (3.8). ∎

###  4.5 Proof of Lemma 3.6

In order to prove that $\mathrm{Pr}\left[R\geq
r\mid{\mathcal{P}}_{N_{n}}\right]$ gets exponentially small in $r$ as claimed
in Lemma 3.6 we show as a preparation the following estimate (that is nothing
else than a Chernoff-type bound).

######  Lemma 4.4.

Set
$\Omega_{n}:=\\{(p_{1},\dots,p_{N_{n}})\in\mathbb{N}_{0}^{N_{n}}:p_{1}+2p_{2}\cdots+N_{n}p_{N_{n}}=N_{n}\\}$
and let $\lambda>0$ be such that $0<\lambda<-\ln\rho/2$. Then for
$(\tau_{j})_{j\geq 2}:=(C({x}_{n}^{j}\mathrm{e}^{\lambda
j})y_{n}^{j}/\mathrm{e}^{\lambda jm})_{j\geq 2}$

$\mathrm{Pr}\left[R\geq
r\mid{\mathcal{P}}_{N_{n}}\right]\leq\mathrm{e}^{-\lambda
r}\cdot\mathrm{e}^{-\sum_{2\leq j\leq
N_{n}}{C({x}_{n}^{j})y_{n}^{j}}/{j}}\cdot\sum_{\mathrm{p}\in\Omega_{n}}\frac{\mathrm{Pr}\left[P_{1}=p_{1}\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\cdot\prod_{2\leq
j\leq N_{n}}\frac{(\tau_{j}/j)^{p_{j}}}{p_{j}!},\qquad r\in\mathbb{N}.$

###### Proof.

The choice of $\lambda$ guarantees that
$\mathrm{e}^{j\lambda}{x}_{n}^{j}<\rho$ for all $j\geq 2$. Hence

$\mathbb{E}\left[\mathrm{e}^{\lambda j(C_{j,i}-m)}\right]=\mathrm{e}^{-\lambda
jm}\frac{\sum_{k\geq 1}c_{k}({x}_{n}^{j}\mathrm{e}^{\lambda
j})^{k}}{C({x}_{n}^{j})}=\frac{C({x}_{n}^{j}\mathrm{e}^{\lambda
j})}{C({x}_{n}^{j})\mathrm{e}^{\lambda jm}},\qquad i\geq 1,j\geq 2.$

Then by Bayes and the independence of the $P_{j}$’s

$\begin{split}\mathrm{Pr}\left[R\geq
r\mid{\mathcal{P}}_{N_{n}}\right]&=\sum_{\mathrm{p}\in\Omega_{n}}\mathrm{Pr}\left[R\geq
r\biggm{|}\bigcap_{1\leq j\leq
N}\\{P_{j}=p_{j}\\}\right]\mathrm{Pr}\left[\bigcap_{1\leq j\leq
N}\\{P_{j}=p_{j}\\}\biggm{|}{\mathcal{P}}_{N_{n}}\right]\\\
&=\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]^{-1}\cdot\sum_{\mathrm{p}\in\Omega_{n}}\mathrm{Pr}\left[\sum_{j\geq
2}j\sum_{1\leq i\leq p_{j}}(C_{j,i}-m)\geq r\right]\prod_{1\leq j\leq
N_{n}}\mathrm{Pr}\left[P_{j}=p_{j}\right].\end{split}$ (4.21)

With Markov’s inequality and the independence of the $(C_{j,i})_{j,i\geq 1}$
and $(P_{j})_{j\geq 1}$ we obtain

$\mathrm{Pr}\left[\sum_{j\geq 2}j\sum_{1\leq i\leq p_{j}}(C_{j,i}-m)\geq
r\right]\leq\mathrm{e}^{-\lambda r}\prod_{2\leq j\leq
N_{n}}\mathbb{E}\left[\mathrm{e}^{\lambda
j(C_{j,i}-m)}\right]^{p_{j}}=\mathrm{e}^{-\lambda r}\prod_{2\leq j\leq
N_{n}}\left(\frac{C({x}_{n}^{j}\mathrm{e}^{\lambda
j})}{C({x}_{n}^{j})\mathrm{e}^{\lambda jm}}\right)^{p_{j}}.$

By plugging this into (4.21) and using that
$P_{j}\sim\textrm{Po}(C(x_{n}^{j})y_{n}^{j}/j)$ we obtain the claimed
statement. ∎

###### Proof of Lemma 3.6 in case $(I)$.

By applying Lemma 4.4 and using that the Poisson distribution is maximised at
its mean, so that
$\mathrm{Pr}\left[P_{1}=p_{1}\right]/\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]\leq
1$, we obtain for some $\lambda>0$

$\displaystyle\mathrm{Pr}\left[R\geq
r\mid{\mathcal{P}}_{N_{n}}\right]\leq\mathrm{e}^{-\lambda
r}\cdot\sum_{\mathrm{p}\in\Omega_{n}}\prod_{2\leq j\leq
N_{n}}\frac{(\tau_{j}/j)^{p_{j}}}{p_{j}!}.$

Lemma 2.7 yields that for some $A>0$

$\tau_{j}\leq c_{m}({x}_{n}^{m}y_{n})^{j}(1+A{x}_{n}^{j}\mathrm{e}^{\lambda
j}),\quad j\geq 2.$

Lemma 4.1 states that there is a $0<\varepsilon<1$ such that
${x}_{n}^{m}y_{n}<1-\varepsilon$ for all sufficiently large $n$. We deduce
that $\exp\\{\sum_{2\leq j\leq N_{n}}\tau_{j}/j\\}=\exp\\{{\cal O}(\sum_{j\geq
2}(1-\varepsilon)^{j}/j)\\}$ is bounded. Consequently, setting $H=\sum_{2\leq
j\leq N_{n}}jH_{j}$ with $H_{j}\sim\mathrm{Po}\left(\tau_{j}/j\right)$
independent, we obtain for some (other) $A>0$

$\mathrm{Pr}\left[R\geq r\mid{\mathcal{P}}_{N_{n}}\right]\leq
A\cdot\mathrm{e}^{-\lambda r}\cdot\sum_{0\leq p\leq
N_{n}}\mathrm{Pr}\left[H=N_{n}-p\right]\leq A\cdot\mathrm{e}^{-\lambda r}.$

∎

###### Proof of Lemma 3.6 in case $(II)$.

Our starting point is Lemma 4.4 so that

$\mathrm{Pr}\left[R\geq
r\mid{\mathcal{P}}_{N_{n}}\right]\leq\mathrm{e}^{-\lambda
r}\cdot\exp\left\\{-\sum_{2\leq j\leq
N_{n}}\frac{C({x}_{n}^{j})y_{n}^{j}}{j}\right\\}\sum_{\mathrm{p}\in\Omega_{n}}\frac{\mathrm{Pr}\left[P_{1}=p_{1}\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\cdot\sum_{2\leq
j\leq N_{n}}\frac{(\tau_{j}/j)^{p_{j}}}{p_{j}!}$

for $0<\lambda<-\ln\rho/2$. Using Lemmas 4.2 and 2.7 we obtain the estimate

$\exp\left\\{\sum_{j\geq
2}\frac{C({x}_{n}^{j})y_{n}^{j}}{j}\right\\}=\frac{1}{(1-{x}_{n}^{m}y_{n})^{c_{m}}}\exp\left\\{-c_{m}{x}_{n}^{m}y_{n}+\sum_{j\geq
2}\frac{C({x}_{n}^{j})y_{n}^{j}-c_{m}{x}_{n}^{jm}y_{n}^{j}}{j}\right\\}={\cal
O}(N_{n}^{c_{m}}).$

Next let $H_{j}\sim\mathrm{Po}\left(\tau_{j}/j\right)$ be independent random
variables for $j\geq 2$ and set $H:=\sum_{2\leq j\leq N_{n}}jH_{j}$.
Abbreviate $\Upsilon:=\exp\\{\sum_{2\leq j\leq N_{n}}\tau_{j}/j\\}$. We obtain
for some $A_{1}>0$

$\displaystyle\mathrm{Pr}\left[R=r\mid{\mathcal{P}}_{N_{n}}\right]\leq
A_{1}\cdot\mathrm{e}^{-\lambda r}\cdot N^{-c_{m}}\cdot\Upsilon\cdot\sum_{0\leq
p\leq
N_{n}}\frac{\mathrm{Pr}\left[P_{1}=p\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\mathrm{Pr}\left[H=N_{n}-p\right].$
(4.22)

Since $(H_{j})_{j\geq 2}$ are independent

$\displaystyle\mathrm{Pr}\left[H=N_{n}-p\right]=\Upsilon^{-1}[x^{N_{n}-p}]\exp\Big{\\{}\sum_{j\geq
2}{\tau_{j}}x^{j}/j\Big{\\}}.$ (4.23)

In the last expression we actually have to restrict to $2\leq j\leq N_{n}$;
however, for all $0\leq M\leq N_{n}$, $[x^{M}]\exp\\{\sum_{2\leq j\leq
N_{n}}\tau_{j}x^{j}/j\\}=[x^{M}]\exp\\{\sum_{j\geq 2}\tau_{j}x^{j}/j\\}$. Then

$\displaystyle\exp\Big{\\{}\sum_{j\geq 2}\tau_{j}x^{j}/j\Big{\\}}$
$\displaystyle=\frac{1}{(1-{x}_{n}^{m}y_{n}x)^{c_{m}}}\cdot\exp\left\\{-c_{m}{x}_{n}^{m}y_{n}x+\sum_{j\geq
2}(\tau_{j}-c_{m}({x}_{n}^{m}y_{n})^{j})\frac{x^{j}}{j}\right\\}$

and so, for any $0\leq M\leq N_{n}$

$\displaystyle[x^{M}]\exp\Big{\\{}\sum_{j\geq 2}\tau_{j}x^{j}/j\Big{\\}}$
$\displaystyle=({x}_{n}^{m}y_{n})^{M}\cdot[x^{M}]\frac{1}{(1-x)^{c_{m}}}\cdot\exp\left\\{-c_{m}x+\sum_{j\geq
2}\left(\frac{C({x}_{n}^{j}\mathrm{e}^{\lambda
j})}{{x}_{n}^{jm}\mathrm{e}^{\lambda
jm}}-c_{m}\right)\frac{x^{j}}{j}\right\\}.$

With Lemma 2.7 we get a bound which holds uniformly for some $A>0$ and all
$j\geq 2$

$0<a_{n,j}:=\frac{C({x}_{n}^{j}\mathrm{e}^{\lambda
j})}{{x}_{n}^{jm}\mathrm{e}^{\lambda
jm}}-c_{m}\leq\frac{C(\rho^{j}\mathrm{e}^{\lambda
j})}{\rho^{jm}\mathrm{e}^{\lambda jm}}-c_{m}\leq
A(\rho\mathrm{e}^{\lambda})^{j}=:a_{j}.$

Using the fact that for a power series $f$ with non-negative coefficients the
coefficients of $\mathrm{e}^{f(x)}$ can get only larger if we make the
coefficients of $f$ larger we get

$\displaystyle({x}_{n}^{m}y_{n})^{-M}[x^{M}]\exp\Big{\\{}\sum_{j\geq
2}\tau_{j}x^{j}/j\Big{\\}}$
$\displaystyle\leq\sum_{m_{1}+m_{2}+m_{3}=M}[x^{m_{1}}]\frac{1}{(1-x)^{c_{m}}}\cdot\lvert[x^{m_{2}}]\mathrm{e}^{-c_{m}x}\rvert\cdot\bigg{\lvert}[x^{m_{3}}]\exp\Big{\\{}\sum_{j\geq
2}a_{n,j}x^{j}/j\Big{\\}}\bigg{\rvert}$
$\displaystyle\leq\sum_{m_{1}+m_{2}+m_{3}=M}[x^{m_{1}}]\frac{1}{(1-x)^{c_{m}}}\cdot[x^{m_{2}}]\mathrm{e}^{c_{m}x}\cdot[x^{m_{3}}]\exp\Big{\\{}\sum_{j\geq
2}a_{j}x^{j}/j\Big{\\}}$
$\displaystyle=[x^{M}]\frac{1}{(1-x)^{c_{m}}}\exp\Big{\\{}c_{m}x+\sum_{j\geq
2}a_{j}x^{j}/j\Big{\\}}=:[x^{M}]A(x)\tilde{R}(x).$

Inserting this into (4.23) we obtain
$\mathrm{Pr}\left[H=N_{n}-p\right]\leq\Upsilon^{-1}(x_{n}^{m}y_{n})^{N_{n}-p}[x^{N_{n}-p}]A(x)\tilde{R}(x)$.
The advantage of this estimate is that $\tilde{R}$ does not depend on $n$
anymore. We have that, compare to (4.19), $[x^{n}]A(x)\sim
n^{c_{m}-1}/\Gamma(c_{m})$ implying that $[x^{n-1}]A(x)/[x^{n}]A(x)\sim 1$. In
addition, $\tilde{R}(1)<\infty$, as the radius of convergence of $\tilde{R}$
is at least $(\rho\mathrm{e}^{\lambda})^{-1}>1$. With Lemma 2.3 we
consequently obtain
$[x^{n}]A(x)\tilde{R}(x)\sim\tilde{R}(1)n^{c_{m}-1}/\Gamma(c_{m})$. This, on
the other hand, implies that we can find a $A_{2}>0$ such that uniformly in
$n$ and $0\leq p<N_{n}$

$[x^{N_{n}-p}]A(x)\tilde{R}(x)\leq A_{2}(N_{n}-p)^{c_{m}-1}.$

All in all, noting that $({x}_{n}^{m}y_{n})^{N_{n}-p}\leq 1$, we get uniformly
in $n$ and $0\leq p<N_{n}$

$\displaystyle\mathrm{Pr}\left[H=N_{n}-p\right]=\mathcal{O}\left(\Upsilon^{-1}(N_{n}-p)^{c_{m}-1}\right).$

For the case $p=N_{n}$ note that the probability that $H$ equals $0$ is
$\Upsilon^{-1}$. Putting these pieces together into (4.22) we obtain that

$\displaystyle\mathrm{Pr}\left[R\geq r\mid{\mathcal{P}}_{N_{n}}\right]$
$\displaystyle=\mathcal{O}\left(\mathrm{e}^{-\lambda r}\cdot
N^{-c_{m}}\cdot\left(\sum_{0\leq
p<N_{n}}\frac{\mathrm{Pr}\left[P_{1}=p\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\left(N_{n}-p\right)^{c_{m}-1}+\frac{\mathrm{Pr}\left[P_{1}=N_{n}\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\right)\right).$

Since according to Lemma 3.5(II) we have that
$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]=\Theta\big{(}({x}_{n}^{m}y_{n})^{N_{n}}/N_{n}\big{)}$
and ${x}_{n}^{m}y_{n}=1-\Theta(1/N_{n})$ due to Lemma 4.2, we have
$\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]=\Theta(1/N_{n})$. Further Lemma
4.2 yields that $\limsup y_{n}C({x}_{n})/N_{n}\leq\limsup\lambda_{n}^{-1}<1$
so that we can estimate
$\mathrm{Pr}\left[P_{1}=N_{n}\right]=\exp\left\\{-\Omega(N_{n})\right\\}$ by
(2.9). Hence

$N^{-c_{m}}\mathrm{Pr}\left[P_{1}=N_{n}\right]/\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]=\mathcal{O}\left(N_{n}^{1-c_{m}}\mathrm{e}^{-\Omega(N_{n})}\right)=o(1).$

With the estimates for $\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]$ we
further obtain

$N_{n}^{-c_{m}}\cdot\sum_{0\leq
p<N_{n}}\frac{\mathrm{Pr}\left[P_{1}=p\right]}{\mathrm{Pr}\left[{\mathcal{P}}_{N_{n}}\right]}\left(N_{n}-p\right)^{c_{m}-1}=\mathcal{O}\left(\sum_{0\leq
p<N_{n}}\mathrm{Pr}\left[P_{1}=p\right]\left(1-\frac{p}{N_{n}}\right)^{c_{m}-1}\right).$

To finish the proof we show that the latter expression is
$\mathcal{O}\left(1\right)$. This is clear for $c_{m}\geq 1$. If $0<c_{m}<1$
we note that there is some $\delta>0$ such that
$(1+\delta)\limsup\mathbb{E}\left[P_{1}\right]/N_{n}=(1+\delta)\limsup
y_{n}C({x}_{n})/N_{n}\leq(1+\delta)\lambda_{n}^{-1}<1$ due to Lemma 4.2. Then
$\sum_{0\leq p\leq
N_{n}/(1+\delta)}\mathrm{Pr}\left[P_{1}=p\right](1-p/N_{n})^{c_{m}-1}\leq(1+\delta^{-1})^{1-c_{m}}$.
For $N/(1+\delta)<p<N_{n}$, on the other hand, we get that
$\sum_{N_{n}/(1+\delta)<p<N_{n}}\mathrm{Pr}\left[P_{1}=p\right](1-p/N_{n})^{c_{m}-1}\leq
N_{n}^{1-c_{m}}\mathrm{Pr}\left[P_{1}>N_{n}/(1+\delta)\right]$. This is
$\mathrm{e}^{-\Omega(N_{n})}$ by (2.9) and the proof is completed. ∎

###  4.6 Proof of Lemma 3.7

This entire section is devoted to the proof of Lemma 3.7. First of all note
that the probability generating function of $C_{1,1}$ is given by
$H(x)=C({x}_{n}x)/C({x}_{n})$, that is,
$\mathrm{Pr}\left[C_{1,1}=k\right]=[x^{k}]H(x)$ for $k\in\mathbb{N}$. Define
$K_{p}:=\sum_{1\leq i\leq p}C_{1,i}$ and
$\nu:={x}_{n}C^{\prime}({x}_{n})/C({x}_{n})$. Then

$\mathrm{Pr}\left[L_{p}=\mu_{p}+t\sigma_{p}\right]=\mathrm{Pr}\left[K_{p}=p\nu+t\sigma_{p}\right]=[x^{p\nu+t\sigma_{p}}]H(x)^{p}.$

The tool of our choice for tackling this problem is the saddle-point method.
Therefore we need appropriate bounds for $H$ in $\mathbb{C}$ on a circle
centred at the origin with radius close to $\rho$; the next lemma shows a
rather diverse picture. For future reference and since we will need this
often, we apply Theorem A.4 to obtain that

$\displaystyle\sum_{k\geq 1}h(k)k^{\beta-1}\mathrm{e}^{-\eta
k}\sim\Gamma(\beta)h(\eta^{-1})\eta^{-\beta}\quad\beta>0,\text{ as }\eta\to
0.$ (4.24)

######  Lemma 4.5.

Let $\alpha>1,0<\rho<1$. Then there exist $\eta_{0}>0,c<1,A>0$ such that the
following is true. Let $0<\eta<\eta_{0}$ and set $G(x):=C(\omega
x)/C(\omega)$, where $\omega=\rho\mathrm{e}^{-\eta}$. Then

$\displaystyle\lvert G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})\rvert\leq
1-\frac{\alpha}{2}\,\left(\frac{\theta}{\eta}\right)^{2}\quad\text{for
any}\quad\lvert\theta\rvert\leq{\eta}/(24\alpha^{2}).$ (4.25)

Moreover,

$\lvert G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})\rvert\leq c\quad\text{for
any}\quad{\eta}/(24\alpha^{2})\leq\lvert\theta\rvert\leq\pi$ (4.26)

and

$\lvert G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})\rvert\leq
A\cdot\max\left\\{{\eta}/{\lvert\theta\rvert},\eta\right\\}\quad\text{for
any}\quad\eta\leq\lvert\theta\rvert\leq\pi.$ (4.27)

###### Proof.

We start with showing the first bound. Recall the basic inequalities

$\cos(x)\leq
1-{x^{2}}/{2}+{x^{4}}/{24}\quad\text{and}\quad\sin(x)\leq|x|,\qquad
x\in\mathbb{R},$

that we will use more than once in the proof. Let $\delta_{1}\in(0,1)$. Let
$R$ denote the real part of $G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})$.
Then, using (4.24), for $\eta>0$ sufficiently small,

$R=\frac{1}{C(\omega)}\sum_{k\geq 1}c_{k}\rho^{k}\mathrm{e}^{-\eta
k}\cos(\theta k)\leq
1-(1-\delta_{1})\frac{(\alpha+1)\alpha}{2}\left(\frac{\theta}{\eta}\right)^{2}+\frac{(\alpha+3)(\alpha+2)(\alpha+1)\alpha}{12}\left(\frac{\theta}{\eta}\right)^{4}.$

Further, if
$\lvert\theta\rvert\leq((\alpha+3)(\alpha+2))^{-1/2}\sqrt{\delta_{1}}\eta$,

$R\leq
1-(1-2\delta_{1})\frac{(\alpha+1)\alpha}{2}\left(\frac{\theta}{\eta}\right)^{2}.$

Moreover, consider the imaginary part $I$ of $G(\mathrm{e}^{\mathrm{i}\mkern
1.0mu\theta})$. Then we obtain with (4.24) that for $\eta>0$ sufficiently
small

$I^{2}=\frac{1}{C(\omega)^{2}}\left(\sum_{k\geq
1}c_{k}\rho^{k}\mathrm{e}^{-\eta k}\sin(\theta
k)\right)^{2}\leq(1+\delta_{1})\alpha^{2}\cdot\left(\frac{\theta}{\eta}\right)^{2}.$

Combining these bounds yields for $\delta_{1}>0$ and
$|\theta|\leq((\alpha+3)(\alpha+2))^{-1/2}\sqrt{\delta_{1}}\eta$ that

$|G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})|^{2}=R^{2}+I^{2}\leq
1-\Big{(}(1-2\delta_{1})\alpha-3\delta_{1}\alpha^{2}\Big{)}\left(\frac{\theta}{\eta}\right)^{2}+(\alpha+1)^{2}\alpha^{2}\left(\frac{\theta}{\eta}\right)^{4}.$

Then, as
$|\theta|\leq((\alpha+3)(\alpha+2))^{-1/2}\sqrt{\delta_{1}}\eta\leq\sqrt{\delta_{1}}\eta/(\alpha+1)$,
we obtain

$|G(\mathrm{e}^{\mathrm{i}\mkern 1.0mu\theta})|^{2}\leq
1-\Big{(}(1-2\delta_{1})\alpha-4\delta_{1}\alpha^{2}\Big{)}\left(\frac{\theta}{\eta}\right)^{2}.$