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 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
LINKS
John P. Linderman, Perl script for a lower bound
Wikipedia, Longest Common Subsequence Problem [from N. J. A. Sloane, Aug 31 2010]
EXAMPLE
Example illustrating a(4) = 10:
abba baab S
------------
a..a .aa. aa
ab.. .a.b ab
ab.. ..ab ab
a.b. .a.b ab
a.b. ..ab ab
.bb. b..b bb
.b.a ba.. ba
.b.a b.a. ba
..ba ba.. ba
..ba b.a. ba
Details for lengths 1 through 12 showing lexicographically earliest examples for X and Y:
len 1: 1 lcs of length 1 for a a
len 2: 2 lcs of length 1 for aa ab
len 3: 4 lcs of length 2 for aab abb
len 4: 10 lcs of length 2 for abba baab
len 5: 24 lcs of length 2 for abbba baaab
len 6: 46 lcs of length 3 for aabbba abaaab
len 7: 100 lcs of length 4 for aaaaabb aabbbbb
len 8: 225 lcs of length 4 for aaaaaabb aabbbbbb
len 9: 525 lcs of length 5 for aaaaaaabb aaabbbbbb
len 10: 1225 lcs of length 6 for aaaaaaabbb aaabbbbbbb
len 11: 3136 lcs of length 6 for aaaaaaaabbb aaabbbbbbbb
len 12: 7056 lcs of length 7 for aaaaaaaaabbb aaaabbbbbbbb
len 13: 17640 lcs of length 7 for aaaaaaaaaabbb aaaabbbbbbbbb
len 14: 44100 lcs of length 8 for aaaaaaaaaabbbb aaaabbbbbbbbbb
len 15: 108900 lcs of length 8 for aaaaaaaaaaabbbb aaaabbbbbbbbbbb
len 16: 261360 lcs of length 9 for aaaaaaaaaaaabbbb aaaaabbbbbbbbbbb
len 17: 637065 lcs of length 9 for aaaaaaaaaaaaabbbb aaaaabbbbbbbbbbbb
CROSSREFS
KEYWORD
nonn,nice,more
AUTHOR
Russ Cox, Jun 13 2004
EXTENSIONS
Aug 31 2010: Something had gone wrong with the examples. They have now been replaced by the examples originally submitted by Russ Cox. - N. J. A. Sloane. Thanks to John P. Linderman for pointing out that there was a problem.
a(13)-a(17) from John P. Linderman, Sep 01 2010, obtained by running Russ Cox's program.
a(18)-a(25) from Akshay Bansal, Jul 08 2017
STATUS
approved