A045629 Number of 2n-bead black-white complementable necklaces with n black beads.

1, 1, 2, 3, 7, 15, 44, 128, 415, 1367, 4654, 16080, 56450, 200170, 716728, 2585850, 9393119, 34319667, 126047906, 465076160, 1723097066, 6407856892, 23910271224, 89493903438, 335912741682, 1264106399934, 4768448177636, 18027218147818

Offset: 0

Author

David W. Wilson

Keywords

• nonn

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Index entries for sequences related to necklaces

Crossrefs

Cf. A006840.

Programs

Mathematica

a[n_] := If[n == 0, 1, (1/(2*n))*DivisorSum[n, EulerPhi[n/#1]*Binomial[2*#1 - 1, #1 - 1] + EulerPhi[2*(n/#1)]*2^(#1 - 1)&]];
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Oct 08 2017, translated from PARI *)

PARI

a(n) = if(n==0, 1, (1/(2*n)) * sumdiv(n, d, eulerphi(n/d)*binomial(2*d-1, d-1) + eulerphi(2*n/d)*2^(d-1))); \\ Andrew Howroyd, Sep 27 2017

Formula

a(n) = (1/2n) * Sum_{d|n} (phi(n/d)*C(2d-1, d-1) + phi(2n/d)*2^(d-1)). - Christian G. Bower

a(n) ~ 4^(n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Oct 08 2017