

A237500


Number of binary strings of length 2n which contain the ones' complement of each of their two halves.


3



2, 6, 12, 28, 58, 118, 244, 500, 1004, 2024, 4070, 8150, 16340, 32720, 65450, 130986, 262056, 524136, 1048422, 2096982, 4194000, 8388300, 16776906
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


LINKS



EXAMPLE

The two halves of 011001 are 011 and 001. Their complements are 100 and 110, and both are substrings of 011001. Since there are 11 other strings of length 2*3 with this property, a(3) = 12.


MATHEMATICA

sQ[L_, {s__}] := MatchQ[L, {___, s, ___}]; a[n_] := Length@ Select[ Tuples[{0, 1}, 2@n], sQ[#, 1Take[#, n]] && sQ[#, 1Take[#, n]] &]; Array[a, 8]


PROG

(Python) # see link for faster version
from itertools import product as prod
def comp(s): z, o = ord('0'), ord('1'); return s.translate({z:o, o:z})
def ok(s): return comp(s[:len(s)//2]) in s and comp(s[len(s)//2:]) in s
def a(n): return 2*sum(ok("0"+"".join(p)) for p in prod("01", repeat=2*n1))


CROSSREFS



KEYWORD

nonn,more


AUTHOR



EXTENSIONS



STATUS

approved



