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 (2n1n) 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}...