This site is supported by donations to The OEIS Foundation. Hints (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)
 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 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 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

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.

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