Birthday and matching problems

What you will be able to do

• find the probability that $n$ people all have different birthdays, and that at least two share one;
• count the ways to put $n$ letters in $n$ envelopes with no letter in its own envelope, called derangements;
• find the chance of exactly $r$ matches.

The room of twenty-three

How many people must be in a room for it to be more likely than not that two of them share a birthday? Many people guess a number near $180$, half of $365$. The true answer is $23$. We need a model first. Assume that there are $365$ days (ignore a leap day), that each person's birthday is equally likely to be any day, and that people are independent.

The complement is easier. The probability that all $n$ people have different birthdays is

The second person must avoid one day, the third must avoid two, and so on. So

For $n = 10$ it is about $0.117$, for $n = 23$ about $0.507$, for $n = 30$ about $0.706$ and for $n = 50$ about $0.970$. The chance grows quickly because the number of pairs of people grows like $\dfrac{n^2}{2}$. Twenty-three people make $253$ pairs, and each pair has a chance $\dfrac{1}{365}$ of sharing a birthday.

The same idea works for any number of boxes. If $n$ objects each land in one of $N$ equally likely boxes, the chance that all land in different boxes is $\dfrac{^NP_n}{N^n}$. For five people and $12$ months of birth, it is $\dfrac{12 \times 11 \times 10 \times 9 \times 8}{12^5}$.

A different question. The chance that someone else shares your birthday in a room of $n$ people is $1 - \left(\dfrac{364}{365}\right)^{n-1}$. You need $253$ other people for an even chance. Do not mix the two questions.

Letters in envelopes

A secretary writes $n$ letters and $n$ addressed envelopes, and then puts the letters in the envelopes at random, one in each. A match is a letter in its own envelope. What is the chance that there is no match?

An outcome is a permutation of the $n$ letters, so there are $n!$ outcomes. We count the permutations with no fixed point. They are called derangements, and their number is $D_n$.

By inclusion and exclusion, let $A_i$ be "letter $i$ is in the right envelope". Then $P(A_i) = \dfrac{(n-1)!}{n!} = \dfrac{1}{n}$, and for any $k$ letters, $P(\text{all of them right}) = \dfrac{(n-k)!}{n!}$. There are $^nC_k$ ways to choose the $k$ letters, so the sum for $k$ letters is $^nC_k \times \dfrac{(n-k)!}{n!} = \dfrac{1}{k!}$. So

The values are $D_1 = 0$, $D_2 = 1$, $D_3 = 2$, $D_4 = 9$, $D_5 = 44$, $D_6 = 265$. A shortcut is $D_n = (n - 1)(D_{n-1} + D_{n-2})$, so $D_6 = 5 \times (44 + 9) = 265$.

The sum $\sum \dfrac{(-1)^k}{k!}$ is the start of the series for $e^{-1}$. So for large $n$, the chance of no match is close to $\dfrac{1}{e} \approx 0.3679$. Already for $n = 6$ it is $\dfrac{265}{720} \approx 0.3681$.

Exactly r matches

To get exactly $r$ matches, choose which $r$ letters are in the right envelope, $^nC_r$ ways. The other $n - r$ letters must all be wrong, which is $D_{n-r}$ ways. So

For $n = 4$: no match is $\dfrac{9}{24}$, exactly one is $\dfrac{4 \times 2}{24} = \dfrac{8}{24}$, exactly two is $\dfrac{6 \times 1}{24}$, exactly three is $\dfrac{4 \times 0}{24} = 0$, and four is $\dfrac{1}{24}$. These add up to $\dfrac{24}{24}$. Exactly three matches is impossible, because if three letters are right, the fourth must be right too.

A worked example

Five students hand in their papers. The teacher returns the papers at random, one to each student. Find the probability that no student gets the right paper, and that exactly one does.

1. No match. $D_5 = 44$ out of $5! = 120$, so the probability is $\dfrac{44}{120} = \dfrac{11}{30}$.
2. Exactly one. Choose the student, $5$ ways. The other four must all be wrong, $D_4 = 9$ ways. So $\dfrac{5 \times 9}{120} = \dfrac{45}{120} = \dfrac{3}{8}$.
3. Check by recurrence. $D_5 = 4 \times (D_4 + D_3) = 4 \times (9 + 2) = 44$. It agrees.

Practise with new numbers

Try it in Python

The program finds the chance of a shared birthday in exact fractions for a few group sizes. It then lists all the permutations of $n$ letters, counts those with no letter in place, and compares the count with the formula and with $\dfrac{1}{e}$.

Common mistakes

• Taking half of $365$. A shared birthday needs a pair, and the number of pairs grows quickly.
• Mixing "some two share" with "someone shares mine". They are different events.
• Dropping the factor $^nC_r$. Exactly $r$ matches also needs the choice of which $r$ letters match.
• Forgetting that exactly $n - 1$ matches is impossible. If $n - 1$ letters are right, so is the last.

Remember these

• All different birthdays: $\dfrac{^{365}P_n}{365^n}$. At least two share: one minus that.
• Derangements: $D_n = n!\displaystyle\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}$, $D_n = (n - 1)(D_{n-1} + D_{n-2})$.
• No match: $\dfrac{D_n}{n!}$, close to $\dfrac{1}{e}$ for $n \ge 5$.
• Exactly $r$ matches: $\dfrac{^nC_r \times D_{n-r}}{n!}$.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Four friends each name a day of the week at random. Find the probability that all four name different days.

2. Three letters are put into three envelopes at random. Find the probability that no letter is in the right envelope.

3. Find $D_4$ with the recurrence $D_n = (n - 1)(D_{n-1} + D_{n-2})$.

4. Four letters go into four envelopes at random. Find the probability that exactly two letters are in the right envelopes.

5. Why is the answer to "exactly $n - 1$ matches" always zero?

References

• OpenStax, Precalculus 2e, Chapter 11, sections on counting principles and on probability.