Combinatorics problem: coefficient of $x^k$ in $(x + x^2 + x^3 + ...)^n$ Define $f(n,k)$ with $k \geq n$ as the number of ways to colour $k$ identical objects with $n$ colours, such that every object has one colour and every colour is used at least once. 
I want to prove that $f(n,k)$ is the coefficient of $x^k$ in $(x + x^2 + x^3 + ...)^n$, I do not however, have any idea how to do this..
What I've done so far:
As another part of the exercise I've found that $f(n,k) = \binom{k - 1}{n - 1}$, but I don't see how that could help here. Any assistance would be much appreciated, thanks!
 A: The coefficient of $x^k$ in $(\sum_{j=1}^\infty x^j)^n$ can be found by considering how many ways you can get the term $x^k$ when you expand the product (since all the coefficients in the original summation polynomials are 1). If you consider this as a product of $n$ summation terms, the exponent of $x$ in the first summation term (call it $j_1$) and the exponent of $x$ in the second summation term (call it $j_2$) and so forth must all add up to $k$, i.e. $\sum_{i=1}^n j_i = k$. But since $x^1$ is the smallest power in each summation term, this is the same as choosing $n$ positive integers (where the ordering matters) that add up to be $k$. This is the bijection you need for your coloring problem: For each of the $n$ colors (where the colors are distinct so the ordering of colors matters) you choose a positive number of objects to color with that color, such that the total number of colored objects is $k$.
A: You can use your combinatorial combination coefficient formula ${k-1} \choose {n-1}$ you proved, in order to get the answer: It is the number of ways you can place $n-1$ identical sticks in between a sequence of $k$ stones such that sticks are placed in distinct positions so that the $k$ stones are split into $n$ groups of at least one stone each. In this bijection, the $m$th group from left-to-right corresponds to the $m$th color, and the number of stones in the $m$th group is the number of identical objects that are colored with color $m$. In order for this bijection to work with your coloring problem, you need that the ordering of the identical objects doesn't matter (which it seems like it doesn't since the objects are "identical").
A: The expansion you cite is easy:
\begin{align}
[z^k] (z + z^2 + \ldots)^n
  &= [z^{k - n}] \left( \sum_{r \ge 0} z^r \right)^n \\
  &= [z^{k - n}] (1 - z)^{-n} \\
  &= (-1)^{k - n} \binom{-n}{k - n} \\
  &= \binom{k - 1}{n - 1}
\end{align}
