Find the number of derangements of {1, 2, ..., n} using inclusion-exclusion principle

Step 1: Define Derangements and Total Permutations

A derangement is a permutation of the elements of a set, such that no element appears in its original position. We want to find the number of such permutations for a set of $n$ elements. First, let's recall that the total number of permutations of $n$ distinct elements is $n!$.

Step 2: Define Properties for Inclusion-Exclusion

To use the inclusion-exclusion principle, we define properties. Let $A_i$ be the set of permutations where the $i$ -th element is in its original position. We are looking for the number of permutations where *none* of the elements are in their original positions, which is $n! - |A_1 \cup A_2 \cup \dots \cup A_n|$.

Step 3: Calculate Sizes of Intersections

If element $i$ is in its original position, the remaining $n-1$ elements can be permuted in $(n-1)!$ ways. Similarly, if $k$ specific elements are in their original positions, the remaining $n-k$ elements can be permuted in $(n-k)!$ ways. There are $\binom{n}{k}$ ways to choose which $k$ elements are fixed.

Step 4: Apply Inclusion-Exclusion Principle

Now we apply the inclusion-exclusion principle to find the size of the union of all sets $A_i$. We substitute the expressions for the sums of the sizes of intersections we found in the previous step.

Step 5: Simplify the Sum

We simplify the term $\binom{n}{k}(n-k)!$ to $\frac{n!}{k!}$. This allows us to factor out $n!$ from the sum, making the expression more compact.

Step 6: Calculate Number of Derangements

The number of derangements $D_n$ is the total number of permutations minus the number of permutations where at least one element is in its original position. We substitute the simplified sum into this formula and factor out $n!$.

More from this chapter

• Find the probability that in a random arrangement of the letters of the word MATHEMATICS, the two A's are not together.
• 36. Find the number of ways in which six people can ride a toboggan if one of a subset of three must drive. 37. (a) Find the number of ways in which five person
• In how many ways can 4 red, 3 yellow and 2 green discs be arranged in a row if the discs of the same colour are indistinguishable?
• How many numbers lying between 100 and 1000 can be formed with the digits 0, 1, 2, 3, 4, 5, if the repetition of the digits is not allowed?
• How many ways can a 2×n rectangle be tiled using 1×2 dominoes?
• The largest n N such that 3^n divides 50! is:
• How many 4-digit numbers can be formed by using the digits 1 to 9 if repetition of digits is not allowed?
• The number of 3-digit numbers, that are divisible by 2 and 3, but not divisible by 4 and 9, is

All Permutations and Combinations solutions →