|
%I #11 Aug 31 2021 06:24:55
%S 8,31,461,815,5463,4347,52813,76981,433219,147811,3144425,4087643,
%T 20844159,13062033,129023493,157220577,757398907,112836563,4263247073,
%U 4991221319,23195548727,13380878071,122721139581,139871649165,634262649523,178870288201,3213642168793
%N 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.
%C Problem posed by user "Anush" in Code Golf Stack Exchange, with a solution by _Christian Sievers_. See link.
%H Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/197524/average-number-of-strings-with-levenshtein-distance-up-to-3/">Average number of strings with Levenshtein distance up to 3</a>, Dec 27 - Dec 31, 2019.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein distance</a>
%o (GAP) See Code Golf Stack Exchange Link.
%o (PARI) f(n)=(40+6*n-4*n^2)/2^n-83/2+331/12*n-6*n^2+2/3*n^3;
%o for(k=3,30,print1(numerator(f(k)),", "))
%o (Python)
%o from fractions import Fraction
%o 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)
%o def a(n): return f(n).numerator
%o print([a(n) for n in range(3, 30)]) # _Michael S. Branicky_, Aug 31 2021
%Y Cf. A332917, A332918.
%K nonn,frac
%O 3,1
%A _Hugo Pfoertner_, Mar 05 2020
|
