A309528 -id:A309528 - cp's OEIS frontend

A032239 Number of identity bracelets of n beads of 2 colors.

2, 1, 0, 0, 0, 1, 2, 6, 14, 30, 62, 127, 252, 493, 968, 1860, 3600, 6902, 13286, 25446, 48914, 93775, 180314, 346420, 666996, 1284318, 2477328, 4781007, 9240012, 17870709, 34604066, 67058880, 130084990, 252545160, 490722342

Offset: 1

Christian G. Bower

nonn

For n > 2, a(n) is also number of asymmetric bracelets with n beads of two colors. - Herbert Kociemba, Nov 29 2016

Andrew Howroyd, Table of n, a(n) for n = 1..1000
C. G. Bower, Transforms (2)
Petros Hadjicostas, Formulas for chiral bracelets, 2019; see Section 5.
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]
Index entries for sequences related to bracelets

Column k=2 of A309528 and A309651 for n >= 3.
Row sums of A308583 for n >= 3.
Cf. A032337, A203399.

m = 2; (* asymmetric bracelets of n beads of m colors *) Table[Sum[MoebiusMu[d] (m^(n/d)/n - If[OddQ[n/d], m^((n/d + 1)/2), ((m + 1) m^(n/(2 d))/2)]), {d, Divisors[n]}]/2, {n, 3, 20}] (* Robert A. Russell, Mar 18 2013 *)
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[Rest[CoefficientList[Series[gf[x,2],{x,0,mx}],x]],{1->2,2->1}] (* Herbert Kociemba, Nov 29 2016 *)

a(n)={if(n<3, binomial(2,n), sumdiv(n, d, moebius(n/d)*(2^d/n - if(d%2, 2^((d+1)/2), 3*2^(d/2)/2)))/2)} \\ Andrew Howroyd, Sep 12 2019

"DHK" (bracelet, identity, unlabeled) transform of 2, 0, 0, 0...
From Herbert Kociemba, Nov 29 2016: (Start)
More generally, gf(k) is the g.f. for the number of asymmetric bracelets with n 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)

A032240 Number of identity bracelets of n beads of 3 colors.

Original entry on oeis.org

3, 3, 1, 3, 12, 37, 117, 333, 975, 2712, 7689, 21414, 60228, 168597, 475024, 1338525, 3788400, 10741575, 30556305, 87109332, 248967446, 713025093, 2046325125, 5883406830, 16944975036, 48880411272, 141212376513

Offset: 1

Christian G. Bower

nonn

For n>2 also number of asymmetric bracelets with n beads of three colors. - Herbert Kociemba, Nov 29 2016

Andrew Howroyd, Table of n, a(n) for n = 1..200
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]
Index entries for sequences related to bracelets

Column k=3 of A309528 for n >= 3.

m = 3; (* asymmetric bracelets of n beads of m colors *) Table[Sum[MoebiusMu[d] (m^(n/d)/n - If[OddQ[n/d], m^((n/d + 1)/2), ((m + 1) m^(n/(2 d))/2)]), {d, Divisors[n]}]/2, {n, 3, 20}] (* Robert A. Russell, Mar 18 2013 *)
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[Rest[CoefficientList[Series[gf[x,3],{x,0,mx}],x]],{1->3,2->3}] (* Herbert Kociemba, Nov 29 2016 *)

a(n)={if(n<3, binomial(3,n), sumdiv(n, d, moebius(n/d)*(3^d/n - if(d%2, 3^((d+1)/2), 2*3^(d/2))))/2)} \\ Andrew Howroyd, Sep 12 2019

"DHK" (bracelet, identity, unlabeled) transform of 3, 0, 0, 0...
From Herbert Kociemba, Nov 29 2016: (Start)
More generally, gf(k) is the g.f. for the number of asymmetric bracelets with n 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)

A309651 T(n,k) is the number of non-equivalent distinguishing colorings of the cycle on n vertices with exactly k colors (k>=1). Regular triangle read by rows, n >= 1, 1 <= k <= n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 3, 3, 0, 0, 12, 24, 12, 0, 1, 34, 124, 150, 60, 0, 2, 111, 588, 1200, 1080, 360, 0, 6, 315, 2484, 7845, 11970, 8820, 2520, 0, 14, 933, 10240, 46280, 105840, 129360, 80640, 20160, 0, 30, 2622, 40464, 254664, 821592, 1481760, 1512000, 816480, 181440

