Permutations with Arithmetic Constraints

Let S lcm ( n ) $$S_{\mathrm {lcm}}(n)$$ denote the set of permutations π $$\pi $$ of [ n ] = { 1 , 2 , … , n } $$[n]=\{1,2,\dots ,n\}$$ such that lcm [ j , π ( j ) ] ≤ n $$\mathrm {lcm}[j,\pi (j)]\le n$$ for each j ∈ [ n ] $$j\in [n]$$ . Further, let S div ( n ) $$S_{\mathrm {div}}(n)$$ denote the number of permutations π $$\pi $$ of [ n ] $$[n]$$ such that j ∣ π ( j ) $$j\mid \pi (j)$$ or π ( j ) ∣ j $$\pi (j)\mid j$$ for each j ∈ [ n ] $$j\in [n]$$ . Clearly S div ( n ) ⊂ S lcm ( n ) $$S_{\mathrm {div}}(n)\subset S_{\mathrm {lcm}}(n)$$ . We get upper and lower bounds for the counts of these sets, showing they grow geometrically. We also prove a conjecture from a recent paper on the number of “anti-coprime” permutations of [ n ] $$[n]$$ , meaning that each gcd ( j , π ( j ) ) > 1 $$\gcd (j,\pi (j))>1$$ except when j = 1 $$j=1$$ .