login
A296600
Number of pairs of binary strings (u,v) with u of length n, v of length 2n, and u and v mutually overlapping.
1
2, 26, 244, 2070, 17100, 138684, 1117200, 8966634, 71848980, 575237140, 4603664560, 36836229636, 294717238960
OFFSET
1,1
COMMENTS
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.
PROG
(Python)
from itertools import product
def overlapping(u, v):
for i in range(1, 1+min(len(u), len(v))):
if v[:i]==u[-i:]: return True
return False
def a(n):
out = 0
for u in product("01", repeat=n-1):
u = ("0", ) + u
for v in product("01", repeat=2*n):
if overlapping(u, v) and overlapping(v, u): out += 1
return 2*out # by symmetry
print([a(n) for n in range(1, 8)]) # Michael S. Branicky, Jul 01 2023
CROSSREFS
Cf. A295863.
Sequence in context: A280556 A198960 A289263 * A187252 A096233 A363985
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Feb 15 2018
EXTENSIONS
a(9)-a(13) from Lars Blomberg, Nov 30 2018
STATUS
approved