a(n)=Number of Unique Matrix Products in (A+B+C)^n When [A,B]=0

[Christian G.Bower]

If I have disjoint sets I and J of letters such that the g.f. of the
number of unique products are A(x) and B(x), then if I create set
K = I u J such that each member of I commutes with each member of J, then
C(x) the g.f. for products in K = A(x)*B(x).

If each member of I commutes with none of the members of J then:
C(x) = A(x)*B(x)/(A(x)+B(x)-A(x)*B(x))

since the examples given so far involve transitivity of the commuters
(i.e. [a,b] and [b,c] implies [a,c]) this formula is enough if you
start with the formula 1/(1-x) for one letter.  Of course not all cases
follow that such as for 3 letters with [a,b] and [b,c].  However this
one satisfies transitivity of noncommuters (we have {a,c} non commuting,
but each commuting with b), giving 1/((1-x)*(1-2*x)) which is just
2^(n+1)-1.

Of course we can create examples where neither transitive rule is
followed: 4 letters with [a,b], [b,c], [c,d].  Counting by hand suggests
the answer of A003462(n+1) = (3^(n+1)-1)/2 or the partial sums of 3^n.
This is the same answer for [a,b],[a,c],[a,d] i.e. a commutes with
everyone.  This suggests I look at the commute pairs.

Some more experimentation suggests the formula

1/(1-a1*x+a2*x^2-a3*x^3+...) where
a1 is number of letters
a2 is number of commuting pairs
a3 is number of commuting triples
...

but I'm still some distance from proving that.

(I wouldn't be surprised if it's a well known combinatorial result.)

Christian