Probability Problem: 'Letter Mix-Up'

[munky]

Four letters and envelopes are addressed to four different people. If the letters are randomly inserted into the envelopes, what is the probability that at least one is inserted in the correct envelope?

I know that since the sample space for this problem is relatively small, one straightforward way to solve this is simply writing out all the possible outcomes. (I also know, according to the answer key, that the answer is 5/8.) However, I'm wondering if it's possible to solve for the answer algebraically. I attempted to do so but got stuck.

So I named the envelopes and letters for convenience.
Envelopes: envA, envB, envC, envD
Letters: lettA, lettB, lettC, lettD

And since the problem calls for 'at least one', I figure that I can find the complementary event (in which none of the envelope/letter pairs are correct), and subtract that probability from 1 to get the answer.

(3 * 2 * 1 * 1)/(4!) = 6/24
or
(3 * 3 * 1 * 1)/(4!) = 9/24

Starting with envA, you can put in any letter except for lettA, so 3 choices.
For envB, if lettA went into envB, then you have 3 choices. If lettA went into envC or envD, you have only 2 choices.
envC has only 1 choice, because you either have to avoid lettC or take lettD to prevent it from going into envD.
Of course, envD has the remaining letter, so 1 choice.

That's my reasoning so far. However, I'm not sure what to do next, and while my reasoning seems sound to me, I'm not 100% sure that's it's correct.

 

[soroban]

Hello, munky!

Your preliminary reasoning is correct,
. . but the problem is quite complicated.

Four letters and envelopes are addressed to four different people.
If the letters are randomly inserted into the envelopes,
what is the probability that at least one is inserted in the correct envelope?

This is a classic problem: "The Misaddressed Envelopes."

If we have \(\displaystyle n\) objects, each with its proper position,
. . an arrangement in which none of them is in its proper position is called a derangement.

\(\displaystyle \text{The number of derangements of }n\text{ objects, }D(n)\text{, is an intricate formula}\)
. . \(\displaystyle \text{with an even more intricate derivation.}\)


With only 4 objects, we may as well crank out the derangements.

\(\displaystyle \text{With four objects }\{A,B,C,D\}\text{. the derangements are:}\)
. . \(\displaystyle BADC,\:BCDA,\:BDAC,\:CADB,\:CDAB,\:CDBA,\ABC,\CAB,\CBA\)


There are 9 derangements, hence there are 15 with at least one letter in its correct envelope.

\(\displaystyle \text{The probability is: }\:\frac{15}{24} \:=\:\frac{5}{8}\)

 

[munky]

Thanks, soroban. I guess the best way to solve this problem really would be to just write out all the possible outcomes.

I also did a quick Google search on derangement, and between all the results about political stuff, I've stumbled upon some interesting information. Can't say I understand all of it, but at least now I can get this problem out of my mind now that I know it can be solved for algebraically. Haha.