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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027433 Sum over all 2^(2n) pairs (u,v) of binary sequences of length n of length of maximal common subsequence between them. 1
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

Table of n, a(n) for n=0..24.

Vacláv Chvátal and David Sankoff, Longest Common Subsequences of Two Random Sequences, Journal of Applied Probability, Vol. 12, No. 2 (Jun., 1975), pp. 306-315, DOI: 10.2307/3212444.

V. Dancik and M. Paterson, Upper bounds for the expected length of a longest common subsequence of two binary sequences, in STACS 94, Proceedings of the Eleventh Annual Symposium on Theoretical Aspects of Computer Science held in Caen, Feb 24 1994. Edited by P. Enjalbert, E. W. Mayr and K. W. Wagner. Lecture Notes in Computer Science, 775. Springer-Verlag, 1994, pp. 669-678.

J. D. Dixon, Longest common subsequences in binary sequences, arXiv preprint arXiv:1307.2796 [math.GR], 2013.

Wikipedia, Chvátal-Sankoff constants

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]];

Table[a[n], {n, 0, 10}] (* Vladimir Reshetnikov, May 12 2016 *)

CROSSREFS

Sequence in context: A038721 A064837 A224902 * A153338 A007798 A058052

Adjacent sequences:  A027430 A027431 A027432 * A027434 A027435 A027436

KEYWORD

nonn,hard

AUTHOR

Paul Zimmermann

EXTENSIONS

More terms from Alex Healy, Dec 17 2002

a(19)-a(24) from Yi Yang, Nov 04 2013

STATUS

approved

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 March 26 18:36 EDT 2019. Contains 321511 sequences. (Running on oeis4.)