A332918 Average number of binary strings of length n with Levenshtein distance <= 3 from a uniform randomly sampled binary string of this length, rounded to nearest integer.

8, 16, 29, 51, 85, 136, 206, 301, 423, 577, 768, 998, 1272, 1594, 1969, 2399, 2889, 3443, 4066, 4760, 5530, 6380, 7315, 8337, 9451, 10661, 11972, 13386, 14908, 16542, 18293, 20163, 22157, 24279, 26534, 28924, 31454, 34128, 36951, 39925, 43055, 46345, 49800

Offset

3,1

Comments

For more information see A332916.

Links

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

Formula

a(n) = round(A332916(n)/2^A332917(n)).

Conjectures from Colin Barker, Mar 05 2020: (Start)

G.f.: x^3*(8 - 8*x + 5*x^2 + 4*x^3 - 5*x^4 + 13*x^5 - 3*x^6 + 2*x^7 - x^8 + 3*x^10 - 4*x^11 + 3*x^12 - x^13) / ((1 - x)^4*(1 + x)*(1 + x^2)).

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + a(n-4) - 3*a(n-5) + 3*a(n-6) - a(n-7) for n>16.

(End)

Prog

(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, 45, print1(round(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 int(round(f(n)))
print([a(n) for n in range(3, 46)]) # Michael S. Branicky, Aug 31 2021

Crossrefs

Cf. A332916, A332917.

Sequence in context: A204644 A191271 A047925 * A363280 A266086 A018922

Adjacent sequences: A332915 A332916 A332917 * A332919 A332920 A332921

Keyword

nonn,easy

Author

Hugo Pfoertner, Mar 05 2020

Status

approved