login
Number of ways to arrange the numbers 1..n in a circle (up to direction) such that every two adjacent numbers are relatively prime.
7

%I #19 Oct 16 2023 12:05:05

%S 1,1,2,2,12,4,72,72,720,576,22032,7776,476928,400896,6352992,8515584,

%T 805146624,279023616,36481536000,23627980800,881012367360,

%U 1065509240832,192859121664000,65362194432000,10489384048435200,12214493322854400,981016943829811200,937734333109862400,268367392739686809600

%N Number of ways to arrange the numbers 1..n in a circle (up to direction) such that every two adjacent numbers are relatively prime.

%C a(n) is also the number of permutations of 2..n such that every two adjacent numbers are relatively prime.

%F For prime p, a(p)=A076220(p-1). - _Max Alekseyev_, Jun 13 2005

%e a(6) = 4 since there are 4 ways to arrange 1,2,3,4,5,6 in a circle such that every two adjacent numbers are relatively prime: 1-2-3-4-5-6-1, 1-4-3-2-5-6-1, 1-6-5-2-3-4-1, 1-6-5-4-3-2-1.

%o (PARI) { A086595(n) = my(d, A, r, M); A=matrix(n,n,i,j,gcd(i,j)==1); r=0; forstep(s=1,2^n-1,2, M=vecextract(A,s,s)^n; d=matsize(M)[1]; r+=(-1)^(n-d)*M[1,1]); r } /* _Max Alekseyev_, Jun 13 2005 */

%Y Cf. A076220.

%K nonn

%O 1,3

%A _Lior Manor_, Jul 23 2003

%E a(15) and a(16) from _Ray Chandler_ and _Joshua Zucker_, Apr 10 2005

%E a(17)-a(29) from _Max Alekseyev_, Jun 13 2005, Jul 05 2014