A027618 c(i,j) is cost of evaluation of edit distance of two strings with lengths i and j, when you use recursion (every call has a unit cost, other computations are free); sequence gives c(n,n).

1, 4, 19, 94, 481, 2524, 13483, 72958, 398593, 2193844, 12146179, 67570078, 377393953, 2114900428, 11885772379, 66963572734, 378082854913, 2138752086628, 12118975586803, 68774144872414, 390815720696161, 2223564321341884

Offset: 0

Author

Bruno Petazzoni (Bruno.Petazzoni(AT)ac-idf.jussieu.fr)

Keywords

• nonn
• easy
• nice

References

• Found by 7 students: Dufour, Hermon, Lesueur, Moynot, Schabanel, Sers and Wolf.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200

Crossrefs

Delannoy numbers A008288, A001850 are given by c'(i, j)=(3c(i, j)-1)/2.

Programs

Mathematica

Table[SeriesCoefficient[(3/Sqrt[1-6*x+x^2]-1/(1-x))/2,{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 08 2012 *)

PARI

x='x+O('x^66); Vec((3/sqrt(1-6*x+x^2)-1/(1-x))/2) \\ Joerg Arndt, May 04 2013

Formula

c(n, n) where c(i, 0)=c(0, j)=1 and c(i+1, j+1)=1+c(i+1, j)+c(i, j+1)+c(i, j) (c(i, j) is A047671).

G.f.: (3/sqrt(1-6*x+x^2)-1/(1-x))/2.

Recurrence: n*(2*n-3)*a(n) = (2*n-1)*(7*n-10)*a(n-1) - (2*n-3)*(7*n-4)*a(n-2) + (n-2)*(2*n-1)*a(n-3). - Vaclav Kotesovec, Oct 08 2012

a(n) ~ 3*sqrt(8+6*sqrt(2))*(3+2*sqrt(2))^n/(8*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012