### Combinatorics: Counting with replacement

Everyone knows the number of ways you can choose *k* items out of *n* without replacement is * _{n}*C

*=*

_{k}*n*!/

*k*!(

*n-k*)!. Often forgotten is that the number of ways to choose

*k*items from

*n*

**with**replacement is

_{n+k-1}C

_{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-1}C

_{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*_{1} ≤ *a*_{2} ≤ … ≤ *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-1}C_{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.