Probability of picking all elements in a set I was studying the birthday paradox and got curious about a related, but slightly different problem. Lets say I have a set S, that has n unique elements. If I randomly pick k elements from the set (assuming equal probability of picking any element), the probability that I'll have picked all the elements in the set, when k=n is n!/n^n.
Now, what would be the value of k for probability of picking all elements in the set to be > 0.9 (or some constant). 
A simpler variation would be - how many times should I flip a coin to have a probability > 0.9 to have thrown heads and tails at least once.
 A: Your first question is about a famous problem called the 
Coupon Collector's Problem.
Look in the Wikipedia write-up, under tail estimates.  That will give you enough information to estimate, with reasonable accuracy, the $k$ that gives you a $90$ percent chance of having seen a complete collection of coupons.
A: The general probability of having picked all the elements after a sample size $k$ with replacement is 
$$\frac{S_2 (k,n) \; n!}{ n^k} $$
where $S_2 (k,n)$ is a Stirling number of the second kind. You want this to be more than 0.9.
For $n=2$, you have $S_2 (k,2) = 2^{k-1}-1$ for $k \gt 2$ so you want 
$$\frac{(2^{k-1}-1) \times 2}{ 2^k} \gt 0.9 $$ 
which is true when $2^{k-1} \gt 10$, so with integers you get $k \ge 5$.
A: Hint: If you throw a coin $k$ times and it's not true that both heads and tails have come up, what must your throws be?
If you're not sure, try some small value of $k$, say $k = 3$. List all possible throws, and cross out those that have both heads and tails. What remains?
