RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 3, Pages 99–109 (Mi mvk38)

Computing the distribution of a combinatorial statistics defined on permutations of a given multiset

D. V. Shuvaev

TVP Laboratory, Moscow

Abstract: 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.

Key words: number of readings, Markov chain.

UDC: 519.12+519.1+519.21

Received 10.V.2011

DOI: 10.4213/mvk38



© Steklov Math. Inst. of RAS, 2024