Enumerating coprime permutations

DOI10.1112/MTK.12159MaRDI QIDQ6074974zbMATH OpenOpenAlexFDO

Authors Ashwin Sah, Mehtaab Sawhney

Publication date 20 September 2023

Published in Mathematika (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2203.06268

Mathematics Subject Classification ID

Other combinatorial number theory (11B75)

Abstract: Define a permutation $sigma$ to be coprime if $gcd(m,sigma(m))=1$ for $min[n]$. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on $[n]$ is $n!cdot(c+o(1){)}^n$ where [c = prod_{p ext{ prime }}frac{(p-1)^{2(1-1/p)}}{pcdot (p-2)^{(1-2/p)}}.] The techniques involve entropy maximization for the upper bound, and a mixture of number-theoretic bounds, permanent estimates, and the absorbing method for the lower bound.

Cites work

• Coprime matchings
• Coprime permutations
• Counting designs
• scientific article; zbMATH DE number 3467229 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3801730 (Why is no real title available?)
• scientific article; zbMATH DE number 3026527 (Why is no real title available?)
• Perfect matchings in \(\varepsilon\)-regular graphs
• Proof of D. J. Newman's coprime mapping conjecture
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Spanning trees in random graphs
• The combinatorial interpretation of the Jacobi identity from Lie algebras

Cited in

(4)

• Enumerating Nondegenerate Permutations
• Coprime permutations
• Permutations and the divisor graph of [1,n]
• The structure of lonely runner spectra

This page was built for publication: Enumerating coprime permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074974)