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

1, 2, 4, 10, 24, 46, 100, 225, 525, 1225, 3136, 7056, 17640, 44100, 108900, 261360, 637065, 1656369, 4008004, 10020010, 25050025, 64128064, 155739584, 393853824, 1012766976

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

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

Russ Cox, C program for the longest common subsequence problem

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

A094838 gives one choice for the length of S (in general the length is not unique). See A094824 for a related problem involving substrings.

Cf. A171001-A171003 for lower bounds.

Sequence in context: A072753 A009884 A032023 * A136427 A350881 A018114

Adjacent sequences: A094834 A094835 A094836 * A094838 A094839 A094840

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