|
%I #21 Jul 01 2023 12:21:06
%S 2,26,244,2070,17100,138684,1117200,8966634,71848980,575237140,
%T 4603664560,36836229636,294717238960
%N Number of pairs of binary strings (u,v) with u of length n, v of length 2n, and u and v mutually overlapping.
%C We say the pair (u,v) is mutually overlapping if some nonempty prefix of u is a suffix of v, and vice versa. For n = 3, an example is (011,110110). If C(m,n) is the number of mutually overlapping ordered pairs (u,v) with |u|=m and |v|=n, then C(m,2m+a) = 2^a C(m,2m) for a >= 0, so the case enumerated by this sequence is in some sense the most useful to understand.
%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=2*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, 8)]) # _Michael S. Branicky_, Jul 01 2023
%Y Cf. A295863.
%K nonn,more
%O 1,1
%A _Jeffrey Shallit_, Feb 15 2018
%E a(9)-a(13) from _Lars Blomberg_, Nov 30 2018
|
