On permutations with cycle lengths from a random set

A. L. Yakymiv

Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 53-62.

Résumé

Let $\xi_1,\dots,\xi_n,\dots $ be a sequence of independent Bernoulli random variables which take the value 1 with probability $\sigma\in (0,1]$. Given this sequence, we construct the random set $A\subseteq\mathbf N=\{1,2,3,\dots\}$ as follows: a number $n\in\mathbf N$ is included in $A$ if and only if $\xi_n=1$. Let $T_n=T_n(A)$ denote the set of the permutations of degree $n$ whose cycle lengths belong to the set $A$. In this paper, we find the asymptotic behaviour of the number of elements of the set $T_n(A)$ as $n\to\infty$. For any fixed $A$, the uniform distribution is defined on $T_n(A)$. Under these hypotheses, limit theorems are obtained for the total number of cycles and the number of cycles of a fixed length in a random permutation in $T_n(A)$. Similar problems were earlier solved for various classes of deterministic sets $A$. This research was supported by the Russian Foundation for Basic Research, grants 00–15–96136 and 00–01–00090.

Bibliographie

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

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

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

[4] Kolchin A. V., Summy nezavisimykh sluchainykh velichin i nekotorye kombinatornye zadachi, Kand. dissertatsiya, MGU, Moskva, 1994 | MR

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

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

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

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

[9] Pavlov A. I., “O chisle podstanovok s dlinami tsiklov iz zadannogo mnozhestva”, Diskretnaya matematika, 3:3 (1991), 109–123

[10] Pavlov A. I., “O chisle podstanovok s konechnym mnozhestvom dlin tsiklov”, Trudy Matem. in-ta im. V. A. Steklova, 207, 1994, 256–267 | Zbl

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

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

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

[14] Yakymiv A. L., “O sluchainykh podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Veroyatnostnye protsessy i ikh primeneniya, 24–27, MIEM, Moskva

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

[16] Grusho A. A., “Properties of random permutations with constrains on the maximum cycle length”, Proc. Third Intern. Petrozavodsk Conf. on Probab., Methods in Discrete Math., 1993, 459–469 | MR

[17] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, Moskva, 1985 | MR | Zbl