A346586 - OEIS

%I #20 Apr 17 2022 01:15:38

%S 0,0,2,8,22,46,98,210,430,886,1790,3638,7350,14830,29758,59802,119802,

%T 240362,480966,963302,1927382,3857746,7715446,15437078,30873042,

%U 61759618,123512490,247051278,494077866,988213906,1976359510,3952834998,7905474522,15811215542,31621940822,63244422558

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

%C 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.

%H Michael S. Branicky, <a href="/A346586/b346586.txt">Table of n, a(n) for n = 1..40</a>

%H Michael S. Branicky, <a href="/A346586/a346586.txt">Python program</a>

%H S. Klavžar and S. Shpectorov, <a href="https://doi.org/10.1016/j.ejc.2011.10.001">Asymptotic number of isometric generalized Fibonacci cubes</a>, European J. Combin. 33 (2012) 220-226.

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

%o (Python) # see link for faster, bit-based version

%o from itertools import product

%o def ham(w, v): return sum(w[i] != v[i] for i in range(len(w)))

%o def m(b):

%o     for i in range(2, len(b)):

%o         p, s = b[:i], b[-i:]

%o         if ham(p, s) == 2: return True

%o     return False

%o def a(n): return 2*sum(m("0"+"".join(b)) for b in product("01", repeat=n-1))

%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jul 24 2021

%K nonn

%O 1,3

%A _Jeffrey Shallit_, Jul 24 2021

%E a(31)-a(36) from _Michael S. Branicky_, Jul 24 2021