A106365 - OEIS

%I #30 Jul 06 2018 08:50:59

%S 3,3,2,6,6,14,18,36,58,108,186,352,630,1182,2190,4116,7710,14602,

%T 27594,52488,99878,190746,364722,699252,1342182,2581428,4971066,

%U 9587580,18512790,35792568,69273666,134219796,260301174,505294128,981706830

%N Necklaces with n beads of 3 colors, no 2 adjacent beads the same color.

%H Andrew Howroyd, <a href="/A106365/b106365.txt">Table of n, a(n) for n = 1..500</a>

%H Petros Hadjicostas, <a href="/A106365/a106365.pdf">Proof of an explicit formula for Bower's CycleBG transform</a>

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F CycleBG transform of (3, 0, 0, 0, ...)

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

%F Carlitz transform T(A(x)) has g.f. 1/(1-sum(k>0, (-1)^(k+1)*A(x^k))).

%F a(n) = (1/n)*sum_{d divides n} phi(n/d)*A092297(d) (n>1). - _Azuma Seiichi_, Oct 25 2014

%F a(n) = -1+(-1)^n+A000031(n) (n>1). - _Azuma Seiichi_, Oct 25 2014 [Corrected by _Petros Hadjicostas_, Feb 16 2018.]

%F From _Petros Hadjicostas_, Feb 16 2018: (Start)

%F 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.)

%F 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)).

%F (End)

%t a[n_] := If[n==1, 3, Sum[EulerPhi[n/d]*(2*(-1)^d+2^d), {d, Divisors[n]}]/n ];

%t Array[a, 35] (* _Jean-François Alcover_, Jul 06 2018, after _Andrew Howroyd_ *)

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

%Y Column 3 of A208535.

%Y Cf. A000031, A001867.

%K nonn

%O 1,1

%A _Christian G. Bower_, Apr 29 2005