cp's OEIS Frontend

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).

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