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 longest common subsequence S of X and Y, there may be several ways to delete entries from X and from Y to get S: let F(X,Y) be the total number of ways. Sequence gives max F(X,Y) over all choices for binary strings X and Y of length n.

It appears that using a larger alphabet than binary does not increase the answers: is this true?

A lower bound can be obtained as follows. For n>=4, let k=ceiling(n/4), let X=a^(n-k) b^k, Y=a^k b^(n-k), S=a^k b^k. There are binomial(n-k,k)^2 choices for S, so this (A171001) is a lower bound on a(n). A171002, A171006 and A171003 give successively more refined lower bounds. - John P. Linderman, Aug 31 2010

Assuming that all optimal pairs (A,B) are in fact of the form described above, it would appear that a better lower bound could be reached using k = round(n/(2+phi)). In the event that such k is closer to a half-integer, X=a^(n-floor(n/(2+phi))) b^floor(n/(2+phi)), Y=a^ceiling(n/(2+phi)) b^(n-ceiling(n/(2+phi))) tends to be stronger. - Charlie Neder, Sep 06 2018

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).