A106365 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,1

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

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). - Azuma Seiichi, Oct 25 2014

a(n) = -1+(-1)^n+A000031(n) (n>1). - Azuma Seiichi, 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)

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 *)

Prog

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

Crossrefs

Column 3 of A208535.

Cf. A000031, A001867.

Sequence in context: A264756 A267942 A147994 * A200174 A266153 A086636

Adjacent sequences: A106362 A106363 A106364 * A106366 A106367 A106368

Keyword

nonn

Author

Christian G. Bower, Apr 29 2005

Status

approved