Find the number of derangements of {1, 2, ..., n} using inclusion-exclusion principle
Get the complete, step-by-step math solution for: "Find the number of derangements of {1, 2, ..., n} using inclusion-exclusion principle". Powered by SolveForX AI math tutor.
Step-by-Step Solution
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 Ai 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!−∣A1∪A2∪⋯∪An∣.
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 (kn) 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 Ai. 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 (kn)(n−k)! to kn!!. 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 Dn 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!.