Better definition for A113166

[Creighton Dement]

Dear Seqfans, 

Among my submitted sequences, two favorites are A113166 and A113910. At
the time I submitted A113166, I found it hard to give a clear and
concise definition. 

Perhaps I've found a better formulation of A113166 (see below). 
However, I doubt the steps given allow one to compute the terms of this
sequence as efficiently as possible.  I would be very pleased if someone
could add comments or extend this sequence. 

Sincerely, 
Creighton 

Alternative definition of A113166: define a(1) = 0. To calculate a(n), 

1. Expand (A + B)^n into 2^n words of length n consisting of letters A
and B (i.e., use of the distributive and associative laws of
multiplication but assume A and B do not commute). 

2. To each of the 2^n words, associate a free binary necklace consisting
of n "black and white pearls". Figuratively, all 2^n necklaces can be
placed inside a  treasure chest.

3. Remove all n-pearled necklaces which are found to have (at least) two
adjacent white pearls from the chest. 

4. If two necklaces are found to be equivalent, remove one of them from
the chest. Continue until no two equivilant necklaces can be found in
the chest. 

5. Counting the total number of white pearls left in the chest returns
a(n). 


Ex. a(2)

Step 1. (A + B)^2 = AA + AB + BA + BB

Step 2. Chest = {AA, AB, BA, BB}

Step 3. Chest = {AB, BA, BB}

Step 4. Chest = {BA, BB}

Step 5. a(2) = 1


Ex. a(3)

Step 1. (A + B)^3 = (AAA + ABA + BAA + BBA) + (AAB + ABB + BAB + BBB) 

Step 2. Chest = {AAA, ABA, BAA, BBA, AAB, ABB, BAB, BBB}

Step 3. Chest = {BBA, ABB, BAB, BBB}

Step 4. Chest = {BBA, BBB}

Step 5. a(3) = 1


To see how the above relates to Lucas / Pell numbers, observe the
following: 

Set A equal to the 4X4 matrix
[[0.,-1.,1.,-1.],[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]] and  
B = [[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.],[-1.,1.,0.,-1.]]. Then
trace((A+B)^n) leads to the n-th Lucas number.

On the other hand, if A =
[[0.,-2.,1.,-1.],[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.]] and B =
[[0.,0.,0.,0.],[0.,0.,0.,0.],[0.,0.,0.,0.],[-1.,1.,0.,-2.]], then
trace((A+B)^n) leads to the n-th term of Numerators of continued
fraction convergents to sqrt(2), A001333 (where "leads to" is written to
avoid referring to the sign / common multiple of the sequences). 

What do A and B defined as matrices have to do with the A and B from
above? Observe that A^2 = 0 in both cases and to each of the 5 steps, we
can find an "equivalent step" involving matrices: 
 
Steps 1: same as above. 

Step 2: Using trace(X + Y) = trace(X) + trace(Y) for square matrices,
partition trace((A+B)^n) into the sum of 2^n terms.  

Step 3. Using the property that A^2 = 0, remove any terms of the form
trace(X) where X is the zero-matrix.  

Step 4. Using the property trace(XY) = trace(YX) for square matrices X
and Y, if two matrices from the chest can be shown to have the same
trace (without explicitely substituting values), remove one of the terms
from the sum.

Step 5. Count the number of A's.  


Note that a(1) = 0 was defined as such because trace(A+B) =  trace(A) +
trace(B) = trace(B) and the total number of A's in trace(B) is 0.