|
Search: id:A086595
|
|
|
| A086595 |
|
Number of ways to arrange the numbers 1..n in a circle such that every two adjacent numbers are relatively prime. |
|
+0
6
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
a(n) is also the number of permutations of 2..n such that every two adjacent numbers are relatively prime.
|
|
FORMULA
|
For prime p, a(p)=A076220(p-1) - Max Alekseyev (maxale(AT)gmail.com), 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.
|
|
PROGRAM
|
(PARI) {A086595(n) = local(d, A, r, M); A=matrix(n, n, i, j, if(gcd(i, j)==1, 1, 0)); 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} (Alekseyev)
|
|
CROSSREFS
|
Cf. A076220.
Sequence in context: A058044 A128269 A109813 this_sequence A013605 A073768 A096855
Adjacent sequences: A086592 A086593 A086594 this_sequence A086596 A086597 A086598
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Lior Manor (lior.manor(AT)gmail.com) Jul 23 2003
|
|
EXTENSIONS
|
a(15)=6352992 and a(16)=8515584 from Ray Chandler (rayjchandler(AT)sbcglobal.net) and Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Apr 10 2005
Many more terms from Max Alekseyev (maxale(AT)gmail.com), Jun 13 2005
|
|
|
Search completed in 0.002 seconds
|
