A327396 -id:A327396 - cp's OEIS frontend

A306888 Number of inequivalent colorful necklaces.

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

A309673 Number of n-bead necklace structures using a maximum of four different colored beads and no adjacent beads having the same color.

Original entry on oeis.org

0, 1, 1, 3, 2, 9, 13, 41, 94, 257, 671, 1881, 5110, 14301, 39871, 112281, 316520, 897297, 2548819, 7265383, 20754748, 59437181, 170549237, 490338539, 1412147684, 4073528481, 11767897903, 34042917197, 98606864030, 285960106473, 830206177801, 2412787265021

Offset: 1

Andrew Howroyd, Oct 05 2019

nonn

Colors may be permuted without changing the necklace structure.

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A056292, A306888, A327396, A328130.

a(n) = Sum_{k=1..4} A327396(n, k).

Terms a(24) and beyond from Andrew Howroyd, Oct 10 2019

A327397 Number of n-bead necklace structures with beads of exactly three colors and no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 1, 1, 1, 3, 3, 7, 11, 19, 31, 63, 105, 201, 367, 695, 1285, 2451, 4599, 8775, 16651, 31837, 60787, 116639, 223697, 430395, 828525, 1598227, 3085465, 5965999, 11545611, 22370999, 43383571, 84217615, 163617805, 318150719, 619094385, 1205614053, 2349384031

Offset: 1

Andrew Howroyd, Oct 04 2019

nonn

Colors may be permuted without changing the necklace structure.

			Necklace structures for n=3..8 are:
  a(3) = 1: ABC;
  a(4) = 1: ABAC;
  a(5) = 1: ABABC;
  a(6) = 3: ABABAC, ABACBC, ABCABC;
  a(7) = 3: ABABABC, ABABCAC, ABACABC;
  a(8) = 7: ABABABAC, ABABACAC, ABABACBC, ABABCABC, ABABCBAC, ABACABAC, ABACBABC.

Andrew Howroyd, Table of n, a(n) for n = 1..200

Column k=3 of A327396.

Cf. A056296, A306888, A328130.

a(n) = A306888(n) - A000035(n-1). - Yuchun Ji, Mar 13 2020

Terms a(33) and beyond from Andrew Howroyd, Oct 09 2019

A328130 Number of n-bead necklace structures with beads of exactly four colors and no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 10, 33, 83, 237, 640, 1817, 5005, 14099, 39504, 111585, 315235, 894845, 2544220, 7256607, 20738097, 59405343, 170488450, 490221899, 1411923987, 4073098085, 11767069378, 34041318969, 98603778565, 285954140473, 830194632190, 2412764894021, 7018972487319

Offset: 1

Andrew Howroyd, Oct 04 2019

nonn

Colors may be permuted without changing the necklace structure.

			Necklace structures for n=4..7 are:
a(4) = 1: ABCD;
a(5) = 1: ABACD;
a(6) = 5: ABABCD, ABACAD, ABACBD, ABACDC, ABCABD;
a(7) = 10: ABABACD, ABABCAD, ABABCBD, ABABCDC, ABACABD, ABACADC, ABACBCD, ABACBDC, ABACDBC, ABCABCD.

Andrew Howroyd, Table of n, a(n) for n = 1..200

Column k=4 of A327396.

Cf. A056297, A309673, A327397.

Terms a(24) and beyond from Andrew Howroyd, Oct 09 2019

A330618 Triangle read by rows: T(n,k) is the number of n-bead necklaces using exactly k colors with no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 1, 0, 0, 2, 0, 1, 3, 6, 0, 0, 6, 24, 24, 0, 1, 11, 80, 180, 120, 0, 0, 18, 240, 960, 1440, 720, 0, 1, 33, 696, 4410, 11340, 12600, 5040, 0, 0, 58, 1960, 18760, 73920, 137760, 120960, 40320, 0, 1, 105, 5508, 76368, 433944, 1209600, 1753920, 1270080, 362880

Offset: 1

Andrew Howroyd, Dec 20 2019

In the case of n = 1, the single bead is considered to be cyclically adjacent to itself giving T(1,1) = 0. If compatibility with A208535 is wanted then T(1,1) should be 1.

			Triangle begins:
  0;
  0, 1;
  0, 0,  2;
  0, 1,  3,    6;
  0, 0,  6,   24,    24;
  0, 1, 11,   80,   180,   120;
  0, 0, 18,  240,   960,  1440,    720;
  0, 1, 33,  696,  4410, 11340,  12600,   5040;
  0, 0, 58, 1960, 18760, 73920, 137760, 120960, 40320;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Column 3 is A093367.
Row sums are A330620.
Cf. A087854, A208535, A327396, A330341.

\\ here U(n,k) is A208535(n,k) for n > 1.
U(n, k)={sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1)}
T(n,k)={sum(j=1, k, (-1)^(k-j)*binomial(k,j)*U(n,j))}

T(n,k) = Sum_{j=1..k} (-1)^(k-j)*binomial(k,j)*A208535(n,j) for n > 1.

T(n,n) = (n-1)! for n > 1.

A328150 Number of n-bead necklace structures with no adjacent elements having the same color.

Original entry on oeis.org

1, 0, 1, 1, 3, 3, 12, 24, 103, 387, 1819, 8933, 48632, 279484, 1716523, 11126025, 76014437, 544945399, 4089010392, 32025053060, 261213946739, 2214280580389, 19471365925297, 177319383231697, 1669735890602062, 16235408370162588, 162796351456044465, 1681427459283678177

Offset: 0

Andrew Howroyd, Oct 05 2019

nonn

Beads may be of any number of colors. Colors may be permuted without changing the necklace structure.

Equivalently, the number of set partitions of an n-set up to rotations where no block contains cyclically adjacent elements of the n-set.

			a(6) = 12 because there are the following 12 necklace structures: ABABAB, ABABAC, ABABCD, ABACAD, ABACBC, ABACBD, ABACDC, ABACDE, ABCABC, ABCABD, ABCADE, ABCDEF.

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row sums of A327396.

Cf. A084423.

seq(n)={Vec(1 + intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(-x + sumdiv(m, d, (exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))} \\ Andrew Howroyd, Oct 09 2019

Terms a(16) and beyond from Andrew Howroyd, Oct 09 2019

cp's OEIS Frontend

A306888 Number of inequivalent colorful necklaces.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A309673 Number of n-bead necklace structures using a maximum of four different colored beads and no adjacent beads having the same color.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A327397 Number of n-bead necklace structures with beads of exactly three colors and no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A328130 Number of n-bead necklace structures with beads of exactly four colors and no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A330618 Triangle read by rows: T(n,k) is the number of n-bead necklaces using exactly k colors with no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A328150 Number of n-bead necklace structures with no adjacent elements having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions