login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 09:50 EDT 2022. Contains 353949 sequences. (Running on oeis4.)