login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005514 Number of n-bead bracelets (turnover necklaces) with 8 red beads and n-8 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 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 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_{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 H. Kociemba's formula below.

Here, a(n) is defined as 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 V. 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 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).

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

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)

Richard H. Reis, A formula for C(T) in Gupta's paper, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 1000-1001.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

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

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)+((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.

(End)

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)

EXAMPLE

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)

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[#] (1-x^#)^(-(k/#))&/@Divisors[k])+(1+x)/(1-x^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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 22:28 EDT 2018. Contains 316378 sequences. (Running on oeis4.)