login
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, 33553866, 67108266, 134217126, 268434342, 536869782, 1073740692, 2147481432, 4294965078, 8589932374, 17179864912, 34359734092, 68719472302, 137438944942, 274877898412, 549755805352, 1099511611042, 2199023238562
OFFSET
1,1
LINKS
Michael S. Branicky, Python program
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[#, 1-Take[#, n]] && sQ[#, 1-Take[#, -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*n-1))
print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Feb 06 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Giovanni Resta, Feb 08 2014
EXTENSIONS
a(17)-a(21) from Michael S. Branicky, Feb 06 2021
a(22) from Michael S. Branicky, Jul 06 2022
a(23) from Michael S. Branicky, Jul 25 2022
Terms a(24) onward from Max Alekseyev, Jul 23 2024
STATUS
approved