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

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.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

Index entries for sequences related to necklaces

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

Cf. A000358, A110706, A110707, A110711.

Sequence in context: A259408 A251684 A129092 * A245881 A078639 A002632

Adjacent sequences: A110707 A110708 A110709 * A110711 A110712 A110713

Keyword

nonn

Author

Max Alekseyev, Aug 05 2005

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 04 2015

Status

approved