longest common subsequences problem

[magictour at free.fr]

 >%S A094858 1,2,2,4,4,6,8,11,15,20,26,36,51

I added 3 more terms

 >%N A094858 Maximal number of longest common subsequences between any
 >           two binary strings of length n (Version 2).
 >%C A094858 Definitions: S is a subsequence of X if S can be obtained
 >           by deleting some (not necessarily adjacent) entries of X.
 >%C A094858 S is a longest common subsequence of X and Y if S is a
 >           subsequence of X, S is a subsequence of Y, and for any T,
 >           if T is a subsequence of X and of Y, then |T| <= |S|.
 >           Let LCS(X,Y) = length of any longest common subsequence
 >           of X and Y.
 >%C A094858 For each common subsequence S of X and Y, there may be
 >           several ways to delete entries from X and from Y to get S,
 >           but in this version of the problem we do not take this
 >           into account (cf. A094837). Let F(X,Y) be the number of
 >           different choices for S, without regard to where it appears
 >           in X and Y. Sequence gives max F(X,Y) over all choices for
 >           binary strings X and Y of length n.
 >%C A094858 For this version of the problem using a larger alphabet
 >           helps (cf. A094859, A094863).
 >%C A094858 For an alphabet of size m, the maximum appears to be attained
 >           for X=123..m123..m..., except for some small values of n.

probably only true for m=2,3,4.
For m>4 it seems that only 4 letters should be chosen in X,Y
to get the maximum, while the other letters are ignored.



 >%S A094863 1,2,3,4,7,10,19,28

I added 2 more terms

 >%N A094863 Maximal number of longest common subsequences between any
 >           two strings of length n (Version 2).
 >%C A094863 Same as A094858 (which has much more information about
 >           the problem), except that now we allow an arbitrary alphabet.


for even n it seems that the maximum is attained for 
X = 123412341234...
Y = 432143214321...
giving values : 
(conjectured) maximum number of maximum-length-common-subsequences
of 2 strings of length 2*n over an arbitrary (infinite) alphabet
f(2*n) = 2,4,10,28,78,220,624,1780,5100,14668,..

now, (3*f(2*n)-f(2*n+2))/2 gives :
1,1,1,3,7,18,46,120,316,841,2257,6103,16611,45475,125139,..
which is A026107 (see below)

does anyone see the connection between Motzkin paths and
longest common subsequences ???


Guenter Stertenbrink, sterten at aol.com



--------------------------------

Sequence:  1,3,7,18,46,120,316,841,2257,6103,16611,45475,125139,345957,
           960417,2676291,7483299,20989833,59042805,166520124,
           470781528,1333970190,3787707322,10775741271,30711538351,
           87677551081,250704001213,717923179762
Name:      Number of (s(0), s(1), ..., s(n)) such that every s(i) is a 
nonnegative
              integer, s(0) = 0, s(1) = 1 = s(n), |s(i) - s(i-1)| <= 1 for i >= 
2.
              Also a(n) = T(n,n-1), where T is array in A026105, and U(n,n+1), 
where U
              is array in A026120.
Comments:  Also number of (s(0),s(1),...,s(n)) such that every s(i) is a
              nonnegative integer, s(0) = 1, s(n) = 0, |s(1) - s(0)| = 1, |s
(i) - s(i-1)|
              <= 1 for i >= 2.
           Number of Motzkin paths of length n+1 that start with a (1,1) step 
and end
              with a (1,-1) step. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
Jul
              11 2001
           The sequence 1,1,3,7,18.... has a(n)=sum{k=0..n,
              C(n,2k)*A000108(k+1) }. - Paul Barry (pbarry(AT)wit.ie), Jul 18 
2003
Formula:   a(n)=A001006(n+1)-2A001006(n)+A001006(n-1); g.f.:
              [(1-z)^2*M-1+z-z^2]/z, where M is the generating function of the
              Motzkin sequence A001006 (M = 1 + zM + z^2M^2).
See also:  Cf. A001006.
           Adjacent sequences: A026104 A026105 A026106 this_sequence A026108