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

2, 6, 30, 130, 536, 2174, 8746, 35070, 140438, 562008, 2248460, 8994530, 35979160, 143917970, 575673270, 2302692898, 9210765608

Offset

1,1

Comments

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).

All terms are even. - Michael S. Branicky, Dec 06 2020

Links

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

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=n):
            if overlapping(u, v) and overlapping(v, u): out += 1
    return 2*out # by symmetry
print([a(n) for n in range(1, 11)]) # Michael S. Branicky, Dec 06 2020

Crossrefs

Cf. A296600.

Sequence in context: A065563 A035105 A073969 * A224530 A120950 A055695

Adjacent sequences: A295860 A295861 A295862 * A295864 A295865 A295866

Keyword

nonn,more

Author

Jeffrey Shallit, Feb 13 2018

Extensions

a(14)-a(17) from Michael S. Branicky, Dec 06 2020

Status

approved