Offset: 1

Bahman Ahmadi, Aug 11 2019

The cycle graph is defined for n>=3; extended to n=1,2 using the closed form.
A vertex-coloring of a graph G is called distinguishing if it is only preserved by the identity automorphism of G. This notion is considered in the subject of symmetry breaking of simple (finite or infinite) graphs. Two vertex-colorings of a graph are called equivalent if there is an automorphism of the graph which preserves the colors of the vertices.  Given a graph G, we use the notation phi_k(G) to denote the number of non-equivalent distinguishing colorings of G with exactly k colors. The sequence here, displays T(n,k)=phi_k(C_n), i.e., the number of non-equivalent distinguishing colorings of the cycle C_n on n vertices with exactly k colors.
From Andrew Howroyd, Aug 15 2019: (Start)
First differs from A305541 at n = 6.
Also the number of n-bead asymmetric bracelets with exactly k different colored beads. More precisely the number of chiral pairs of primitive (aperiodic) color loops of length n with exactly k different colors. For example, for n=4 and k = 3, there are 3 achiral loops (1213, 1232, 1323) and 3 pairs of chiral loops (1123/1132, 1223/1322, 1233/1332).
(End)

			The triangle begins:
  0
  0,  0;
  0,  0,    1;
  0,  0,    3,     3;
  0,  0,   12,    24,     12;
  0,  1,   34,   124,    150,     60;
  0,  2,  111,   588,   1200,   1080,     360;
  0,  6,  315,  2484,   7845,  11970,    8820,    2520;
  0, 14,  933, 10240,  46280, 105840,  129360,   80640,  20160;
  0, 30, 2622, 40464, 254664, 821592, 1481760, 1512000, 816480, 181440;
  ...
For n=4, we can color the vertices of the cycle C_4 with exactly 3 colors, in 3 ways, such that all the colorings distinguish the graph (i.e., no non-identity automorphism of C_4 preserves the coloring) and that all the three colorings are non-equivalent. The color classes are as follows:
{ { 1 }, { 2 }, { 3, 4 } }
{ { 1 }, { 2, 3 }, { 4 } }
{ { 1, 2 }, { 3 }, { 4 } }

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Columns k=2..4 are A032239(n>=3), A326660, A326789.
Row sums are A326888.
Cf. A001710, A254040, A309528, A305541.

\\ U(n,k) is A309528
U(n,k)={sumdiv(n, d, moebius(n/d)*(k^d/n - if(d%2, k^((d+1)/2), (k+1)*k^(d/2)/2)))/2}
T(n,k)={sum(i=2, k, (-1)^(k-i)*binomial(k,i)*U(n,i))} \\ Andrew Howroyd, Aug 12 2019

Let n>2. For any k >= floor(n/2) we have phi_k(C_n)=k! * Stirling2(n,k)/2n.
T(n, k) = Sum_{i=2..k} (-1)^(k-i)*binomial(k,i)*A309528(n, i). - Andrew Howroyd, Aug 12 2019
Column k is the Moebius transform of column k of A305541. - Andrew Howroyd, Sep 13 2019

A032241 Number of identity bracelets of n beads of 4 colors.

Original entry on oeis.org

4, 6, 4, 15, 72, 266, 1044, 3780, 14056, 51132, 188604, 693845, 2572920, 9566046, 35758628, 134134080, 505159200, 1908539864, 7233104844, 27486455049, 104713295712, 399817073946, 1529746919604

Offset: 1

Christian G. Bower

nonn

For n>2 also number of asymmetric bracelets with n beads of four colors. - Herbert Kociemba, Nov 29 2016

Andrew Howroyd, Table of n, a(n) for n = 1..200
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]
Index entries for sequences related to bracelets

Column k=4 of A309528 for n >= 3.

m = 4; (* asymmetric bracelets of n beads of m colors *) Table[Sum[MoebiusMu[d] (m^(n/d)/n - If[OddQ[n/d], m^((n/d + 1)/2), ((m + 1) m^(n/(2 d))/2)]), {d, Divisors[n]}]/2, {n, 3, 20}] (* Robert A. Russell, Mar 18 2013 *)
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[Rest[CoefficientList[Series[gf[x,4],{x,0,mx}],x]],{1->4,2->6}] (* Herbert Kociemba, Nov 29 2016 *)

