A032193 -id:A032193 - cp's OEIS frontend

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

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

A032194 Number of necklaces with 9 black beads and n-9 white beads.

Original entry on oeis.org

1, 1, 5, 19, 55, 143, 335, 715, 1430, 2704, 4862, 8398, 14000, 22610, 35530, 54484, 81719, 120175, 173593, 246675, 345345, 476913, 650325, 876525, 1168710, 1542684, 2017356, 2615104, 3362260, 4289780, 5433736, 6835972

Offset: 9

Christian G. Bower

nonn

The g.f. is Z(C_9,x)/x^9, the 9-variate cycle index polynomial for the cyclic group C_9, with substitution x[i]->1/(1-x^i), i=1,...,9. Therefore by Polya enumeration a(n+9) is the number of cyclically inequivalent 9-necklaces whose 9 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_9,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

Christian G. Bower, Transforms (2)
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See p. 19.
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]
Index entries for sequences related to necklaces
Index entries for linear recurrences with constant coefficients, signature (6,-15,22,-27,36,-42,36,-27,23,-21,21,-23,27,-36,42,-36,27,-22,15,-6,1).

Column k=9 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193.

k = 9; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)

"CIK[ 9 ]" (necklace, indistinct, unlabeled, 9 parts) transform of 1, 1, 1, 1...
G.f.: (x^9)*(1-5*x+14*x^2-18*x^3+21*x^4-21*x^5+25*x^6 -21*x^7 +21*x^8 -18*x^9 +14*x^10 -5*x^11 +x^12) / ((1-x)^6*(1-x^3)^2*(1-x^9)).
G.f.: (1/9)*x^9*(1/(1-x)^9+2/(1-x^3)^3+6/(1-x^9)^1). - Herbert Kociemba, Oct 22 2016

A347975 Triangle read by rows: T(n, k) is the number of k-dimensional subspaces in (F_9)^n, counted up to coordinate permutation (n >= 0, 0 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 21, 21, 1, 1, 64, 374, 64, 1, 1, 163, 5900, 5900, 163, 1, 1, 380, 82587, 644680, 82587, 380, 1, 1, 809, 1018388, 66136870, 66136870, 1018388, 809, 1, 1, 1619, 11174165, 6057912073, 52901629980, 6057912073, 11174165, 1619, 1, 1, 3049, 110404788

Offset: 0

Álvar Ibeas, Sep 21 2021

Columns can be computed by a method analogous to that of Fripertinger for isometry classes of linear codes, disallowing scalar transformation of individual coordinates.

Regarding the formula for column k = 1, note that A241926(q-1, n) counts, up to coordinate permutation, one-dimensional subspaces of (F_q)^n generated by a vector with no zero component.

			Triangle begins:
  k:  0    1    2    3    4    5
      --------------------------
n=0:  1
n=1:  1    1
n=2:  1    6    1
n=3:  1   21   21    1
n=4:  1   64  374   64    1
n=5:  1  163 5900 5900  163    1
There are 10 = A022173(2, 1) one-dimensional subspaces in (F_9)^2. Among them, <(1, 1)> and <(1, 2)> are invariant by coordinate swap and the rest are grouped in orbits of size two. Hence, T(2, 1) = 6.

Álvar Ibeas, Entries up to T(10, 4)
H. Fripertinger, Isometry classes of codes
Álvar Ibeas, Column k=1 up to n=100
Álvar Ibeas, Column k=2 up to n=100
Álvar Ibeas, Column k=3 up to n=100
Álvar Ibeas, Column k=4 up to n=100

Cf. A022173, A032193, A241926.

T(n, 1) = T(n-1, 1) + A032193(n+8).

A032195 Number of necklaces with 10 black beads and n-10 white beads.

Original entry on oeis.org

1, 1, 6, 22, 73, 201, 504, 1144, 2438, 4862, 9252, 16796, 29414, 49742, 81752, 130752, 204347, 312455, 468754, 690690, 1001603, 1430715, 2016144, 2804880, 3856892, 5245128, 7060984, 9414328, 12440668, 16301164

Offset: 10

Christian G. Bower

nonn

The g.f. is Z(C_10,x)/x^10, the 10-variate cycle index polynomial for the cyclic group C_10, with substitution x[i]->1/(1-x^i), i=1,...,10. By Polya enumeration, a(n+10) is the number of cyclically inequivalent 10-necklaces whose 10 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_10,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

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 necklaces
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 A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193, A032194.

k = 10; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)

