A114438 -id:A114438 - cp's OEIS frontend

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

Alford Arnold

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

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

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.

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

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.

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

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

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.

More terms from Christian G. Bower

A056353 Number of bracelet structures using a maximum of three different colored beads.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 22, 40, 100, 225, 582, 1464, 3960, 10585, 29252, 80819, 226530, 636321, 1800562, 5107480, 14548946, 41538916, 118929384, 341187048, 980842804, 2824561089, 8147557742, 23536592235, 68087343148, 197216119545, 571924754778, 1660419530056, 4825588205920

Offset: 0

Marks R. Nester

nonn

Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Andrew Howroyd, Table of n, a(n) for n = 0..200
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.

Cf. A002076, A000011, A027671, A114438, A152176.

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.

a(n) = Sum_{k=1..3} A152176(n, k) for n > 0. - Andrew Howroyd, Oct 25 2019

a(0)=1 prepended and terms a(28) and beyond from Andrew Howroyd, Oct 25 2019

A306888 Number of inequivalent colorful necklaces.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 3, 8, 11, 20, 31, 64, 105, 202, 367, 696, 1285, 2452, 4599, 8776, 16651, 31838, 60787, 116640, 223697, 430396, 828525, 1598228, 3085465, 5966000, 11545611, 22371000, 43383571, 84217616, 163617805, 318150720, 619094385, 1205614054, 2349384031, 4581315968

Offset: 1

Omran Kouba, Mar 15 2019

nonn

Cf. Bernstein-Kouba paper, function K(n).

A necklace or bracelet is colorful if no pair of adjacent beads are the same color. In addition, two necklaces are equivalent if one results from the other by permuting its colors, and two bracelets are equivalent if one results from the other by either permuting its colors or reversing the order of the beads; a bracelet is thus a necklace that can be turned over.

Michael De Vlieger, Table of n, a(n) for n = 1..3336
Dennis S. Bernstein and Omran Kouba, Counting Colorful Necklaces and Bracelets in Three Colors, arXiv:1901.10703 [math.CO], 2019.
Dennis S. Bernstein and Omran Kouba, Counting Colorful Necklaces and Bracelets in Three Colors, Aequat. Math, 2019.

Cf. A114438, A306896, A306898, A306899, A309673, A327396, A327397.

# Maple code from N. J. A. Sloane, Mar 15 2019
p:=numtheory[phi]; M:=80;
fA:=proc(n) local d,t1; global p; t1:=0; # A_n, A306896
for d from 1 to n do
if (n mod d) = 0 then t1:=t1 + (2^d+ 2*(-1)^d)*p(n/d); fi; od; t1; end;
[seq(fA(n),n=1..M)]; # A306896
fB:=proc(n) local d,t1; global p; t1:=0; # B_n, A306898
for d from 1 to n do
if ((n mod 2) = 0 and ((n/2) mod d) = 0) then t1:=t1 + 2^d*p(n/d); fi; od; t1; end;
[seq(fB(2*n),n=1..M)]; # A306898
fC:=proc(n) local d,t1; global p; t1:=0; # C_n, A306899
for d from 1 to n do
if ((n mod 3) = 0 and ((n/3) mod d) = 0)
then t1:=t1 + (2^d - (-1)^d)*p(n/d); fi; od; t1; end;
[seq(fC(3*n),n=1..M)]; # A306899
K:=proc(n) global fA, fB, fC;
(fA(n)+3*fB(n)+2*fC(n))/(6*n); end;
[seq(K(n),n=1..M)]; # A306888

