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