"CIK[ 10 ]" (necklace, indistinct, unlabeled, 10 parts) transform of 1, 1, 1, 1...
G.f.: (x^10)*(1-3*x+4*x^2+12*x^3-8*x^4-x^5+31*x^6-4*x^8+16*x^9 +11*x^10 +3*x^11+8*x^12+4*x^13+4*x^14+x^15+x^16) /((1-x)^4*(1-x^2)^4 *(1-x^5)*(1-x^10)).
G.f.: (1/10)*x^10*(1/(1 - x)^10 + 1/(1 - x^2)^5 + 4/(1 - x^5)^2 + 4/(1 - x^10)^1). - Herbert Kociemba, Oct 22 2016

A032196 Number of necklaces with 11 black beads and n-11 white beads.

Original entry on oeis.org

1, 1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32066, 58786, 104006, 178296, 297160, 482885, 766935, 1193010, 1820910, 2731365, 4032015, 5864750, 8414640, 11920740, 16689036, 23107896, 31666376, 42975796

Offset: 11

Christian G. Bower

nonn

The g.f. is Z(C_11,x)/x^11, the 11-variate cycle index polynomial for the cyclic group C_11, with substitution x[i]->1/(1-x^i), i=1..11. By Polya enumeration, a(n+11) is the number of cyclically inequivalent 11-necklaces whose 11 beads are labeled with nonnegative integers such that the sum of labels is n, for n=0,1,2,... See A102190 for Z(C_11,x). See the comment in A032191 on the equivalence of this problem with the one given in the `Name' line. - Wolfdieter Lang, Feb 15 2005

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 necklaces
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1,1,-10,45,-120,210,-252,210,-120,45,-10,1).

Column k=11 of A047996.

Cf. A004526, A007997, A008610, A008646, A032191, A032192, A032193, A032194, A032195.

k = 11; Table[Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n, {n, k, 30}] (* Robert A. Russell, Sep 27 2004 *)
DeleteCases[CoefficientList[Series[(x^11) (1 - 9 x + 41 x^2 - 109 x^3 + 191 x^4 - 229 x^5 + 191 x^6 - 109 x^7 + 41 x^8 - 9 x^9 + x^10)/((1 - x)^10 (1 - x^11)), {x, 0, 39}], x], 0] (* Michael De Vlieger, Oct 10 2016 *)

"CIK[ 11 ]" (necklace, indistinct, unlabeled, 11 parts) transform of 1, 1, 1, 1...
G.f.: (x^11) * (1 - 9*x + 41*x^2 - 109*x^3 + 191*x^4 - 229*x^5 + 191*x^6 - 109*x^7 + 41*x^8 - 9*x^9 + x^10) / ((1-x)^10 * (1-x^11)).
a(n) = ceiling(binomial(n, 11)/n) (conjecture Wolfdieter Lang).
From Herbert Kociemba, Oct 11 2016: (Start)
This conjecture indeed is true.
Sketch of proof:
There are binomial(n,11) ways to place the 11 black beads in the necklace with n beads. If n is not divisible by 11 there are no necklaces with a rotational symmetry. So exactly n necklaces are equivalent up to rotation and there are binomial(n,11)/n = ceiling(binomial(n,11)/n) equivalence classes.
If n is divisible by 11 the only way to get a necklace with rotational symmetry is to space out the 11 black beads evenly. There are n/11 ways to do this and all ways are equivalent up to rotation. So there are  binomial(n,11) - n/11 unsymmetric necklaces which give binomial(n,11)/n - 1/11 equivalence classes. If we add the single symmetric equivalence class we get Binomial(n,11)/n - 1/11 + 1 which also is ceiling(binomial(n,11)/n). (End)
G.f.: (10/(1 - x^11) + 1/(1 - x)^11)*x^11/11. - Herbert Kociemba, Oct 16 2016

cp's OEIS Frontend

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

A032194 Number of necklaces with 9 black beads and n-9 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A347975 Triangle read by rows: T(n, k) is the number of k-dimensional subspaces in (F_9)^n, counted up to coordinate permutation (n >= 0, 0 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A032195 Number of necklaces with 10 black beads and n-10 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A032196 Number of necklaces with 11 black beads and n-11 white beads.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula