Enumerating coprime permutations

2022/03/11 by Ashwin Sah, Mehtaab Sawhney, Sah, Ashwin +1
Computer Science · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2203.06268

openalex publication_date 2022/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Define a permutation σ to be coprime if gcd(m,σ(m)) = 1 for m∈[n]. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on [n] is n!⋅ (c+o(1))ⁿ where c = ∏_{p prime} \frac(p-1)^2(1-1/p)p⋅ (p-2)^(1-2/p). The techniques involve entropy maximization for the upper bound, and a mixture of number-theoretic bounds, permanent estimates, and the absorbing method for the lower bound.

Related

• Coprime Permutations
• Permutations with arithmetic constraints
• Permutations with orders coprime to a given integer
• Refining enumeration schemes to count according to permutation statistics
• Six bijections between deco polyominoes and permutations