|
EXAMPLE
|
Form a tree with the empty word 0 as the root. Each node has potentially 4 children, corresponding to premultiplication by x or y and postmultiplication by x and y.
Layers 0 through 3 of the tree are as follows (the edges, which just join one layer to the next, have been omitted):
.............0.................
.......x...........y...........
..xx.....xy.....yx....yy.......
xxx xxy xyx yxx xyy yxy yyx yyy
a(n) is the minimal number of edges in a subtree that includes the root and all 2^n nodes at level n.
a(3)=11 because each of xxx,xxy,xyx,xyy,yxx,yxy,yyx,yyy can be obtained in one step from xx,xy,yy; that is, we don't need yx. The corresponding subtree has 2 + 3 + 8 = 13 edges.
a(4) = 27 because one computes successively: 0, x,y, xx,xy,yy, xxx,xyx,xxy,yxy,yyx,yyy, and then all 16 words of length 4.
|
