Geodesic
Computing the distribution of a combinatorial statistics defined on permutations of a given multiset
Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 3, pp. 99-109 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For a finite integer sequence $\alpha$ we consider the number $X(\alpha)$ of readings of $\alpha$ from left to right necessary to count all elements of the sequence in a nondecreasing order. We describe a method to calculate the distribution of $X(\alpha)$ exactly when $\alpha$ is uniformly distributed on the set of all permutations of $n$ given numbers. 
@article{MVK_2011_2_3_a4,
     author = {D. V. Shuvaev},
     title = {Computing the distribution of a~combinatorial statistics defined on permutations of a~given multiset},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {99--109},
     year = {2011},
     volume = {2},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a4/}
}
TY  - JOUR
AU  - D. V. Shuvaev
TI  - Computing the distribution of a combinatorial statistics defined on permutations of a given multiset
JO  - Matematičeskie voprosy kriptografii
PY  - 2011
SP  - 99
EP  - 109
VL  - 2
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a4/
LA  - ru
ID  - MVK_2011_2_3_a4
ER  - 
%0 Journal Article
%A D. V. Shuvaev
%T Computing the distribution of a combinatorial statistics defined on permutations of a given multiset
%J Matematičeskie voprosy kriptografii
%D 2011
%P 99-109
%V 2
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a4/
%G ru
%F MVK_2011_2_3_a4
D. V. Shuvaev. Computing the distribution of a combinatorial statistics defined on permutations of a given multiset. Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 3, pp. 99-109. http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a4/

[1] Vatutin V. A., “Predelnye teoremy dlya chisla otrezkov vozrastaniya v sluchainykh perestanovkakh, porozhdaemykh algoritmami sortirovki”, Diskretnaya matematika, 6:1 (1994), 83–99 | MR | Zbl

[2] Vatutin V. A., Mikhailov V. G., “O chisle chtenii sluchainykh neravnoveroyatnykh failov pri ustoichivoi sortirovke”, Diskretnaya matematika, 8:2 (1996), 14–30 | MR | Zbl

[3] Knut D., Iskusstvo programmirovaniya, v. 3, Sortirovka i poisk, Vilyams, M., 2000

[4] Riordan Dzh., Vvedenie v kombinatornyi analiz, Izd-vo inostrannoi literatury, M., 1963

[5] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, M., 2004

[6] Eiler L., Differentsialnoe ischislenie, GITTL, M., 1949

[7] Carlitz L., Roselle D. P., Scoville R., “Permutations and sequences with repetitions by number of increases”, J. Comb. Theory, 1 (1966), 350–374 | DOI | MR | Zbl

[8] Dilon J. F., Roselle D. R., “Simon Newcomb's problem”, SIAM J. Appl. Math., 17:6 (1969), 1086–1093 | DOI | MR

[9] Foata D., “Distributions eulériennes et mahoniennes sur le groupe des permutations”, Higher combinatorics, Proc. NATO Adv. Study Inst. (Berlin, 1976), ed. M. Aigner, D. Reidel, Amsterdam, 1977, 27–49 ; Foata D., “Raspredeleniya tipa Eilera i tipa Makmagona na gruppe perestanovok”, Problemy kombinatornogo analiza, 19, Mir, M., 1980, 120–141 | MR

[10] Fu J. C., Koutras M. V., “Distribution theory of runs: A Markov chain approach”, J. Amer. Statist. Assoc., 89 (1994), 1050–1058 | DOI | MR | Zbl

[11] Fu J. C., Lou W. Y. W., “Exact and limiting distributions of the number of successions in a random permutation”, Ann. Inst. Statist. Math., 47:3 (1995), 435–446 | MR

[12] Fu J. C., Lou W. Y. W., “Joint distributions of rises and falls”, Ann. Inst. Statist. Math., 52:3 (2000), 415–425 | DOI | MR | Zbl

[13] Fu J. C., Lou W. Y. W., Wang Y.-J., “On exact distributions of Eulerian and Simon Newcomb numbers associated witn random permutations”, Stat. and Probab. Letters, 42 (1999), 115–125 | DOI | MR | Zbl

[14] Fu J. C., Lou W. Y. W., Distribution theory of runs and patterns and its application. A finite Markov chain imbedding approach, World Scientific Publishing Co. Pte. Ltd., Singapore, 2003 | MR

[15] Johnson C. B., “The distribution of 2-sequences in random permutations of arbitrary multi-sets”, Stat. and Probab. Lett., 59 (2002), 67–74 | DOI | MR | Zbl

[16] Rawlings D., “Enumerations of permutations by descends, indescends, imajor index, and basic components”, J. Comb. Theory Ser. A, 36 (1984), 1–14 | DOI | MR | Zbl

[17] Wolfowitz J., “Asymptotic distribution of runs up and down”, Ann. Math. Statist., 15:2 (1944), 163–172 | DOI | MR | Zbl