A296600 Number of pairs of binary strings (u,v) with u of length n, v of length 2n, and u and v mutually overlapping.

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.

Links

Table of n, a(n) for n=1..13.

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

Adjacent sequences: A296597 A296598 A296599 * A296601 A296602 A296603

Keyword

nonn,more

Author

Jeffrey Shallit, Feb 15 2018

Extensions

a(9)-a(13) from Lars Blomberg, Nov 30 2018

Status

approved