Problem 7.26 Medium Free

Every Value but One Chosen

Seven people each independently and uniformly pick a number from {1,2,…,7}\{1,2,\dots,7\}. Given that nobody picks the number 77, find the probability that 77 is the only number nobody picks (so every number in {1,…,6}\{1,\dots,6\} 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 77 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 77, the seven choices are i.i.d. Unif{1,…,6}\mathrm{Unif}\{1,\dots,6\}. To see this, note that the conditioning event has probability (6/7)7(6/7)^7. Each individual assignment avoiding 77 has probability 7−77^{-7}, so its conditional probability is 6−76^{-7}. Hence all 676^7 assignments into {1,…,6}\{1,\dots,6\} are equally likely.

We need the number of assignments that use every value in {1,…,6}\{1,\dots,6\}. 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 (72)=21\binom{7}{2}=21 ways;
  • choose their common value, in 66 ways;
  • assign the remaining 55 values bijectively to the remaining 55 people, in 5!5! ways.

Each surjection arises exactly once. So there are 21⋅6⋅5!=21⋅720=1512021\cdot 6\cdot 5! = 21\cdot 720 = 15120 of them. Therefore

P(every value in {1,…,6} is picked∣7 not picked)=1512067=15120279936=35648≈0.054.\mathbb{P}(\text{every value in }\{1,\dots,6\}\text{ is picked}\mid 7\text{ not picked}) =\frac{15120}{6^7}=\frac{15120}{279936}=\frac{35}{648}\approx 0.054.
35648\boxed{\dfrac{35}{648}}

Alternative. Inclusion–exclusion counts the surjections as ∑j=06(−1)j(6j)(6−j)7\sum_{j=0}^{6}(-1)^j\binom{6}{j}(6-j)^7. This also equals 1512015120.