Permutations and the divisor graph of [1,n]

2022/07/20 by Nathan McNew, McNew, Nathan
Computer Science · Mathematics · #05A05 #05A16 #05C38 #11A05 #11B75 #11N45 #Algebraic Geometry and Number Theory #Analytic Number Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2207.09652

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

Abstract

Let S_{\rm div}(n) denote the set of permutations π of n such that for each 1≤ j ≤ n either j | π(j) or π(j) | j. These permutations can also be viewed as vertex-disjoint directed cycle covers of the divisor graph D_[1,n] on vertices v₁, …, v_n with an edge between v_i and v_j if i| j or j | i. We improve on recent results of Pomerance by showing c_d = lim_{n → ∞} (# S_{\rm div}(n))^1/n exists and that 2.069

Related

• Permutations with arithmetic constraints
• Enumerating cycles in the graph of overlapping permutations
• Divisor graphs have arbitrary order and size
• On some properties of the number of permutations being products of pairwise disjoint d-cycles
• Etude du graphe divisoriel 6