---
# System prepended metadata

title: Lab 11/7

---

# Lab 11/7
**Problem (A Small Example)**: $bcda, dcba, cdba, cdab, dcab, cadb, badc, bdac, dabc$
**Problem (Choices For First Student):** $n - 1$
**Problem (Second Student: Chooses First Student’s Paper):** If two students pair up, then we find the number of derangements of $!(n - 2)$ students instead.
**Problem (Second Student: Chooses Another Paper):** $!(n - 1)$
**Exercise (Putting It All Together):** 
$!n = n - 1 * (!(n - 2) + !(n - 1))$


**Exercise (Increasing Non-Derangements):**
Let $S_k$ be the set of permutations with at least k in its correct position
$S_1: abcd, acbd, adcb, acdb, abdc, adbc$ (6)
$S_2: abcd, cbad, cbda, dbca, abdc, dbac$ (6)
$S_3: abcd, bacd, bdca, dbca, dacb, adcb$ (6)
$S_4: abcd, bacd, cabd, acbd, bcad, cbad$ (6)

At lease one:
$abcd, bacd, cabd, acbd, bcad, cbad, cbda, bdca, dbca, dacb, adcb, acdb, abdc, dbac, adbc$ (15)   
At least two:
$abcd, bacd, acbd, cbad, dbca, adcb, abdc$ (8)
At least three:
$abcd$ (1)
At least four:
$abcd$ (1)

**Exercise (A Concrete Formula):**
Total number of derangements: $4! - |S_1 \cup S_2 \cup S_3 \cup S_4|$
$|S_1 \cup S_2 \cup S_3 \cup S_4| = (|S_1| + |S_2| +|S_3 + |S_4|) -
(|S_1| \cup |S_2|) - (|S_1| \cup |S_3|) - (|S_1| \cup |S_4|) -
(|S_2| \cup |S_3|) - (|S_2| \cup |S_4|) - (|S_3| \cup |S_2|) +
(|S_1| \cup |S_2| \cup |S_3|) + (|S_1| \cup |S_2| \cup |S_4|) +
(|S_2| \cup |S_3| \cup |S_4|) - (|S_1| \cup |S_2| \cup |S_3|\cup |S_4|)$

**Exercise (An Abstract Formula):**
Total number of derangements: $n! - |S_1 \cup S_2 \cup ... S_k|$

**Exercise (The Punchline):**
The two formulae:
$!n = n - 1 * (!(n - 2) + !(n - 1))$
or 
$!n = n! - |S_1 \cup S_2 \cup ... S_k|$



