|
|
A027433
|
|
Sum over all 2^(2n) pairs (u,v) of binary sequences of length n of length of maximal common subsequence between them.
|
|
2
|
|
|
0, 2, 18, 116, 646, 3324, 16302, 77356, 358424, 1630988, 7317424, 32458400, 142638568, 621948448, 2693978986, 11602817444, 49726594628, 212195409348, 902038055526, 3821542566420, 16141064174876, 67988725603820, 285670814425030, 1197613640781032, 5010423893820844
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The proved bounds for gamma_2 (see asymptotic formula below) are 0.788071 <= gamma_2 <= 0.82628, and conjectured value is around 0.811 [see Dixon].
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ gamma_2*n*4^n, where gamma_2 is the Chvátal-Sankoff constant.
|
|
MATHEMATICA
|
a[0] = 0;
a[n_] := a[n] = With[{s = Partition[Tuples[{0, 1}, n], 2^(n-1)], f = Composition[Length, LongestCommonSequence]}, 2^n n + 4 Total[ReleaseHold[LowerTriangularize[Outer[Hold[f], s[[1]], s[[1]], 1], -1]], 2] + 2 Total[Outer[f, s[[1]], s[[2]], 1], 2]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(19)-a(24) from Yi Yang, Nov 04 2013
a(25)-a(28) from Yi Yang, May 10 2022
|
|
STATUS
|
approved
|
|
|
|