A106365 Number of necklaces with n beads of 3 colors, no 2 adjacent beads the same color.

3, 3, 2, 6, 6, 14, 18, 36, 58, 108, 186, 352, 630, 1182, 2190, 4116, 7710, 14602, 27594, 52488, 99878, 190746, 364722, 699252, 1342182, 2581428, 4971066, 9587580, 18512790, 35792568, 69273666, 134219796, 260301174, 505294128, 981706830

Offset: 1

Author

Christian G. Bower, Apr 29 2005

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform
• Index entries for sequences related to necklaces

Crossrefs

Column 3 of A208535.

Cf. A000031, A001867.

Programs

Mathematica

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

PARI

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

Formula

CycleBG transform of (3, 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 divides n} phi(n/d)*A092297(d) (n>1). - Seiichi Azuma, Oct 25 2014

a(n) = -1+(-1)^n+A000031(n) (n>1). - Seiichi Azuma, Oct 25 2014 [Corrected by Petros Hadjicostas, Feb 16 2018.]

From Petros Hadjicostas, Feb 16 2018: (Start)

General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = 3*x.)

G.f.: Sum_{n>=1} a(n)*x^n = 3*x - 2*x/(1-x^2) - Sum_{n>=1} (phi(n)/n)*log(1-2*x^n) = 3*x - Sum_{n>=1} (phi(n)/n)*(2*log(1+x^n) + log(1-2*x^n)).

(End)