A052307 -id:A052307 - cp's OEIS frontend

A072605 Number of necklaces with n beads over an n-ary alphabet {a1,a2,...,an} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 0, where #(w,x) counts the letters x in word w.

1, 1, 2, 4, 13, 50, 270, 1641, 11945, 96784, 887982, 8939051, 99298354, 1195617443, 15619182139, 219049941201, 3293800835940, 52746930894774, 897802366250126, 16167544246362567, 307372573011579188, 6148811682561390279, 129164845357784003661

Offset: 0

Wouter Meeussen, Aug 06 2002

Alois P. Heinz, Table of n, a(n) for n = 0..200
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Eric Weisstein's world of Mathematics, Necklaces

Cf. A005651, A052307, A247551, A261531, A261599, A261600.

neck[li:{__Integer}] := Module[{n, d}, n=Plus@@li; d=n-First[li]; Fold[ #1+(EulerPhi[ #2]*(n/#2)!)/Times@@((li/#2)!)&, 0, Divisors[GCD@@li]]/n]; Table[ Plus@@(neck /@ IntegerPartitions[n]), {n, 24}]

a(n)={if(n==0, 1, my(p=prod(k=1, n, 1/(1-x^k/k!) + O(x*x^n))); sumdiv(n, d, eulerphi(n/d)*d!*polcoeff(p,d))/n)} \\ Andrew Howroyd, Dec 20 2017

a(n) = (1/n) * Sum_{d|n} phi(n/d) * A005651(d) for n > 0. - Andrew Howroyd, Sep 25 2017
See Mathematica line.
a(n) ~ c * (n-1)!, where c = Product_{k>=2} 1/(1-1/k!) = A247551 = 2.52947747207915264818011615... . - Vaclav Kotesovec, Aug 27 2015

a(0)=1 prepended by Alois P. Heinz, Aug 23 2015

Name changed by Andrew Howroyd, Sep 25 2017

A005514 Number of n-bead bracelets (turnover necklaces) with 8 red beads and n-8 black beads.

Original entry on oeis.org

1, 1, 5, 10, 29, 57, 126, 232, 440, 750, 1282, 2052, 3260, 4950, 7440, 10824, 15581, 21879, 30415, 41470, 56021, 74503, 98254, 127920, 165288, 211276, 268228, 337416, 421856, 523260, 645456, 790704, 963793, 1167645, 1408185

Offset: 8

N. J. A. Sloane

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of 8 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in case k=8 (see our comment at A032279). (End)
From Petros Hadjicostas, Jul 14 2018: (Start)
Let (c(n): n >= 1) be a sequence of nonnegative integers and let C(x) = Sum_{n>=1} c(n)*x^n be its g.f. Let k be a positive integer. Let a_k = (a_k(n): n >= 1) be the output sequence of the DIK[k] transform of sequence (c(n): n >= 1), and let A_k(x) = Sum_{n>=1} a_k(n)*x^n be its g.f. See Bower's web link below. It can be proved that, when k is even, A_k(x) = ((1/k)*Sum_{d|k} phi(d)*C(x^d)^(k/d) + (1/2)*C(x^2)^((k/2)-1)*(C(x)^2 + C(x^2)))/2.
For this sequence, k=8, c(n) = 1 for all n >= 1, and C(x) = x/(1-x). Thus, a(n) = a_8(n) for all n >= 1. Since a_k(n) = 0  for 1 <= n <= k-1, the offset of this sequence is n = k = 8. Applying the formula for the g.f. of DIK[8] of (c(n): n >= 1) with C(x) = x/(1-x) and k=8, we get Herbert Kociemba's formula below.
Here, a(n) is defined to be the number of n-bead bracelets of two colors with 8 red beads and n-8 black beads. But it is also the number of dihedral compositions of n with 8 parts. (This statement is equivalent to Vladimir Shevelev's statement above that a(n) is the "number of non-equivalent necklaces of 8 beads each of them painted by one of n colors." By "necklaces", he means "turnover necklaces". See the second paragraph of Section 2 in his 2004 paper in the Indian Journal of Pure and Applied Mathematics.)
Two cyclic compositions of n (with k = 8 parts) belong to the same equivalence class corresponding to a dihedral composition of n if and only if one can be obtained from the other by a rotation or reversal of order. (End)

			From _Petros Hadjicostas_, Jul 14 2018: (Start)
Every n-bead bracelet of two colors such that 8 beads are red and n-8 are black can be transformed into a dihedral composition of n with 8 parts in the following way. Start with one R bead and go in one direction (say clockwise) until you reach the next R bead. Continue this process until you come back to the original R bead.
Let b_i be the number of beads from R bead i until you reach the last B bead before R bead i+1 (or R bead 1). Here, b_i = 1 iff there are no B beads between R bead i and R bead i+1 (or R bead 8 and R bead 1). Then b_1 + b_2 + ... + b_8 = n, and we get a dihedral composition of n. (Of course, b_2 + b_3 + ... + b_8 + b_1 and b_8 + b_7 + ... + b_1 belong to the same equivalence class of the dihedral composition b_1 + ... + b_8.)
For example, a(10) = 5, and we have the following bracelets with 8 R beads and 2 B beads. Next to the bracelets we list the corresponding dihedral compositions of n with k=8 parts (they must be viewed on a circle):
RRRRRRRRBB <-> 1+1+1+1+1+1+1+3
RRRRRRRBRB <-> 1+1+1+1+1+1+2+2
RRRRRRBRRB <-> 1+1+1+1+1+2+1+2
RRRRRBRRRB <-> 1+1+1+1+2+1+1+2
RRRRBRRRRB <-> 1+1+1+2+1+1+1+2
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 8..1000
Christian G. Bower, Transforms (2)
S. J. Cyvin, B. N. Cyvin, J. Brunvoll, I. Gutman, Chen Rong-si, S. El-Basil, and Zhang Fuji, Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem, Z. Naturforsch., 52a (1997), 867-873.
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 1-15.
W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)
Richard H. Reis, A formula for C(T) in Gupta's paper, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 1000-1001.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
A. P. Street, Letter to N. J. A. Sloane, N.D.
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (4,-4,-4,11,-8,0,8,-10,0,8,0,-10,8,0,-8,11,-4,-4,4,-1).

Column k=8 of A052307.

Cf. A008805, A032193, A032279, A032280, A032281, A032282, A119963, A292906.

k = 8; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
k=8;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

S. J. Cyvin et al. (1997) give a g.f. (See equation (18) on p. 870 of their paper. Their g.f. is the same as the one given by V. Jovovic below except for the extra x^8.) - Petros Hadjicostas, Jul 14 2018
G.f.: (x^8/16)*(1/(1 - x)^8 + 4/(1 - x^8) + 5/(1 - x^2)^4 + 2/(1 - x^4)^2 + 4/(1 - x)^2/(1 - x^2)^3) = x^8*(2*x^10 - 3*x^9 + 7*x^8 - 6*x^7 + 7*x^6 - 2*x^5 + 2*x^4 - 2*x^3 + 5*x^2 - 3*x + 1)/(1 - x)^8/(1 + x)^4/(1 + x^2)^2/(1 + x^4). - Vladeta Jovovic, Jul 17 2002
a(n) = ((n+4)/32)*s(n,0,8) + ((n-4)/32)*s(n,4,8) + (48*C(n-1,7) + (n+1)*(n-2)*(n-4)*(n-6))/768, if n is even >= 8; a(n) = (48*C(n-1,7) + (n-1)*(n-3)*(n-5)*(n-7))/768, if n odd >= 8, where s(n,k,d)=1, if n == k (mod d), and 0 otherwise. - Vladimir Shevelev, Apr 23 2011
G.f.: k=8, x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^floor((k+2)/2))/2. - Herbert Kociemba, Nov 05 2016 [edited by Petros Hadjicostas, Jul 18 2018]
From Petros Hadjicostas, Jul 14 2018: (Start)
a(n) = (A032193(n) + A119963(n, 8))/2 = (A032193(n) + C(floor(n/2), 4))/2 for n >= 8.
The sequence (a(n): n >= 8) is the output sequence of Bower's "DIK[ 8 ]" (bracelet, indistinct, unlabeled, 8 parts) transform of 1, 1, 1, 1, ...
(End)

Sequence extended and description corrected by Christian G. Bower

Name edited by Petros Hadjicostas, Jul 20 2018

A032280 Number of bracelets (turnover necklaces) of n beads of 2 colors, 7 of them black.

Original entry on oeis.org

1, 1, 4, 8, 20, 38, 76, 133, 232, 375, 600, 912, 1368, 1980, 2829, 3936, 5412, 7293, 9724, 12760, 16588, 21287, 27092, 34112, 42640, 52819, 65008, 79392, 96405, 116280, 139536, 166464, 197676, 233529, 274740, 321741, 375364

Offset: 7

Christian G. Bower

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of nonequivalent necklaces of 7 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in case k=7 (see our comment to A032279).
(End)

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Vincenzo Librandi, Table of n, a(n) for n = 7..1000
C. G. Bower, Transforms (2)
S. J. Cyvin, B. N. Cyvin, J. Brunvoll, I. Gutman, Chen Rong-si, S. El-Basil, and Zhang Fuji, Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem, Z. Naturforsch., 52a (1997), 867-873.
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
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]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, A problem of enumeration of two-color bracelets with several variations, arXiv:0710.1370 [math.CO], 2007-2011.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (3,0,-8,6,6,-8,1,0,-1,8,-6,-6,8,0,-3,1).

