Hugo asks:
Here you introduce the word "different" for the first time. Are two substrings "different" if the substrings themselves differ, or is it sufficient for the letters of the substring to be drawn from different positions in X or Y? Ie given: X = "aabaa", Y = "aaabb" are there 1 or 4 occurrences of the LCS "aaa"?
Me: The latter, I think, since the goal of the question is to determine how rapidly these numbers can grow. So in your example, the LCS has length 3, and there seem to be 10 ways to get 3: X = aabaa Y = aaabb --------------------- aab.. aa.b. aab.. aa..b aab.. a.ab. aab.. a.a.b aab.. .aab. aab.. .aa.b aa.a. aaa.. aa..a aaa.. a..aa aaa.. .a.aa aaa.. so a(5) >= 10. NJAS