Coprime permutations

Abstract

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