a(n)={if(n<3, binomial(4, n), sumdiv(n, d, moebius(n/d)*(4^d/n - if(d%2, 4^((d+1)/2), 5*4^(d/2)/2)))/2)} \\ Andrew Howroyd, Sep 12 2019

"DHK" (bracelet, identity, unlabeled) transform of 4, 0, 0, 0...
From Herbert Kociemba, Nov 29 2016: (Start)
More generally, gf(k) is the g.f. for the number of asymmetric bracelets with n 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)

A032242 Number of identity bracelets of n beads of 5 colors.

Original entry on oeis.org

5, 10, 10, 45, 252, 1120, 5270, 23475, 106950, 483504, 2211650, 10148630, 46911060, 217863040, 1017057256, 4767774375, 22438419120, 105960830300, 501928967930, 2384170903140, 11353241255900

Offset: 1

Christian G. Bower

nonn

For n>2 also number of asymmetric bracelets with n beads of five colors. - Herbert Kociemba, Nov 29 2016

Robert Israel, Table of n, a(n) for n = 1..1434
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]
Index entries for sequences related to bracelets

Column k=5 of A309528 for n >= 3.

N:= 50: # for a(1)..a(N)
G:= add(1/2*numtheory:-mobius(n)*(-log(1-5*x^n)/n - add(binomial(5,i)*x^(n*i)/(1-5*x^(2*n)),i=0..2)), n=1..N):
S:= series(G,x,N+1):
5,10,seq(coeff(S,x,j),j=3..N); # Robert Israel, Jun 24 2019

m=5; (* asymmetric bracelets of n beads of m colors *) Table[Sum[MoebiusMu[d](m^(n/d)/n - If[OddQ[n/d], m^((n/d+1)/2), ((m+1)m^(n/(2d))/2)]), {d,Divisors[n]}]/2, {n,3,20}] (* Robert A. Russell, Mar 18 2013 *)
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[Rest[CoefficientList[Series[gf[x,5],{x,0,mx}],x]],{1->5,2->10}] (* Herbert Kociemba, Nov 29 2016 *)

a(n)={if(n<3, binomial(5,n), sumdiv(n, d, moebius(n/d)*(5^d/n - if(d%2, 5^((d+1)/2), 3*5^(d/2))))/2)} \\ Andrew Howroyd, Sep 12 2019

"DHK" (bracelet, identity, unlabeled) transform of 5, 0, 0, 0...
From Herbert Kociemba, Nov 29 2016: (Start)
More generally, gf(k) is the g.f. for the number of asymmetric bracelets with n 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)

A326888 Number of length n asymmetric bracelets with integer entries that cover an initial interval of positive integers.

Original entry on oeis.org

0, 0, 1, 6, 48, 369, 3341, 33960, 393467, 5111052, 73753685, 1170468816, 20263758984, 380047813297, 7676106093000, 166114206886740, 3834434320842720, 94042629507381957, 2442147034668044933, 66942194905675830162, 1931543452344523775050, 58519191359155952404837

Offset: 1

Andrew Howroyd, Sep 12 2019

nonn

Asymmetric bracelets are those primitive (period n) bracelets that when turned over are different from themselves.

			For n = 4, the six asymmetric bracelets are  1123, 1223, 1233, 1234, 1243, 1324.

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

Row sums of A309651.

Cf. A309528.

\\ U(n,k) is A309528
U(n,k)={sumdiv(n, d, moebius(n/d)*(k^d/n - if(d%2, k^((d+1)/2), (k+1)*k^(d/2)/2)))/2}
a(n)={sum(k=1, n, U(n,k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)))}

Moebius transform of A326895.

cp's OEIS Frontend

A032239 Number of identity bracelets of n beads of 2 colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032240 Number of identity bracelets of n beads of 3 colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A309651 T(n,k) is the number of non-equivalent distinguishing colorings of the cycle on n vertices with exactly k colors (k>=1). Regular triangle read by rows, n >= 1, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A032241 Number of identity bracelets of n beads of 4 colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032242 Number of identity bracelets of n beads of 5 colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A326888 Number of length n asymmetric bracelets with integer entries that cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula