%I #14 Oct 07 2013 03:24:56
%S 1,4,19,94,481,2524,13483,72958,398593,2193844,12146179,67570078,
%T 377393953,2114900428,11885772379,66963572734,378082854913,
%U 2138752086628,12118975586803,68774144872414,390815720696161,2223564321341884
%N 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).
%D Found by 7 students: Dufour, Hermon, Lesueur, Moynot, Schabanel, Sers and Wolf.
%H Vincenzo Librandi, <a href="/A027618/b027618.txt">Table of n, a(n) for n = 0..200</a>
%F 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).
%F G.f.: (3/sqrt(1-6*x+x^2)-1/(1-x))/2.
%F 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
%F a(n) ~ 3*sqrt(8+6*sqrt(2))*(3+2*sqrt(2))^n/(8*sqrt(Pi*n)). - _Vaclav Kotesovec_, Oct 08 2012
%t Table[SeriesCoefficient[(3/Sqrt[1-6*x+x^2]-1/(1-x))/2,{x,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 08 2012 *)
%o (PARI) x='x+O('x^66); Vec((3/sqrt(1-6*x+x^2)-1/(1-x))/2) \\ _Joerg Arndt_, May 04 2013
%Y Delannoy numbers A008288, A001850 are given by c'(i, j)=(3c(i, j)-1)/2.
%K nonn,easy,nice
%O 0,2
%A Bruno Petazzoni (Bruno.Petazzoni(AT)ac-idf.jussieu.fr)