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

[Max]

Max wrote:

> Suppose that you have m variables A1,...,Am that pairwise commute and 
> variable B no commuting with the others.
> Then general term in the expansion (A1+...+Am+B)^n has the form
> A1^x01*...*Am^x0m * B * A1^x11*...*Am^x1m * B * ... * B * A1^xk1*...*Am^xkm
> where k is the number of B's, and xij are nonnegative integers such that
> x01 + ... + x0m + x11 + ... + x1m + ... + xk1 + ... + xkm = n-k.
> 
> Therefore, the number of distinct terms is
> Sum_{k=0..n} binomial( n+(m-1)k+m-1, mk+m-1 )

It easy to generalize this to the case with t non-commuting variables (i.e., instead of B we have B1,...,Bt).
The number of distinct terms in the expansion of (A1+...+Am+B1+...+Bt)^n is

Sum_{k=0..n} binomial( n+(m-1)k+m-1, mk+m-1 ) * t^k

Max