Column k=7 of A052307.

k = 7; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
CoefficientList[Series[-(4 x^6 - 2 x^5 - 2 x^4 + 4 x^3 + x^2 - 2 x + 1)/((x - 1)^7 (x + 1)^3 (x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 19 2013 *)
k=7; CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

S. J. Cyvin et al. (1997) give a g.f.
"DIK[ 7 ]" (necklace, indistinct, unlabeled, 7 parts) transform of 1, 1, 1, 1...
From Vladimir Shevelev, Apr 23 2011: (Start)
Put s(n,k,d) = 1, if n == k(mod d); 0, otherwise. Then
a(n) = (3/7)*s(n,0,7) + (48*C(n-1,6) + 7*(n-2)*(n-4)*(n-6))/672, if n is even;
a(n) = (3/7)*s(n,0,7) + (48*C(n-1,6) + 7*(n-1)*(n-3)*(n-5))/672, if n is odd. (End)
G.f.: -x^7*(4*x^6-2*x^5-2*x^4+4*x^3+x^2-2*x+1) / ((x-1)^7*(x+1)^3*(x^6+x^5+x^4+x^3+x^2+x+1)). - Colin Barker, Feb 06 2013
From Herbert Kociemba, Nov 05 2016: (Start)
G.f.: (1/2)*x^7*((1+x)/(1-x^2)^4 + 1/7*(1/(1-x)^7 + 6/(1-x^7))).
G.f.: k=7, x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^floor((k+2)/2))/2. [edited by Petros Hadjicostas, Jul 18 2018] (End)

A032281 Number of bracelets (turnover necklaces) of n beads of 2 colors, 9 of them black.

Original entry on oeis.org

1, 1, 5, 12, 35, 79, 185, 375, 750, 1387, 2494, 4262, 7105, 11410, 17930, 27407, 41107, 60335, 87154, 123695, 173173, 238957, 325845, 438945, 585265, 772252, 1009868, 1308742, 1682660, 2146420, 2718806, 3419924, 4274905, 5310667, 6560225, 8059021, 9849925

Offset: 9

Christian G. Bower

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of 9 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in the case k=9 (see our comment to A032279). (End)

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 9..1000
Christian G. Bower, Transforms (2).
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
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]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (2,3,-6,-6,6,13,-2,-18,-1,11,3,0,0,-3,-11,1,18,2,-13,-6,6,6,-3,-2,1).

Column k=9 of A052307.

k = 9; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
k=9;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

"DIK[ 9 ]" (necklace, indistinct, unlabeled, 9 parts) transform of 1, 1, 1, 1...
Put s(n,k,d) = 1, if n == k (mod d), and s(n,k,d) = 0, otherwise. Then a(n) =(1/3)*s(n,0,9) + (n-3)*(n-6)*s(n,0,3)/162 + (n-2)(n-4)*(n-6)*(n-8)*(945 + (n-1)*(n-3)*(n-5)*(n-7))/725760, if n is even; a(n) = (1/3)*s(n,0,9) + (n-3)*(n-6)*s(n,0,3)/162 +(n-1)*(n-3)*(n-5)*(n-7)*(945 + (n-2)*(n-4)*(n-6)*(n-8))/725760, if n is odd. - Vladimir Shevelev, Apr 23 2011
From Herbert Kociemba, Nov 05 2016: (Start)
G.f.: (1/2)*x^9*((1+x)/(1-x^2)^5 + 1/9*(1/(1-x)^9 - 2/(-1+x^3)^3 - 6/(-1+x^9))).
G.f.: k=9, x^k*((1/k)*(Sum_{d|k} phi(d)*(1-x^d)^(-k/d)) + (1+x)/(1-x^2)^floor((k+2)/2))/2. [edited by Petros Hadjicostas, Jul 18 2018] (End)

A032282 Number of bracelets (turnover necklaces) of n beads of 2 colors, 11 of them black.

Original entry on oeis.org

1, 1, 6, 16, 56, 147, 392, 912, 2052, 4262, 8524, 16159, 29624, 52234, 89544, 148976, 242086, 384111, 597506, 911456, 1367184, 2017509, 2934559, 4209504, 5963464, 8347612, 11558232, 15837472, 21493712, 28903332

Offset: 11

Christian G. Bower

nonn

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of 11 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in case k=11 (see our comment to A032279).
(End)

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 11..1000
Christian G. Bower, Transforms (2).
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.
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]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (5,-5,-15,35,1,-65,45,45,-65,1,36,-20,0,20,-36,-1,65,-45,-45,65,-1,-35,15,5,-5,1).

Column k=11 of A052307.

k = 11; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
k=11;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

"DIK[ 11 ]" (necklace, indistinct, unlabeled, 11 parts) transform of 1, 1, 1, 1...
From Vladimir Shevelev, Apr 23 2011: (Start)
Put s(n,k,d)=1, if n==k(mod d), and s(n,k,d)=0, otherwise. Then
a(n) = 5*s(n,0,11)/11+(3840*C(n-1,10)+11*(n-2)*(n-4)*(n-6)(n-8)*(n-10))/84480, if n is even;
a(n) = 5*s(n,0,11)/11+(3840*C(n-1,10)+11*(n-1)*(n-3)*(n-5)*(n-7)*(n-9))/84480, if n is odd.
(End)
From Herbert Kociemba, Nov 05 2016: (Start)
G.f.: 1/22*x^11*(1/(1-x)^11 + 11/((-1+x)^6*(1+x)^5) - 10/(-1+x^11)).
G.f.: k=11, x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^floor[(k+2)/2])/2. [edited by Petros Hadjicostas, Jul 18 2018]
(End)

A180472 Triangle T(n, k) = OC(n, k; not -1), read by rows, where OC(n, k; not -1) is the number of k-subsets of Z_n without -1 as a multiplier, up to congruency.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 3, 4, 4, 3, 0, 0, 0, 0, 0, 0, 4, 6, 10, 6, 4, 0, 0, 0, 0, 0, 0, 5, 10, 16, 16, 10, 5, 0, 0, 0, 0, 0, 0, 7, 14, 28, 30, 28, 14, 7, 0, 0, 0, 0, 0, 0, 8, 20, 42, 56, 56, 42, 20, 8, 0, 0, 0, 0, 0, 0, 10, 26, 64, 91, 113, 91, 64, 26, 10, 0, 0, 0, 0, 0, 0, 12, 35, 90, 150, 197, 197, 150, 90, 35, 12, 0, 0, 0, 0, 0, 0, 14, 44, 126, 224, 340, 370, 340, 224, 126, 44, 14, 0, 0, 0, 0, 0, 0, 16, 56, 168, 336, 544, 680, 680, 544, 336, 168, 56, 16, 0, 0, 0

