|
%I #37 Sep 22 2023 10:21:28
%S 1,2,4,10,24,46,100,225,525,1225,3136,7056,17640,44100,108900,261360,
%T 637065,1656369,4008004,10020010,25050025,64128064,155739584,
%U 393853824,1012766976
%N Maximal number of longest common subsequences between any two binary strings of length n (Version 1).
%C Definitions: S is a subsequence of X if S can be obtained by deleting some (not necessarily adjacent) entries of X.
%C 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.
%C 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.
%C It appears that using a larger alphabet than binary does not increase the answers: is this true?
%C 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
%C 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
%H Russ Cox, <a href="/A094837/a094837.txt">C program for the longest common subsequence problem</a>
%H John P. Linderman, <a href="/A094837/a094837pl.txt">Perl script for a lower bound</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence">Longest Common Subsequence Problem</a> [from _N. J. A. Sloane_, Aug 31 2010]
%e Example illustrating a(4) = 10:
%e abba baab S
%e ------------
%e a..a .aa. aa
%e ab.. .a.b ab
%e ab.. ..ab ab
%e a.b. .a.b ab
%e a.b. ..ab ab
%e .bb. b..b bb
%e .b.a ba.. ba
%e .b.a b.a. ba
%e ..ba ba.. ba
%e ..ba b.a. ba
%e Details for lengths 1 through 12 showing lexicographically earliest examples for X and Y:
%e len 1: 1 lcs of length 1 for a a
%e len 2: 2 lcs of length 1 for aa ab
%e len 3: 4 lcs of length 2 for aab abb
%e len 4: 10 lcs of length 2 for abba baab
%e len 5: 24 lcs of length 2 for abbba baaab
%e len 6: 46 lcs of length 3 for aabbba abaaab
%e len 7: 100 lcs of length 4 for aaaaabb aabbbbb
%e len 8: 225 lcs of length 4 for aaaaaabb aabbbbbb
%e len 9: 525 lcs of length 5 for aaaaaaabb aaabbbbbb
%e len 10: 1225 lcs of length 6 for aaaaaaabbb aaabbbbbbb
%e len 11: 3136 lcs of length 6 for aaaaaaaabbb aaabbbbbbbb
%e len 12: 7056 lcs of length 7 for aaaaaaaaabbb aaaabbbbbbbb
%e len 13: 17640 lcs of length 7 for aaaaaaaaaabbb aaaabbbbbbbbb
%e len 14: 44100 lcs of length 8 for aaaaaaaaaabbbb aaaabbbbbbbbbb
%e len 15: 108900 lcs of length 8 for aaaaaaaaaaabbbb aaaabbbbbbbbbbb
%e len 16: 261360 lcs of length 9 for aaaaaaaaaaaabbbb aaaaabbbbbbbbbbb
%e len 17: 637065 lcs of length 9 for aaaaaaaaaaaaabbbb aaaaabbbbbbbbbbbb
%Y A094838 gives one choice for the length of S (in general the length is not unique). See A094824 for a related problem involving substrings.
%Y Cf. A171001-A171003 for lower bounds.
%K nonn,nice,more
%O 1,2
%A _Russ Cox_, Jun 13 2004
%E 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.
%E a(13)-a(17) from _John P. Linderman_, Sep 01 2010, obtained by running _Russ Cox_'s program.
%E a(18)-a(25) from _Akshay Bansal_, Jul 08 2017
| 