%I #32 Mar 20 2023 06:31:07

%S 1,2,5,16,70,348,1948,11444,70380,445944,2896590,19186740,129186596,

%T 881808728,6089851874,42482906040,298976142764,2120377458900,

%U 15141289233972,108784152585236,785869931659980,5705406374249272

%N Number of ternary necklaces with n beads of each color and no adjacent beads of the same color (i.e., no substrings 00, 11, 22).

%C The number of circular arrangements (counted up to rotations) of n blue, n red and n green items such that there are no adjacent items of the same color. The number of various linear arrangements is given by A110706, A110707 and A110711.

%H G. C. Greubel, <a href="/A110710/b110710.txt">Table of n, a(n) for n = 0..1000</a>

%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

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

%F a(n) = Sum_{d|n} A110707(n/d)*eulerphi(d) / (3n) for n>0, a(0)=1.

%F a(n) ~ sqrt(3) * 2^(3*n - 1) / (Pi * n^2). - _Vaclav Kotesovec_, Mar 20 2023

%e For n=2 there are 5 necklaces: 010212, 012012, 012021, 012102, 021021.

%t b = Binomial; A110707[n_] := 2*Sum[b[n - 1, k]*(b[n - 1, k]*(b[2*n + 1 - 2*k, n + 1] - 3*b[2*n - 1 - 2*k, n + 1]) + b[n - 1, k + 1]*(b[2*n - 2*k, n + 1] - 3*b[2*n - 2*k - 2, n + 1])), {k,0, n/2}]; a[n_] := DivisorSum[n, A110707[n/#]*EulerPhi[#]&]/(3n); a[0]=1; Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Dec 04 2015, adapted from PARI *)

%o (PARI) { A110707(n) = 2 * sum(k=0,n\2, binomial(n-1,k) * (binomial(n-1,k)*(binomial(2*n+1-2*k,n+1)-3*binomial(2*n-1-2*k,n+1)) + binomial(n-1,k+1)*(binomial(2*n-2*k,n+1)-3*binomial(2*n-2*k-2,n+1)) )); A110710(n) = sumdiv(n,d,A110707(n\d)*eulerphi(d))\(3*n); }

%Y Cf. A000358, A110706, A110707, A110711.

%K nonn

%O 0,2

%A _Max Alekseyev_, Aug 05 2005

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2015