Graph explorer

Coprime permutations

Let $C(n)$ denote the number of permutations $σ$ of $[n]=\{1,2,\dots,n\}$ such that $\gcd(j,σ(j))=1$ for each $j\in[n]$. We prove that for $n$ sufficiently large, $n!/3.73^n < C(n) < n!/2.5^n$.