A171002 -id:A171002 - cp's OEIS frontend

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

Russ Cox, Jun 13 2004

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

			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

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]

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.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A171001 Binomial(n-k,k)^2 where k = ceiling(n/4).

Views

Author

Keywords

Crossrefs

A171006 Binomial(n-k-1,k) * binomial(n-k,k+1) where k = ceiling(n/4).

Views

Author

Keywords

Crossrefs