A332916 a(n)/2^A332917(n) is the average number of binary strings of length n with Levenshtein distance <= 3 from a uniform randomly sampled binary string of this length.

8, 31, 461, 815, 5463, 4347, 52813, 76981, 433219, 147811, 3144425, 4087643, 20844159, 13062033, 129023493, 157220577, 757398907, 112836563, 4263247073, 4991221319, 23195548727, 13380878071, 122721139581, 139871649165, 634262649523, 178870288201, 3213642168793

Offset

3,1

Comments

Problem posed by user "Anush" in Code Golf Stack Exchange, with a solution by Christian Sievers. See link.

Links

Table of n, a(n) for n=3..29.

Code Golf Stack Exchange, Average number of strings with Levenshtein distance up to 3, Dec 27 - Dec 31, 2019.

Wikipedia, Levenshtein distance

Prog

(GAP) See Code Golf Stack Exchange Link.
(PARI) f(n)=(40+6*n-4*n^2)/2^n-83/2+331/12*n-6*n^2+2/3*n^3;
for(k=3, 30, print1(numerator(f(k)), ", "))
(Python)
from fractions import Fraction
def f(n): return Fraction(40+6*n-4*n**2, 2**n) - Fraction(83, 2) + Fraction(331*n, 12) - 6*n**2 + Fraction(2*n**3, 3)
def a(n): return f(n).numerator
print([a(n) for n in range(3, 30)]) # Michael S. Branicky, Aug 31 2021

Crossrefs

Cf. A332917, A332918.

Sequence in context: A209484 A209343 A270523 * A270353 A270400 A269999

Adjacent sequences: A332913 A332914 A332915 * A332917 A332918 A332919

Keyword

nonn,frac

Author

Hugo Pfoertner, Mar 05 2020

Status

approved