

A005514


Number of nbead bracelets (turnover necklaces) with 8 red beads and n8 black beads.
(Formerly M3801)


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

8,3


COMMENTS

From Vladimir Shevelev, Apr 23 2011: (Start)
Also number of nonequivalent necklaces of 8 beads each of them painted by one of n colors.
The sequence solves the socalled Reis problem about convex kgons in case k=8 (see our comment to 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_{dk} 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/(1x). Thus, a(n) = a_8(n) for all n >= 1. Since a_k(n) = 0 for 1 <= n <= k1, 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/(1x) and k=8, we get H. Kociemba's formula below.
Here, a(n) is defined as the number of nbead bracelets of two colors with 8 red beads and n8 black beads. But it is also the number of dihedral compositions of n with 8 parts. (This statement is equivalent to V. Shevelev's statement above that a(n) is the "number of nonequivalent necklaces of 8 beads each of them painted by one of n colors." By "necklaces" he means "turnover necklaces". See paragraph (2) 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)


REFERENCES

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), 3740.


LINKS

Table of n, a(n) for n=8..42.
C. G. Bower, Transforms (2)
S. J. Cyvin, B. N. Cyvin, J. Brunvoll, I. Gutman, Chen Rongsi, S. ElBasil, and Zhang Fuji, Polygonal systems including the corannulene and coronene homologs: novel applications of PĆ³lya's theorem, Z. Naturforsch., 52a (1997), 867873.
H. Gupta, Enumeration of incongruent cyclic kgons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964999.
W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 115.
W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 115. (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, 10001001.
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 kgons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629638.
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


FORMULA

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
From Vladimir Shevelev, Apr 23 2011: (Start)
Let s(n,k,d)=1, if n==k(mod d), and 0 otherwise. Then
a(n) = ((n+4)/32)*s(n,0,8)+((n4)/32)*s(n,4,8)+(48*C(n1,7)+(n+1)*(n2)*(n4)*(n6))/768, if n is even >= 8; a(n) = (48*C(n1,7)+(n1)*(n3)*(n5)*(n7))/768, if n odd >= 8.
(End)
G.f.: k=8, x^k*((1/k)*Sum_{dk} phi(d)*(1x^d)^(k/d) + (1+x)/(1x^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)


EXAMPLE

From Petros Hadjicostas, Jul 14 2018: (Start)
Every nbead bracelet of two colors such that 8 beads are red and n8 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)


MATHEMATICA

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[#] (1x^#)^((k/#))&/@Divisors[k])+(1+x)/(1x^2)^Floor[(k+2)/2])/2, {x, 0, 50}], x] (* Herbert Kociemba, Nov 04 2016 *)


CROSSREFS

Cf. A008805, A032193, A032279, A032280, A032281, A032282, A119963, A292906.
Sequence in context: A105862 A093029 A105505 * A069921 A053818 A294286
Adjacent sequences: A005511 A005512 A005513 * A005515 A005516 A005517


KEYWORD

nonn,easy,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

Sequence extended and description corrected by Christian G. Bower
Name edited by Petros Hadjicostas, Jul 20 2018


STATUS

approved



