Anchor Article: Counting Derangements: A Comprehensive Guide to Solving Derangements

Problem Introduction: What Are Derangements?

Imagine you are organizing a Secret Santa gift exchange with five friends. You write each person's name on a slip of paper, put the slips in a hat, and have everyone draw one name. But there is a catch: no one can draw their own name. How many different ways can the names be drawn so that nobody gets themselves?

This is a derangement problem. A derangement is a permutation of a set where no element appears in its original position. In mathematical terms, for a set of N items, a derangement is a rearrangement with zero fixed points.

The problem appears simple but quickly becomes complex. For 3 items, there are 2 derangements. For 4 items, there are 9. For 10 items, there are 1,334,961. Understanding how to count these arrangements efficiently is a foundational skill in combinatorics and dynamic programming.

Why It Matters

Derangements are not just a mathematical curiosity. They appear in:

• Cryptography: Ensuring no encryption key maps to itself

• Randomized algorithms: Verifying shuffle algorithms produce true randomness

• Security protocols: Creating "total scrambling" scenarios

• Technical interviews: FAANG companies regularly test derangement logic

According to recent data, approximately 40% of software engineering interviews at top tech companies include at least one combinatorics or DP problem. Derangements are a favorite because they test both mathematical reasoning and algorithmic optimization.

• Looking to step up your coding interview prep? Check out our Tutoring Page for personalized 1-on-1 coaching.*

Step-by-Step Breakdown

Step 1: Understanding the Base Cases

Before building any algorithm, establish the smallest possible scenarios:

• N = 1: With only one item, the only possible arrangement puts that item in its original position. There are zero derangements. D(1) = 0

• N = 2: Two items can only swap positions. Item 1 goes to position 2, item 2 goes to position 1. Exactly one derangement. D(2) = 1

• N = 3: Let's list them manually. Items A, B, C. Valid derangements: (B, C, A) and (C, A, B). Two derangements. D(3) = 2

These base cases serve as the foundation for our recurrence relation.

Step 2: Visualizing the Problem

This diagram shows the branching nature of derangement counting. Each choice leads to subproblems of size N-1 or N-2.

Step 3: Deriving the Recurrence Relation

Let D(N) represent the number of derangements for N items. Consider placing the first item (item 1).

How many positions can item 1 go to? It cannot stay in position 1, so it has (N - 1) possible positions. Let's say item 1 goes to position k (where k ≠ 1).

Now look at item k (the item originally belonging to position k). We have two distinct scenarios:

Scenario A: Item k goes to position 1 (the swap case)

• Item 1 is at position k, item k is at position 1

• These two items have swapped places

• The remaining (N - 2) items must form a derangement among themselves

• Number of ways: D(N - 2)

Scenario B: Item k does NOT go to position 1 (the reduction case)

• Item 1 is at position k

• Item k must go somewhere else, but NOT to position 1

• This effectively means we have (N - 1) remaining items (including item k) that need to be arranged with the restriction that item k cannot go to position 1

• This is exactly a derangement problem of size (N - 1)

• Number of ways: D(N - 1)

Since there are (N - 1) choices for where item 1 goes, and for each choice we have D(N - 1) + D(N - 2) arrangements of the remaining items, the recurrence relation is:

D(N) = (N - 1) × [D(N - 1) + D(N - 2)]

Let's verify with N = 3: D(3) = (2) × [D(2) + D(1)] = 2 × [1 + 0] = 2 ✓

Step 4: Recursive Implementation

The recurrence relation translates directly into recursive code:

