|
%I #19 Dec 06 2020 10:56:22
%S 2,6,30,130,536,2174,8746,35070,140438,562008,2248460,8994530,
%T 35979160,143917970,575673270,2302692898,9210765608
%N Number of ordered pairs of length-n mutually overlapping binary strings.
%C A pair of strings (u,v) is mutually overlapping if some nonempty suffix of u is a prefix of v, and vice versa, such as (00101010,10110001).
%C All terms are even. - _Michael S. Branicky_, Dec 06 2020
%o (Python)
%o from itertools import product
%o def overlapping(u, v):
%o for i in range(1, 1+min(len(u), len(v))):
%o if v[:i]==u[-i:]: return True
%o return False
%o def a(n):
%o out = 0
%o for u in product("01", repeat=n-1):
%o u = ("0",) + u
%o for v in product("01", repeat=n):
%o if overlapping(u, v) and overlapping(v, u): out += 1
%o return 2*out # by symmetry
%o print([a(n) for n in range(1, 11)]) # _Michael S. Branicky_, Dec 06 2020
%Y Cf. A296600.
%K nonn,more
%O 1,1
%A _Jeffrey Shallit_, Feb 13 2018
%E a(14)-a(17) from _Michael S. Branicky_, Dec 06 2020
| 