Limit Theorem for the Middle Members of Ordered Cycle Lengths in Random $A$-Permutations

A. L. Yakymiv

Teoriâ veroâtnostej i ee primeneniâ, Tome 54 (2009) no. 1, pp. 63-79

Résumé

In this article, random permutation $\tau_n$ is considered uniformly distributed on the set of all permutations with degree $n$ and with cycle lengths from fixed set $A$ (so-called $A$-permutations). Let $\zeta_n$ be the general number of cycles and $\eta_n(1)\leq\eta_n(2)\leq\cdots\leq\eta_n(\zeta_n)$ be the ordered cycle lengths in a random permutation $\tau_n$. The central limit theorem is obtained here for the middle members of this sequence, i.e., for random variables $\eta_n(m)$ with numbers $m=\alpha\log n+o(\sqrt{\log n})$ as $n\to\infty$ for fixed $\alpha\in(0,\sigma)$ and for some class of the sets $A$ with positive asymptotic density $\sigma$. The basic approach to the proof is the new three-dimensional Tauberian theorem. Asymptotic behavior of extreme left and extreme right members of this sequence was investigated earlier by the author.

Détail

Keywords: random $A$-permutation, ordered cycle lengths of permutation, Tauberian theorem.

Bibliographie

[1] Bender E. A., “Asymptotic methods in enumeration”, SIAM Rev., 16:4 (1974), 485–515 ; corrections: ibid. 18:2 (1976), 292 | DOI | MR | Zbl | DOI | MR | Zbl

[2] Bolotnikov Yu. V., Sachkov V. N., Tarakanov V. E., “Asimptoticheskaya normalnost nekotorykh velichin, svyazannykh s tsiklovoi strukturoi sluchainykh podstanovok”, Matem. sb., 99(141):1 (1976), 121–133 | MR | Zbl

[3] Volynets L. M., “Primer nestandartnoi asimptotiki chisla podstanovok s ogranicheniyami na dliny tsiklov”, Veroyatnostnye protsessy i ikh prilozheniya, MIEM, M., 1989, 85–90 | MR

[4] Goncharov V. L., “Iz oblasti kombinatoriki”, Izv. AN SSSR, 8:1 (1944), 3–48

[5] Ivchenko G. I., Medvedev Yu. I., “Metod V. L. Goncharova i ego razvitie v analize razlichnykh modelei sluchainykh podstanovok”, Teoriya veroyatn. i ee primen., 47:3 (2002), 558–566 | MR | Zbl

[6] Kolchin V. F., “Odna zadacha o razmeschenii chastits po yacheikam i tsikly sluchainykh podstanovok”, Teoriya veroyatn. i ee primen., 16:1 (1971), 67–81 | MR | Zbl

[7] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 206 pp. | MR

[8] Kolchin V. F., “O chisle podstanovok s ogranicheniyami na dliny tsiklov”, Diskretn. matem., 1:2 (1989), 97–109 | MR

[9] Kolchin V. F., “The number of permutations with cycle lengths from a fixed set”, Random Graphs, v. 2 (Poznań, 1989), Wiley, New York, 1992, 139–149 | MR | Zbl

[10] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2000, 255 pp. | MR | Zbl

[11] Mineev M. P., Pavlov A. I., “O chisle podstanovok spetsialnogo vida”, Matem. sb., 99:3 (1976), 468–476 | MR | Zbl

[12] Mineev M. P., Pavlov A. I., “Ob uravnenii v podstanovkakh”, Tr. MIAN, 142, 1976, 182–194 | MR | Zbl

[13] Pavlov A. I., “O nekotorykh klassakh podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Matem. sb., 129:2 (1986), 252–263 | MR | Zbl

[14] Pavlov A. I., “O podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Teoriya veroyatn. i ee primen., 31:3 (1986), 618–619

[15] Pavlov A. I., “O chisle podstanovok s dlinami tsiklov iz zadannogo mnozhestva”, Diskretn. matem., 3:3 (1991), 109–123 | MR

[16] Pavlov A. I., “O dvukh klassakh podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Matem. zametki, 62:6 (1997), 881–891 | MR | Zbl

[17] Sachkov V. N., “Otobrazheniya konechnogo mnozhestva s ogranicheniyami na kontury i vysotu”, Teoriya veroyatn. i ee primen., 17:4 (1972), 679–694 | MR | Zbl

[18] Sachkov V. N., “Sluchainye otobrazheniya ogranichennoi vysoty”, Teoriya veroyatn. i ee primen., 18:1 (1973), 122–132 | Zbl

[19] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, M., 1977, 319 pp.

[20] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978, 287 pp. | MR | Zbl

[21] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, M., 1985, 141 pp. | MR | Zbl

[22] Yakymiv A. L., “Raspredelenie dliny $m$-go maksimalnogo tsikla sluchainoi $A$-podstanovki”, Diskretnaya matem., 17:4 (2005), 40–58 | MR | Zbl

[23] Yakymiv A. L., Veroyatnostnye prilozheniya tauberovykh teorem, Fizmatlit, M., 2005, 256 pp. | Zbl

[24] Yakymiv A. L., “Predelnaya teorema dlya obschego chisla tsiklov sluchainoi $A$-podstanovki”, Teoriya veroyatn. i ee primen., 52:1 (2007), 69–83 | MR

[25] Yakymiv A. L., “Sluchainye $A$-podstanovki: skhodimost k puassonovskomu protsessu”, Matem. zametki, 81:6 (2007), 939–947 | MR | Zbl