# Probability of choosing all the numbers in a set

Suppose you have $m=5$ people and $n=4$ numbers. Each person chooses, independently and at random, one of these numbers.

What's the probability that all the numbers will be chosen?

I've been able to experimentally find a result, which is ~0.234146. I've also been able to enumerate the favorable outcomes and the possible outcomes, which gives me a probability of:

$P(\text{all numbers are chosen}) = \dfrac{240}{1024} = 0.234375$

which conforms to the experimental result.

What I'm not able to do is to get a combinatorial meaning for this number, even in the form of a general formula with parameters $m$ and $n$.

My (wrong) reasoning:

• Notice that, for all the numbers to be chosen, one of them must be chosen twice.
• Suppose that the duplicate number is chosen by person 1, then the other 4 people have $4!$ ways to choose the 4 numbers.
• Repeat the reasoning in case the duplicate number is chosen by person 2, 3, 4 or 5.
• Get a result of $\dfrac{n! \cdot m}{n^m} = \dfrac{4! \cdot 5}{4^5} = \dfrac{120}{1024}$, which is wrong.

So, where's the flaw in my reasoning, and how do you obtain the result in terms of $m$ and $n$?

Let $$g(m,n)$$ count the number of choices in which all $$n$$ or fewer values appear. Because each of $$m$$ people have $$n$$ independent choices, there are $$n\times n\times \cdots \times n = n^m$$ total ways to do this. From these we must exclude the cases where $$n-1$$ or fewer values appear. That happens in $$n=\binom{n}{1}$$ ways. Those, in turn, must exclude the cases where $$n-2$$ or fewer values appear (those happen in $$\binom{n}{2}$$ possible ways), and so on, going all the way down to where everyone picks the same number (which can happn in $$\binom{n}{n-1}=n$$ distinct ways).

By the Principle of Inclusion-Exclusion, the number of choices in which all $$n$$ values appear is obtained by alternately including and excluding all these different possibilities, all the way down from $$n$$ distinct choices to $$1$$ distinct choice:

$$g(m,n) - \binom{n}{1}g(m,n-1) + \binom{n}{2}g(m,n-2) - \cdots = \sum_{i=0}^n(-1)^i \binom{n}{i}(n-i)^m.$$

Divide this by the total number of choices, $$g(m,n)$$, to obtain the probability.

For $$m=5$$ and $$n=4$$ this yields

$$4^5 - \binom{4}{1}3^5 + \binom{4}{2}2^5 - \binom{4}{3}1^5 =240,$$

which is to be divided by $$4^5=1024$$.

• To add to this: if $m$ is decently large (more than 15), then a good rule of thumb is that $\approx m (\ln (m) + 0.577)$ is the average number of people you'd need to touch everything in the set. Add a factor of 3 or 4 to that, and you'll touch everything in the set with decently high probability. See en.wikipedia.org/wiki/Coupon_collector%27s_problem for details – chausies Mar 29 '19 at 16:28