gen-define-derangements-and-give-one-short-worked-example-f8da

Define derangements and give one short worked example.

# Derangements A **derangement** is a permutation of a set where no element appears in its original position. In other words, it's a permutation with no fixed points. For a set of n elements, the number of derangements is denoted **!n** or **D_n**. ## Formula The number of derangements of n elements is: **!n = n! × Σ(k=0 to n) [(-1)^k / k!]** Or approximately: **!n ≈ n!/e** (for large n) ## Worked Example **Problem:** How many derangements are there of {1, 2, 3}? **Solution:** List all 3! = 6 permutations and check which have no element in its original position: 1. (1,2,3) - ✗ (1 is in position 1) 2. (1,3,2) - ✗ (1 is in position 1) 3. **(2,3,1) - ✓** (no element in original position) 4. (2,1,3) - ✗ (3 is in position 3) 5. **(3,1,2) - ✓** (no element in original position) 6. (3,2,1) - ✗ (2 is in position 2) **Answer:** !3 = **2** derangements Using the formula: !3 = 3![1 - 1 + 1/2 - 1/6] = 6 × 1/3 = **2** ✓