This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A094837 Maximal number of longest common subsequences between any two binary strings of length n (Version 1). 9
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 (list; graph; refs; listen; history; text; internal format)



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


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


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 A018114 A089484

Adjacent sequences:  A094834 A094835 A094836 * A094838 A094839 A094840




Russ Cox, Jun 13 2004


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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 11:09 EST 2019. Contains 329319 sequences. (Running on oeis4.)