Sum of products of numbers with specific sum I came across a problem recently which involved finding
$$\sum_{a_1+a_2+...+a_m=n}a_1a_2a_3...a_m$$
given $n$ and $m$ where all $a_i$ are positive integers.  While I was able to try different values and find the answer to be
${n+m-1}\choose{n-m}$, I don't understand why this answer is correct.  How would one go about solving this equation without just plugging in values and guessing?
 A: The combinatorial solution is that $$\sum_{a_1+a_2+...+a_m=n}a_1a_2a_3...a_m$$ counts the number of ways to first split $n$ identical objects into $m$ parts of positive size, and then mark one object in each part. (If the parts have size $a_1, a_2, \dots, a_m$, then there are exactly $a_1 a_2 \dotsb a_m$ ways to pick the objects to mark.)
We can also count this by using a stars-and-bars approach (Wikipedia link). We can split up $n$ objects into $m$ parts by inserting $m-1$ dividers between them; then we can replace $m$ of the objects, one in each part, by a marked object. Something like this:
$${\star} {\bigstar} {\star} \mid {\star} {\star} {\star} {\bigstar} \mid {\star} {\bigstar} \mid {\bigstar}{\star}{\star}{\star}{\star}$$
We know that the marked objects ($\bigstar$) and the dividers ($\mid$) alternate, so we can get any such representation in a unique way by picking which $2m-1$ of the $n+m-1$ total symbols will be either $\bigstar$ or $\mid$. There are $$\binom{n+m-1}{2m-1} = \binom{n+m-1}{(n+m-1)-(2m-1)} = \binom{n+m-1}{n-m}$$ ways to do this.
A: This is a great place for generating functions. Note that
$$
\sum_{a_1+\cdots+a_m=n}a_1\cdots a_m=[x^n]\left(\sum_{a_1=0}^{\infty}a_1x^{a_1}\right)\cdots\left(\sum_{a_m=0}^{\infty}a_mx^{a_m}\right)=[x^n]\left(\sum_{a=0}^{\infty}ax^a\right)^m,
$$
where $[x^n]$ indicates "the coefficient by $x^n$ in...".
Now, we can write
$$
\sum_{a=0}^{\infty}ax^a=x\sum_{a=1}^{\infty}ax^{a-1}=x\frac{d}{dx}\left[\sum_{a=0}^{\infty}x^a\right]=x\frac{d}{dx}\left[\frac{1}{1-x}\right]=\frac{x}{(1-x)^2},
$$
so that
$$
\sum_{a_1+\cdots+a_m=n}a_1\cdots a_m=[x^n]\frac{x^m}{(1-x)^{2m}}=[x^{n-m}]\frac{1}{(1-x)^{2m}}.
$$
But, this last can be rewritten as $(1-x)^{-2m}$, so that by the binomial theorem we have
$$
(1-x)^{-2m}=\sum_{k=0}^{\infty}\binom{-2m}{k}(-x)^k,
$$
and therefore
$$
\sum_{a_1+\cdots+a_m=n}a_1\cdots a_m=\binom{-2m}{n-m}(-1)^{n-m}.
$$
Now, by definition,
$$
\begin{align*}
\binom{-2m}{n-m}&=\frac{(-2m)(-2m-1)\cdots(-2m-(n-m-1))}{(n-m)!}\\
&=(-1)^{n-m}\frac{(2m)(2m+1)\cdots(m+n-1)}{(n-m)!}\\
&=(-1)^{n-m}\binom{m+n-1}{n-m}.
\end{align*}
$$
Plugging that into the above yields
$$
\sum_{a_1+\cdots+a_m=n}a_1\cdots a_m=(-1)^{2(n-m)}\binom{m+n-1}{n-m}=\binom{m+n-1}{n-m},
$$
as expected.
