Everyone knows the number of ways you can choose k items out of n without replacement is _nC_k = n!/k!(n-k)!. Often forgotten is that the number of ways to choose k items from n with replacement is _n+k-1C_k. I think this is because a) it doesn’t come up as much, and b) there’s a clear intuitition behind the first formula but not so the second. So, why is the value _n+k-1C_k? Proving it with induction is a simple matter, but doesn’t shed much light.

Let’s look at it differently… We can number our items 1, 2, …, n and order the k chosen items accordingly, making a non-decreasing sequence. So the problem becomes counting the non-decreasing sequences a₁ ≤ a₂ ≤ … ≤ a_k. Turn each sequence into a bar graph, so that for n=7, k=4 the sequence [3,5,5,6] becomes

We can make the graph into a path from (0,1) to (k,n)

This path has n-1+k steps, n-1 vertical and k horizontal. Choosing one such path is choosing the k horizontal steps from the n+k-1 total, hence _n+k-1C_k.

Another way to think about it is to consider the items chosen to be bins to fill with balls: Choosing at item becomes putting a ball in the bin, and the number of balls in a bin represents how many times that item was chosen. So the problem becomes count the number of ways you can put k identical balls in n bins. Start with bin 1. At each step you can put a ball into the current bin, or move to the next bin. You’ll place balls in k of the steps, and move bins in n-1 of them, so it’s a matter of choosing the k steps out of the k+n-1 total in which to place balls.