On asymptotic expansions for the distribution of the number of cycles in a random permutation

A. N. Timashev

Diskretnaya Matematika, Tome 15 (2003) no. 3, pp. 117-127.

Résumé

We obtain explicit formulas for the coefficients of asymptotic expansions in the domain of large deviations for the distributions of the number of cycles $\nu_n$ in a random permutation of degree $n$, that is, for the probability $\mathsf P\{\nu_n=N\}$ under the condition that $n,N\to\infty$ in such a way that $1\alpha_0\le\alpha=n/N\le\alpha_1\infty$, where $\alpha_0$, $\alpha_1$ are constants. These formulas express the coefficients in terms of cumulants of the random variable which has the distribution of the logarithmic series with specially chosen parameter. For the cumulants of the third and fourth orders we give the corresponding values. We discuss the accuracy of the obtained approximations. If $n,N\to\infty$ so that $0\gamma_0\le\gamma=N/\ln n\le\gamma_1\infty$, where $\gamma_0$, $\gamma_1$ are constants, we give asymptotic estimates of the probabilities $\mathsf P\{\nu_n=N\}$, $\mathsf P\{\nu_n\le N\}$, $\mathsf P\{\nu_n\ge N\}$ with the remainder terms of order $O((\ln n)^{-2})$ uniform in $\gamma\in[\gamma_0, \gamma_1]$. The corresponding estimate for the probability $\mathsf P\{\nu_n=N\}$ refines the previously known results for the case $N=\beta\ln n+o(\ln n)$, where $\beta$ is a positive constant.

Bibliographie

[1] Riordan Dzh., Vvedenie v kombinatornyi analiz, IL, Moskva, 1963

[2] Kolchin V. F., Sluchainye grafy, Nauka, Moskva, 2000 | MR

[3] Good I. J., “An asymptotic formula for the differences of the powers at zero”, Ann. Math. Statist., 32:1 (1961), 249–256 | DOI | MR | Zbl

[4] Timashëv A. N., “Ob asimptoticheskikh razlozheniyakh dlya chisel Stirlinga 1-go i 2-go roda”, Diskretnaya matematika, 10:3 (1998), 148–159 | MR

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

[6] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, Moskva, 1976 | MR | Zbl

[7] Petrov V. V., Summy nezavisimykh sluchainykh velichin, Nauka, Moskva, 1972 | MR

[8] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1977

[9] Timashëv A. N., “Ob asimptoticheskikh razlozheniyakh v lokalnykh predelnykh teoremakh v ravnoveroyatnykh skhemakh razmescheniya chastits po razlichnym yacheikam”, Diskretnaya matematika, 12:1 (2000), 60–69 | MR

[10] Evgrafov M. A., Asimptoticheskie otsenki i tselye funktsii, Fizmatlit, Moskva, 1962 | MR

[11] Olver F., Vvedenie v asimptoticheskie metody i spetsialnye funktsii, Nauka, Moskva, 1978 | MR

[12] Beitmen G., Erdeii A., Vysshie transtsendentnye funktsii. Gipergeometricheskaya funktsiya. Funktsii Lezhandra, Nauka, Moskva, 1973

[13] Pavlov Yu. L., “O sluchainykh otobrazheniyakh s ogranicheniyami na chislo tsiklov”, Trudy Matem. in-ta im. V. A. Steklova, 177, 1986, 122–132 | MR | Zbl

[14] Pavlov A. I., “Lokalnye teoremy dlya chisla komponent v sluchainykh podstanovkakh i otobrazheniyakh”, Teoriya veroyatnostei i ee primeneniya, 33:1 (1988), 196–200

[15] Volynets L. M., “Otsenka skorosti skhodimosti k predelnomu raspredeleniyu dlya chisla tsiklov v sluchainoi podstanovke”, Veroyatnostnye zadachi diskretnoi matematiki, MIEM, Moskva, 1987, 40–46 | MR

[16] Timashëv A. N., “Sluchainye razbieniya mnozhestv s izvestnym chislom blokov”, Diskretnaya matematika, 15:2 (2003), 138–148 | MR | Zbl