Mallows's sequences, was: Addition chains

[N. J. A. Sloane]

Colin Mallows recently asked for more terms of this
sequence, but I didn't see any followups, so I'll restate his
question.

Given x and y, we want to form all the words of
length n, and we pay $1 every time we multiply 2 words.
What is the minimal total cost needed?

Examples: a(1) = 0, no multiplications are needed.
a(2) = 4, since we have to do 4 multiplications
to get xx xy yx and yy

a(3) = 11, because each of xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy
can be obtained in one step from xx,xy,yy,
and it takes three multiplications to produce xx, xy, yy.

Here is the current entry:

%I A075099
%S A075099 0,4,11,20,42,75
%N A075099 Minimal total number of multiplications needed to generate all words of length n in the free monoid on two generators.
%C A075099 I believe a(2n) = a(n) + 2^(2n). I guess a(7) = 156.
%e A075099 a(3)=11 because each of xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy can be obtained in one step from xx,xy,yy, and it takes three multiplications to produce xx, xy, yy.
%Y A075099 Cf. A075100, A124677.
%K A075099 hard,more,nonn
%O A075099 1,2
%A A075099 Colin Mallows (colinm(AT)research.avayalabs.com), Aug 31 2002

Note that for large n you can save money by multipying subwords
in nontrivial ways. (Like addition chains.)

If you can only progress by multiplying by singletons each time,
you get my simple-minded version, A124677

Colin has a related sequence, A075100, whose definition
is not clear to me.

All three sequences need extending.

Neil