|
| |
|
|
A346586
|
|
Number of length-n 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 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
|
|
|
|
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))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