Offset: 0

John P. McSorley, Sep 06 2010

Let Z_n = {0,1,...,n-1} denote the integers mod n.
Let S be a k-subset of Z_n.
Then S has multiplier -1 iff there is a z in Z_n for which S = -S + z. Otherwise, S doesn't have multiplier -1.
For example in Z_7 the set S = {0,1,2} has multiplier -1 since -S = {0,-1,-2} = {0,5,6} and then {0,1,2} = {0,5,6} + 2, so S = -S + 2. But S={0,1,3} doesn't have multiplier -1.
Let S and S' be two k-subsets of Z_n.
Define an equivalence relation on the set of k-subsets as follows: S is congruent to S' iff S=S'+z or S = -S' + z for some z in Z_n.
Then define OC(n, k) to be the number of such congruence classes.
And define OC(n, k; not -1) to be the number of such congruence classes in which the representative doesn't have -1 as a multiplier.
Then this sequence is the 'OC(n,k; not -1)' triangle read by rows.
For convenience we start the triangle at n = 0, and we have 0 <= k <= n.
See the McSorley and Schoen (2013) reference below for equivalent definitions of this sequence in terms of (n,k)-Ovals and k-compositions of n.
From Petros Hadjicostas, May 29 2019: (Start)
Here, T(n, k) is the number of bracelets (turnover necklaces) of length n that have no reflection symmetry and consist of k white beads and n - k black beads. (Bracelets that have no reflection symmetry are also known as chiral bracelets.)
It is also the number of dihedral compositions of n into k parts with no reflection symmetry. It is also the number of dihedral compositions of n into n - k parts with no reflection symmetry. (For a definition of a dihedral composition, see Knopfmacher and Robbins (2013) in the references.)
For MacMahon's method for transforming a cyclic composition into a necklace and vice versa, see the comments for sequence A308401. See also p. 273 in Sommerville (1909).
(End)

			The triangle begins (with rows for n >= 0 and columns for k >= 0) as follows:
  0
  0  0
  0  0  0
  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  1  0  0  0
  0  0  0  1  1  0  0   0
  0  0  0  2  2  2  0   0  0
  0  0  0  3  4  4  3   0  0  0
  0  0  0  4  6 10  6   4  0  0  0
  0  0  0  5 10 16 16  10  5  0  0  0
  0  0  0  7 14 28 30  28 14  7  0  0  0
  0  0  0  8 20 42 56  56 42 20  8  0  0  0
  0  0  0 10 26 64 91 113 91 64 26 10  0  0  0  0
  ...
