A094837 - OEIS

This site is supported by donations to The OEIS Foundation.

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 (list; graph; refs; listen; history; 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?` `Comment from John Linderman, Aug 31 2010: A lower bound can be obtained as follows. For n>=4, let k=ceil(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.`
	LINKS	`Russ Cox, C program for the longest common subsequence problem` `John 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 (rsc(AT)swtch.com), 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 Linderman for pointing out that there was a problem.` `a(13)-a(17) from John Linderman, Sep 01 2010, obtained by running Russ Cox's program.`

Content is available under The OEIS End-User License Agreement .

Last modified February 16 11:30 EST 2012. Contains 205907 sequences.