Number of n-dimensional vectors I have a simple counting problem. Given the set of n-dimensional vectors over the natural numbers, how many vectors sum to exactly k? 
I've tried counting it in two different ways:


*

*I need to place k units into n bins. The first unit has n choices, the second - also n choices, etc, up to n^k options. I then divide by k! to account for the units being indistinguishable

*This is analogous to the problem of placing k items between n-1 fences. The answer to this would be (k+n-1) choose k. 
I'm not sure which one of those ideas is correct, and why. 
Any suggestions?
Thanks.
 A: Your counting problem is exactly the same as trying to find the number of natural number solutions to $x_1+...+x_n=k$ (I'm assuming $0$ is a natural number for our purposes.)
This is the same as, given $k$ items, the number of ways to separate them by placing $n-1$ fences in their midst.
Let i denote an item and | denote a fence.
Suppose for now $k=5$ and $n=3$.
ii|i|ii represents the solution $x_1=2, x_2=1,x_3=2$
i|iiii|| represents the solution $x_1=1,x_2=4,x_3=0$ 
As you can see, we have $k+(n-1)$ slots and we have to choose $k$ of them to be items. So there are $k+n-1 \choose k$ possibilties, so your idea #2 is correct.

Your idea #1 is incorrect, however, since ${k+n-1 \choose k} \neq \frac {n^k} {k!}$ when k=5 and n=3. In fact, in this case, $\frac {n^k} {k!}$ isn't even an integer!
A: Let $\vec{v}$ = <$x_1, x_2, ..., x_n$> be an $n$-dimensional vector whose entries sum to $k$. Then the number of such vectors corresponds to the number of solutions to $x_1 + x_2 + ... + x_n = k$. By the stars and bars method, the number of vectors is $\binom{k + n - 1}{k}$.
