A106366 Number of necklaces with n beads of 4 colors, no 2 adjacent beads the same color.

4, 6, 8, 24, 48, 130, 312, 834, 2192, 5934, 16104, 44368, 122640, 341802, 956632, 2690844, 7596480, 21524542, 61171656, 174342216, 498112272, 1426419858, 4093181688, 11767920118, 33891544416, 97764131646, 282429537944

Offset: 1

Author

Christian G. Bower, Apr 29 2005

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Index entries for sequences related to necklaces

Crossrefs

Column 4 of A208535.

Cf. A000031, A001868, A226493.

Programs

Mathematica

a[n_] := If[n==1, 4, Sum[EulerPhi[n/d]*(3*(-1)^d+3^d), {d, Divisors[n]}]/n ];
Array[a, 35] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

PARI

a(n) = if(n==1, 4, sumdiv(n, d, eulerphi(n/d)*(3*(-1)^d + 3^d))/n); \\ Andrew Howroyd, Oct 14 2017

Formula

CycleBG transform of (4, 0, 0, 0, ...)

CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.

Carlitz transform T(A(x)) has g.f. 1/(1-Sum_{k>0} (-1)^(k+1)*A(x^k)).

a(n) = (1/n) * Sum_{d | n} totient(n/d) * (3*(-1)^d + 3^d) for n > 1. - Andrew Howroyd, Mar 12 2017