%% Pagal Roberto + taisau D(z) % EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Local probabilities for random permutations without long cycles} %% Čia failas, kuris 2014 m. spalio 16 d. buvo elektroniškai įteiktas Electr. J. Comb. % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Eugenijus Manstavi\v cius\\ \small Department of Mathematics and Informatics\\[-0.8ex] \small Vilnius University\\[-0.8ex] \small Vilnius, Lithuania\\ \small\tt eugenijus.manstavicius@mif.vu.lt\\ \and Robertas Petuchovas\\ \small Department of Mathematics and Informatics\\[-0.8ex] \small Vilnius University\\[-0.8ex] \small Vilnius, Lithuania\\ \small\tt robertas.petuchovas@mif.vu.lt} % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{October 16, 2014}{??, 201?}\\ \small Mathematics Subject Classifications: 60C05, 60F10, 05A16} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We explore the probability $\nu(n,r)$ that a permutation sampled from the symmetric group of order $n!$ uniformly at random has no cycles of length exceeding $r$, where $1\leq r\leq n$ and $n\to\infty$. Asymptotic formulas valid in specified regions for the ratio $n/r$ are obtained using the saddle-point method combined with ideas originated in analytic number theory. % keywords are optional \bigskip\noindent \textbf{Keywords:} Symmetric group; cycle structure; short cycles; saddle-point method \end{abstract} \def\E{\mathbf{E}} \def\C{\mathbf{C}} \def\D{\mathbf{D}} \def\N{\mathbf{N}} \def\R{\mathbf{R}} \def\S{\mathbf{S}_n} \def\Z{\mathbf{Z}} \def\k{\kappa} \def\e{\varepsilon} \def\n{$n\to\infty$} \def\cF{\mathcal F} \def\re{{\rm e}} \def\rO{{\rm O}} \def\ro{{\rm o}} \def\rd{{\rm d}} \def\s{\smallskip} \def\b{\bigskip} \section{Introduction} Enumeration of decomposable structures missing large components started in 1930 with a paper by K. Dickman \cite{Dickman} dealing with natural numbers composed of small prime factors. Two decades later, in a series of works, N.G. de Bruijn extended this to a deep analytical theory. A survey \cite{Moree} gives a broad historical account. In the 1980's, A. Hildebrand, G. Tenenbaum and other mathematicians again advanced in the same direction. Their results are well exposed in a book \cite{GT} and in more recent papers. By analogy, a similar theory was carried out for polynomials over a finite field (see, for example, \cite{Odlyzko}, \cite{GarePana}) and generalized to the so-called additive arithmetical semigroups (see \cite{Warlimont}, \cite{EM-Pal92}, \cite{EM-LMJ92}). A survey \cite{Granv} discusses the analogy between the theories. In no way, the list does not pretend to be complete, however, it has influenced the present paper devoted to permutations. So far, the results on this particular class of structures do not reach the level of research achieved for natural numbers. We focus only on permutations comprising the symmetric group $\S$ and seek asymptotic formulas for the probability $\nu(n,r)$ that a permutation sampled uniformly at random has no cycles of length exceeding $r$, where $1\leq r\leq n$, $r\in \N$, and $n\to\infty$. The goal is to cover the whole range for the parameter $r$. Let us start from an exact formula. Denote $\N_0=\N\cup\{0\}$, $\ell_r(\bar s)=1s_1+\cdots+rs_r$, $\ell(\bar s)=\ell_n(\bar s)$, where $\bar s=(s_1,\dots, s_n)\in\N_0^n$. If $k_j(\sigma)$ equals the number of cycles of length $j$ in a permutation $\sigma\in\S$ and $\bar k(\sigma):= \big(k_1(\sigma),\dots,k_n(\sigma)\big)$ is the cyclic structure vector, then (see, for example, (2.6) on page 48 of \cite{ABT}) \[ \big|\{\sigma\in\S:\; \bar k(\sigma)=\bar s\}\big|={\mathbf 1}\{\ell(\bar s)=n\} n!\prod_{j=1}^n\frac{1}{j^{s_j} s_j!}. \] Hence \begin{equation}\label{exact} \nu(n,r)=\frac{1}{n!}\big|\{\sigma\in\S:\; k_j(\sigma)=0\,\ \forall j\in\overline{r+1, n}\}\big|= \sum_{\ell_r(\bar s)=n}\prod_{j=1}^r\frac{1}{j^{s_j} s_j!}, \end{equation} where the summation is over the vectors $\bar s\in\N_0^r$ with $\ell_r(\bar s)=n$. The formula can be rewritten in terms of independent Poisson random variables $Z_j$, $1\leq j\leq n$, such that $\E Z_j=1/j$. Namely, \begin{equation} \nu(n,r)= \exp\bigg\{\sum_{j^=1}^r\frac{1}{j}\bigg\} P\big(\ell_r(\bar Z)=n\big), \label{P-ell} \end{equation} where $\bar Z:=(Z_1,\dots, Z_n)$. There are two trivial cases $ \nu(n,1)=1/n!$ and $\nu(n,n)=1$. As the referee has kindly informed us, the first few values of $\nu(n,r)$ are in the \textit{Online Encyclopedia of Integer Sequences}: \begin{align*} \nu(n,2)n!&=A000085,\quad \nu(n,3)n!=A057693,\quad \nu(n,4)n!=A070945,\\ & \nu(n,5)n!=A070946,\quad \nu(n,5)n!=A070947. \end{align*} In it, a great attention is paid to $\nu(n,2)n!$ which equals the number of involutions in $\S$. In particular, it is indicated that $\nu(n,2)n!$ can be expressed via a value of the Hermite polynomial $H_n(x)$ at a point on the imaginary axis of a complex plane. Asymptotic analysis of $\nu(n,r)$ gives more information than~\eqref{exact} if parameters are large. For start, we have Cauchy's integral representation \begin{equation} \nu(n,r)={1\over 2\pi i}\int_{|z|=\alpha} \exp\left\{\sum_{j=1}^r\frac{z^j}{j}\right\} {dz\over z^{n+1}}, \label{C-integr} \end{equation} where $\alpha>0$. An idea of applying the saddle-point method might be taken from the pioneering work \cite{Pl-Ro29} concerning $H_n(x)$ if $x\in\R$. Indeed, this method was used by L. Moser and M. Wyman \cite{MoWy55} to prove that \begin{equation} \nu(n,2)= \frac{1}{\sqrt{4\pi n}}\exp\Big\{-\frac{n\log n}{2}+\frac{n}{2}+n^{1/2}- \frac{1}{4}\Big\}\big(1+o(1)\big).\label{nun2} \end{equation} By another approach, the relation was established earlier by S.\ Chowla, I.N.\ Herstein and W.K.\ Moore~\cite{ChHeMo1951}. H.~Wilf included a detailed proof of (\ref{nun2}) into Chapter 5 of his book \cite{Wilf}. However, Exercise 8 on pages 190-191 in it gives an erroneous expression for $r=3$. Actually, \begin{equation} \nu(n,3)=\frac{1}{\sqrt{6\pi n}} \exp\Big\{-\frac{n\log n}{3}+\frac{n}{3} +\frac{1}{2} n^{2/3} +\frac{5}{6} n^{1/3}-\frac{5}{18}\Big\} \big(1+o(1)\big).\label{nun3} \end{equation} As we have been able to check, the last formula firstly appears in A.N. Timashov's paper \cite{Timash}. It gives a reference to V.N.~Sachkov's work \cite{Sachkov} where formulas (23) and (24) for $\nu(n,r)$ with $r$ fixed are presented. However, given without a proof the formulas contain inaccuracies; they go in contrast to (\ref{nun3}) and even to (\ref{nun2}). A year later, M. Lugo \cite{Lugo} also gave (\ref{nun3}) leaving for a reader other cases of $\nu(n,r)$. A detailed proof of an asymptotic formula for $\nu(n,r)n!$ if $r$ is fixed was recently presented by T. Amdeberhan and V.H. Moll \cite{AmdMoll}. The first our result improves on their Theorem 8.1 providing the error estimate and extending the range of the parameter $r$. Let $\Gamma(z)$ be the Euler gamma-function, where $z\in\C$. Avoiding numerous brackets, instead of $O(\cdot)$, we will use a complex quantity $B$, not the same at different places but always bounded by an absolute constant. Otherwise, stressing dependence on a parameter $v$ in an estimate, we will write $O_v(\cdot)$ with the extra index. \begin{theorem}\label{Theorem 1} If $ 1\leq r\leq \log n$, then \[ \nu(n,r)= \frac{1}{\sqrt{2\pi nr}}\exp\bigg\{-\frac{n\log n}{r}+\frac{n}{r}+\sum_{N=1}^r d_{rN} n^{(r-N)/r}\bigg\} \big(1+Bn^{-1/r}\big). \] Here \[ d_{r,r}=-\frac{1}{r}\sum_{j=2}^r\frac{1}{j} \] and \[ d_{rN}= \frac{\Gamma(N+N/r)}{(r-N)\Gamma(N+1) \Gamma(1+N/r)} \] if $1\leq N\leq r-1$. \end{theorem} If $r=2$ and 3, the obtained asymptotic formula sharpens (\ref{nun2}) and (\ref{nun3}). To prove Theorem~\ref{Theorem 1}, we also apply the saddle-point method for the Cauchy integral (\ref{C-integr}) with $\alpha=x:=x(n/r)$, where the function $x(u):=x_r(u)$ is the unique positive solution to the equation \begin{equation}\label{saddle} \sum_{j=1}^rx(u)^j=ur, \quad u\geq 1. \end{equation} The methodology has been elaborated by W.K.~Hayman \cite{Hayman} and later by B.~Harris and L.~Schoenfeld \cite{Har+Schon68}. The latter succeeded in obtaining further asymptotic terms and, in particular, showed that \begin{equation} \nu(n,r)=\frac{D(x)}{\sqrt{2\pi \lambda(x)}}\left(1+O_r\Big(\frac{1}{n}\Big)\right), \label{1Pnr} \end{equation} for an arbitrary bounded $r$. Here $x=x(n/r)$ and \[ D(z):= z^{-n} \exp\left\{\sum_{j=1}^r\frac{z^j}{j}\right\}, \qquad \lambda(z):=\sum_{j=1}^r jz^j. \] Actually, we owe to E. Schmutz whose Theorem 1 and the facts presented below it in \cite{Schmutz88} clarify the use of the general and fairly complicated expansion given in \cite{Har+Schon68}. A.N.~Timashov \cite{Timash} mentions a Sachkov's result from 1986, extending formula (\ref{1Pnr}) for $r=o(\log n)$. Unfortunately, we failed to find a relevant paper. The above mentioned results deal with the case when the ratio $u=n/r$ is large. Beside this there exists a vast literature dealing with the case when $u$ is small. Such a case is related to the limit distribution of the longest cycle length (say, $L_n(\sigma)$) and other statistics of $\sigma\in\S$. V.L.~Goncharov's result \cite{Gonch44} from 1944 shows that \begin{eqnarray}\label{goncharov} \nu(n, r)= \frac{1}{n!}\big|\{\sigma\in \S:\; L_n(\sigma)\leq n/u\}\big|=\rho(u)+o(1) \end{eqnarray} uniformly in $u=n/r\geq1$. Here $\rho(u)$ is the Dickman function defined as the continuous solution to the difference-differential equation \[ u\rho'(u)+\rho(u-1)=0 \] with the initial condition $\rho(u)=1$ for $0\leq u\leq 1$. The challenge to estimate the remainder term in \eqref{goncharov} was taken up by X. Gourdon in his notable thesis \cite{Gourd-th}. Formula (12) on page 131 in it gives a result \[ \nu(n, r)=\rho(n/r)+Br^{-1}\log n \] for $n/r\geq1$. In addition, an $l$-term asymptotic expansion of $\nu(n,r)$ with a remainder term $O_l\big( n^{-l+1/2}\log n\big)$ for an arbitrary $l\in\N$ is obtained in Theorem 2 on page 207. Recalling that \[ \rho(u)=\exp\bigg\{-u\Big(\log (u \log (u+2)) -1 +B\frac{\log\log (u+2)}{\log (u+2)}\Big)\bigg\}, \quad u\geq 1, \] (see, for example, (2.6) in \cite{AH+GT}), one can verify that the error terms in either of Gourdon's asymptotic formulas swallow the main term $\rho(u)$ if $u\geq \log n$. Therefore, it is better to estimate the relative error term. Theorem 4.13 on page 91 in \cite{ABT}, applied for permutations, yields \begin{equation}\label{relative asymptotic} \nu(n, r)=\rho(\beta)\big(1+o(1)\big) \end{equation} if $n/r\to \beta\in(0,\infty)$. As a byproduct of enumeration of corresponding elements in an additive semigroup, the last relation (extended even to a larger region for $n/r$) has appeared in the first author's paper \cite{EM-LMJ92}. The result is in Theorem \ref{thm2} below. Here we present a detailed and direct proof instead of sketchy and indirect one. The next result is a generalization of Theorem~\ref{Theorem 1} in a wider region. \begin{theorem}\label{thm1} As above, let $x=x(n/r)$. Then \begin{equation} \nu(n,r)=\frac{D(x)}{\sqrt{2\pi \lambda(x)}}\left(1+\frac{Br}{n}\right)\label{fullx} \end{equation} provided that $ 1\leq r\leq c n(\log n)^{-1}(\log\log n)^{-2}$, where $c=1/(12\pi^2 \re)$ and $n\geq 4$. \end{theorem} Theorem~\ref{thm1} is proved by the classic saddle-point method described, for example, on page 551 in~\cite{Fl-Sed}. The upper bound of the parameter $r$ indicates the limitation of the approach. For larger $r$, it is difficult to estimate the integrand in (\ref{C-integr}) outside a vicinity of the saddle-point. Combined with the Lagrange-B\"{u}rmann inversion, the result is useful in obtaining explicit approximations of $\nu(n,r)$ in specific regions for $n/r$. In this way, we derive Theorem \ref{Theorem 1}. The asymptotic analysis of the saddle-point is not simple. We obtain in Lemma \ref{lema11} of Section 5 that \begin{align} x&= n^{1/r}-\frac{1}{r} -\sum_{N=2}^{r}\frac{ \Gamma(N+(N-1)/r)}{(N-1)\Gamma(N+1)\Gamma((N-1)/r)} n^{-(N-1)/r} \nonumber\\ &\quad + \frac{1}{r}n^{-1+1/r}+\frac{B}{n} \label{xnr-Skleid} \end{align} if $1\leq r\leq \log n$. This implies that $x\to\infty$ if $r=o(\log n)$. On the other hand, it is easily seen from the definition that $x\to 1$ if $\log n=o(r)$. In this case, a different approximation of $x$ is established. It involves the implicit function $\xi=\xi(u)$ being a unique positive solution to the equation \begin{equation} \re^\xi=1+u\xi \label{alpha} \end{equation} for $u> 1$. We have from Lemma \ref{4lema} that \[ x=x(u)= \exp\Big\{\frac{\xi}{r}\Big\}\Big(1+\frac{B\log (u+1)}{r^2}\Big) \] if $1\leq u\leq \re^r$ and $\xi(1):=0$. This helps in the analysis of $D(x)$ and $\lambda(x)$. Exploiting an asymptotic formula for $\rho(u)$ which also involves $\xi(u)$ (see Lemma \ref{rho-lema} below) we obtain the following result where $x$ is eliminated. \begin{corollary} \label{1cor} If $n\geq 4$, $u=n/r$, and \[ n^{1/3}(\log n)^{2/3}\leq r\leq cn(\log n)^{-1}(\log\log n)^{-2}, \] then \begin{equation} \nu(n,r)= \rho(u) \exp\Big\{\frac{u\xi(u)}{2r}\Big\}\bigg(1+\frac{Bu\log^2(u+1)}{r^2}+\frac{B}{u}\bigg). \label{nu-cor1} \end{equation} \end{corollary} Thus, we have discovered that an extra exponential factor next to the Dickman function is necessary if $r=o\big((n\log n)^{1/2}\big)$. The next result adds some precision to Corollary \ref{1cor} for larger $r$ and helps to validate formula \eqref{fullx} in a whole region $1\leq r\leq n$. \begin{theorem}\label{thm2} If $1\leq \sqrt{n\log n}\leq r\leq n$ and $u=n/r$, then \[ \nu(n,r)=\rho(u)\bigg(1+\frac{Bu\log(u+1)}{r}\bigg). \] \end{theorem} As it is seen from Corollary 3, the order of the error estimate in Theorem \ref{thm2} is precise. To prove the theorem, we approximate the Cauchy integral in (\ref{C-integr}) by the inverse Laplace transform of a function related to Dickman's one. \begin{corollary}\label{2cor} Relations $(\ref{fullx})$ and $(\ref{nu-cor1})$ remain to hold if the upper bounds of $r$ are substituted by $n$. \end{corollary} The paper is organized as follows. Section 2 collects known and new properties of the involved functions. Theorem \ref{thm1} and Corollary \ref{1cor} are proved in Section 3. Section 4 is devoted to Theorem \ref{thm2} and Corollary \ref{2cor}. In Section 5, we prove Theorem~\ref{Theorem 1}. \section{Auxiliary Lemmas} There are six lemmas in this section. The first, Lemma~\ref{1lema} presents all needed information about the function $\xi(u)$. Lemma~\ref{rho-lema} gives an asymptotic formula for $\rho(u)$ in terms of the function $\xi(u)$, and Lemma~\ref{rholap} provides the Laplace transform of $\rho(u)$ which we use in the proof of Theorem \ref{thm2}. In Lemmas~\ref{2lema} and~\ref{4lema} the saddle-point $x$ and function $\lambda(x)$ are estimated. Lemma~\ref{6lema}, which has a special role, gives estimates for a function $T(z)$ needed in error analysis in all the formulated Theorems. Throughout the section, we assume that $r\geq 2$ if it is not indicated otherwise. Let $\xi(u)$, $\rho(u)$, and $ x(u)$ be the functions defined above for $u\geq 1$. Recall that they are positive and differentiable if $u>1$. We will often use the abbreviations $f=f(u)$ and $f'=f'(u)$ for the values at the point $u$, where $f(v)$, $v>1$, is any of the involved functions. Denote \[ I(s)=\int_0^s \frac{\re^v-1}{v} dv, \quad s\in \C. \] \begin{lemma}\label{1lema} If $u>1$, then $\log u<\xi:=\xi(u)\leq 2\log u$, \[ \xi=\log u +\log\log (u+2)+\frac{B\log\log (u+2)}{ \log (u+2)} \] and \begin{equation} \xi':=\xi'(u)=\frac{1}{u}\,\frac{\xi}{\xi-1+1/u}=\frac{1}{u}\exp\bigg\{\frac{B}{\log (u+1)}\bigg\}. \label{deriv} \end{equation} \end{lemma} \begin{proof} To establish the effective bounds for all $u>1$, it suffices to employ the strictly increasing function $I'(v)$ if $v\geq 0$. Indeed, the lower bound follows from the inequality \[ u=I'(\xi(u))=\int_0^1\re^{t\xi} dt> I'(\log u)=\frac{u-1}{\log u} \] following from $ u\log u-u+1>0$ if $u>1$. To prove the upper estimate, it suffices to repeat the same argument. The asymptotic formulas for $\xi(u)$ and its derivative can be found in \cite{AH+GT} or in the book \cite{GT}. The lemma is proved. \end{proof} \begin{lemma}\label{rho-lema} For $u\geq 1$, \[ \rho(u)=\sqrt{\frac{\xi'}{2\pi}}\exp\big\{\gamma -u\xi +I(\xi)\big\}\Big(1+\frac{B}{u}\Big). \] \end{lemma} \begin{proof} This is Theorem 8 in Section III.5.4 of \cite{GT}. The result has been proved by \mbox{K. Alladi \cite{Alladi}.} \end{proof} \begin{lemma}\label{rholap} Let \[ \hat\rho(s):=\int_0^\infty \re^{-sv} \rho(v) dv=\exp\left\{\gamma+I(-s)\right\}, \quad s \in \C, \] be the Laplace transform of $\rho(v)$, $s=-\xi(u)+i\tau=:-\xi+i\tau$ and $\tau\in\R$. Then \begin{equation*} \hat{\rho}(s) =\begin{cases}B \exp\left\{I(\xi)-\tau^2u/2\pi^2\right\} & {\rm if}\; |\tau|\leq\pi, \\ B\exp\left\{ I(\xi)-u/(\pi^2+\xi^2) \right\} & {\rm if}\; |\tau|>\pi \end{cases} \end{equation*} and \begin{equation*} \hat{\rho}(s)=\frac{1}{s}\bigg(1+\frac{B(1+\xi u)}{s}\bigg)\quad {\rm if}\; |\tau|>1+u\xi. \end{equation*} \end{lemma} \begin{proof} This is Lemma 8.2 in Section III.5.4 of \cite{GT}. \end{proof} Denote $a\wedge b:=\min\{a, b\}$ and $a\vee b:=\max\{a, b\}$ if $a,b\in \R$. Recall that $x:=x(u)$ is the solution to the saddle-point equation and $\lambda(x)=\sum_{j=1}^r jx^j$. \begin{lemma}\label{2lema} If $u\geq 3$, then \begin{equation} x=\exp\bigg\{{\log\big( u(r\wedge \log u)\big)\over r}\bigg\}\bigg(1+{B\over r}\bigg). \label{wedge} \end{equation} If $3\leq u\leq \re^r$, then \begin{align} x&=\exp\left\{\frac{\log\left(u\log u\right)}{r}\right\}\left(1+\frac{B\log\log u}{r\log u}+\frac{B\log u}{r^2}\right)\nonumber\\ &= \exp\Big\{{\xi\over r}\Big\}\left(1+\frac{B\log\log u}{r\log u}+\frac{B\log u}{r^2}\right). \label{xxi} \end{align} Moreover, for $u>1$, \begin{equation} |\lambda(x)/(r^2u)-1|\leq \log^{-1} u. \label{lambda} \end{equation} \end{lemma} \begin{proof} By definition, $x>1$ and $u\leq x^r\leq ru$ for $u>1$. The well-known property of geometric and arithmetic means \[ x^{(r+1)/2}=(x^1 x^2\cdots x^r)^{1/r}\leq {1\over r}\sum_{j=1}^r x^j=u \] yields \begin{equation} u^{1/r}\leq x\leq u^{2/(r+1)}\leq u. \label{urx} \end{equation} We have from the definition that \begin{equation} x^r=1+ru(1- x^{-1}). \label{xr} \end{equation} Consequently, by (\ref{urx}) and by virtue of $1-\re^{-t}\geq t\re^{-t}$ if $t\geq 0$, \[ x^r> ru\big(1-\exp\{-(\log u)/r\}\big)\geq u\log u \exp\{-(\log u)/r\}\geq {\rm e}^{-1} u\log u \] provided that $r\geq \log u$. Similarly, \[ x^r\leq 1+ru(1-\exp\{-2(\log u)/r\})\leq 1+2u\log u. \] The last two inequalities imply \begin{equation} r\log x =\log (u\log u)+ B \label{rlog} \end{equation} for $r\geq \log u$. If $r\leq \log u$, we have \[ x^r> ru\big(1-\exp\{-(\log u)/r\}\big)\geq \big(1-\re^{-1}\big) ru. \] and $x^r\leq 1+ru$. Now \[ r\log x =\log (ur)+ B. \] The latter and (\ref{rlog}) lead to relation (\ref{wedge}). To sharpen (\ref{wedge}) for $3\leq u\leq \re^r$, we iterate once more and obtain \begin{align*} r\log x &=\log \Big[1+ru\big(1-x^{-1}\big)\Big]\\ &= \log\bigg[1+ r u\bigg(1-\exp\bigg\{{-\log( u\log u)\over r}\bigg\}\Big(1+{B\over r}\Big)\bigg)\bigg]\\ &= \log\Big( u\log( u\log u)+Bu+B(u/r)\log^2 u\Big)\\ &= \log( u\log u)+{B\log\log u\over \log u}+{B\log u\over r}. \end{align*} This is the first relation in (\ref{xxi}). Comparing the result and Lemma \ref{1lema}, we have the second one. To prove (\ref{lambda}), we first observe that \begin{equation} \lambda(x)=\frac{rx^{r+1}}{x-1}-\frac{x^{r+1}-x}{(x-1)^2}=\frac{rx^{r+1}-ru}{x-1}= r^2u+\frac{r(x-u)}{x-1}. \label{Lambda} \end{equation} Further, \[ 0\leq \frac{1}{ru} \frac{u-x}{x-1}<\frac{1}{r(x-1)}\leq \frac{1}{\log u}, \] due to (\ref{urx}) and $r(x-1)\geq r(\re^{(\log u)/r}-1)\geq \log u$. The lemma is proved. \end{proof} Using properties of differentiable functions, we improve the remainder term estimates. \begin{lemma}\label{4lema} If $1< u\leq \re^r$, $\xi:=\xi(u)$, and $\xi':=\xi'(u)$, then \begin{equation} x=x(u)= \exp\Big\{\frac{\xi}{r}\Big\}+\frac{B\log (u+1)}{r^2} \label{xxii} \end{equation} and \begin{equation} \frac{r}{\lambda(x)}=\frac{x'}{x}(u)= \frac{\xi'}{r}\Big(1+\frac{B \log (u+1)}{r}\Big). \label{xxiii} \end{equation} \end{lemma} \begin{proof} One may skip the trivial case when $r$ is bounded. From (\ref{saddle}) and (\ref{lambda}), for the differentiable function $x(v)$, we have \begin{equation} 01$ such that $x=\re^{\xi(y)/r}$ and claim that \begin{equation} \xi=\xi(y)\big(1+B/r\big). \label{y} \end{equation} Indeed, if also $u\leq \re^r$, then an observation in the proof of Lemma \ref{2lema} gives us $\xi(y)=r\log x\leq \log (ur) \leq (6/5) r$ if $r$ is sufficiently large. By the definitions and inequalities \[ 0<\frac{t}{1-\re^{-t}}-1=\frac{t-1+\re^{-t}}{1-\re^{-t}}\leq \frac{t^2/2}{t-t^2/2}\leq \frac{3t}{2} \] if $00. \] Now using (\ref{u}) and (\ref{y}), we obtain \[ \frac{x'}{x} = \frac{1}{ru} \frac{y\xi(y)}{1+y\xi(y)-y}\Big(1+\frac{B}{r}\Big)= \frac{1}{ru} \frac{u\xi}{1+u\xi-u}\Big(1+\frac{B\log u}{r}\Big)= \frac{\xi'}{r}\Big(1+\frac{B\log u}{r}\Big) \] if $3\leq u\leq \re^r$. In the case $11. \] Its behavior outside a vicinity of the point $t=0$ is rather complicated; therefore, we consider it in a separate lemma. Denote \[ \lambda_k:=\sum_{j=1}^rj^{k-1}x^j,\ k\geq 1, \] where $x=x(n/r)$. In particular, $\lambda_1=ur$ and $\lambda_2=\lambda(x)$. \begin{lemma} \label{7lema} If $t\in [-\pi,\pi]$ and $y>1$, then \begin{equation} \Re g_r(t,y)\leq -\frac{2}{\pi^2}\frac{y^{r+1}}{r(y-1)}\frac{t^2}{(y-1)^2+t^2}+\frac{2y}{r(y-1)}. \label{grt} \end{equation} If $1/r\leq |t|\leq \pi$, $x=x(u)$, and $u:=n/r\geq 3$, then \begin{equation} \Re g_r(t):=\Re g_r(t,x)\leq -\frac{1}{4\pi^2} \frac{u^{1-4/(r+1)}}{\log^2 u}+\frac{2}{r}+\frac{2}{\log u}. \label{grt1} \end{equation} \end{lemma} \begin{proof} Observe that \begin{align} \Re\sum_{j=1}^r\frac{y^j(e^{itj}-1)}{j} &\leq \frac{1}{r} \Re \sum_{j=1}^ry^j(e^{itj}-1)\nonumber\\ &= \frac{y^{r+1}}{r(y-1)}\left(\Re \frac{e^{it(r+1)}(y-1)}{ye^{it}-1}-1\right)+\frac{y}{r(y-1)}\left(1-\Re \frac{e^{it}(y-1)}{ye^{it}-1}\right)\nonumber\\ &\leq \frac{y^{r+1}}{r(y-1)}\left(\frac{y-1}{|ye^{it}-1|}-1\right)+\frac{2y}{r(y-1)}. \label{grt0} \end{align} If $|t|\leq \pi$, then \[ \frac{|ye^{it}-1|}{y-1}=\left(1+\frac{2y(1-\cos{t})}{(y-1)^2}\right)^{\frac{1}{2}}\geq\frac{((y-1)^2+(4/\pi^2)t^2)^{\frac{1}{2}}}{y-1} \] because of \begin{equation} 2t^2/\pi^2\leq 1-\cos{t}\leq t^2/2. \label{cos} \end{equation} Using also \[ \frac{\alpha}{\sqrt{\alpha^2+v^2}}-1\leq -\frac{1}{2}\frac{v^2}{\alpha^2+v^2},\quad \alpha\geq 0,\; v\in\R, \] with $\alpha=y-1$ and $v=(2/\pi) t$, we obtain \[ \frac{y-1}{|ye^{it}-1|}-1\leq -\frac{2}{\pi^2}\frac{t^2}{(y-1)^2+t^2}. \] Inserting this into (\ref{grt0}), we complete the proof of inequality (\ref{grt}). If $y=x$, $1/r\leq |t|\leq \pi$ and $u\geq 3$, we combine (\ref{grt}) with estimate (\ref{urx}). We have \[ \frac{x^{r+1}}{x-1}=n+\frac{x}{x-1}\geq ur \] and \[ 1<\log u\leq r(x-1)\leq r(u^{2/(r+1)}-1)\leq \frac{2r}{r+1} u^{2/(r+1)}\log u. \] So, we obtain \begin{align*} \Re g_r(t)&\leq -\frac{1}{\pi^2} \frac{u}{r^2(x-1)^2}+\frac{2}{r}\Big(1+\frac{1}{x-1}\Big)\\ &\leq -\Big(\frac{r+1}{2\pi r}\Big)^2 \frac{u^{1-4/(r+1)}}{\log^2 u}+\frac{2}{r}+\frac{2}{\log u}. \end{align*}. Lemma~\ref{7lema} is proved. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm1}] As it has been mentioned in the Introduction, it suffices to examine the case when $r\geq 4$ and $n$ is large. It is more convenient to examine the probability $P\big(\ell(\overline Z)=n\big)$ introduced in (\ref{P-ell}). Set \begin{equation} Q(z)= z^{-n} \exp\left\{\sum_{j=1}^r\frac{z^j-1}{j}\right\}=D(z)\exp\Big\{-\sum_{j\leq r}1/j\Big\}. \label{Qz-naujas} \end{equation} In the introduced notation, we have $u\geq c^{-1} (\log n)(\log\log n)^2$ and \begin{align} P\big(\ell_r(\bar Z)=n\big)&= \frac{Q(x)}{2\pi}\left(\int_{|t|\leq t_0}+\int_{t_0<|t|\leq \pi}\right)\exp\left\{g_r(t)\right\}e^{-itn}dt\nonumber\\ &=: \frac{Q(x)}{2\pi}\big(K_1(n)+K_2(n)\big)\label{P-int} \end{align} with $t_0:=r^{-7/12}n^{-5/12}$. Expanding the integrand in $K_1(n)$, we use relations ${\re}^{it}=1+it-t^2/2-it^3/6+Bt^4$ if $ t\in\mathbf{R}$ and $ \re^{w}=1+B|w| \re^{|w|}$ if $ w\in\mathbf{C}$. Consequently, checking that $\lambda_4t_0^4\leq (r^3 n)(r^{-7/3}n^{-5/3})= (r/n)^{2/3}\leq 1$ and using the abbreviation $\lambda:=\lambda_2$, we obtain \begin{align*} \exp\{g_r(t)\}&= \exp\big\{i \lambda_1t-(\lambda/2)t^2-i(\lambda_3/6)t^3+B\lambda_4t^4\big\}\\ &=\exp\big\{it \lambda_1-(\lambda/2)t^2\big\}\big(1-i(\lambda_3/6)t^3 +B\lambda_3^2 t^6\big) + B\lambda_4 t^4 \exp\big\{-(\lambda/2)t^2\big\}\\ &=\exp\big\{it \lambda_1-(\lambda/2)t^2\big\}\big(1-i(\lambda_3/6)t^3\big)+B\big(\lambda_4t^4+\lambda_3^2 t^6\big)\exp\big\{-(\lambda/2)t^2\big\}. \end{align*} Recall that $u=n/r$, $\lambda_1=n$, $\lambda_k\leq r^k u$ if $k\geq 1$, and, by Lemma \ref{2lema}, $\lambda=\lambda(x)\sim nr$ as $n\to\infty$ because of $u\to\infty$. We now see that \begin{align*} K_1(n)&=\int_{|t|\leq t_0} \re^{-(\lambda/2)t^2} dt +\frac{B}{\sqrt\lambda}\left(\frac{\lambda_4}{\lambda^2}+\frac{\lambda_3^2}{\lambda^3}\right)\\ &= \sqrt{\frac{2\pi}{ \lambda}}-\frac{1}{\sqrt{\lambda}}\int_{|v|> t_0\sqrt{\lambda}} \re^{-v^2/2} dv+\frac{B}{u\sqrt{\lambda}}= \sqrt{\frac{2\pi}{ \lambda}}+\frac{B}{u\sqrt{\lambda}}. \end{align*} Considering $K_2(n)$, we first observe that, by virtue of (\ref{cos}), $ \Re g_r(t)\leq -(2/\pi^2) \lambda t^2 $ if $t_0\leq |t|\leq 1/r$. Therefore, the contribution of the integral over this interval to $K_2(n)$ equals $B/u\sqrt{\lambda}$. Further, we apply Lemmas \ref{2lema} and \ref{7lema} to get \begin{align*} K_2(n)&=B\max_{1/r\leq |t|\leq \pi} \big|\exp\big\{g_r(t)\big\}\big| +\frac{B}{u\sqrt{\lambda}}\\ &= \frac{B}{\sqrt\lambda} \exp\bigg\{-\frac{1}{4\pi^2} \frac{u^{1-4/(r+1)}}{\log^2 u}+\frac{1}{2}\log u+\log r\bigg\}+\frac{B}{u\sqrt{\lambda}}. \end{align*} It remains to prove that the quantity in the large curly braces does not exceed $-\log u+B$ if the bounds of $r$ are as in Theorem \ref{thm1}. This is trivial, if $4\log u>r+1\geq 5$. If $4\log u\leq r+1$ and $n$ is sufficiently large, we have an estimate \[ \frac{1}{4\pi^2} \frac{u^{1-4/(r+1)}}{\log^2 u}\geq \frac{3 c u}{\log^2 u}\geq \frac{3\log n(\log\log n)^2} {(\log\log n+2\log\log\log n +B)^2}\sim 3\log n \] which assures the desired bound $K_2(n)=B/u\sqrt \lambda$. Inserting the estimates of $K_j(n)$, $j=1,2$, into (\ref{P-int}), we finish the proof of Theorem~\ref{thm1}. \end{proof} \begin{proof} [Proof of Corollary~\ref{1cor}] In the above notation, \begin{align} \log Q(x)&= -n\log x+\int_1^x\sum_{j=1}^r t^{j-1} dt =-n\log x+\int_1^x\frac{t^r-1}{t-1} dt\nonumber\\ &= -n\log x+\int_0^{r\log x}\frac{\re^v-1}{v} \frac{v}{r} \frac{dv}{1-\re^{-v/r}}\nonumber\\ &= -u r\log x +I(r\log x)+T(r\log x). \label{Tx} \end{align} Observe that relation (\ref{xr}), rewritten as \[ \re^{r\log x}=1+\Big(\frac{u(1-x^{-1})}{\log x}\Big)(r\log x)=:1+u'(r\log x), \] gives $\xi(u')=r\log x$ with the uniquely defined $u'=u(1-x^{-1})/\log x\leq u$. Hence, by virtue of monotonicity, $r\log x\leq\xi(u)=\xi$ if $x\geq 1$. Therefore \begin{align*} -u r\log x +I(r\log x) &= -u \xi +I(\xi)+u(\xi- r\log x) -\int_{r\log x}^\xi\frac{\re^{t}-1}{t} dt\\ &= -u \xi +I(\xi)+(\xi- r\log x)\bigg(u-\frac{\re^{t_0}-1}{t_0}\bigg) \end{align*} with a $t_0\in[r\log x,\xi]$ and, consequently, if $1\leq u\leq \re^r$, \[ (\re^{t_0}-1)/t_0\in \big[(x^r-1)/(r\log x), u\big]=[u+Bu\xi/r, u]. \] In the last step, we have applied (\ref{xxii}) in the form \[ x^r=(1+u\xi)\big(1+Br^{-1}\log(u+1)\big). \] This yields \begin{equation} -u r\log x +I(r\log x)=-u \xi +I(\xi)+\frac{Bu\log^2(u+1)}{r^2}. \label{urlog} \end{equation} If $1\leq u\leq \re^r$, by Lemma~\ref{1lema}, we have $r\log x\leq \xi \leq 2\log u$. Thus, we may apply estimate (\ref{Tz2}) in Lemma~\ref{6lema} to obtain \begin{align*} T(r\log x)&=\frac{x^r}{2r}+\frac{B\log (u+1)}{r}+\frac{Bu\log^2(u+1)}{r^2}\\ &= \frac{u\xi}{2r}+\frac{B\log (u+1)}{r}+\frac{Bu\log^2(u+1)}{r^2}. \end{align*} Inserting this and (\ref{urlog}) into expression (\ref{Tx}), we deduce a relation \begin{equation} \log Q(x)=-u \xi +I(\xi)+\frac{u\xi}{2r}+\frac{B\log (u+1)}{r}+\frac{Bu\log^2(u+1)}{r^2} \label{logQ} \end{equation} which is non-trivial if $\log u=o(r)$. Combining this with (\ref{xxiii}) and Lemma \ref{rho-lema}, we arrive at \begin{align} \frac{Q(x)}{\sqrt{2\pi\lambda(x)}}&= \frac{\re^{-\gamma}}{r}\frac{\sqrt{\xi'}}{\sqrt{2\pi}}\exp\bigg\{\gamma-u\xi +I(\xi)+\frac{u\xi}{2r}\bigg\}\bigg(1\nonumber\\ &\quad +\frac{B\log (u+1)}{r}+\frac{Bu\log^2(u+1)}{r^2}\bigg)\nonumber\\ &= \frac{\re^{-\gamma}}{r}\rho(u)\re^{u\xi/(2r)}\bigg(1+\frac{B}{u} +\frac{Bu\log^2(u+1)}{r^2}\bigg) \label{Qlambda} \end{align} if $n^{1/3}\log^{2/3} (n+1)\leq r\leq n$. If, in addition, $r\leq cn(\log n)^{-1}(\log\log n)^{-2}$, then by Theorem \ref{thm1}, the ratio on the left hand side approximates the probability $P\big(\ell_r(\bar Z)=n\big)$. Recalling (\ref{P-ell}), we complete the proof of the corollary. \end{proof} \section{An approximation of $\nu(n,r)$ by $\varrho(u)$}\label{s:4} \begin{proof}[Proof of Theorem~\ref{thm2}] The idea is to use the Cauchy integral (\ref{C-integr}) with $\alpha=y:=\re^{\xi/r}$ which is a good approximation of the saddle-point. Here, as above, $\xi=\xi(u)$ is defined by the relation $\re^\xi=1+u\xi$ for $u>1$ and $\xi(1)=0$. Such a choice relates $Q(z)$ defined in (\ref{Qz-naujas}) with the Laplace transform of Dickman's function. Namely, if $z=\re^{-s/r}$, $s=-\xi+ir t=:-\xi+i\tau $, and $|t|\leq\pi$, then, as in (\ref{Tx}), \begin{equation} Q\big(\re^{-s/r}\big)= \exp\big\{us+I(-s)+T(-s)\big\}= \hat\rho(s)\exp\big\{-\gamma+us+T(-s)\big\}, \label{Qz} \end{equation} where $T(-s)$ is the function examined in Lemma \ref{6lema}. Observe that, under the conditions of Theorem 2, $1\leq u\leq \sqrt{ n/\log n}$, where $n$ may be considered large. Let us introduce the following vertical line segments in the complex plane: \[ \Delta_0:=\{s=-\xi+i\tau:\; |\tau|\leq \pi\},\qquad \Delta_1:=\{s=-\xi+i\tau:\; \pi\leq \tau\leq r\pi\}, \] \[ \Delta_2:=\{s=-\xi+i\tau:\; -\pi r\leq \tau\leq -\pi\},\qquad \Delta=\{s=-\xi+i\tau:\; |\tau|\leq r\pi\}, \] and $\Delta_\infty=\{s=-\xi+i\tau:\; |\tau|\geq r\pi\}$. Taking into account (\ref{Qz}), we have from (\ref{C-integr}) \begin{align*} P\big(\ell_r(\bar Z)=n\big)&=\frac{1}{2\pi i}\int_{|z|=y} \frac{Q(z) dz}{z}\nonumber\\ &= \frac{\re^{-\gamma}}{r}\frac{1}{2\pi i}\int_{\Delta}\re^{us}\hat\rho(s) ds+ \frac{\re^{-\gamma}}{2\pi r i}\int_{\Delta}\re^{us}\hat\rho(s)\big(\re^{T(-s)}-1\big) ds\\ &=: I+J. \end{align*} Using Lemmas \ref{1lema}, \ref{rho-lema}, and \ref{rholap} for the case $|\tau|\geq \pi r>1+u\xi$, we obtain \begin{align*} I&=\frac{\re^{-\gamma}\rho(u)}{r}- \frac{1}{2\pi i r u} \int_{\Delta_\infty}\hat\rho(s) d(\re^{us})\\ &= \frac{\re^{-\gamma}\rho(u)}{r}+ \frac{B\re^{-u\xi}}{ur^2} + \frac{1}{2\pi i u r}\int_{\Delta_\infty}\re^{us}\hat\rho(s)\frac{\re^{-s}-1}{s} ds\\ &= \frac{\re^{-\gamma}\rho(u)}{r}+ \frac{B\re^{\xi-u\xi}}{ur^2} \\ &= \frac{\re^{-\gamma}\rho(u)}{r}+ \frac{B\rho(u) \re^{\xi-I(\xi)}}{r^2} \\ &= \frac{\re^{-\gamma}\rho(u)}{r}\Big(1+\frac{B}{r}\Big). \end{align*} In the last step, we have used the fact that $I(\xi)\sim \re^\xi/\xi$ as $\xi\to\infty$. The next task is to estimate $J$. If $s\in\Delta$ then, by Lemma \ref{6lema}, $T(-s)=B$ and $\exp\{T(-s)\}=1+B T(-s)$. Let us split $J$ into the sum of three integrals $J_k$ over the strips $\Delta_k$, where $k=0,1$ and 2, respectively. If $s\in \Delta_0$ then $T(-s)=B(1+u\log u)/r$. Therefore, using Lemmas \ref{1lema}, \ref{rho-lema}, and \ref{rholap}, now for the case $|\tau|\leq \pi$, we derive \begin{align*} J_0&=\frac{B(1+u\log u)}{r^2}\int_{\Delta_0} \big|\hat\rho(s)\re^{us}\big||ds|\\ &= \frac{B(1+u\log u)\rho(u)\sqrt u}{r^2} \int_{-\pi}^{\pi}\re^{-\tau^2u/(2\pi^2)} d\tau\\ &= \frac{B(1+u\log u)\rho(u)}{r^2}. \end{align*} Further, \begin{align*} J_1&=\frac{1}{2\pi i u r}\int_{\Delta_1} \hat\rho(s)\big(\re^{T(-s)}-1\big) d \re^{us}\\ &= \frac{B\re^{-u\xi}}{u r}\big|\hat\rho(-\xi+\pi i)T(\xi-\pi i)\big| +\frac{B\re^{-u\xi}}{u r}\big|\hat\rho(-\xi+\pi r i)T(\xi-\pi r i)\big|\\ &\quad + \frac{B}{u r}\int_{\Delta_1} \re^{us}\Big(\hat\rho(s)'\big(\re^{T(-s)}-1\big)- \hat\rho(s)T'(-s)\re^{T(-s)}\Big)d s\\ &=: L_1+L_2+\frac{B}{u r}L_3. \end{align*} To estimate $L_1$, we combine the first estimate of $\hat\rho(s)$ given in Lemma \ref{rholap} with Lemmas~\ref{1lema} and \ref{rho-lema}. So we obtain \[ L_1=\frac{B(1+u\log u)}{u r^2}\re^{-u\xi+I(\xi)}=\frac{B\rho(u)(1+u\log u)}{r^2}. \] Similarly, the second estimate in Lemma \ref{rholap} leads to \[ L_2=\frac{B\re^{-u\xi}}{u r^2}=\frac{B\rho(u)\re^{-I(\xi)}}{r^2\sqrt u}=\frac{B\rho(u)}{r^2}. \] Estimation of the integral $L_3$ is more subtle. It uses an estimate \[ 1- b(-s/r)-T(-s)= B\left(\frac{\re^\xi}{r}+\left|\frac{s}{r}\right|^2\right) \] following from Lemma \ref{6lema} and the asymptotic formula $ b(v)=1+v/2+Bv^2 $ for $|v|\leq \pi\sqrt2$. We have \begin{align*} L_3&= \int_{\Delta_1}\re^{us} \frac{\re^{-s}-1}{s}\hat{\rho}(s)\left(1+\frac{s}{r(1-\re^{s/r})}\re^{T(-s)}\right) ds\\ &= \int_{\Delta_1}\re^{us} \frac{\re^{-s}-1}{s}\hat{\rho}(s)\left(1- b(-s/r)\re^{T(-s)}\right)ds\\ &= \int_{\Delta_1}\re^{us} \frac{\re^{-s}-1}{s}\hat{\rho}(s)\bigg(\big(1- b(-s/r)-T(-s)\big)+B\Big(\frac{s T(-s)}{r}+T(-s)^2\Big)\bigg) ds\\ &= B\re^{-u\xi}\int_{\Delta_1} \frac{|\re^{-s}-1|}{|s|}|\hat{\rho}(s)|\Big(\frac{e^\xi}{r}+\frac{|s|^2}{r^2}\Big) |ds|. \end{align*} Using the two different estimates of $\hat\rho(s)$ on the line segments $\Delta_{11}:=\{s\in\Delta_1:\; |\Im s|\leq 1+u\xi\}$ and $\Delta_{12}:=\Delta_1\setminus \Delta_{11}$ given by Lemma \ref{rholap}, we proceed as follows: \begin{align*} L_3&= B\exp\bigg\{ -u\xi+I(\xi)-\frac{u}{\pi^2+\xi^2} +\xi\bigg\}\int_{\Delta_{11}}\frac{1}{|s|} \bigg(\frac{\re^{\xi}}{r}+ \frac{|s|^2}{r^2}\bigg)|d s|\\ &\qquad +B\exp\big\{-u\xi +\xi\big\} \int_{\Delta_{12}}\frac{1}{|s|^2} \bigg(\frac{\re^{\xi}}{r}+ \frac{|s|^2}{r^2}\bigg)|d s|\\ &= B\exp\bigg\{ -u\xi+I(\xi)-\frac{u}{\pi^2+\xi^2} +2\xi\bigg\}\frac{1+\xi}{r}+\frac{B\exp\big\{-u\xi +\xi\big\}}{r}\\ &= \frac{B\rho(u)\sqrt u\log(u+2)}{r}. \end{align*} Collecting the obtained estimates, we obtain \[ J_1= L_1+L_2+\frac{B}{u r}L_3=\frac{B\rho(u)(1+u\log u)}{r^2}. \] The same holds for integral $J_2$. Consequently, \[ P\big(\ell_r(\bar Z)=n\big)=I+J_0+J_1+J_2= \frac{\re^{-\gamma}\rho(u)}{r}\Big(1+\frac{B(1+u\log u)}{r}\Big). \] Theorem \ref{thm2} is proved. \end{proof} \begin{proof}[Proof of Corollary~\ref{2cor}] By relation (\ref{Qlambda}), the result of Theorem \ref{thm2} can be exposed as (\ref{fullx}) provided that $\sqrt{n\log n}\leq r\leq n$. Then the assertions of Theorems \ref{thm1} and \ref{thm2} can be joined up as it is indicated in Corollary \ref{2cor}. Now, formula (\ref{fullx}), valid for $1\leq r\leq n$, and (\ref{Qlambda}) justify (\ref{nu-cor1}) for $n^{1/3}\log^{2/3}(n+1)\leq r \leq n$. \end{proof} \section{An application of the Lagrange-B\" urmann formula}\label{s:5} We now present a proof of Theorem \ref{Theorem 1}. Actually, the first steps in it have been done in \cite{AmdMoll}. It suffices to apply the Lagrange-B\"{u}rmann Inversion Formula (presented, for example, on page 732 in \cite{Fl-Sed}) to the functions $D(x)$ and $\lambda(x)$ in expression (\ref{fullx}). Firstly, we list a few formulas of the power series coefficients for superpositions of functions involving $y=y(z)$ defined implicitly as \[ y=z\bigg(\frac{1-y^r}{1-y}\bigg)^{1/r}. \] \begin{lemma}\label{lema3} Let $k,r, j\in\N$ and let $g(z):=z/y(z)$, then the following assertions hold. $(I)$ \quad If $g(z)^j=:\sum_{N=0}^\infty g_N^{(j)} z^N$, then \[ g_N^{(j)}= \frac{j}{j-N}\sum_{rl+m=N\atop l,m\in\N_0} {(N-j)/r\choose l}(-1)^l {m-1+(N-j)/r\choose m} \] for $N\in\N_0\setminus\{j\}$ and \begin{equation} g_j^{(j)}={\mathbf 1}\{j\equiv 0({\rm mod}\, r)\}-\frac{1}{r}. \label{gjj} \end{equation} $(II)$ \quad If $\log g(z)=:\sum_{N=1}^\infty b_N z^N$, then \[ b_N=-\frac{1}{N}\sum_{rl+m=N\atop l,m\in\N_0} {N/r\choose l}(-1)^l {m-1+N/r\choose m}, \quad N\geq1. \] $(III)$ \quad If \[ h(z):=\sum_{j=1}^r\frac{1}{j y(z)^j}=\sum_{N=-r}^\infty h_N z^N, \] then $h_{-r}=1/r$, \[ h_0=- \frac{1}{r}\sum_{j=2}^r\frac{1}{j} \] and \[ h_N= \frac{N+r}{N} b_{N+r} \] for $N=-r+1,-r+2,\dots$ and $N\not=0$. $(IV)$ \quad If \[ \Lambda(z):=\bigg(z^r\sum_{j=1}^r\frac{j}{y(z)^j}\bigg)^{-1}=\sum_{N=0}^\infty \Lambda_N z^N, \] then $\Lambda_0=1/r$ and $\Lambda_N=-Nb_N/r$ for $N=1, 2,\dots$. \end{lemma} \begin{proof} Use the formulas given on pages 732-733 of \cite{Fl-Sed}, except, for the case $N=j$. The latter contains an inaccuracy which rectification is easy. Further, combine them with an expression \[ [y^{N}]\bigg(\frac{1-y^r}{1-y}\bigg)^{\alpha}=\sum_{rl+m=N\atop l,m\in\N_0} {\alpha\choose l}(-1)^l {m-1+\alpha \choose m}, \quad N\in\N_0,\, \alpha\in\R. \] We omit the routine details. The lemma is proved.\end{proof} \begin{lemma}\label{cor1} Let $g(z)$ be as in Lemma $\ref{lema3}$ and $g_N:=g_N^{(1)}$. Then $g_0=1$, $g_1=-1/r$, \begin{equation*} g_N= \frac{ \Gamma(N+(N-1)/r)}{(1-N)\Gamma(N+1)\Gamma((N-1)/r)} %\label{ykj} \end{equation*} if $2\leq N\leq r-1$, and \[ g_r= \frac{ \Gamma(r+1-1/r)}{(1-r)\Gamma(r+1)\Gamma(1-1/r)}+\frac{1}{r}. \] Moreover, $ |g_N|\leq \frac{1}{N-1} r^{(N-1)/r} $ if $N\geq 2$. \end{lemma} \begin{proof} Apply $(I)$ of Lemma \ref{lema3} for $j=1$. If $2\leq N\leq r-1$, the relevant sum has the only nonzero summand corresponding to the pair $(l,m)=(0,N)$. A formula for $g_r$ has two summands giving the expression. If $N\geq 2$, then by the definition and Cauchy's inequality, \[ |g_N|= \frac{1}{N-1}\Big|[y^N](1+y+\cdots+y^{r-1})^{(N-1)/r}\Big|\leq \frac{1}{N-1} r^{(N-1)/r}. \] The lemma is proved. \end{proof} \begin{lemma} \label{cor2} We have \begin{equation} b_N=[z^N]\log g(z)=- \frac{\Gamma(N+N/r)}{N\Gamma(N+1)\Gamma(N/r)} \label{bN} \end{equation} if $1\leq N\leq r-1$ and $b_r=0$. Moreover, \[ N|b_N|\leq 1 \quad \text{if}\quad N\leq r-1, \] \[ b_N =BN/r \quad \text{if}\quad r0$. Finally, by Cauchy's inequality, \begin{equation} N|b_N|= \bigg| [y^{N}]\bigg(\frac{1-y^r}{1-y}\bigg)^{N/r}\bigg|= \big| [y^{N}](1+y+\cdots+ y^{r-1})^{N/r}\big|\leq r^{N/r} \label{NbN} \end{equation} if $N\geq 1$. The lemma is proved. \end{proof} We now derive the mentioned expansion (\ref{xnr-Skleid}) of the saddle-point. \begin{lemma} \label{lema11} If $2\leq r\leq \log n$, then \begin{align*} x&= n^{1/r}-\frac{1}{r} -\sum_{N=2}^{r}\frac{ \Gamma(N+(N-1)/r)}{(N-1)\Gamma(N+1)\Gamma((N-1)/r)} n^{-(N-1)/r}\\ &\quad + \frac{1}{r}n^{-1+1/r}+\frac{B}{n}. %\label{xnr-Skleid} \end{align*} \end{lemma} \begin{proof} The equation defining $x$ can be rewritten as \[ x^{-1}=\bigg(\frac{1-x^{-r}}{1-x^{-1}}\bigg)^{1/r}n^{-1/r}. \] This gives the relation $y(n^{-1/r})=x^{-1}$, where $y=y(z)$ has been explored in Lemma \ref{lema3}. Consequently, we may apply the expansions of $g(z)$ given in $(I)$ with respect to powers of $z=n^{-1/r}$. The first coefficients have been calculated in Lemma \ref{cor1}. It remains to estimate the remainder. Using also the obtained estimates, we have \[ \sum_{N=r+1}^\infty |g_N| |z|^N\leq r^{-1-1/r}\sum_{N=r+1}^\infty |r^{1/r} z|^N\leq \frac{|z|^{r+1}}{1-\sqrt[3]{3} {\rm e}^{-1}} \] if $|z|\leq {\rm e}^{-1}$. Consequently, we obtain \begin{align*} x&= n^{1/r} \sum_{N=0}^r g_N n^{-N/r}+ \frac{B}{n}\\ &= n^{1/r}-\frac{1}{r} -\sum_{N=2}^{r}\frac{ \Gamma(N+(N-1)/r)}{(N-1)\Gamma(N+1)\Gamma((N-1)/r)} n^{-(N-1)/r} \\ & \quad + \frac{1}{r}n^{-1+1/r}+\frac{B}{n} \end{align*} as desired. \end{proof} \begin{proof}[Proof of Theorem~\ref{Theorem 1}] Let us preserve the notation introduced in Lemma \ref{lema3}. First of all we seek a simple expression containing the first terms in an expansion of \[ K(z):= \sum_{j=1}^r \frac{1}{j y(z)^j}-n\log \frac{z}{y(z)}= h(z)-n\log g(z). \] Recall that $D(x)=\exp\left\{\sum_{j=1}^r x^j/j\right\}$, we have \begin{equation} \log D(x)-n\log x= K(n^{-1/r})-\frac{n\log n}{r}. \label{Dx} \end{equation} Define the functions $R(z)$ and $K_r(z)$ by \[ K(z)=\sum_{N=-r+1}^0 h_N z^N-n\sum_{N=1}^{r-1} b_N z^N +R(z)=K_r(z)+R(z) \] We claim that $R(z)=B(|z|+n|z|^{r+1})$ if $|z|\leq \rm e^{-1}$ implying \begin{equation} R(n^{-1/r})=Bn^{-1/r}. \label{Rz} \end{equation} for $r\leq \log n$. Indeed, by $(III)$ of Lemma \ref{lema3} and the estimates in Lemma \ref{cor2}, we have \begin{align*} \sum_{N=1}^\infty |h_N||z|^N&= \bigg(\sum_{N=1}^{r-1}+\sum_{N=r}^\infty\bigg)\frac{N+r}{N}|b_{N+r}||z|^N\\ &= B\sum_{N=1}^{r-1}\frac{N+r}{r}|z|^N +B\sum_{N=r}^\infty\frac{r}{N}\big(r^{1/r}|z|\big)^N =B|z| \end{align*} if $|z|\leq \rm e^{-1}$. Similarly, \[ \sum_{N=r+1}^\infty |b_N||z|^N=B |z|^{r+1} \] if $|z|\leq \rm e^{-1}$. The last two estimates yield our claim and (\ref{Rz}). For the main term, we obtain from Lemma \ref{lema3} that \begin{align*} K_r(n^{-1/r})&= h_0+\sum_{N=-r+1}^{-1} h_N n^{-N/r}- \sum_{N=1}^{r-1} b_N n^{(r-N)/r}+h_{-r} n\\ &= h_0 -\sum_{N=1}^{r-1} \frac{r-N}{N} b_{r-N} n^{N/r}- \sum_{N=1}^{r-1} b_N n^{(r-N)/r}+h_{-r} n\\ &= h_0 -r\sum_{N=1}^{r-1} \frac{1}{N} b_{r-N} n^{N/r}+h_{-r} n\\ &= - \frac{1}{r}\sum_{j=2}^r\frac{1}{j}+ r \sum_{N=1}^{r-1}\frac{1}{N(r-N)}\, \frac{\Gamma(N+N/r)}{\Gamma(N+1)\Gamma(N/r)}n^{(r-N)/r}+\frac{n}{r}. \end{align*} It remains to approximate \[ \Big(\frac{1}{\lambda(x)}\Big)^{1/2}= \frac{1}{\sqrt n} \Lambda(n^{-1/r})^{1/2}=\frac{1}{\sqrt {n r}}\bigg(1-\sum_{N=1}^\infty Nb_N n^{-N/r}\bigg)^{1/2}. \] By virtue of Lemma \ref{cor2}, $N|b_N|\leq 1$ if $N\leq r$ and $N|b_N|\leq r^{N/r}$ if $N\geq 1$. Thus, if $2\leq r\leq \log n$, then \[ \sum_{N=1}^\infty N|b_N|n^{-N/r}\leq (5/2) n^{-1/r}\leq (5/2){\rm e}^{-1}<1. \] Consequently, \[ \Big(\frac{1}{\lambda(x)}\Big)^{1/2}= \frac{1}{\sqrt {n r}}\big(1+Bn^{-1/r}\big). \] We now return to probabilities. Applying \eqref{P-ell}, \eqref{fullx}, (\ref{Dx}), (\ref{Rz}) and the last estimate, we obtain \begin{align*} n!\nu(n,r)&= \frac{n!}{{\sqrt{ 2\pi \lambda(x)}}} n^{-n/r}\exp\big\{K_r(n^{-1/r})\big\}\big(1+Bn^{-1/r}\big)\\ &= \frac{1}{\sqrt {2\pi nr}} n^{-n/r}\exp\big\{K_r(n^{-1/r})\big\}\big(1+Bn^{-1/r}\big) \end{align*} for all $2\leq r\leq \log n$. Theorem 1 is proved. \end{proof} \subsection*{Concluding Remark} The approach can be adopted for more general decomposable structures, in particular, for the so-called logarithmic classes of set constructions (see \cite{ABT}). X. Gourdon's paper \cite{Gourdon} is a good pattern in doing such extensions. \subsection*{Acknowledgements} The authors thank the referee for his benevolent suggestions which have helped in improving the exposition of the paper. \begin{thebibliography}{99} \bibitem{Alladi} K.~Alladi. The Tur\'an--Kubilius inequality for integers without large prime factors. \textit{ J. Reine Angew. Math.}, 335:180--196, 1982. \bibitem{AmdMoll} T.~Amdeberhan and V.H.~Moll. Involutions and their progenies. \textit{J. Comb.}, 6(4):483--508, 2015. \bibitem{ABT} R.~Arratia, A.D.~Barbour, and S.~Tavar\'{e}. \textit{Logarithmic Combinatorial Structures: A Probabilistic Approach}. EMS Monogr. Math., EMS Publishing House, Z\"{u}rich, 2003. \bibitem{ChHeMo1951} S.~Chowla, I.N.~Herstein, W.K.~Moore. On recursions connected with symmetric groups. I. \textit{Can. J. Math.}, 3:328--334, 1951. \bibitem{Dickman} K.~Dickman. On the frequency of numbers containing prime factors of a certain relative magnitude. \textit{Ark. Mat. Astr. Fys.}, 22:1--14, 1930. \bibitem{Fl-Sed} P.~Flajolet and R.~Sedgewick. \textit{Analytic Combinatorics}. Cambridge University Press, 2009. \bibitem{GarePana} T.~Garefalakis and D.~Panario. Polynomials over finite fields free from large and small degree irreducible factors. \textit{ J. Algorithms}, 44(1):98--120, 2002. \bibitem{Gonch44} V.L.~Goncharov. On the field of combinatorial analysis. \textit{Izv. Akad. Nauk SSSR, Ser. Mat.}, 8:3--48 (Russian), 1944. Translation in \textit{Transl. Am. Math. Soc., Ser.} 2, 19:1--46, 1962. \bibitem{Gourd-th} X. Gourdon. \textit{Combinatoire, algorithmique et g\'{e}om\'{e}trie des polyn\^{o}mes}. Ph.D. thesis, \'{E}cole Polytechnique, 1996. \bibitem{Gourdon} X.~Gourdon. Largest component in random combinatorial structures. \textit{ Discrete Math.}, 180:185--209, 1998. \bibitem{Granv} A.~Granville. Smooth numbers: computational number theory and beyond. In \textit{Algorithmic Number Theory}, volume 44 of \textit{MSRI Publications}, 267--323, 2008. \bibitem{Har+Schon68} B.~Harris and L.~Schoenfeld. Asymptotic expansions for the coefficients of analytic generating functions. \textit{Illinois J. Math.}, 12:264--277, 1968. \bibitem{Hayman} W.K.~Hayman. A generalization of Stirling's formula. \textit{J. Reine Angew. Math.}, 196:67--95, 1956. \bibitem{AH+GT} A.~Hildebrand and G.~Tenenbaum. Integers without large prime factors. \textit{J. Th\'eorie des Nombres de Bordeaux}, 5:411--484, 1993. \bibitem{Lugo} M.~Lugo. The number of cycles of specified normalized length in permutations, \arxiv{0909.2909v1}, 2009. \bibitem{EM-Pal92} E.~Manstavi\v cius. Semigroup elements free of large prime factors. In \textit{Analytic and Probabilistic Methods in Number Theory}, volume 2 of \textit{New Trends in Probability and Statistics} (F.~Schweiger and E.~Manstavi\v cius, Eds), 135--153. TEV/Vilnius and VSP/Utrecht, 1992. \bibitem{EM-LMJ92} E.~Manstavi\v cius. Remarks on the semigroup elements free of large prime factors. \textit{ Lith. Math. J.}, 32(4):400--410, 1992. \bibitem{Moree} P. Moree. Nicolaas Govert de Bruijn, the enchantert of friable integers. \textit{Indag. Math.}, 24(4):774--801, 2013. \bibitem{MoWy55} L.~Moser and M.~Wyman. On solutions of $x^d=1$ in symmetric groups. \textit{ Canad. J. Math.}, 7:159--168, 1955. \bibitem{Odlyzko} A.M.~Odlyzko. Discrete logarithms and smooth polynomials. In \textit{Finite Fields: Theory, Applications and Algorithms}, volume 168 of \textit{Contemporary Math.}, 269--278, 1993. \bibitem{Pl-Ro29} M.~Plancherel and W.~Rotach. Sur les valeurs asymptotiques des polyn\^{o}mes d{'}Hermite. \textit{Commentarii Math. Helvetici}, 1:273--288, 1929. \bibitem{Sachkov} V.N.~Sachkov. Asymptotic formulas and limit distributions for combinatorial configurations generated by polynomials. \textit{Discrete Math.}, 19(3):3--14 (Russian), 2007. Translation in \textit{Discrete Math. Appl.}, 17(4):319--330, 2007. \bibitem{Schmutz88} E.~Schmutz. Asymptotic expansions for the coefficients of $\re^{P(z)}$. \textit{ Bull. London Math. Soc.}, 21:482--486, 1989. \bibitem{GT} G.~Tenenbaum. \textit{Introduction to Analytic and Probabilistic Number Theory}. Cambridge University Press, 1995. \bibitem{Timash} A.N.~Timashov. Random permutations with cycle lengths in a given finite set. \textit{Discrete Math.}, 20(1):25--37, 2008 (Russian). Translation in \textit{Discrete Math. Appl.}, 18(1):25--39, 2008. \bibitem{Warlimont} R.~Warlimont. Arithmetical semigroups, II: sieving by large and small prime elements, sets of multiples. \textit{Manuscripta Math.}, 71:197--221, 1991. \bibitem{Wilf} H.~Wilf. \textit{generatingfunctionology}. Academic Press, San Diego, 2nd edn, 1994. \end{thebibliography} \end{document}