Asymptotic expansions for the distribution of the number of components in random mappings and partitions (Q2889724)

Let \(S_n\) be an \(n\)-element set and \(F_n\) be the set of all single-valued functions from \(S_n\) into \(S_n\). Denote by \(V_n\) the number of connected components of a randomly and equi-probably chosen function in \(F_n\) and by \(X_n\) the number of cycles in a permutation randomly and equiprobably chosen from the \(n!\) permutations of the \(n\)-elements of \(S_n\). Let \(Y_n\) be the number of blocks in a partition randomly and equi-probably chosen partition from among all the partitions of the elements of \(S_n\).NEWLINENEWLINE The following results are proven in this paper.NEWLINENEWLINE Theorem 1. Let \(n\), \(N\to\infty\) in such a way that \(0< a< x= N/(\ln n)\Leftarrow b\) where \(a\), \(b\) are constants. Then, uniformly in \(x\in[a, b]\), NEWLINE\[NEWLINE\operatorname{P}(V_n= N)= \nu(2x/n) e^{\phi(x)}((\ln n)/2N!))^N(1+ o(1)),NEWLINE\]NEWLINE where NEWLINE\[NEWLINE\phi(x)= x(1- \ln(2x))- 1/2\quad\text{for}\quad x> 0\quad\text{and} \quad x\neq 1/2\quad\text{and}\quad \phi(1/2)= 0.NEWLINE\]NEWLINE Theorem 2. Let \(n\), \(N\to\infty\) in such a way that \(N= (\ln n)/2+ x\nu((\ln n)/2)\), where \(x= x(n)= o(\nu(\ln n))\). Then NEWLINE\[NEWLINE\begin{multlined} \operatorname{P}\{V_n= N\}= {1\over\sqrt{\pi\ln n}}\times \exp\Biggl(-{x^2\over 2}+ \sum^\infty_{m=1} {(-1)^{m-1} x^{m+2}\over (m+1)(m+2)} \Biggl({2\over \ln n}\Biggr)^{m/2}\Biggr)((1+ o(1)).\end{multlined}NEWLINE\]NEWLINE Theorem 3. Under the conditions of Theorem 1 NEWLINE\[NEWLINE\operatorname{P}(X_n= N)= n^{\psi(x)}/(\Gamma(x)\nu(2\pi x\ln n))(1+ o(1)),NEWLINE\]NEWLINE where NEWLINE\[NEWLINE\psi(x)= x(1-\ln x)-1\quad\text{for}\quad x> 0\quad\text{and}\quad x\neq 1\quad\text{and}\quad\psi(1)= 0.NEWLINE\]NEWLINE Theorem 4. Let \(n\), \(N\to\infty\) in such a way that \(N=\ln n+ y\nu(l\ln n)\), where \(y= y(n)= o(\nu(\ln n))\) Then NEWLINE\[NEWLINE\begin{multlined} \operatorname{P}\{X_n= N\}= {1\over\sqrt{2\pi\ln n}}\exp\Biggl(- {y^2\over 2}+ \sum^\infty_{m=1} {(-1)^{m-1} y^{m+2}\over (m+ 1)(m+2)} (\ln n)^{-m/2}\Biggr)\times\\ \Biggl(1+ O\Biggl({|y|\over \sqrt{\ln n}}+ {1\over\ln n}\Biggr)\Biggr).\end{multlined}NEWLINE\]NEWLINE Theorem 5. Let \(n< N\) and \(n\to\infty\) in such a way that \(N= (n+ z\nu n)/r\), where \(z= z(n)= o(\nu(n)/\ln n)\) and \(r> 0\) satisfies \(re'= n\). Then NEWLINE\[NEWLINE\begin{multlined} \operatorname{P}\{Y_n= M\}= {\ln n\over\sqrt{2\pi n}}\times\exp\Biggl(-{z^2\over 2}\Biggl(1+{1\over r}\Biggr)+\\ \sum^\infty_{m=1} {(-1)^{m-1} z^{m+2}\over (m+2) n^{m/2}} \Biggl(1+{1\over r(m+ 1)}\Biggr)\Biggr)\times (1+ o(1)).\end{multlined}NEWLINE\]NEWLINE Several corollaries are derived. Two samples are provided below.NEWLINENEWLINE Corollary 2. Let \(n\to\infty\) and \(x= x(n)= o((\ln n)^{1/6})\). Then NEWLINE\[NEWLINEP(V_n= N)= (1/\nu(\pi\ln n))\exp(-x^2/2)\;(1+ o(1).NEWLINE\]NEWLINE Corollary 6. Under the conditions of Theorem 5, if \(z= o(\nu\ln n)\), then NEWLINE\[NEWLINEP(Y_n= N)= ((\ln n)/\nu(2\pi n))\exp(- z^2/2)\,(1+ o(1).NEWLINE\]