A027671 Number of necklaces with n beads of 3 colors, allowing turning over.

1, 3, 6, 10, 21, 39, 92, 198, 498, 1219, 3210, 8418, 22913, 62415, 173088, 481598, 1351983, 3808083, 10781954, 30615354, 87230157, 249144711, 713387076, 2046856566, 5884491500, 16946569371, 48883660146, 141217160458, 408519019449, 1183289542815

Offset

0,2

Comments

Number of bracelets of n beads using up to three different colors. - Robert A. Russell, Sep 24 2018

References

J. L. Fisher, Application-Oriented Algebra (1977), ISBN 0-7002-2504-8, circa p. 215.

M. Gardner, "New Mathematical Diversions from Scientific American" (Simon and Schuster, New York, 1966), pp. 245-246.

Links

T. D. Noe, Table of n, a(n) for n = 0..200

E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

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]

M. Taniguchi, H. Du, and J. S. Lindsey, Enumeration of virtual libraries of combinatorial modular macrocyclic (bracelet, necklace) architectures and their linear counterparts, Journal of Chemical Information and Modeling, 53 (2013), 2203-2216.

R. M. Thompson and R. T. Downs, Systematic generation of all nonequivalent closest-packed stacking sequences of length N using group theory, Acta Cryst. B57 (2001), 766-771; B58 (2002), 153.

Eric Weisstein's World of Mathematics, Necklace.

Index entries for sequences related to bracelets

Formula

G.f.: (1 - Sum_{n>=1} phi(n)*log(1 - 3*x^n)/n + (1+3*x+3*x^2)/(1-3*x^2))/2. - Herbert Kociemba, Nov 02 2016

For n > 0, a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))* Sum_{d|n} phi(d)*k^(n/d), where k=3 is the maximum number of colors. - Robert A. Russell, Sep 24 2018

a(0) = 1; a(n) = (k^floor((n+1)/2) + k^ceiling((n+1)/2))/4 + (1/(2*n))*Sum_{i=1..n} k^gcd(n,i), where k=3 is the maximum number of colors.

(See A075195 formulas.) - Richard L. Ollerton, May 04 2021

Example

For n=2, the six bracelets are AA, AB, AC, BB, BC, and CC. - Robert A. Russell, Sep 24 2018

Mathematica

Needs["Combinatorica`"];  Join[{1}, Table[CycleIndex[DihedralGroup[n], s]/.Table[s[i]->3, {i, 1, n}], {n, 1, 30}]] (* Geoffrey Critzer, Sep 29 2012 *)
Needs["Combinatorica`"]; Join[{1}, Table[NumberOfNecklaces[n, 3, Dihedral], {n, 30}]] (* T. D. Noe, Oct 02 2012 *)
mx=40; CoefficientList[Series[(1-Sum[ EulerPhi[n]*Log[1-3*x^n]/n, {n, mx}]+(1+3 x+3 x^2)/(1-3 x^2))/2, {x, 0, mx}], x] (* Herbert Kociemba, Nov 02 2016 *)
t[n_, k_] := (For[t1 = 0; d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*k^(n/d)]]; If[EvenQ[n], (t1 + (n/2)*(1+k)*k^(n/2))/(2*n), (t1 + n*k^((n+1)/2))/(2*n)]); a[0] = 1; a[n_] := t[n, 3]; Array[a, 30, 0] (* Jean-François Alcover, Nov 02 2017, after Maple code for A081720 *)
k=3; Prepend[Table[DivisorSum[n, EulerPhi[#] k^(n/#) &]/(2n) + (k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2])/4, {n, 1, 30}], 1] (* Robert A. Russell, Sep 24 2018 *)

Prog

(PARI) a(n, k=3) = if(n==0, 1, (k^floor((n+1)/2) + k^ceil((n+1)/2))/4 + (1/(2*n))* sumdiv(n, d, eulerphi(d)*k^(n/d) ) );
vector(55, n, a(n-1)) \\ Joerg Arndt, Oct 20 2019

Crossrefs

Cf. A056353, A114438.

a(n) = A081720(n,3), n >= 3. - Wolfdieter Lang, Jun 03 2012

Column 3 of A051137.

a(n) = (A001867(n) + A182751(n+1)) / 2 = A278639(n) + A182751(n+1).

Equals A001867 - A278639.

Sequence in context: A299017 A136569 A061883 * A167617 A274018 A068149

Adjacent sequences: A027668 A027669 A027670 * A027672 A027673 A027674

Keyword

nonn,easy,nice

Author

Alford Arnold

Extensions

More terms from Christian G. Bower

Status

approved