Number of terms in $(a_1+a_2+a_3+\cdots+a_k)^n$

Question

Number of terms in $(a_1+a_2+a_3+\cdots+a_k)^n$ is $${n+k-1 \choose k-1}$$ I know that this is stars and bars but How does this theorem applies here ? Thank you for answering.

Answer 1

Think about how to multiply out the terms. If $n=2$ (i.e., we're multiplying two groups of terms), $(a_1 + a_2 + \dots + a_k)(a_1 + a_2 + \dots + a_k) = a_1a_1 + a_1a_2 + \dots + a_1a_k + a_2a_1 + \dots + a_ka_k$. Each term come from picking one term from the first group, one from the second, and multiplying them together. If $n=3$, the terms look like $a_1a_1a_1$, $a_1a_1a_2$, etc..

In general, each term is generated by picking one term from each of the $n$ groups, so it looks like $a_1a_1a_2a_3a_3a_3a_5$ with $n$ terms total. Combining terms with the same base, this becomes$a_1^{i_1}a_2^{i_2}\cdots a_k^{i_k}$. Since each term $a_j$ is repeated $i_j$ times in the original format, and the original format had a total of $n$ terms, we have $i_1 + i_2 + \dots + i_k = n$. We have $n$ units to divide between the $k$ exponents. This should look more like classic stars and bars now: imagine we choose the $k$ exponents in the following manner. We have $n$ stars and $k-1$ bars to arrange in a line. After arranging them, we let $i_1$ be the number of stars before the first bar, $i_2$ be the number of stars between the first bar and the second bar, etc. The number of ways to arrange the stars and bars is exactly the same as the number of ways to choose the exponents.

Answer 2

We know that each term is in the form $$a_1^{i_1}a_2^{i_2}\cdots a_k^{i_k}$$ with $$i_1 + i_2 + \dots + i_k = n$$

thus the problem reduce to find the number of partition of n as sum of $k$ integers $\ge$ 1.

The trick to solve the problem is to consider $n+k-1$ boxes which you can fill with $k-1$ balls, with no more than one balls for each box, in this way the remaining empty boxes correspond to the partition thus we have

$${n+k-1 \choose k-1}$$