login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 4

%I

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 02:33 EST 2019. Contains 320200 sequences. (Running on oeis4.)