cp's OEIS Frontend

A110710 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).

%I A110710 #32 Mar 20 2023 06:31:07
%S A110710 1,2,5,16,70,348,1948,11444,70380,445944,2896590,19186740,129186596,
%T A110710 881808728,6089851874,42482906040,298976142764,2120377458900,
%U A110710 15141289233972,108784152585236,785869931659980,5705406374249272
%N A110710 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 A110710 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 A110710 G. C. Greubel, <a href="/A110710/b110710.txt">Table of n, a(n) for n = 0..1000</a>
%H A110710 F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H A110710 F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H A110710 <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%F A110710 a(n) = Sum_{d|n} A110707(n/d)*eulerphi(d) / (3n) for n>0, a(0)=1.
%F A110710 a(n) ~ sqrt(3) * 2^(3*n - 1) / (Pi * n^2). - _Vaclav Kotesovec_, Mar 20 2023
%e A110710 For n=2 there are 5 necklaces: 010212, 012012, 012021, 012102, 021021.
%t A110710 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 A110710 (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 A110710 Cf. A000358, A110706, A110707, A110711.
%K A110710 nonn
%O A110710 0,2
%A A110710 _Max Alekseyev_, Aug 05 2005
%E A110710 a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2015