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

%I #3 Dec 31 2023 10:28:09

%S 1,2,3,4,7,10,19,28

%N Maximal number of longest common subsequences between any two strings of length n (Version 2).

%C Same as A094858 (which has much more information about the problem), except that we now we allow an arbitrary alphabet.

%C For even n it seems that the maximum is attained for X = 123412341234..., Y = 432143214321..., giving values : (conjectured) maximum number of maximum-length-common-subsequences of 2 strings of length 2*n over an arbitrary (infinite) alphabet f(2*n) = 2,4,10,28,78,220,624,1780,5100,14668,.. Note that (3*f(2*n)-f(2*n+2))/2 gives 1,1,1,3,7,18,46,120,316,841,2257,6103,16611,45475,125139,.. which is A026107. Is there an explanation for this?

%Y Cf. A026107, A094858.

%K nonn,more,nice,hard

%O 1,2

%A Guenter Stertenbrink (Sterten(AT)aol.com), Jun 14 2004