

A346586


Number of lengthn binary words having borders with two mismatches.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A word x has a border with two mismatches if there are an equallength 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) 220226.


EXAMPLE

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


PROG

(Python) # see link for faster, bitbased 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=n1))
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



