Saturday 14 May 2016

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


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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...