A007148 Number of self-complementary 2-colored bracelets (turnover necklaces) with 2n beads.

1, 2, 3, 6, 10, 20, 37, 74, 143, 284, 559, 1114, 2206, 4394, 8740, 17418, 34696, 69194, 137971, 275280, 549258, 1096286, 2188333, 4369162, 8724154, 17422652, 34797199, 69505908, 138845926, 277383872, 554189329, 1107297290, 2212558942

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• 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. A000013, A000079, A007147.

Different from, but easily confused with, A045690 and A093371.

Programs

Maple

# see A245558
L := proc(n,k)
    local a,j ;
    a := 0 ;
    for j in numtheory[divisors](igcd(n,k)) do
        a := a+numtheory[mobius](j)*binomial(n/j,k/j) ;
    end do:
    a/n ;
end proc:
A007148 := proc(n)
    local a,k,l;
    a := 0 ;
    for k from 1 to n do
        for l in numtheory[divisors](igcd(n,k)) do
            a := a+L(n/l,k/l)*ceil(k/2/l) ;
        end do:
    end do:
    a;
end proc:
seq(A007148(n),n=1..20) ; # R. J. Mathar, Jul 23 2017

Mathematica

a[n_] := (1/2)*(2^(n-1) + Total[ EulerPhi[2*#]*2^(n/#) &  /@ Divisors[n]]/(2*n)); Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 25 2011 *)

PARI

a(n)= (1/2) *(2^(n-1)+sumdiv(n,k,eulerphi(2*k)*2^(n/k))/(2*n))

Python

from sympy import divisors, totient
def a(n):
    if n==1: return 1
    return 2**(n - 2) + sum(totient(2*d)*2**(n//d) for d in divisors(n))//(4*n)
print([a(n) for n in range(1, 31)]) # Indranil Ghosh, Jul 24 2017

Formula

a(n) = 2^(n-2) + (1/(4n)) * Sum_{d|n} phi(2d)*2^(n/d). - N. J. A. Sloane, Sep 25 2012

a(n) = (1/2)*(A000079(n-1) + A000013(n)).

Extensions

Description corrected by Christian G. Bower