Permutations with equal orders. (27th September 2021)

• Record Type: Journal Article
• Authors: Acan, Huseyin; Burnette, Charles; Eberhard, Sean; Schmutz, Eric; Thomas, James
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 5(2021)
• Page Start: 800
• Page End: 810
• Publication Date: 2021-09-27
• Subjects: 60C05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000043
• Languages: English
• ISSNs: 0963-5483

Abstract

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 many n . (Here lg * n is the height of the tallest tower of twos that is less than or equal to n .)