Coprime Permutations

2022/03/07 by Carl Pomerance, Pomerance, Carl
Computer Science · Mathematics · #11A25 #11B75 #11N60 #Analytic Number Theory Research #Bayesian Methods and Mixture Models #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2203.03085

openalex publication_date 2022/03/07 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28

Abstract

Let C(n) denote the number of permutations σ of [n]=\1,2,…,n\ such that gcd(j,σ(j))=1 for each j∈[n]. We prove that for n sufficiently large, n!/3.73ⁿ < C(n) < n!/2.5ⁿ.

Related

• Enumerating coprime permutations
• Permutations with arithmetic constraints
• On counting permutations by pairs of congruence classes of major index
• Permutations containing and avoiding certain patterns
• Counting occurences of 132 in a permutation