3
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – chausies Mar 29 '19 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.