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 (2n−1n) 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).
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}.
No comments:
Post a Comment