login
Number of ordered pairs of length-n mutually overlapping binary strings.
1

%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