login
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).
8
1, 2, 5, 16, 70, 348, 1948, 11444, 70380, 445944, 2896590, 19186740, 129186596, 881808728, 6089851874, 42482906040, 298976142764, 2120377458900, 15141289233972, 108784152585236, 785869931659980, 5705406374249272
OFFSET
0,2
COMMENTS
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.
FORMULA
a(n) = Sum_{d|n} A110707(n/d)*eulerphi(d) / (3n) for n>0, a(0)=1.
a(n) ~ sqrt(3) * 2^(3*n - 1) / (Pi * n^2). - Vaclav Kotesovec, Mar 20 2023
EXAMPLE
For n=2 there are 5 necklaces: 010212, 012012, 012021, 012102, 021021.
MATHEMATICA
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 *)
PROG
(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); }
CROSSREFS
KEYWORD
nonn
AUTHOR
Max Alekseyev, Aug 05 2005
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 04 2015
STATUS
approved