Probability

Maths Help suggests:

This is a well known problem in probability. It is known as the "drunken secretary problem" - conjuring up images of a secretary who has had a few too many drinks not bothering about how the letters are put into the envelopes.

It is quite a tricky problem. There are several methods of approaching it, each needing maths of at least A-level standard. The one below is not necessarily the shortest, but we think it is the easiest to follow and try yourself.

We will start with the case of 2 letters and 2 envelopes, and then build it up to 3, 4, and 5 letters and envelopes. We could of course go further. In each case, we will work out the number of ways of getting 0 correct matches, 1 correct match, 2 correct matches etc, and we will need to do this in reverse order. When we have a table of the number of ways of getting all the different numbers of matches, we can easily find the probabilities.

Some essential background results before we start:

• Assuming the envelopes are in fixed positions, the total number of ways of ordering the n letters to go into the n envelopes is n! (n factorial).
• If r of the n letters are matched correctly, the number of ways of choosing which r of the n are matched correctly is ⁿC_r
• We will use the notation N(0/m) to stand for "the number of ways of getting no correct matches with m letters and m envelopes.
• There is only one way that all letters can be correctly matched.
• There is no way that all but one letter can be correctly matched (think about it...!)

CONSIDER THE CASE OF 2 LETTERS AND 2 ENVELOPES

There are 2! = 2 ways in total.

Number of ways of 2 correct matches = 1 (always)

Number of ways of getting 1 correct match = 0 (always)

Number of ways of getting 0 correct matches is 2 - (1 + 0) = 1
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:

Correct matches	2	1	0
Number of ways	1	0	1

CONSIDER THE CASE OF 3 LETTERS AND 3 ENVELOPES

There are 3! = 6 ways in total.

Number of ways of 3 correct matches = 1 (always)

Number of ways of getting 2 correct matches = 0 (always)

Number of ways of getting 1 correct match = ³C₁ × N(0/2) = 3×1 = 3
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 0 correct matches is 6 - (1 + 0 + 3) = 2
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:

Correct matches	3	2	1	0
Number of ways	1	0	3	2

CONSIDER THE CASE OF 4 LETTERS AND 4 ENVELOPES

There are 4! = 24 ways in total.

Number of ways of 4 correct matches = 1 (always)

Number of ways of getting 3 correct matches = 0 (always)

Number of ways of getting 2 correct matches = ⁴C₂ × N(0/2) = 6×1 = 6
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 1 correct match = ⁴C₁ × N(0/3) = 4×2 = 8
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 0 correct matches is 24 - (1 + 0 + 6 + 8) = 9
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:

Correct matches	4	3	2	1	0
Number of ways	1	0	6	8	9

CONSIDER THE CASE OF 5 LETTERS AND 5 ENVELOPES

There are 5! = 120 ways in total.

Number of ways of 5 correct matches = 1 (always)

Number of ways of getting 4 correct matches = 0 (always)

Number of ways of getting 3 correct matches = ⁵C₃ × N(0/2) = 10×1 = 10
Note this is "number of ways of choosing the three which match" times "number of ways that none of the remaining ones match". N(0/2) is taken from the previous table.

Number of ways of getting 2 correct matches = ⁵C₂ × N(0/3) = 10×2 = 20
Note this is "number of ways of choosing the two which match" times "number of ways that none of the remaining ones match". N(0/3) is taken from the previous table.

Number of ways of getting 1 correct match = ⁵C₁ × N(0/4) = 5×9 = 45
Note this is "number of ways of choosing the one which matches" times "number of ways that none of the remaining ones match". N(0/4) is taken from the previous table.

Number of ways of getting 0 correct matches is 120 - (1 + 0 + 10 + 20 + 45) = 44
Note that this is given by "total number of ways" minus "all the other answers"

The results here can be presented in a table:

Correct matches	5	4	3	2	1	0
Number of ways	1	0	10	20	45	44

This procedure can be continued recursively for higher numbers of letters and envelopes.

So the answer to your question is:
The probability of no correct matches for 5 letters and 5 envelopes is 44/120 = 11/30