Choose $n$ objects with replacement from a bag with $n$ objects

What is the number of ways of choosing $n$ objects with replacement from a bag with $n$ objects (where order doesn't matter and each object is distinct)?

The answer is $\binom{2n-1}{n}$ but I don't see why (this is the number of ways to exhaustively enumerate every possible resample of a data set with $n$ observations http://en.wikipedia.org/wiki/Bootstrapping_%28statistics%29).

1 Answer

I think that stars and bars can be used here. For any pair of natural numbers $n$ and $k$, the number of distinct $k$-tuples of non-negative integers whose sum is $n$ is given by the binomial coefficient $${n+k-1\choose n}.$$ In this case, $k=n$ and we obtain the answer ${2n-1\choose n}$.

• Just to confirm that I understand: in the stars and bars argument we have $n$ objects (which in the above example are the $n$ chosen objects) and $n$ bins (which in the above example are the $n$ objects we're choosing from). Sorry for being a little slow here. Jun 3 '15 at 13:56
• @user103828 Yes, you're right. Each bin represents an object in the bag (these objects are distinguishable and we have $n$ of them) and we want to put $n$ balls into these bins (the balls are indistinguishable). For example, if we put $3$ balls into the first bin, it means that we take the first object from the bag $3$ times. So the number of ways we can distribute these $n$ balls into these $n$ bins is given by ${n+n-1\choose n}$. Jun 3 '15 at 14:02