|
Search: id:A027618
|
|
|
| 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). |
|
+0
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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
REFERENCES
|
Found by 7 students: Dufour, Hermon, Lesueur, Moynot, Schabanel, Sers and Wolf.
|
|
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-6x+x^2)-1/(1-x)]/2.
|
|
CROSSREFS
|
Delannoy numbers A008288, A001850 are given by c'(i, j)=(3c(i, j)-1)/2.
Sequence in context: A005978 A083065 A137636 this_sequence A020060 A122394 A047781
Adjacent sequences: A027615 A027616 A027617 this_sequence A027619 A027620 A027621
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Bruno.Petazzoni(AT)ac-idf.jussieu.fr (Bruno Petazzoni)
|
|
|
Search completed in 0.002 seconds
|
