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

[Max]

Paul D. Hanna wrote:

> I would like to take a wild guess at the formula for this case:
>  
> (A4) "a(n) = number of unique matrix products in (A+B+C+D+E)^n 
> where A,B,C, and D all commute with each other, but not with E."
>  
> FORMULA (predicted from trend):
> a(n) = Sum_{i=0..n} Sum_{j=0..n} Sum_{k=0..n} Sum_{m=0..n}
>           C(n-j-k-m,i)*C(n-i-k-m,j)*C(n-i-j-m,k)*C(n-i-j-k,m)
> which would begin:
>    1,5,19,69,250,907,3292,11949,43371,157422,571388,...
> which is OEIS: A055991  (a(n) is its own 4th difference).  
>  
> Would someone like to enumerate (A4) to see if it matches the formula?

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 )

Max