×

zbMATH — the first resource for mathematics

On the distribution of the \(m\)th maximal cycle lengths of random \(A\)-permutations. (English, Russian) Zbl 1101.60004
Discrete Math. Appl. 15, No. 5, 527-546 (2005); translation from Diskretn. Mat. 17, No. 4, 40-58 (2005).
Summary: Let \(S_n\) be the symmetric group of all permutations of degree \(n\), \(A\) be some subset of the set of natural numbers \({\mathbf N}\), and \(T_n=T_n(A)\) be the set of all permutations of \(S_n\) with cycle lengths belonging to \(A\). The permutations of \(T_n\) are called \(A\)-permutations. We consider a wide class of the sets \(A\) with the asymptotic density \(\sigma>0\). The limit distributions are obtained for \(\mu_m(n)/n\) as \(n\to\infty\) and \(m\in{\mathbf N}\) is fixed. Here \(\mu_m(n)\) is the length of the \(m\)th maximal cycle in a random permutation uniformly distributed on \(T_n\). It is shown here that these limit distributions coincide with the limit distributions of the corresponding functionals of the random permutations in the Ewens model with parameter \(\sigma\).

MSC:
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Yu V., Math. USSR Sbornik 28 pp 107– (1977)
[2] Yu V., Math. USSR Sbornik 36 pp 87– (1980)
[3] Yu. V. Bolotnikov and V. E. Tarakanov, Limit distributions in problems on the cycles of random permutations. In: Combinatorial and Asymptotic Analysis. Krasnoyarsk Univ. Press, Krasnoyarsk, 1977, pp. 62-68 (in Russian).
[4] SIAM Review 16 pp 485– (1974)
[5] Theor. Popul. Biol. 3 pp 87– (1972)
[6] W. Feller, An Introduction to Probability Theory and its Applications, v. 2. Wiley, New York, 1971. · Zbl 0219.60003
[7] Amer. Math. Soc. Transl. 19 pp 1– (1962)
[8] A. A. Grusho, Properties of random permutations with constraints on the maximum cycle length. In: Probabilistic Methods in Discrete Mathematics. TVP/VSP, Moscow/Utrecht, 1993, pp. 459- 469. · Zbl 0816.60009
[9] Papers on Discrete Mathematics 5 pp 73– (2002)
[10] Theory Probab. Appl. 47 pp 518– (2003)
[11] Discrete Math. Appl. 4 pp 59– (1994)
[12] V. F. Kolchin, Random Mappings. Optimization Software, New York, 1986.
[13] Discrete Math. Appl. 1 pp 179– (1991)
[14] V. F. Kolchin, The number of permutations with cycle lengths from a fixed set. In: Random Graphs, v. 2. Wiley, Chichester, 1992, pp. 139-149. · Zbl 0820.05001
[15] V. F. Kolchin, Random Graphs. Cambridge Univ. Press, Cambridge, 1999. · Zbl 0918.05001
[16] Period. Math. Hung. 42 pp 37– (2001)
[17] Mineev A. I, Math. USSR Sbornik 28 pp 421– (1978)
[18] Mineev A. I, Proc. Steklov Inst. Math. 142 pp 195– (1979)
[19] Math. USSR Sbornik 52 pp 521– (1985)
[20] Math. USSR Sbornik 57 pp 263– (1987)
[21] Theory Probab. Appl. 31 pp 618– (1986)
[22] Discrete Math. Appl. 2 pp 445– (1992)
[23] Proc. Steklov Inst. Math. 207 pp 233– (1995)
[24] Math. 49 pp 380– (1994)
[25] Math. Notes 62 pp 739– (1997)
[26] A. G. Postnikov, Introduction to Analytic Number Theory. AMS, Providence, RI, 1988. · Zbl 0641.10001
[27] Theory Probab. Appl. 17 pp 640– (1972)
[28] Theory Probab. Appl. 18 pp 120– (1973)
[29] V. N. Sachkov, Probabilistic Methods in Combinatorial Analysis. Cambridge Univ. Press, Cambridge, 1996. · Zbl 0874.60020
[30] E. Seneta, Regularly Varying Functions. Springer, New York, 1976. · Zbl 0324.26002
[31] Shepp S. P, Trans. Amer. Math. Soc. 121 pp 340– (1966)
[32] Tarakanov V. P, Soviet Math. Sbornik 96 (138) pp 594– (1975)
[33] Vladimirov B. I, J. Soviet Math. 16 pp 1487– (1981)
[34] L. M. Volynets, The number of solutions of an equation in the symmetric group. In: Probabilistic Processes and their Applications. MIEM, Moscow, 1985, pp. 104-109 (in Russian). · Zbl 0645.05003
[35] Math. Notes 40 pp 586– (1986)
[36] L. M. Volynets, An example of nonstandard asymptotics of the number of permutations with constraints on the lengths of the cycles. In: Probabilistic Processes and their Applications. MIEM, Moscow, 1989, pp. 85-90 (in Russian).
[37] Soviet Math. Sbornik 66 pp 301– (1990)
[38] Discrete Math. Appl. 1 pp 105– (1991)
[39] A. L. Yakymiv, On random permutations with cycle lengths from a given set. In: Probabilistic Processes and their Applications. MIEM, Moscow, 1991, pp. 24-27 (in Russian).
[40] Discrete Math. Appl. 3 pp 213– (1993)
[41] A. L. Yakymiv, Limit theorems for random A-permutations. In: Probabilistic Methods in Discrete Mathematics. TVP/VSP, Moscow/Utrecht, 1993, pp. 459-469. · Zbl 0810.60020
[42] Discrete Math. Appl. 10 pp 543– (2000)
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.