Permutations with equal orders
Open Access
- 27 January 2021
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 30 (5) , 800-810
Abstract
Let ${\mathbb{P}}(ord\pi = ord\pi ')$ be the probability that two independent, uniformly random permutations of [n] have the same order. Answering a question of Thibault Godin, we prove that ${\mathbb{P}}(ord\pi = ord\pi ') = {n^{ - 2 + o(1)}}$ and that ${\mathbb{P}}(ord\pi = ord\pi ') \ge {1 \over 2}{n^{ - 2}}lg*n$ for infinitely manyn. (Herelg*nis the height of the tallest tower of twos that is less than or equal ton.)
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- An analogue to Dixon's theorem for automaton groups2017
- Analytic Combinatorics in Several Variables2013
- Estimation Problems and Randomised Group Algorithms2012
- New software for computing asymptotics of multivariate generating functionsACM Communications in Computer Algebra, 2012
- On permutations of order dividing a given integerJournal of Algebraic Combinatorics, 2007
- Applications of the theory of records in the study of random treesActa Informatica, 1988
- The asymptotics of 𝑒^{𝑃(𝑧)} and the number of elements of each order in 𝑆_{𝑛}Bulletin of the American Mathematical Society, 1986
- Über die Anzahl der Lösungen vonx n = 1 in der symmetrischen GruppeS nArchiv der Mathematik, 1978
- On some problems of a statistical group-theory. IVActa Mathematica Hungarica, 1968
- On some problems of a statistical group-theory. IIIActa Mathematica Hungarica, 1967