The Matching Problem

The "matching problem" is a fascinating probability conundrum with a surprising answer. It has been presented using various scenarios involving hats, envelopes, cards, and more. My personal favorite involves a teacher returning homework assignments to students.

Consider a class with 5 students, where the teacher randomly returns the completed homework assignments. The "matching problem" is: What is the probability that every student receives someone else's homework? In other words, what is the likelihood that no student receives their own assignment?

Two surprises emerge from the answer to this question. First, the famous irrational number e = 2.718… makes an appearance in the solution. Second, the probability scarcely changes with the class size (as long as it is greater than 5 or so).

To formulate the problem more precisely, let's label both the homework assignments and the students from 1 to 5. For instance, if the teacher hands back the assignments in the order 1, 2, 3, 4, 5, every student will receive their own homework. If the order is 2, 3, 4, 1, 5, one student, specifically student 5, will receive the correct assignment. If the order is 5, 3, 2, 1, 4, no student will receive their own homework, and so on.

To calculate the aforementioned probability, we need to determine two crucial factors.

First, we must establish the total number of possible ways the teacher can distribute the homework. This isn’t too difficult. As you may recall from combinatorics, the number of permutations for n items is given by n! (read as "n factorial").

Hence, with 5 students, we have:

\(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\)

possible permutations.

Out of these 120 permutations, we want to determine the number of arrangements where no number appears in its original position. This is equivalent to no student receiving their own homework. The mathematical term for this special type of permutation is a derangement. For instance, the permutation 5, 3, 2, 1, 4 qualifies as a derangement because no number remains in its original position.

There is a formula to calculate the number of derangements, although it is not as concise as other combinatorial formulas. The number of derangements for 5 items is given by:

\(5! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)\)

Punching this expression into a calculator gives 44.

The derivation of this formula is not particularly advanced, but I’ll skip the details. If you're interested, you can refer to the Wikipedia page where they obtain a recursive expression and use it to arrive at the formula.

Returning to our problem, we have established that the teacher can distribute the homework in 120 = 5! different ways, and the number of derangements, representing the arrangements where no student receives their own assignment, is given by the formula above. To calculate the proportion of scenarios where no student receives their own homework, we simply divide the number of derangements (all outcomes where no student receives their own homework) by the total number of possible permutations (all possible outcomes):

\(\frac{5! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)}{5!}\)

The two 5! terms cancel and we are left with:

\(\left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)\)

This comes out to approximately .367, so there is about a 36.7% chance that no student receives their own homework in a class of 5 students.

Using the same logic, if the class size was 10 then the probability would be:

\(\left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \frac{1}{8!} - \frac{1}{9!} + \frac{1}{10!} \right)\)

which comes out to about .36788. Barely different from the class size of 5.

If you’ve had a calculus course, the expression above will look quite familiar. It turns out that the inverse of the famous irrational number e can be written as the following alternating infinite sum:

\( \frac{1}{e} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \;...\)

The factorial grows very quickly, which means that the terms in this infinite sum tend toward 0 very fast. So if we truncate the infinite sum at a particular term, the answer will not change by much. Since the answer to the matching problem is exactly a truncated version of this infinite sum, this implies that the class size hardly matters!

In conclusion, for any class size above, say 5 or so, the probability that no student receives their own homework back is very close to:

\(\frac{1}{e} = 0.367879...\)

On a side note, if you’ve had a course in probability theory you might be wondering why the answer to this problem (e.g. with 10 students) isn’t simply:

\(\left( \frac{9}{10} \right)^{10} \approx .349\)

The reasoning is that each student has a 9 in 10 chance of receiving the wrong homework, and there are 10 students, so the probabilities can be multiplied together 10 times.

This is actually a very good approximation to the problem, especially as the class size grows. However, it is not quite right. To multiply the probabilities, we need the “events” of each student receiving the wrong homework to be independent. Unfortunately, independence doesn’t quite hold. For instance, with a class size of 2, if student 1 receives their own homework, the probability that student 2 also gets their own homework increases from 0.5 to 1.