Previous |  Up |  Next


random permutation; cycle structure; Poisson distribution; factorial moment
Inspired by probabilistic number theory, we establish necessary and sufficient conditions under which the numbers of cycles with lengths in arbitrary sets posses an asymptotic limit law. The approach can be extended to deal with the counts of components with the size constraints for other random combinatorial structures.
[1] Arratia R., Barbour A.D., Tavaré S.: Logarithmic Combinatorial Structures: a Probabilistic Approach. EMS Monographs in Mathematics, EMS Publishing House, Zürich, 2003. MR 2032426
[2] Arratia R., Tavaré S.: Limit theorems for combinatorial structures via discrete process approximations. Random Structures and Algorithms 3(1992), 3, 321–345. DOI 10.1002/rsa.3240030310 | MR 1164844
[3] Babu G.J., Manstavičius E.: Processes with independent increments for the Ewens sampling formula. Ann. Inst. Stat. Math. 54(2002), 3, 607–620. DOI 10.1023/A:1022419328971 | MR 1932405
[4] Elliott P. D. T. A.: Probabilistic Number Theory. I, II. Springer, New York–Heidelberg–Berlin, 1979/80. MR 0551361 | Zbl 0431.10029
[5] Goncharov V.L.: On the distribution of cycles in permutations. Dokl. Acad. Nauk SSSR 35(1942), 299–301.
[6] Kolchin V.F.: Random Mappings. Optimization Software, Inc. New York, 1986. MR 0865130 | Zbl 0605.60010
[7] Kubilius J.: Probabilistic Methods in the Theory of Numbers. Amer. Math. Soc. Translations 11, Providence, RI, 1964. MR 0160745 | Zbl 0133.30203
[8] Manstavičius E.: Additive and multiplicative functions on random permutations. Lith. Math. J. 36(1996), 4, 400–408. DOI 10.1007/BF02986863 | MR 1456921
[9] Manstavičius E.: The law of iterated logarithm for random permutations. Lith. Math. J. 38(1998), 2, 160–171. DOI 10.1007/BF02465552 | MR 1657912
[10] Manstavičius E.: Functional limit theorem for sequences of mappings on the symmetric group. In: Anal. Probab. Methods in Number Theory, A. Dubickas et al (Eds), TEV, Vilnius, 2002, 175–187. MR 1964861
[11] Manstavičius E.: Value concentration of additive functions on random permutations. Acta Applicandae Math. 79(2003), 1–8. DOI 10.1023/A:1025812604540 | MR 2021871
[12] Manstavičius E.: Asymptotic value distribution of additive functions defined on the symmetric group. (submitted, 2005, 23 p.).
[13] Šiaulys J.: Factorial moments for distributions of additive functions. Lith. Math. J. 40(2000), 4, 389–408. DOI 10.1023/A:1007617714857
Partner of
EuDML logo