A276550 -id:A276550 - cp's OEIS frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 2, 1, 0, 5, 13, 11, 3, 1, 0, 8, 31, 33, 16, 3, 1, 0, 14, 80, 136, 85, 27, 4, 1, 0, 21, 201, 478, 434, 171, 37, 4, 1, 0, 39, 533, 1849, 2270, 1249, 338, 54, 5, 1, 0, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1

Offset: 1

Andrew Howroyd, Apr 09 2017

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

			Triangle starts:
  1
  0  1
  0  1   1
  0  2   2    1
  0  3   5    2    1
  0  5  13   11    3    1
  0  8  31   33   16    3   1
  0 14  80  136   85   27   4  1
  0 21 201  478  434  171  37  4 1
  0 39 533 1849 2270 1249 338 54 5 1
  ...

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 = 1..1275

Columns 1-6 are A063524, A056366, A056367, A056368, A056369, A056370.
Partial row sums include A000046, A056362, A056363, A056364, A056365.
Row sums are A276548.
Cf. A276550, A152175, A152176, A107424, A137651, A276544, A304972.

\\ Ach is A304972 and R is A152175 as square matrices.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={my(M=(R(n)+Ach(n))/2); Mat(vectorv(n,n,sumdiv(n, d, moebius(d)*M[n/d,])))}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n, k) = Sum_{d|n} mu(n/d) * A152176(d, k).

A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.

Original entry on oeis.org

1, 2, 1, 2, 3, 6, 8, 16, 24, 42, 69, 124, 208, 378, 668, 1214, 2220, 4110, 7630, 14308, 26931, 50944, 96782, 184408, 352450, 675180, 1296477, 2493680, 4805388, 9272778, 17919558, 34669600, 67156800, 130215996, 252741255, 490984464, 954629662, 1857545298

Offset: 0

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence, in two entries, N0045 and N0285).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..400
Jairo Bochi and Piotr Laskawiec, Spectrum maximizing products are not generically unique, arXiv:2301.12574 [math.OC], 2023.
Edgar N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frany Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Index entries for sequences related to necklaces

Column 2 of A276550.

with(numtheory); A001371 := proc(n) local s,d; if n = 0 then RETURN(1) else s := 0; for d in divisors(n) do s := s+mobius(d)*A000029(n/d); od; RETURN(s); fi; end;

a29[n_] := a29[n] = (s = If[OddQ[n], 2^((n-1)/2) , 2^(n/2 - 2) + 2^(n/2 - 1)]; a29[0] = 1; Do[s = s + EulerPhi[d]*2^(n/d)/(2*n), {d, Divisors[n]}]; s); a[n_] := Sum[ MoebiusMu[d]*a29[n/d], {d, Divisors[n]}]; a[0] = 1; Table[ a[n], {n, 0, 34}] (* Jean-François Alcover, Oct 04 2011 *)
mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; ReplacePart[CoefficientList[Series[gf[x,2],{x,0,mx}],x],1->1] (* Herbert Kociemba, Nov 28 2016 *)

from sympy import divisors, totient, mobius
def a000029(n):
    return 1 if n<1 else ((2**(n//2+1) if n%2 else 3*2**(n//2-1)) + sum(totient(n//d)*2**d for d in divisors(n))//n)//2
def a(n):
    return 1 if n<1 else sum(mobius(d)*a000029(n//d) for d in divisors(n))
print([a(n) for n in range(51)]) # Indranil Ghosh, Apr 23 2017

a(n) = Sum_{ d divides n } mu(d)*A000029(n/d).
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, for n>0, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

More terms from Christian G. Bower

Entry revised by N. J. A. Sloane, Jun 10 2012

A032294 Number of aperiodic bracelets (turnover necklaces) with n beads of 3 colors.

Original entry on oeis.org

3, 3, 7, 15, 36, 79, 195, 477, 1209, 3168, 8415, 22806, 62412, 172887, 481552, 1351485, 3808080, 10780653, 30615351, 87226932, 249144506, 713378655, 2046856563, 5884468110, 16946569332, 48883597728, 141217159239

Offset: 1

Christian G. Bower

nonn

C. G. Bower, Transforms (2)
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]
N. J. A. Sloane, Transforms
Index entries for sequences related to bracelets

Column 3 of A276550.

mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; CoefficientList[Series[gf[x,3],{x,0,mx}],x] (* Herbert Kociemba, Nov 28 2016 *)

a(x, k) = sum(n=1, 40, moebius(n) * (-log(1 - k*x^n )/n + sum(i=0, 2, binomial(k, i) * x^(n*i)) / (1 - k* x^(2*n)))/2);
Vec(a(x, 3) + O(x^41)) \\ Indranil Ghosh, Mar 29 2017

MOEBIUS transform of A027671.
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

A032295 Number of aperiodic bracelets (turn over necklaces) with n beads of 4 colors.

Original entry on oeis.org

4, 6, 16, 45, 132, 404, 1296, 4380, 15064, 53622, 192696, 703895, 2589300, 9606744, 35824088, 134297280, 505421340, 1909194056, 7234153416, 27489073899, 104717489748, 399827555604, 1529763696816

Offset: 1

Christian G. Bower

nonn

C. G. Bower, Transforms (2)
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]
N. J. A. Sloane, Transforms
Index entries for sequences related to bracelets

Column 4 of A276550.

mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; CoefficientList[Series[gf[x,4],{x,0,mx}],x] (* Herbert Kociemba, Nov 28 2016 *)

MOEBIUS transform of A032275.
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

A032296 Number of aperiodic bracelets (turnover necklaces) with n beads of 5 colors.

Original entry on oeis.org

5, 10, 30, 105, 372, 1460, 5890, 25275, 110050, 492744, 2227270, 10195070, 46989180, 218096780, 1017447736, 4768944375, 22440372240, 105966686200, 501938733550, 2384200190580, 11353290083380

Offset: 1

Christian G. Bower

nonn

C. G. Bower, Transforms (2)
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]
N. J. A. Sloane, Transforms
Index entries for sequences related to bracelets

Column 5 of A276550.

mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; CoefficientList[Series[gf[x,5],{x,0,mx}],x] (* Herbert Kociemba, Nov 28 2016 *)

MOEBIUS transform of A032276.
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

A056347 Number of primitive (period n) bracelets using a maximum of six different colored beads.

Original entry on oeis.org

6, 15, 50, 210, 882, 4220, 20640, 107100, 563730, 3036411, 16514100, 90778485, 502474350, 2799199380, 15673672238, 88162569180, 497847963690, 2821127257950, 16035812864940, 91404065292036

Offset: 1

Marks R. Nester

nonn

Turning over will not create a new bracelet.

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]

Column 6 of A276550.

Cf. A032164.

mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; CoefficientList[Series[gf[x,6],{x,0,mx}],x] (* Herbert Kociemba, Nov 28 2016 *)

sum mu(d)*A056341(n/d) where d|n.
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

cp's OEIS Frontend

A276543 Triangle read by rows: T(n,k) = number of primitive (period n) n-bead bracelet structures using exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A001371 Number of n-bead necklaces with beads of 2 colors and primitive period n, when turning over is allowed.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A032294 Number of aperiodic bracelets (turnover necklaces) with n beads of 3 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032295 Number of aperiodic bracelets (turn over necklaces) with n beads of 4 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A032296 Number of aperiodic bracelets (turnover necklaces) with n beads of 5 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A056347 Number of primitive (period n) bracelets using a maximum of six different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

Formula