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$?
 A: 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$.
