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

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

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
1, 4, 19, 94, 481, 2524, 13483, 72958, 398593, 2193844, 12146179, 67570078, 377393953, 2114900428, 11885772379, 66963572734, 378082854913, 2138752086628, 12118975586803, 68774144872414, 390815720696161, 2223564321341884 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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

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

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

PROG

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

CROSSREFS

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

Sequence in context: A005978 A083065 A137636 * A020060 A122394 A047781

Adjacent sequences:  A027615 A027616 A027617 * A027619 A027620 A027621

KEYWORD

nonn,easy,nice

AUTHOR

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

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 31 00:00 EDT 2014. Contains 248844 sequences.