A346586 Number of length-n binary words having borders with two mismatches.

0, 0, 2, 8, 22, 46, 98, 210, 430, 886, 1790, 3638, 7350, 14830, 29758, 59802, 119802, 240362, 480966, 963302, 1927382, 3857746, 7715446, 15437078, 30873042, 61759618, 123512490, 247051278, 494077866, 988213906, 1976359510, 3952834998, 7905474522, 15811215542, 31621940822, 63244422558

Offset

1,3

Comments

A word x has a border with two mismatches if there are an equal-length prefix p and suffix s (nonempty, not equal to x, but allowed to overlap) such that the Hamming distance of p and s is exactly two. For example, the English word 'added' has a prefix 'add' and a suffix 'ded' at Hamming distance two.

Links

Michael S. Branicky, Table of n, a(n) for n = 1..40

Michael S. Branicky, Python program

S. Klavžar and S. Shpectorov, Asymptotic number of isometric generalized Fibonacci cubes, European J. Combin. 33 (2012) 220-226.

Example

For n = 3 the only examples are 010 and 101.

Prog

(Python) # see link for faster, bit-based version
from itertools import product
def ham(w, v): return sum(w[i] != v[i] for i in range(len(w)))
def m(b):
    for i in range(2, len(b)):
        p, s = b[:i], b[-i:]
        if ham(p, s) == 2: return True
    return False
def a(n): return 2*sum(m("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jul 24 2021

Crossrefs

Sequence in context: A284922 A212970 A212683 * A094533 A006696 A094939

Adjacent sequences: A346583 A346584 A346585 * A346587 A346588 A346589

Keyword

nonn

Author

Jeffrey Shallit, Jul 24 2021

Extensions

a(31)-a(36) from Michael S. Branicky, Jul 24 2021

Status

approved