Derangements: Calculating the Number of Incorrect Envelopes

In combinatorics, one interesting problem revolves around the concept of derangements. A derangement is a permutation of elements such that none of the elements appear in their original position. This problem requires the correct utilization of permutations and factorials to determine the number of ways to place letters in addressed envelopes so that none of the letters are in the correct envelope.

Introduction to Derangements

A derangement is a permutation of n objects such that none of the objects appear in their original positions. For example, in a scenario where we have 5 letters and 5 addressed envelopes, we want to calculate the number of ways to place these letters into the envelopes such that no letter is in the correct envelope.

The Formula for Derangements

The formula for the number of derangements, denoted as !n, is given by:

!n n! sum_{i0}^n frac{(-1)^i}{i!}

Here, n! (n factorial) is the total number of permutations of n objects. The summation component (sum_{i0}^n frac{(-1)^i}{i!}) accounts for the derangement possibilities by iterating through each term where i ranges from 0 to n.

Calculating Derangements for 5 Letters

Let's calculate for the case n 5.

Calculate 5!

(text{5!} 120)

Calculate the sum

[ sum_{i0}^5 frac{(-1)^i}{i!} ]

(i 0: quad frac{(-1)^0}{0!} 1) (i 1: quad frac{(-1)^1}{1!} -1) (i 2: quad frac{(-1)^2}{2!} frac{1}{2}) (i 3: quad frac{(-1)^3}{3!} -frac{1}{6}) (i 4: quad frac{(-1)^4}{4!} frac{1}{24}) (i 5: quad frac{(-1)^5}{5!} -frac{1}{120})

Sum these values

[ 1 - 1 frac{1}{2} - frac{1}{6} frac{1}{24} - frac{1}{120} ]

Find a common denominator (120) (frac{120}{120} - frac{120}{120} frac{60}{120} - frac{20}{120} frac{5}{120} - frac{1}{120}) (frac{120 - 120 60 - 20 5 - 1}{120} frac{44}{120} frac{11}{30})

Substitute back into the derangement formula

( !5 5! cdot frac{11}{30} 120 cdot frac{11}{30} 4 cdot 11 44)

Therefore, the number of ways to place the letters in the envelopes such that no letter is in the correct envelope is 44.

Alternative Calculation Methods

Alternatively, we can also solve the problem using basic permutation principles:

1. Total Permutations: There are 5! 120 ways to place one letter in each envelope.

2. Correct Placement: Only one out of these 120 ways places all letters correctly.

3. Calculation of Incorrect Placements: Therefore, there are 120 - 1 119 ways to place the letters incorrectly.

Another Method:

1. "First Envelope First to Get Wrong": There are 4 ways to place the first envelope incorrectly and 4! 24 ways to arrange the remaining letters. So, 4 x 24 96.

2. "First Envelope Correct, Second Envelope First to Get Wrong": There are 3 ways to place the second letter incorrectly, and 3! 6 ways to arrange the remaining three. Thus, 3 x 6 18.

3. "First Two Envelopes Correct, Third Envelope First to Get Wrong": There are 2 x 2! 4 ways.

4. "First Three Envelopes Correct, Fourth Envelope First to Get Wrong": There is 1 x 1! 1 way.

Summing these gives 96 18 4 1 119.

Therefore, the answer is 119 ways to place the letters in the envelopes incorrectly.