A094858 Maximal number of longest common subsequences between any two binary strings of length n (Version 2).

1, 2, 2, 4, 4, 6, 8, 11, 15, 20, 26, 36, 51

Offset

1,2

Comments

Definitions: S is a subsequence of X if S can be obtained by deleting some (not necessarily adjacent) entries of X.

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.

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.

For this version of the problem using a larger alphabet helps (cf. A094859, A094863).

For an alphabet of size m = 2, 3 or 4, the maximum appears to be attained for X=123..m123..m..., except for some small values of n. 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.

Hill-climbing gives the following lower bounds for the next few terms: 26,36,50,70,96,141,192.

Links

Table of n, a(n) for n=1..13.

Crossrefs

Cf. A094859-A094862, A094837, A094824, A094291.

Sequence in context: A293627 A264393 A362307 * A327851 A029940 A045674

Adjacent sequences: A094855 A094856 A094857 * A094859 A094860 A094861

Keyword

nonn,nice,more

Author

Guenter Stertenbrink (Sterten(AT)aol.com), Jun 14 2004

Status

approved