cp's OEIS Frontend

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

%I A106365 #37 Apr 22 2025 02:42:35
%S A106365 3,3,2,6,6,14,18,36,58,108,186,352,630,1182,2190,4116,7710,14602,
%T A106365 27594,52488,99878,190746,364722,699252,1342182,2581428,4971066,
%U A106365 9587580,18512790,35792568,69273666,134219796,260301174,505294128,981706830
%N A106365 Number of necklaces with n beads of 3 colors, no 2 adjacent beads the same color.
%H A106365 Andrew Howroyd, <a href="/A106365/b106365.txt">Table of n, a(n) for n = 1..500</a>
%H A106365 Petros Hadjicostas, <a href="/A106365/a106365.pdf">Proof of an explicit formula for Bower's CycleBG transform</a>
%H A106365 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A106365 CycleBG transform of (3, 0, 0, 0, ...)
%F A106365 CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.
%F A106365 Carlitz transform T(A(x)) has g.f. 1/(1-sum(k>0, (-1)^(k+1)*A(x^k))).
%F A106365 a(n) = (1/n)*sum_{d divides n} phi(n/d)*A092297(d) (n>1). - _Seiichi Azuma_, Oct 25 2014
%F A106365 a(n) = -1+(-1)^n+A000031(n) (n>1). - _Seiichi Azuma_, Oct 25 2014 [Corrected by _Petros Hadjicostas_, Feb 16 2018.]
%F A106365 From _Petros Hadjicostas_, Feb 16 2018: (Start)
%F A106365 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 A106365 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 A106365 (End)
%t A106365 a[n_] := If[n==1, 3, Sum[EulerPhi[n/d]*(2*(-1)^d+2^d), {d, Divisors[n]}]/n ];
%t A106365 Array[a, 35] (* _Jean-François Alcover_, Jul 06 2018, after _Andrew Howroyd_ *)
%o A106365 (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 A106365 Column 3 of A208535.
%Y A106365 Cf. A000031, A001867.
%K A106365 nonn
%O A106365 1,1
%A A106365 _Christian G. Bower_, Apr 29 2005