Distinct Outcomes in Dice Rolls
A fair six-sided die is rolled six times. What is the probability of getting exactly four distinct numbers among the six outcomes?
Hints
- Think of this as a two-stage counting problem: first choose which faces appear, then count how to distribute the rolls among them.
- The number of ways to distribute $n$ objects into $k$ non-empty groups is counted by inclusion-exclusion: $\sum_{j=0}^{k}(-1)^j \binom{k}{j}(k-j)^n$.
- Choose 4 of the 6 faces ($\binom{6}{4} = 15$), then count surjections from 6 rolls onto those 4 faces. The total sample space is $6^6$.
Worked Solution
How to Think About It: Six rolls, six faces -- if you got all distinct values that would be $6!/6^6$, a birthday-problem style calculation. But we want exactly four distinct values, meaning two of the six faces never show up, and the four that do show up must cover all six rolls. The trick is counting how many ways to distribute six rolls across exactly four values so that every value appears at least once. This is a classic surjection (onto function) count, and the standard tool is inclusion-exclusion or Stirling numbers of the second kind.
Quick Estimate: There are $\binom{6}{4} = 15$ ways to choose which four faces appear. For each choice, we need to distribute 6 rolls onto 4 bins with no bin empty. The total unrestricted ways to fill 4 bins with 6 balls is $4^6 = 4096$. By inclusion-exclusion, subtract the arrangements that miss at least one bin. Roughly, $4^6 - \binom{4}{1}3^6 + \binom{4}{2}2^6 - \binom{4}{3}1^6 = 4096 - 2916 + 384 - 4 = 1560$. So the favorable count is $15 \times 1560 = 23{,}400$ out of $6^6 = 46{,}656$. That gives $23400/46656 \approx 0.5015$. So roughly a coin flip -- makes sense, since with 6 rolls and 6 faces, getting exactly 4 distinct is the most common outcome.
Approach: We count the favorable outcomes using the "choose then surject" method: pick which 4 faces appear, then count onto functions from 6 rolls to those 4 faces via inclusion-exclusion.
Formal Solution:
1. Choose the 4 faces that appear among the six rolls: $$\binom{6}{4} = 15$$
2. Count surjections from 6 rolls onto 4 chosen values. A surjection ensures each of the 4 values appears at least once. By inclusion-exclusion, the number of onto functions from an $n$-set to a $k$-set is: $$\sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n$$
With $n = 6$, $k = 4$: $$\sum_{j=0}^{4} (-1)^j \binom{4}{j}(4-j)^6 = 4^6 - 4 \cdot 3^6 + 6 \cdot 2^6 - 4 \cdot 1^6 + 0$$ $$= 4096 - 4(729) + 6(64) - 4(1)$$ $$= 4096 - 2916 + 384 - 4 = 1560$$
(Equivalently, this equals $4! \cdot S(6,4)$ where $S(6,4) = 65$ is a Stirling number of the second kind.)
3. Total favorable outcomes: $$15 \times 1560 = 23{,}400$$
- Total outcomes: $6^6 = 46{,}656$.
5. Probability: $$P(\text{exactly 4 distinct}) = \frac{23{,}400}{46{,}656} = \frac{325}{648}$$
Answer: The probability is $\dfrac{325}{648} \approx 0.5015$.
Intuition
This problem is really about the occupancy distribution -- how many bins get filled when you throw balls at random. With 6 balls and 6 bins, the most probable number of occupied bins turns out to be 4 or 5, and the probability of exactly 4 is just over 50%. The technique of "choose which bins are occupied, then count onto functions via inclusion-exclusion" is the standard approach for any occupancy problem. Stirling numbers of the second kind $S(n,k)$ are just a compact notation for this inclusion-exclusion count divided by $k!$.
In quant work, this same combinatorial structure appears whenever you are counting distinct events in a fixed number of trials -- for example, how many distinct counterparties traded in a given session, or how many unique error codes appeared in a log window. The birthday problem is a special case (asking for all-distinct). Once you internalize the "choose then surject" template, these problems become mechanical.