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

[Paul Barry]

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

Very nice result.
Note that the first sequences are related to the sequences Sum_{k=0..n}
binomial( mn-(m-1)k-1, k) which 
give the row sums of the Riordan arrays (1,1/(1-x)^m) with g.f.s 
(1-x)^m/((1-x)^m-x). They provide 
bi/tri/quadri- etc sections of the sequences 1/(1-x-x^m). The first few
are 

1  1   1   1   1     1     1       1       1       1         1  
1  1   2   4   8    16    32      64      128     256       512 
1  1   3   8  21    55    144     377     987    2584      6765  
1  1   4  13  41    129   406    1278    4023    12664     39865 
1  1   5  19  69    250   907    3292    11949   43371    157422 
1  1   6  26  106   431  1757    7168    29244  119305    486716 
1  1   7  34  153   686  3088    13917   62721  282646    1273690 
1  1   8  43  211  1030  5055    24851  122166  600470    2951330 
1  1   9  53  281  1479  7837    41623  221049  1173662   6231255 
1  1  10  64  364  2050  11638   66268  377308  2147563  12222605 
1  1  11  76  461  2761  16688  101245  614207  3724489  22582581 

Paul (Barry).