number of longest common substrings problem

[N. J. A. Sloane]

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