How many different terms are there in the expansion of $(x_1 + x_2 + \cdots + x_m)^n$ after all terms with identical sets of exponents are added?

Question

I just can't understand how to go about it!

Answer 1

As user545963 has commented, each pattern involves $m$ non-negative integer exponents adding up to $n$. The number of compositions of this form can be found with stars and bars $(n$ stars and $m-1$ bars separating them into $m$ values$)$ so $${n+m-1 \choose n} \text{ possible patterns of the exponents}$$

You can also express the coefficient of each $x_1^{d_1}x_2^{d_2}\cdots x_m^{d_m}$ pattern: it is $\dfrac{n!}{d_1!\,d_2!\,\cdots d_m!}$ and if you add these all up you get the unsurprising answer of $m^n$