cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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

Views

Author

Omran Kouba, Mar 15 2019

Keywords

Comments

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.

Links

Crossrefs

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

Programs

  • Maple
    # 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
  • Mathematica
    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 *)
  • PARI
    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

Formula

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

A327396 Triangle read by rows: T(n,k) is the number of n-bead necklace structures with beads of exactly k colors and no adjacent beads having the same color.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 3, 5, 2, 1, 0, 0, 3, 10, 8, 2, 1, 0, 1, 7, 33, 40, 18, 3, 1, 0, 0, 11, 83, 157, 104, 28, 3, 1, 0, 1, 19, 237, 650, 615, 246, 46, 4, 1, 0, 0, 31, 640, 2522, 3318, 1857, 495, 65, 4, 1, 0, 1, 63, 1817, 9888, 17594, 13311, 4911, 944, 97, 5, 1
Offset: 1

Views

Author

Andrew Howroyd, Oct 04 2019

Keywords

Comments

Permuting the colors does not change the necklace structure.
Equivalently, the number of k-block partitions of an n-set up to rotations where no block contains cyclically adjacent elements of the n-set.

Examples

			Triangle begins:
  0;
  0, 1;
  0, 0,  1;
  0, 1,  1,    1;
  0, 0,  1,    1,    1;
  0, 1,  3,    5,    2,     1;
  0, 0,  3,   10,    8,     2,     1;
  0, 1,  7,   33,   40,    18,     3,    1;
  0, 0, 11,   83,  157,   104,    28,    3,   1;
  0, 1, 19,  237,  650,   615,   246,   46,   4,  1;
  0, 0, 31,  640, 2522,  3318,  1857,  495,  65,  4, 1;
  0, 1, 63, 1817, 9888, 17594, 13311, 4911, 944, 97, 5, 1;
  ...

Links

Crossrefs

Columns k=3..4 are A327397, A328130.
Partial row sums include A306888, A309673.
Row sums are A328150.
Cf. A152175, A261139, A208535.

Programs

  • PARI
    R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace((y-1)*exp(-x + O(x*x^(n\m))) - y + exp(-x + sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d)) ), x, x^m))/x), -n)]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ 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

Views

Author

Andrew Howroyd, Oct 04 2019

Keywords

Comments

Colors may be permuted without changing the necklace structure.

Examples

			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.

Links

Crossrefs

Column k=4 of A327396.
Cf. A056297, A309673, A327397.

Extensions

Terms a(24) and beyond from Andrew Howroyd, Oct 09 2019
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.