1,2

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: 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?

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 aaabbbbbbbbb

A094838 gives length of S. See A094824 for a related problem involving substrings.

Sequence in context: A072753 A009884 A032023 this_sequence A136427 A018114 A089484

Adjacent sequences: A094834 A094835 A094836 this_sequence A094838 A094839 A094840

nonn,nice,more,new

Russ Cox (rsc(AT)swtch.com), Jun 13 2004

An example line corrected by Hugo van der Sanden (hv(AT)crypt.org), Nov 26 2009