For example the row which corresponds to Z_7 is: 0 0 0 1 1 0 0 0.
The first '1' here corresponds to the 3-subsets of Z_7.
There are 4 congruence classes of the 3-subsets of Z_7, their representatives are {0,1,2}, {0,2,4}, {0,1,4} and {0,1,3}. The first 3 representatives have multiplier -1, but the last doesn't. Hence there is just one 3-subset of Z_7 without multiplier -1, up to congruency.

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
Petros Hadjicostas, The aperiodic version of Herbert Kociemba's formula for bracelets with no reflection symmetry, 2019.
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-Ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math. 313 (2013), 129-154. (See Table 1 on p. 137.) - From _N. J. A. Sloane_, Nov 26 2012
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Duncan M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

This sequence is A052307-A119963. The sequence A052307 is formed from the triangle whose (n, k)-term is the number of k-subsets of Z_n up to congruence, and the sequence A119963 is formed from the triangle whose (n, k)-term is the number of k-subsets of Z_n with multiplier -1 up to congruence.
The row sums of the 'OC(n, k, not -1)' triangle above give sequence A059076.
Cf. A001399 (column k = 3 with different offset), A008804 (column k = 4 with different offset), A032246 (column k = 5), A308401 (column k = 6), A032248 (column k = 7).

T(n,k) = if ((n==0) && (k==0), 0, -binomial(floor(n/2) - (k % 2) * (1 - n % 2), floor(k/2)) / 2 + sumdiv(gcd(n,k), d, (eulerphi(d)*binomial(n/d, k/d))) / (2*n));tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n,k), ", ")); print); \\ Michel Marcus, May 30 2019

From Petros Hadjicostas, May 29 2019: (Start)
T(n,k) = -binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) / 2 + Sum_{d|n, d|k} (phi(d)*binomial(n/d, k/d)) / (2*n) for n >= 1 and 0 <= k <= n. (This is a modification of formulas due to Gupta (1979), Shevelev (2004), and W. Bomfim in sequence A052307.)
T(n, k) = A052307(n, k) - A119963(n,k) for 0 <= k <= n. (See the comments in CROSSREFS by J. P. McSorley.)
T(n, k) = T(n, n - k) for 0 <= k <= n.
G.f. for column k >= 1: (x^k/2) * (-(1 + x)/(1 - x^2)^floor((k/2) + 1) + (1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m)). (This formula is due to Herbert Kociemba.)
(End)
Bivariate g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = (1/2) * (1 - (1 + x) * (1 + x*y) / (1 - x^2 * (1 + y^2)) - Sum_{d >= 1} (phi(d) / d) * log(1 - x^d * (1 + y^d))). - Petros Hadjicostas, Jun 15 2019

Name edited by Petros Hadjicostas, May 29 2019

Offset corrected by Andrew Howroyd, Sep 27 2019

A005515 Number of n-bead bracelets (turnover necklaces) of two colors with 10 red beads and n-10 black beads.

Original entry on oeis.org

1, 1, 6, 14, 47, 111, 280, 600, 1282, 2494, 4752, 8524, 14938, 25102, 41272, 65772, 102817, 156871, 235378, 346346, 502303, 716859, 1010256, 1404624, 1931540, 2625658, 3534776, 4711448, 6226148, 8156396, 10603704, 13679696, 17527595, 22304765, 28209566, 35459694

Offset: 10

N. J. A. Sloane

nonn

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent (turnover) necklaces of 10 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in case k=10 (see our comment to A032279). (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Andrew Howroyd, Table of n, a(n) for n = 10..1000
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.
W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A, 33 (1982), no. 1, 1-15.
W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
A. P. Street, Letter to N. J. A. Sloane, N.D.
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (4,-2,-12,17,9,-32,10,29,-29,-9,28,-7,-5,-5,-7,28,-9,-29,29,10,-32,9,17,-12,-2,4,-1).

Column k=10 of A052307.

k = 10; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
k=10;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[(k+2)/2])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

From Vladimir Shevelev, Apr 23 2011: (Start)
Put s(n,k,d) = 1, if n == k (mod d), and s(n,k,d) = 0, otherwise. Then a(n) = n*s(n,0,5)/25 + (384*C(n-1,9) + (n+1)*(n-2)*(n-4)*(n-6)*(n-8))/7680, if n is even; a(n) = (n-5)*s(n,0,5)/25 + (384*C(n-1,9) + (n-1)*(n-3)*(n-5)*(n-7)*(n-9))/7680, if n is odd. (End)
From Herbert Kociemba, Nov 04 2016: (Start)
G.f.: (1/20)*x^10*(1/(-1+x)^10 + 10/((-1+x)^6*(1+x)^5) + 1/(1-x^2)^5 + 4/(-1+x^5)^2 - 4/(-1+x^10)).
G.f.: k=10, x^k*((1/k)*Sum_{d|k} phi(d)*(1-x^d)^(-k/d) + (1+x)/(1-x^2)^floor((k+2)/2))/2. [edited by Petros Hadjicostas, Jan 10 2019] (End)

Sequence extended and description corrected by Christian G. Bower

Name edited by Petros Hadjicostas, Jan 10 2019

A005516 Number of n-bead bracelets (turnover necklaces) with 12 red beads.

Original entry on oeis.org

1, 1, 7, 19, 72, 196, 561, 1368, 3260, 7105, 14938, 29624, 56822, 104468, 186616, 322786, 544802, 896259, 1444147, 2278640, 3532144, 5380034, 8070400, 11926928, 17393969, 25042836, 35638596, 50152013, 69855536

Offset: 12

N. J. A. Sloane

nonn

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent (turnover) necklaces of 12 beads each of them painted by one of n colors.
The sequence solves the so-called Reis problem about convex k-gons in case k=12 (see our comment to A032279). (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 12..1000
H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 1-15.
W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)
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]
V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
V. Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5.)
A. P. Street, Letter to N. J. A. Sloane, N.D.
Index entries for sequences related to bracelets
Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,4,-4,12,-12,2,2,-12,24,-18,4,4,-6,15,-20,0,10,-4,10,0,-20,15,-6,4,4,-18,24,-12,2,2,-12,12,-4,4,-2,-4,4,-1).

Column k=12 of A052307.

