|
Search: id:A076220
|
|
|
| A076220 |
|
Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime. |
|
+0
11
|
|
| 1, 2, 6, 12, 72, 72, 864, 1728, 13824, 22032, 555264, 476928, 17625600, 29599488, 321115392, 805146624, 46097049600, 36481536000, 2754120268800, 3661604352000, 83905105305600, 192859121664000, 20092043520000000, 15074060547686400
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
FORMULA
|
a(p-1)=A086595(p) for prime p. - Max Alekseyev (maxale(AT)gmail.com), Jun 12 2005
|
|
EXAMPLE
|
a(4) = 12 since there are 12 permutations of 1234 in which every 2 adjacent numbers are relatively prime: 1234, 1432, 2134, 2143, 2314, 2341, 3214, 3412, 4123, 4132, 4312, 4321
|
|
MAPLE
|
with (combinat): for n from 1 to 7 do P:=permute(n): ct:=0: for j from 1 to n! do if add(gcd(P[j][i+1], P[j][i]), i=1..n-1)=n-1 then ct:=ct+1 else ct:=ct fi od: a[n]:=ct: od: seq(a[n], n=1..7); (Deutsch)
|
|
MATHEMATICA
|
f[n_] := Block[{p = Permutations[ Table[i, {i, 1, n}]], c = 0, k = 1}, While[k < n! + 1, If[ Union[ GCD @@@ Partition[p[[k]], 2, 1]] == {1}, c++ ]; k++ ]; c]; Do[ Print[ f[n]], {n, 2, 15}]
|
|
PROGRAM
|
(PARI) {A076220(n)=local(A, d, n, r, M); A=matrix(n, n, i, j, if(gcd(i, j)==1, 1, 0)); r=0; for(s=1, 2^n-1, M=vecextract(A, s, s)^(n-1); d=matsize(M)[1]; r+=(-1)^(n-d)*sum(i=1, d, sum(j=1, d, M[i, j]))); r} (Alekseyev)
|
|
CROSSREFS
|
Cf. A086595.
Sequence in context: A106037 A136240 A090747 this_sequence A107763 A166470 A144144
Adjacent sequences: A076217 A076218 A076219 this_sequence A076221 A076222 A076223
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Lior Manor (lior.manor(AT)gmail.com) Nov 04 2002
|
|
EXTENSIONS
|
Extended by Frank Ruskey (fruskey(AT)cs.uvic.ca), Nov 11 2002
a(15)=321115392 and a(16)=805146624 from Ray Chandler (rayjchandler(AT)sbcglobal.net) and Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Apr 10 2005
Many further terms from Max Alekseyev (maxale(AT)gmail.com), Jun 12 2005
|
|
|
Search completed in 0.002 seconds
|
