login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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 (list; graph; refs; listen; history; text; internal format)
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 27 07:28 EST 2021. Contains 349365 sequences. (Running on oeis4.)