Search: id:a005648
|
|
A005648
|
|
Number of 2n-bead black-white reversible necklaces with n black beads.
(Formerly M0878)
|
|
+0
13
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
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)
|
|
EXAMPLE
|
a(2) = 2: BBWW, BWBW.
a(3) = 3: BBBWWW, BBWBWW, BWBWBW.
a(4) = 8: BBBBWWWW, BBBWBWWW, BBBWWBWW, BBWWBBWW, BBWBWBWW, BBWBWWBW, BBWBBWWW, BWBWBWBW.
|
|
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 *)
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 *)
|
|
PROG
|
(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) ));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.005 seconds
|