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).


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}$.

  • $\begingroup$ 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. $\endgroup$
    – user103828
    Jun 3 '15 at 13:56
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – Cm7F7Bb
    Jun 3 '15 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.