A098964 - OEIS

%I #2 Sep 29 2006 03:00:00

%S 2,6,18,62,266,1494,10862

%N Number of elements in the free semigroup on 2 generators x, y which can be constructed from x and y using at most n multiplications.

%e a(2)=18 because we can construct the following 18 elements using at most 2 multiplications: x, y (0 multiplications), xy, yx, x^2, y^2 (1 multiplication), xyx, yx^2, x^3, y^2x, xy^2, yxy, x^2y, y^3, (xy)^2, (yx)^2, x^4, y^4 (2 multiplications). Note that despite being a word of length 4, (xy)^2 can be produced in just two multiplications; first calculate z=xy then calculate z^2.

%o (GAP) # Calculate the list [ a(1) ... a(n) ] semigroupcount := function(n) local G, x, y, f, ans; G := FreeSemigroup("x", "y"); x := G.1; y := G.2; ans := List([1..n+1], x->[]); f := function(wds) local i, j, l, w, newwds; l := Length(wds); if l > 2 then AddSet(ans[l-1], wds[l]); fi; if l < n + 2 then for i in [1..l] do for j in [1..l] do w := wds[i] * wds[j]; if not w in wds then newwds := Concatenation(wds, [w]); f(newwds); fi; od; od; fi; end; f([x, y]); return List(ans, x->Size(x) + 2); end;

%K nonn

%O 0,1

%A Simon Nickerson (simonn(AT)maths.bham.ac.uk), Oct 22 2004