login
Sum over all 2^(2n) pairs (u,v) of binary sequences of length n of length of maximal common subsequence between them.
2

%I #52 May 10 2022 11:13:08

%S 0,2,18,116,646,3324,16302,77356,358424,1630988,7317424,32458400,

%T 142638568,621948448,2693978986,11602817444,49726594628,212195409348,

%U 902038055526,3821542566420,16141064174876,67988725603820,285670814425030,1197613640781032,5010423893820844

%N Sum over all 2^(2n) pairs (u,v) of binary sequences of length n of length of maximal common subsequence between them.

%C 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].

%H Yi Yang, <a href="/A027433/b027433.txt">Table of n, a(n) for n = 0..28</a>

%H Vacláv Chvátal and David Sankoff, <a href="http://www.jstor.org/stable/3212444">Longest Common Subsequences of Two Random Sequences</a>, Journal of Applied Probability, Vol. 12, No. 2 (Jun., 1975), pp. 306-315, DOI: 10.2307/3212444.

%H V. Dancik and M. Paterson, <a href="http://dx.doi.org/10.1007/3-540-57785-8_180">Upper bounds for the expected length of a longest common subsequence of two binary sequences</a>, 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.

%H J. D. Dixon, <a href="https://arxiv.org/abs/1307.2796">Longest common subsequences in binary sequences</a>, arXiv preprint arXiv:1307.2796 [math.GR], 2013.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Chvátal-Sankoff_constants">Chvátal-Sankoff constants</a>

%F a(n) ~ gamma_2*n*4^n, where gamma_2 is the Chvátal-Sankoff constant.

%t a[0] = 0;

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

%t Table[a[n], {n, 0, 10}] (* _Vladimir Reshetnikov_, May 12 2016 *)

%K nonn,hard

%O 0,2

%A _Paul Zimmermann_

%E More terms from _Alexander D. Healy_, Dec 17 2002

%E a(19)-a(24) from _Yi Yang_, Nov 04 2013

%E a(25)-a(28) from _Yi Yang_, May 10 2022