|
|
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
|
|
|
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.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Bruno Petazzoni (Bruno.Petazzoni(AT)ac-idf.jussieu.fr)
|
|
STATUS
|
approved
|
|
|
|