f[n_] := DivisorSum[n, (2^# + 2 (-1)^#) EulerPhi[n/#] &]; g[n_] := DivisorSum[n, 2^# *EulerPhi[n/#] &, And[Mod[n, 2] == 0, Mod[(n/2), #] == 0] &]; h[n_] := DivisorSum[n, (2^# - (-1)^#) EulerPhi[n/#] &, And[Mod[n, 3] == 0, Mod[(n/3), #] == 0] &]; Array[(f[#] + 3 g[#] + 2 h[#])/(6 #) &, 40] (* Michael De Vlieger, Mar 18 2019 *)
(* Alternatively, using Remark 4.4 from the article *)
K[n_]:=Floor[ 1/(6 n) DivisorSum[n, 2^(n/#)(1 + 4/3 Cos[# Pi/2]^2
Sin[# Pi/3]^2) GCD[#,6] EulerPhi[#] &]]; Table[K[n],{n,1,500}]
(* Omran Kouba, Apr 11 2019; typo fixed by Jean-François Alcover, May 01 2020 *)

a(n) = round(sumdiv(n, d, (1 + (4/3) * (1-(d%2)) * (if (d%3, 3/4))) * gcd(d, 6) * eulerphi(d) * 2^(n/d))/(6*n)); \\ Michel Marcus, May 01 2020; corrected Jun 15 2022

a(n) = floor(Sum_{d|n} (1 + 4/3 * cos(d * Pi/2)^2 * sin(d * Pi/3)^2 ) * gcd(d,6) * phi(d) * 2^(n/d)/(6*n)). [corrected by Omran Kouba, Apr 11 2019]
Eq. (4.15) of Bernstein-Kouba expresses K(n) in terms of A_n, B_n, C_n, and the Maple code below calculates all four sequences and confirms the values given here. - N. J. A. Sloane, Mar 15 2019
a(n) = Sum_{k=1..3} A327396(n, k). - Andrew Howroyd, Oct 09 2019
a(n) ~ 2^(n-1) / (3*n). - Vaclav Kotesovec, May 02 2020

A011768 Number of Barlow packings that repeat after exactly n layers.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 3, 6, 7, 16, 21, 43, 63, 129, 203, 404, 685, 1343, 2385, 4625, 8492, 16409, 30735, 59290, 112530, 217182, 415620, 803076, 1545463, 2990968, 5778267, 11201472, 21702686, 42140890, 81830744, 159139498, 309590883, 602935713, 1174779333, 2290915478, 4469734225, 8726815264

Offset: 1

N. J. A. Sloane and Michael OKeeffe (MOKeeffe(AT)asu.edu)

N. J. A. Sloane, Table of n, a(n) for n = 1..200
Dennis S. Bernstein and Omran Kouba, Counting Colorful Necklaces and Bracelets in Three Colors, arXiv:1901.10703 [math.CO], 2019.
E. Estevez-Rams, C. Azanza-Ricardo, J. Martínez García and B. Aragón-Fernández, On the algebra of binary codes representing closed-packed staking sequences, Acta Cryst. A61 (2005), 201-208.
Ernesto Estevez-Rams, Cristy Azanza Ricardo and Beatriz Aragón Fernández, An alternative expression for counting the number of close-packaged polytypes, Z. Krist. 220 (2005) 592-595, Table 1
T. J. McLarnan, The numbers of polytypes in close-packings and related structures, Zeits. Krist. 155, 269-291 (1981).

Cf. A114438, A371991, A371992.

Cf. A011946, A011947, A011948, A011949, A011950, A011951, A011952, A011953, A011954, A011955, A011956.

with(numtheory); read transforms; M:=200;
A:=proc(N,d) if d mod 3 = 0 then 2^(N/d) else (1/3)*(2^(N/d)+2*cos(Pi*N/d)); fi; end;
E:=proc(N) if N mod 2 = 0 then N*2^(N/2) + add( did(N/2,d)*phi(2*d)*2^(N/(2*d)),d=1..N/2) else (N/3)*(2^((N+1)/2)+2*cos(Pi*(N+1)/2)); fi; end;
PP:=proc(N) (1/(4*N))*(add(did(N,d)*phi(d)*A(N,d), d=1..N)+E(N)); end;
for N from 1 to M do t1[N]:=PP(N); od:
P:=proc(N) local s,d; s:=0; for d from 1 to N do if N mod d = 0 then s:=s+mobius(N/d)*t1[d]; fi; od: s; end; for N from 1 to M do lprint(N,P(N)); od: # N. J. A. Sloane, Aug 10 2006

M = 40;
did[m_, n_] := If[Mod[m, n] == 0, 1, 0];
A[n_, d_] := If[Mod[d, 3] == 0, 2^(n/d), (1/3)(2^(n/d) + 2 Cos[Pi n/d])];
EE[n_] := If[Mod[n, 2] == 0, n 2^(n/2) + Sum[did[n/2, d] EulerPhi[2d]* 2^(n/(2 d)), {d, 1, n/2}], (n/3)(2^((n+1)/2) + 2 Cos[Pi(n+1)/2])];
PP[n_] := PP[n] = (1/(4n))(Sum[did[n, d] EulerPhi[d] A[n, d], {d, 1, n}] + EE[n]);
P[n_] := Module[{s = 0, d}, For[d = 1, d <= n, d++, If[Mod[n, d] == 0, s += MoebiusMu[n/d] PP[d]]]; s];
Array[P, M] (* Jean-François Alcover, Apr 21 2020, from Maple *)

apply( {A011768(n)=A371991(n)+if(n%3, 0, n>3, A371992(n/3), 1)}, [1..42]) \\ M. F. Hasler, May 27 2025

a(n) = (A011946(n/4) + A011947((n-2)/4) + A011948(n/2) + A011949(n/2) + A011950((n+1)/2) + A011951(n/2) + A011952(n/2) + A011953(n)) + (A011954((n-3)/6) + A011955(n/6-1) + A011955(n/6) + A011956(n/3)), where the terms with non-integer indices are set to 0. For n > 3, the two parenthesized terms are resp. A371991(n) and A371992(n/3). - Andrey Zabolotskiy, Feb 14 2024 and May 27 2025

More terms from N. J. A. Sloane, Aug 10 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056353 Number of bracelet structures using a maximum of three different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A306888 Number of inequivalent colorful necklaces.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A011768 Number of Barlow packings that repeat after exactly n layers.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions