RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2014 Volume 26, Issue 4, Pages 110–118 (Mi dm1309)

On the probability of coincidence of cycle lengths for independent random permutations with given number of cycles

A. N. Timashev

Institute of Cryptography, Communications and Informatics, Academy of Federal Security Service of Russian Federation, Moscow

Abstract: From the set of all permutations of the degree $n$ with a given number $ N \le n $ of cycles two permutations are choosed randomly, uniformly and independently. The cycles of each permutation are numbered in some of $N!$ possible ways. We study the coincidence probability of the cycle lengths of permutations for a given numbering. This probability up to a suitably selected renumbering of cycles of the first permutation equals to the probability of similarity of these permutations. The asymptotic estimates of the coincidence probability of the cycle lengths are obtained for five types of relations between $N,n\to\infty$.

Keywords: coincidence probability, cycle lengths, random permutations, generalized scheme of random allocations, Stirling numbers of the first kind.

UDC: 519.212.2

Received: 01.04.2014

DOI: 10.4213/dm1309


 English version:
Discrete Mathematics and Applications, 2015, 25:6, 385–392

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025