A005648 Number of 2n-bead black-white reversible necklaces with n black beads.

1, 1, 2, 3, 8, 16, 50, 133, 440, 1387, 4752, 16159, 56822, 200474, 718146, 2587018, 9398520, 34324174, 126068558, 465093571, 1723176308, 6407924300, 23910576230, 89494164973, 335913918902, 1264107416466

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

a(n) is the coefficient of c_1^n*c_2^n in the cycle index polynomial for the dihedral group D_{2*n} evaluated with the figure counting polynomial c = c_1 + c_2, n>=1, abbreviated as Z(D_{2*n},c). See, e.g., the Harary-Palmer reference (given under A212355), p. 42, Theorem (PET), and the example for all 6 two-colored 4-bracelets (called there necklaces) on p. 44, Figure 2.4.2. - Wolfdieter Lang, Jun 05 2012

Examples

			a(2) = 2: BBWW, BWBW.
a(3) = 3: BBBWWW, BBWBWW, BWBWBW.
a(4) = 8: BBBBWWWW, BBBWBWWW, BBBWWBWW, BBWWBBWW, BBWBWBWW, BBWBWWBW, BBWBBWWW, BWBWBWBW.
		

References

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

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1665 (terms 0..200 from Andrew Howroyd)
• Marcia Ascher, Mu torere: an analysis of a Maori game, Math. Mag. 60 (1987), no. 2, 90-100.
• R. K. Guy & N. J. A. Sloane, Correspondence, 1985
• Paul Melotti, Sanjay Ramassamy, Paul Thévenin, Points and lines configurations for perpendicular bisectors of convex cyclic polygons, arXiv:2003.11006 [math.CO], 2020.
• E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations Pacific J. Math., 110 (1984), 203-221.
• 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

Crossrefs

Cf. A000984, A003239.

Programs

Mathematica

f[k_Integer, n_] := (Plus @@ (EulerPhi[ # ]Binomial[n/#, k/# ] & /@ Divisors[GCD[n, k]])/n + Binomial[(n - If[OddQ@n, 1, If[OddQ@k, 2, 0]])/2, (k - If[OddQ@k, 1, 0])/2])/2 (* Robert A. Russell, Sep 27 2004 *)
Table[ f[n, 2n], {n, 27}] (* Robert G. Wilson v, Mar 29 2006 *)
a[0] = 1; a[n_] := 1/2*(Binomial[2*Quotient[n, 2], Quotient[n, 2]] + DivisorSum[n, EulerPhi[#]*Binomial[2*n/#, n/#]&]/(2*n)); Array[a, 26, 0] (* Jean-François Alcover, Nov 05 2017, translated from PARI *)

PARI

a(n) = 1/2*( binomial(2*(n\2), n\2) + if(n<1, n >= 0, sumdiv(n, k, eulerphi(k)*binomial(2*n/k, n/k))/(2*n) ));

Formula

a(n) = ( Sum_{d|n} phi(n/d)*C(2*d, d) )/(4*n) + C(2*k, k)/2, where k = floor(n/2). - Michael Somos

a(n) = (A003239(n) + C(2*k, k))/2, where k = [ n/2 ]. - R. J. Fletcher, (yylee(AT)mail.ncku.edu.tw)

Extensions

Sequence extended and description corrected by Christian G. Bower

Example n=8 (word no. 6) corrected by Wolfdieter Lang, Jun 05 2012