def count_derangements_recursive(n: int) -> int:
    """
    Naive recursive solution for counting derangements.
    Time: O(2^N) - Exponential, only works for very small N
    Space: O(N) - Recursion stack depth
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    return (n - 1) * (count_derangements_recursive(n - 1) + 
                      count_derangements_recursive(n - 2))

# Example usage
print(count_derangements_recursive(4))  # Output: 9

Why this is inefficient: The recursive tree has massive overlap. Calculating D(5) requires computing D(4) and D(3). D(4) requires D(3) and D(2). D(3) is computed multiple times. For N = 40, this would take longer than the age of the universe.

Step 5: Top-Down Dynamic Programming (Memoization)

We add a memoization dictionary to cache results:

def count_derangements_top_down(n: int, memo: dict = None) -> int:
    """
    Top-down DP with memoization.
    Time: O(N) - Each n computed once
    Space: O(N) - Memo dictionary + recursion stack
    """
    if memo is None:
        memo = {}
    
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n in memo:
        return memo[n]
    
    memo[n] = (n - 1) * (count_derangements_top_down(n - 1, memo) + 
                         count_derangements_top_down(n - 2, memo))
    return memo[n]

Key insight: Memoization transforms exponential time into linear time by storing each computed value. The recursion still uses O(N) stack space.

Step 6: Bottom-Up Dynamic Programming (Tabulation)

We eliminate recursion entirely by building from base cases upward:

def count_derangements_bottom_up(n: int) -> int:
    """
    Bottom-up DP with tabulation.
    Time: O(N)
    Space: O(N) - Full DP array
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    # dp[i] = number of derangements for i items
    dp = [0] * (n + 1)
    dp[1] = 0
    dp[2] = 1
    
    for i in range(3, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
    
    return dp[n]

Why tabulation is better: No recursion overhead, no stack overflow risk, and the iterative structure is easier to optimize further.

Step 7: Space Optimization (O(1) Extra Space)

Observe that dp[i] only depends on dp[i-1] and dp[i-2]. We don't need the entire array:

def count_derangements_optimized(n: int) -> int:
    """
    Space-optimized bottom-up DP.
    Time: O(N)
    Space: O(1) - Only two variables
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    # prev2 = D(i-2), prev1 = D(i-1)
    prev2 = 0  # D(1)
    prev1 = 1  # D(2)
    
    for i in range(3, n + 1):
        current = (i - 1) * (prev1 + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

Final complexity: O(N) time, O(1) space. This is the optimal solution for exact derangement counting.

Ready to crush your next technical interview?
Visit our Order Page now to grab our exclusive Dynamic Programming bootcamp courses!

Common Mistakes (And How to Avoid Them)

Mistake 1: Incorrect Base Cases

Many beginners set D(1) = 1, thinking "one item can go to one position." But that position is its original spot, so it's not a derangement. 

Always remember: D(1) = 0.

Mistake 2: Missing the (N-1) Multiplier

A common error is writing D(N) = D(N-1) + D(N-2) (like Fibonacci). This ignores the (N-1) choices for the first element's position. Without this multiplier, D(3) would be 1+0=1, which is wrong.

Mistake 3: Forgetting Modular Arithmetic

Derangements grow super-exponentially. D(20) is about 8.9 × 10^17, which exceeds 64-bit integer limits. In competitive programming, problems often require modulo 10^9+7:

MOD = 10**9 + 7

def count_derangements_mod(n: int) -> int:
    if n == 1: return 0
    if n == 2: return 1
    prev2, prev1 = 0, 1
    for i in range(3, n + 1):
        current = ((i - 1) % MOD) * ((prev1 + prev2) % MOD) % MOD
        prev2, prev1 = prev1, current
    return prev1

Mistake 4: Overflow in Other Languages

If coding in C++ or Java, use long long (64-bit) for N ≤ 20. For larger N, implement modular arithmetic or use Python's arbitrary-precision integers.

Frequently Asked Questions

Q1: What is the probability that a random permutation is a derangement?

A: As N grows large, the probability approaches 1/e ≈ 0.367879. For N = 10, it's already 0.367879. This convergence is remarkably fast.

Q2: Can derangements be computed without iteration?

A: Yes, using the closed-form formula: D(N) = N! × Σ_{k=0 to N} ((-1)^k / k!). However, this requires computing factorials and has O(N) time anyway, with potential floating-point precision issues for large N.

Q3: How is this different from the "hat check problem"?

A: They are mathematically identical. The hat check problem asks: N people check their hats, the attendant returns them randomly. What's the probability nobody gets their own hat? That probability is D(N)/N!.

Q4: Why do technical interviews focus on derangements?

A: Because derangements test three key skills: (1) translating a word problem into a recurrence, (2) recognizing overlapping subproblems for DP, and (3) optimizing space complexity. It's the perfect medium-difficulty DP problem.

Q5: What is the time complexity of the optimized solution?

A: O(N) time with O(1) space. The single loop from 3 to N performs constant-time operations at each iteration.

Explore 10 Real-World Derangement Applications

The derangement recurrence D(N) = (N-1) × (D(N-1) + D(N-2)) appears in dozens of real-world scenarios. Below are 10 practical applications, each with its own unique twist, visualization, and implementation details. Click any title to dive into the full guide.

1. Solving the Secret Santa Problem with Dynamic Programming

Hint: That office holiday party where everyone draws a name from a hat? Behind the fun is a surprisingly deep combinatorial problem. Did you know that for 10 people, there are over 1.3 million valid Secret Santa assignments? This article walks through the exact recurrence, shows you how to generate valid assignments randomly, and explains why your simple "shuffle and check" method fails 63% of the time. Read the full Secret Santa guide →

2. Dynamic Programming in the Hat Check Puzzle

Hint: A forgetful attendant returns hats at random to N guests. What's the probability that absolutely no one gets their own hat? The answer converges to a famous constant: 1/e ≈ 36.79%. This article reveals why this probability appears in everything from cryptography to finance interviews, and includes a full probability analysis with convergence tables. Read the full Hat Check guide →

3. Mismatched Letters and Envelopes Algorithm

Hint: You have N letters and N pre-addressed envelopes. You stuff them randomly. What's the chance that not a single letter goes into its correct envelope? This is the historic "Problème des Rencontres" that puzzled mathematicians for centuries. The article includes a closed-form solution using inclusion-exclusion and shows how to use it for randomized testing. Read the full Letters & Envelopes guide →

4. Exam Seating Rearrangements using DP

Hint: A professor wants to rearrange seating so no student sits in the same desk as the previous exam. For a class of 30, the number of valid seating charts is astronomical—far more than atoms in the observable universe. This article connects derangements to academic integrity and includes production-ready code for validating seating assignments. Read the full Exam Seating guide →

5. Network Node Routing Preventing Immediate Return

Hint: In a peer-to-peer network, each node forwards a packet to another node. But if a node sends a packet to itself, it creates a micro-loop that brings down performance. Counting valid routing tables is a derangement problem. This article includes a network topology visualization and explains how telecom companies use these counts for load balancing. Read the full Network Routing guide →

6. Optimizing Job Reassignments without Overlap

Hint: A manager wants to reassign N employees to N roles, but no one can keep their current job. This is a classic "total rotation" problem used in banking to prevent long-term fraud. The article includes a mathematical proof of why the number of valid reassignments is the nearest integer to N!/e and how to implement this in HR software. Read the full Job Reassignments guide →

7. General Gift Exchange Combinatorics

Hint: Instead of individuals, imagine N departments exchanging gifts with each other. No department can give to itself. This macro-level derangement models supply chain inter-trading and economic dependencies. The article includes a multi-node diagram and shows how to scale derangement logic to weighted graphs. Read the full Gift Exchange guide →

8. Key and Lock Re-matching Logic

Hint: A hotel has N rooms and N keys. After a security breach, management scrambles keys so no original key opens its matched room. How many ways? This article includes a physical security visualization and explains why derangements are essential for "total scrambling" in cryptographic protocols. Read the full Key & Lock guide →

9. Team Restructuring Total Derangement Scenario

Hint: An esports organization with N players wants to completely restructure its rosters so zero players remain in their original position. This application bridges game theory and sports management. The article includes a partial derangement extension (where exactly K players stay) and shows how to transition from total to partial derangements. Read the full Team Restructuring guide →

10. Derangement Probability Algorithm Evaluation

Hint: Given an array of N unique integers, what's the probability that randomly shuffling yields no element in its original index? The answer converges to 1/e, but the rate of convergence matters for randomized algorithm testing. This article includes empirical convergence graphs and a comparison of Monte Carlo simulation vs. exact DP. Read the full Probability Evaluation guide →

Conclusion

Counting derangements is a gateway problem for understanding dynamic programming. You've progressed from a naive recursive solution (exponential time) to memoization (linear time with linear space) to tabulation (linear time with linear space) to the final optimized version (linear time with constant space).

This progression mirrors real-world software optimization: start with correctness, then improve efficiency systematically. 

The recurrence relation D(N) = (N-1) × (D(N-1) + D(N-2)) will serve you well in interviews and algorithmic challenges.

Now that you've mastered the core derangement algorithm, explore the 10 applications above. Each article takes the same recurrence and applies it to a distinct domain—Secret Santa, network routing, job reassignments, and more—with unique visualizations, code examples, and insights. You'll learn something new from every one.

Take Your Skills to the Next Level!
Want to master Advanced Dynamic Programming alongside FAANG engineers? Our platform has everything you need.

👉 Visit Our Tutoring Page to book a session today.
👉 Check Our Order Page for direct access to our full DP coursework!