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

1, 1, 2, 2, 12, 4, 72, 72, 720, 576, 22032, 7776, 476928, 400896, 6352992, 8515584, 805146624, 279023616, 36481536000, 23627980800, 881012367360, 1065509240832, 192859121664000, 65362194432000, 10489384048435200, 12214493322854400, 981016943829811200, 937734333109862400, 268367392739686809600

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..29.

Formula

For prime p, a(p)=A076220(p-1). - Max Alekseyev, Jun 13 2005

Example

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.

Prog

(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 */

Crossrefs

Cf. A076220.

Sequence in context: A353767 A288339 A288808 * A279718 A279671 A279179

Adjacent sequences: A086592 A086593 A086594 * A086596 A086597 A086598

Keyword

nonn

Author

Lior Manor, Jul 23 2003

Extensions

a(15) and a(16) from Ray Chandler and Joshua Zucker, Apr 10 2005

a(17)-a(29) from Max Alekseyev, Jun 13 2005, Jul 05 2014

Status

approved