×

zbMATH — the first resource for mathematics

On asymptotic expansions for the distributions of the number of cycles in a random permutation. (English. Russian original) Zbl 1048.05009
Discrete Math. Appl. 13, No. 5, 417-427 (2003); translation from Diskretn. Mat. 15, No. 3, 117-126 (2003).
Summary: We obtain explicit formulas for the coefficients of asymptotic expansions in the domain of large deviations for the distributions of the number of cycles \(\nu_n\) in a random permutation of degree \(n\), that is, for the probability \({\mathbf P} \{\nu_n= N\}\) under the condition that \(n\), \(N\to\infty\) in such a way that \(1< \alpha_0 \leq\alpha= n/N\leq\alpha_1 <\infty\), where \(\alpha_0\), \(\alpha_1\) are constants. These formulas express the coefficients in terms of cumulants of the random variable which has the distribution of the logarithmic series with specially chosen parameter. For the cumulants of the third and fourth orders we give the corresponding values. We discuss the accuracy of the obtained approximations. If \(n\), \(N\to\infty\) so that \(0<\gamma_0 \leq\gamma=N/ \ln n\leq\gamma_1 <\infty\), where \(\gamma_0\), \(\gamma_1\) are constants, we give asymptotic estimates of the probabilities \({\mathbf P}\{\nu_n=N\}\), \({\mathbf P}\{\nu_n\leq N\}\), \({\mathbf P} \{\nu_n\geq N\}\) with the remainder terms of order \(O((\ln n)^{-2})\) uniform in \(\gamma\in[\gamma_0,\gamma_1]\). The corresponding estimate for the probability \({\mathbf P}\{\nu_n=N\}\) refines the previously known results for the case \(N=\beta\ln n+o(\ln n)\), where \(\beta\) is a positive constant.

MSC:
05A16 Asymptotic enumeration
05A05 Permutations, words, matrices
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Riordan, Introduction to Combinatorial Analysis. Wiley, New York, 1958. · Zbl 0078.00805
[2] V. F. Kolchin, Random Graphs. Cambridge Univ. Press, Cambridge, 1999. · Zbl 0918.05001
[3] Ann. Math. Statist. 32 (1) pp 249– (1961)
[4] Discrete Math. Appl. 8 pp 533– (1998)
[5] Amer. Math. Soc. Translat. pp 1– (1962)
[6] V. F. Kolchin, B. A. Sevastyanov, and V. P. Chistyakov, Random Allocations. Wiley, New York, 1978.
[7] V. V. Petrov, Sums of Independent Random Variables. Springer, New York, 1975. · Zbl 0322.60043
[8] V. N. Sachkov, Combinatorial Methods in Discrete Mathematics. Cambridge Univ. Press, Cambridge, 1996.
[9] Timashov, Discrete Math. Appl. 10 pp 63– (2000)
[10] M. A. Evgrafov, Asymptotic Estimates and Entire Functions. Gordon and Breach, New York, 1961. · Zbl 0121.30202
[11] F. W. J. Olver, Introduction to Asymptotics and Special Functions. Academic Press, New York, 1974. · Zbl 0308.41023
[12] A. Erdlyi, W. Magnus, F. Oberhettinger, and F. G. Tricomi, Higher Transcendental Functions. Bateman Manuscript Project, McGraw-Hill, New York, 1953. · Zbl 0051.30303
[13] Yu L, Proc. Steklov Inst. Math. 177 pp 131– (1988)
[14] Theory Probab. Appl. 33 pp 183– (1988)
[15] L. M. Volynets, An estimate of the rate of convergence to the limit distribution for the number of cycles in a random permutation. In: Probab. Probl. Discrete Math., MIEM, Moscow, 1987, pp. 40-46 (in Russian).
[16] Discrete Math. Appl. 13 pp 307– (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.