cp's OEIS Frontend

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.

This is the number of longest common subsequences between two binary strings of the form 00...011...1.

This is a lower bound for A094837, equivalent to choosing first string (x "a"s followed by (n-x) "b"s) and second string (y "a"s followed by (n-y) "b"s).