|
| |
|
|
A098964
|
|
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.
|
|
0
|
| |
|
|
|
OFFSET
|
0,1
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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;
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Simon Nickerson (simonn(AT)maths.bham.ac.uk), Oct 22 2004
|
|
|
STATUS
|
approved
|
| |
|
|
