Limit theorem for the general number of cycles in a random $A$-permutation

A. L. Yakymiv

Teoriâ veroâtnostej i ee primeneniâ, Tome 52 (2007) no. 1, pp. 69-83

Résumé

Let $S_n$ be the symmetric group of all permutations of degree $n, A$ be some nonempty subset of the set of natural numbers $N$, and let $T_n=T_n(A)$ be the set of all permutations from $S_n$ with cycle lengths from $A$. The permutations from $T_n$ are called $A$-permutations. Let $\zeta_n$ be the general number of cycles in a random permutation uniformly distributed on $T_n$. In this paper, we find the way to prove the limit theorem for $\zeta_n$ starting with the asymptotics of $|T_n|$. The limit theorem obtained here is new in a number of cases when the asymptotics of $|T_n|$ is known but the limit theorem for $\zeta_n$ has not yet been proven by other methods. As has been noted by the author, $|T_n|/n!$ is the Karamata regularly varying function with index $\sigma-1$, where $\sigma>0$ is the density of the set $A$, in a number of papers of different authors. Proof of the limit theorem for $\zeta_n$ is the main goal of this paper, assuming none of the additional restrictions typical of previous investigations.

Détail

Keywords: asymptotic density of the set $A$, logarithmic density of the set $A$, general number of cycles in random $A$-permutation, regularly varying functions, slowly varying functions, Tauberian theorem.
Mots-clés : random $A$-permutations

Bibliographie

[1] 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

[2] Bolotnikov Yu. V., Sachkov V. N., Tarakanov V. E., “O nekotorykh klassakh sluchainykh velichin na tsiklakh podstanovok”, Matem. sb., 108(150):1 (1979), 91–104 | MR | Zbl

[3] Bender E. A., “Asimptoticheskie metody v teorii perechislenii”, Perechislitelnye zadachi kombinatornogo analiza, Mir, M., 1979, 266–310

[4] Volynets L. M., “Chislo reshenii uravneniya v simmetricheskoi gruppe”, Veroyatnostnye protsessy i ikh prilozheniya, MIEM, M., 1985, 104–109

[5] Volynets L. M., “O chisle reshenii uravneniya $x^s=e$ v simmetricheskoi gruppe”, Matem. zametki, 40:2 (1986), 155–160 | MR | Zbl

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

[7] Grusho A. A., “Properties of random permutations with constrains on the maximum cycle length”, Proceedings of the Third Petrozavodsk Conference on Probabilistic Methods in Discrete Mathematics (Petrozavodsk, 1992), Progr. Pure Appl. Discrete Math., 1, TVP/VSP, Moscow/Utrecht, 1993, 60–63 | MR | Zbl

[8] Ivchenko G. I., Medvedev Yu. I., “O sluchainykh podstanovkakh”, Trudy po diskretnoi matematike, 5, Fizmatlit, M., 2002, 73–92

[9] Kolchin A. V., “Uravneniya, soderzhaschie neizvestnuyu podstanovku”, Diskretn. matem., 6:1 (1994), 100–115 | MR | Zbl

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

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

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

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

[14] Manstavičius E., “On random permutations without cycles of some lengths”, Period. Math. Hungar., 42:1–2 (2001), 37–44 | DOI | MR | Zbl

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

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

[17] Pavlov A. I., “O chisle i tsiklovoi strukture podstanovok nekotorykh klassov”, Matem. sb., 124:4 (1984), 536–556 | MR | Zbl

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

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

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

[21] Pavlov A. I., “O chisle podstanovok s konechnym mnozhestvom dlin tsiklov”, Tr. MIRAN, 207, 1994, 256–267 | MR | Zbl

[22] Pavlov A. I., “Asimptotika chisla podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Dokl. RAN, 335:5 (1994), 556–559 | MR | Zbl

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

[24] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971, 416 pp. | MR

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

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

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

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

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

[30] Shepp L. A., Lloyd S. P., “Ordered cycle lengths in a random permutation”, Trans. Amer. Math. Soc., 121:2 (1966), 340–357 | DOI | MR | Zbl

[31] Timashev A. N., “Predelnye teoremy v skhemakh razmeschenii chastits po razlichnym yacheikam s ogranicheniyami na zapolneniya yacheek”, Teoriya veroyatn. i ee primen., 49:4 (2004), 712–725 | MR

[32] Yakymiv A. L., “O chisle $A$-podstanovok”, Matem. sb., 180:2 (1989), 294–303 | MR | Zbl

[33] Yakymiv A. L., “O podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Diskretn. matem., 1:1 (1989), 125–134 | MR

[34] Yakymiv A. L., “O sluchainykh podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Veroyatnostnye protsessy i ikh prilozheniya, MIEM, M., 1991, 24–27

[35] Yakymiv A. L., “O nekotorykh klassakh podstanovok s dlinami tsiklov iz zadannogo mnozhestva”, Diskretn. matem., 4:3 (1992), 128–134 | MR | Zbl

[36] Yakymiv A. L., “Limit theorems for random $A$-permutations”, Proceedings of the Third Petrozavodsk Conference on Probabilistic Methods in Discrete Mathematics (Petrozavodsk, 1992), Progr. Pure Appl. Discrete Math., 1, TVP/VSP, Moscow/Utrecht, 1993, 459–469 | MR | Zbl

[37] Yakymiv A. L., “O podstanovkakh s dlinami tsiklov iz sluchainogo mnozhestva”, Diskretn. matem., 12:4 (2000), 53–62 | MR | Zbl

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

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