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

%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