k = 12; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] (* Robert A. Russell, Sep 27 2004 *)
k=12;CoefficientList[Series[x^k*(1/k Plus@@(EulerPhi[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^2)^Floor[k/2+1])/2,{x,0,50}],x] (* Herbert Kociemba, Nov 04 2016 *)

Let s(n,k,d) = 1, if n==k (mod d), s(n,k,d) = 0, otherwise. Then a(n) = s(n,0,12)/6 + (n-6)*s(n,0,6)/72 + (n-4)*(n-8)*s(n,0,4)/384 + (n-3)*(n-6)*(n-9)*s(n,0,3)/1944 + (3840*C(n-1,11) + (n+1)*(n-2)*(n-4)*(n-6)*(n-8)*(n-10))/92160, if n is even; a(n) = (n-3)*(n-6)*(n-9)*s(n,0,3)/1944 + (3840*C(n-1,11) + (n-1)*(n-3)*(n-5)*(n-7)*(n-9)*(n-11))/92160, if n is odd. - Vladimir Shevelev, Apr 23 2011
From Herbert Kociemba, Nov 04 2016: (Start)
G.f.: 1/2*x^12*((1+x)/(1-x^2)^7 + 1/12*(1/(-1+x)^12 + 1/(-1+x^2)^6 + 2/(-1+x^3)^4 - 2/(-1+x^4)^3 + 2/(-1+x^6)^2 - 4/(-1+x^12))).
G.f.: k=12, x^k*((1/k)*(Sum_{d|k} phi(d)*(1 - x^d)^(-k/d)) + (1 + x)/(1 -x^2)^floor((k+2)/2))/2. (End)

Sequence extended and description corrected by Christian G. Bower

A073020 Triangle of T(n,m) = number of bracelets (necklaces than can be turned over) with m white beads and (2n-m) black ones, for 1<=m<=n.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 4, 5, 8, 1, 5, 8, 16, 16, 1, 6, 12, 29, 38, 50, 1, 7, 16, 47, 79, 126, 133, 1, 8, 21, 72, 147, 280, 375, 440, 1, 9, 27, 104, 252, 561, 912, 1282, 1387, 1, 10, 33, 145, 406, 1032, 1980, 3260, 4262, 4752, 1, 11, 40, 195, 621, 1782, 3936, 7440, 11410

Offset: 1

Wouter Meeussen, Aug 03 2002

Left half of even rows of table A052307 with left column deleted.

			1; 1,2; 1,3,3; 1,4,5,8; 1,5,8,16,16; ...

Index entries for sequences related to bracelets

Cf. A052307, A047996, A072506, A005648. Cf. A078925 for odd number of beads. Last term in each row gives A005648.

Table[Length[ Union[Last[Sort[Flatten[Table[{RotateLeft[ #, i], Reverse[RotateLeft[ #, i]]}, {i, 2k}], 1]]]& /@ Permutations[IntegerDigits[2^(2k-j) (2^j-1), 2]]] ], {k, 9}, {j, k}]
Table[( -(-1)^n If[EvenQ[m+n], 0, Binomial[n-1, Floor[(m-2)/2]] ]/2 + Fold[ #1+EulerPhi[ #2]Binomial[2n/#2, m/#2]/(2n)&, Binomial[2Floor[n/2], Floor[m/2]], Intersection[Divisors[2n], Divisors[m]]]/2), {n, 9}, {m, n}]
Table[ f[k, 2n], {n, 11}, {k, n}] // Flatten (* Robert G. Wilson v, Mar 29 2006 *)

(1/2)*(C(2*(n\2), m\2) +Sum (d|(2n, m) phi(d)C(2n/d, m/d) ) - (-1)^n if(even(n+m), 0, C(n-1, floor(m/2-1/2) ).

cp's OEIS Frontend

A072605 Number of necklaces with n beads over an n-ary alphabet {a1,a2,...,an} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 0, where #(w,x) counts the letters x in word w.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A005514 Number of n-bead bracelets (turnover necklaces) with 8 red beads and n-8 black beads.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A032280 Number of bracelets (turnover necklaces) of n beads of 2 colors, 7 of them black.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A032281 Number of bracelets (turnover necklaces) of n beads of 2 colors, 9 of them black.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A032282 Number of bracelets (turnover necklaces) of n beads of 2 colors, 11 of them black.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A180472 Triangle T(n, k) = OC(n, k; not -1), read by rows, where OC(n, k; not -1) is the number of k-subsets of Z_n without -1 as a multiplier, up to congruency.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A005515 Number of n-bead bracelets (turnover necklaces) of two colors with 10 red beads and n-10 black beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica