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

Author

Alford Arnold

Keywords

• nonn
• easy
• nice

Comments

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

Examples

			For n=2, the six bracelets are AA, AB, AC, BB, BC, and CC. - _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

Crossrefs

Cf. A056353, A114438.

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

Column 3 of A051137.

a(n) = A278639(n) + A182751(n+1).

Equals A001867 - A278639.

Programs

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

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

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

2*a(n) = A182751(n+1) + A001867(n), n>0.

Extensions

More terms from Christian G. Bower