A109813 Number of permutations of (the positive integers <= n and coprime to n), where each element of the permutations is coprime to its adjacent elements.

1, 1, 2, 2, 12, 2, 72, 24, 144, 12, 22032, 24, 476928, 480, 1728, 9600, 805146624, 720, 36481536000, 30240, 1728000, 312000, 192859121664000, 40320, 2159795404800, 46293120, 249684249600, 58423680

Offset

1,3

Comments

Sequence continues: a(29) = ?, 40320, ?, 1893397524480, 32006016000000, 478511953920, ?, 209018880, ?, 122634632171520, ?, 665481277440, ?, 399168000. - Franklin T. Adams-Watters, Sep 25 2006

Links

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

Example

The integers coprime to 10 and <= 10 are (1,3,7,9).
Of the permutations of these integers, there are 12 permutations where all adjacent terms are coprime, i.e., where 3 and 9 are not adjacent. So the 10th term of the sequence is 12.

Prog

(PARI) {A109813(x)=local(v, A, d, r, M, i, j); n=eulerphi(x); v=vector(n, i, 0); j=0; for(i=1, x, if(gcd(i, x)==1, j++; v[j]=i)); A=matrix(n, n, i, j, gcd(v[i], v[j])==1); 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} \\ Franklin T. Adams-Watters, Sep 25 2006

Crossrefs

Cf. A076220.

Sequence in context: A286152 A243306 A128269 * A241519 A353767 A288339

Adjacent sequences: A109810 A109811 A109812 * A109814 A109815 A109816

Keyword

more,nonn

Author

Leroy Quet, Aug 16 2005

Extensions

More terms from Franklin T. Adams-Watters, Sep 25 2006

Status

approved