Every Value but One Chosen
Seven people each independently and uniformly pick a number from . Given that nobody picks the number , find the probability that is the only number nobody picks (so every number in is picked by at least one person).
Work it out, then compare with the answer.
SolutionShow the worked solution
Key idea. Conditioning on nobody picking leaves each person’s choice uniform on the other six values. We then count the maps from seven people onto all six values.
Given that nobody picks , the seven choices are i.i.d. . To see this, note that the conditioning event has probability . Each individual assignment avoiding has probability , so its conditional probability is . Hence all assignments into are equally likely.
We need the number of assignments that use every value in . Seven people cover six values, so exactly one value is picked by two people and each other value by exactly one. To build such an assignment:
- choose the pair of people who share a value, in ways;
- choose their common value, in ways;
- assign the remaining values bijectively to the remaining people, in ways.
Each surjection arises exactly once. So there are of them. Therefore
Alternative. Inclusion–exclusion counts the surjections as . This also equals .