Mismatched Letters and Envelopes Algorithm

Problem Introduction

Imagine you are a 18th-century French mathematician. Before you sits a desk covered with N letters, each carefully written and addressed.

Next to them lie N envelopes, each bearing a single name. You have a mischievous assistant who, without looking, stuffs each letter into a random envelope.

What is the probability that not a single letter ends up in its correct envelope?

This is the famous Problème des Rencontres (Problem of Coincidences), first studied by Pierre Raymond de Montmort in 1708. It is the original derangement problem—the one that started it all. For over 300 years, mathematicians have been fascinated by the elegant answer: as N grows large, the probability approaches 1/e ≈ 36.79%.

But the problem goes beyond probability. It asks: How many ways can N letters be mismatched with N envelopes so that no letter reaches its intended destination? This count is the number of derangements of N items.

For 4 letters and 4 envelopes, there are 9 ways. For 10 letters and 10 envelopes, there are over 1.3 million ways. For 20 letters and 20 envelopes, there are roughly 895 quadrillion ways—more than the number of stars in the observable universe.

Looking to master dynamic programming for combinatorial problems? Check out our  Tutoring Page  for personalized 1-on-1 coaching.

Why It Matters

The mismatched letters and envelopes problem is historically significant and practically important:

• Cryptographic randomness testing: When generating random permutations for encryption, the frequency of derangements is a statistical test for bias.

• Randomized algorithm validation: Algorithms that rely on random shuffles (e.g., randomized quicksort, Monte Carlo methods) should produce derangements with probability 1/e.

• Quality control in manufacturing: Randomly pairing components to test for defects follows the same mathematics.

• Historical significance: This problem introduced the inclusion-exclusion principle and derangements to mathematics, influencing probability theory for centuries.

Unlike the Secret Santa or job reassignment problems, the letters and envelopes problem is the historical original. Understanding it gives you a direct connection to the 18th-century mathematicians who laid the foundations of modern probability.

Step-by-Step Breakdown

Step 1: Understanding the Mismatch Constraint

Let L₁, L₂, ..., Lₙ be the letters, and E₁, E₂, ..., Eₙ be the envelopes addressed to the corresponding recipients. A mismatched stuffing is a permutation f such that:

• f is a bijection (each letter goes into exactly one envelope, each envelope receives exactly one letter)

• f(Lᵢ) ≠ Eᵢ for all i (no letter goes into its correctly addressed envelope)

This is a derangement of N items. The number of such permutations is !N (subfactorial N).

Step 2: Visualizing the Mismatching Process

In the valid section, every letter goes to the wrong envelope. Letter to Alice goes to Bob's envelope, etc. This forms a 4-cycle.

In the invalid section, the letter to Alice goes into Alice's envelope (a fixed point), violating the mismatching rule.

Step 3: Small Case Analysis (18th Century Style)

Let M(N) be the number of ways to mismatched N letters and N envelopes.

N = 1 (single letter): The only possible stuffing puts the letter into its own envelope. Invalid. M(1) = 0.

N = 2 (two letters): Valid mismatchings:

• Letter A → Envelope B, Letter B → Envelope A (swap)

• That's it. M(2) = 1.

N = 3 (three letters): Let's list systematically:
All 6 permutations of [A,B,C] with envelopes [a,b,c]:

M(3) = 2.

N = 4: M(4) = 9. Montmort himself computed this in 1708.

N = 5: M(5) = 44.

Step 4: Deriving the Recurrence Relation (Historical Method)

Let M(N) be the number of valid mismatched stuffings for N letters.

Step A: Where does Letter 1 go? Letter 1 cannot go into Envelope 1. So it goes into Envelope k, where k ∈ {2, 3, ..., N}. That's (N - 1) possibilities.

Step B: Analyze where Letter k goes.
Now consider Letter k (the letter that belongs in Envelope k). Two scenarios:

Scenario 1: Letter k goes into Envelope 1 (a swap)

• Letter1 → Envelopek, Letterk → Envelope1

• These two letters have swapped envelopes

• The remaining (N - 2) letters must be mismatched among themselves

• Number of ways: M(N - 2)

Scenario 2: Letter k goes into a different envelope (not Envelope 1)

• Letter1 → Envelopek

• Letter k cannot go into Envelope1 (by this scenario) and also cannot go into Envelopek (its own)

• This is equivalent to finding a mismatched stuffing for the remaining (N - 1) letters, with Envelope1 now "forbidden" for Letter k

• Number of ways: M(N - 1)

Step C: Combine
For each of the (N - 1) choices for Letter1's envelope:

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

Base cases: M(1) = 0, M(2) = 1.

This is exactly the recurrence Montmort discovered over 300 years ago.

Step 5: Visualizing Montmort's Recurrence

Step 6: Inclusion-Exclusion Formula (Euler's Contribution)

Leonhard Euler later derived a closed-form formula using inclusion-exclusion:

M(N) = N! × Σ_{k=0 to N} (-1)^k / k!

This is the subfactorial !N. It can also be written as:

!N = round(N! / e)

For example: !4 = round(24 / 2.71828) = round(8.829) = 9 ✓

import math

def mismatched_letters_inclusion_exclusion(n: int) -> int:
    """
    Count mismatched letter-envelope pairings using inclusion-exclusion.
    
    !N = N! × Σ_{k=0 to N} (-1)^k / k!
    
    Time: O(N)
    Space: O(1)
    """
    total = math.factorial(n)
    sum_terms = 0.0
    
    factorial_k = 1
    for k in range(n + 1):
        if k > 0:
            factorial_k *= k
        sum_terms += ((-1) ** k) / factorial_k
    
    return int(round(total * sum_terms))

# Verify for small N
print("Inclusion-Exclusion Verification:")
for n in range(1, 11):
    m = mismatched_letters_inclusion_exclusion(n)
    print(f"  N={n}: M(N) = {m}")

Step 7: Naive Recursive Implementation

def mismatched_letters_recursive(n: int) -> int:
    """
    Naive recursive solution for mismatched letters and envelopes.
    
    Time: O(2^N) - Exponential, only usable for N <= 30
    Space: O(N) - Recursion stack depth
    
    This directly implements Montmort's recurrence.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    return (n - 1) * (
        mismatched_letters_recursive(n - 1) + 
        mismatched_letters_recursive(n - 2)
    )

# Calculate for historical interest
print("Montmort's Original Calculations:")
for n in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:
    m = mismatched_letters_recursive(n)
    print(f"  {n} letters: {m} mismatched arrangements")

Ready to master combinatorial algorithms like the 18th-century mathematicians?

Visit our Order Page now to grab our exclusive Dynamic Programming bootcamp courses!

Step 8: Top-Down DP with Memoization

def mismatched_letters_top_down(n: int, memo: dict = None) -> int:
    """
    Top-down dynamic programming with memoization.
    
    Time: O(N) - Each N computed once
    Space: O(N) - Memo dictionary + recursion stack
    
    This approach makes computing M(1000) instantaneous.
    """
    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) * (
        mismatched_letters_top_down(n - 1, memo) + 
        mismatched_letters_top_down(n - 2, memo)
    )
    return memo[n]

# Large example
n = 50
m = mismatched_letters_top_down(n)
print(f"M({n}) = {m}")
print(f"Number of digits: {len(str(m))}")
print(f"Approximately: {m:.2e}")

Step 9: Bottom-Up DP with Tabulation

def mismatched_letters_bottom_up(n: int) -> int:
    """
    Bottom-up dynamic programming using tabulation.
    
    Time: O(N)
    Space: O(N) - Full DP array
    
    Useful for analyzing all values up to N simultaneously.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    # dp[i] = number of mismatched arrangements for i letters
    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]

# Historical table of values
print("Historical Table of M(N):")
print("N\tM(N)\t\t\tM(N)/N!\t\tApproximation")
print("-" * 70)

for n in range(1, 13):
    m = mismatched_letters_bottom_up(n)
    total = math.factorial(n)
    ratio = m / total if total > 0 else 0
    print(f"{n}\t{m:>18,}\t{ratio:.8f}\t{1/math.e:.8f}")

Step 10: Space-Optimized Solution (For Large N)

def mismatched_letters_optimized(n: int) -> int:
    """
    Space-optimized bottom-up solution.
    
    Time: O(N)
    Space: O(1) - Only two variables
    
    This is the optimal solution for exact counting,
    requiring only O(1) memory regardless of N.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    # prev2 = M(i-2), prev1 = M(i-1)
    prev2 = 0  # M(1)
    prev1 = 1  # M(2)
    
    for i in range(3, n + 1):
        current = (i - 1) * (prev1 + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

# Demonstrate for a very large N
n = 100
m = mismatched_letters_optimized(n)
print(f"M({n}) has approximately {len(str(m))} digits")
print(f"First few digits: {str(m)[:20]}...")

Step 11: Generating Random Mismatched Stuffings

import secrets

def random_mismatched_stuffing(n: int) -> list:
    """
    Generate a random valid mismatched stuffing (derangement).
    
    Uses rejection sampling with cryptographic randomness.
    Expected trials: ~2.718
    """
    if n == 1:
        raise ValueError("Cannot mismatch a single letter")
    if n == 2:
        return [1, 0]  # Swap
    
    while True:
        # Generate random permutation using Fisher-Yates
        perm = list(range(n))
        for i in range(n - 1, 0, -1):
            j = secrets.randbelow(i + 1)
            perm[i], perm[j] = perm[j], perm[i]
        
        # Check for fixed points (letter in correct envelope)
        if all(perm[i] != i for i in range(n)):
            return perm

# Simulate for 5 letters
letters = ["Letter to Alice", "Letter to Bob", "Letter to Charlie", 
           "Letter to Diana", "Letter to Eve"]
envelopes = ["Envelope: Alice", "Envelope: Bob", "Envelope: Charlie",
             "Envelope: Diana", "Envelope: Eve"]

stuffing = random_mismatched_stuffing(5)
print("Random Mismatched Stuffing:")
for i, letter in enumerate(letters):
    print(f"  {letter} → {envelopes[stuffing[i]]}")

# Verify no correct matches
correct_matches = sum(1 for i in range(5) if stuffing[i] == i)
print(f"\nNumber of correct matches: {correct_matches} (should be 0)")

Step 12: Cryptographic Application - Derangement-Based Cipher

def derangement_cipher_encrypt(plaintext: str, key_derangement: list) -> str:
    """
    Simple cipher using a derangement as a substitution key.
    
    The key must be a derangement (no character maps to itself).
    """
    if len(plaintext) != len(key_derangement):
        raise ValueError("Plaintext length must match key length")
    
    ciphertext = [''] * len(plaintext)
    for i, char in enumerate(plaintext):
        ciphertext[key_derangement[i]] = char
    
    return ''.join(ciphertext)

def derangement_cipher_decrypt(ciphertext: str, key_derangement: list) -> str:
    """Decrypt using the inverse of the derangement."""
    # Find inverse permutation
    inverse = [0] * len(key_derangement)
    for i, val in enumerate(key_derangement):
        inverse[val] = i
    
    plaintext = [''] * len(ciphertext)
    for i, char in enumerate(ciphertext):
        plaintext[inverse[i]] = char
    
    return ''.join(plaintext)

# Example with 10 characters
import string
alphabet = list(string.ascii_lowercase[:10])  # a through j
derangement = random_mismatched_stuffing(10)

plain = "helloworld"
print(f"Plaintext: {plain}")
print(f"Derangement key: {derangement}")

cipher = derangement_cipher_encrypt(plain, derangement)
print(f"Ciphertext: {cipher}")

decrypted = derangement_cipher_decrypt(cipher, derangement)
print(f"Decrypted: {decrypted}")
print(f"Valid? {plain == decrypted}")

Common Mistakes

Mistake 1: Confusing the Problem with "Randomly Stuffing One Letter"

The classic puzzle is sometimes misstated as "what is the probability that at least one letter is correct?" That's the complement (1 - 1/e). The original problème des rencontres asks for no correct matches.

Mistake 2: Forgetting That M(1) = 0

A single letter cannot be mismatched. The only possible stuffing puts it in its own envelope. This is a common off-by-one error.

Mistake 3: Assuming Independence of Events

P(Letter i is correct) = 1/N, but these events are not independent. P(Letter i correct AND Letter j correct) = 1/(N(N-1)), not 1/N². This is why the inclusion-exclusion formula requires alternating signs.

Mistake 4: Using the Rounding Formula Without Understanding

!N = round(N!/e) works for N ≥ 1, but you must use proper rounding (not floor or ceiling). For N=4, 24/e = 8.829, round = 9 ✓. For N=5, 120/e = 44.14, round = 44 ✓.

Mistake 5: Ignoring Historical Context

The problème des rencontres introduced the inclusion-exclusion principle to mathematics. Understanding this history helps appreciate why the formula works.

Frequently Asked Questions

Q1: How does the letters and envelopes problem differ from the hat check problem?

A: They are mathematically identical. The only difference is the storytelling: letters/envelopes vs. hats/people. The hat check problem is actually a later rephrasing of Montmort's original.

Q2: Who solved the problème des rencontres first?

A: Pierre Raymond de Montmort published the solution in his 1708 book "Essay d'analyse sur les jeux de hazard." He derived the recurrence and computed values up to N=10. Euler later generalized it with inclusion-exclusion.

Q3: Why is the subfactorial denoted !N?

A: The notation was introduced by Christian Kramp in 1808. The exclamation mark before the number indicates the number of derangements, as opposed to n! (factorial) after the number.

Q4: Can this problem be solved with generating functions?

A: Yes. The exponential generating function for derangements is e^{-x}/(1-x). The coefficient of x^N/N! is !N.

Q5: How does this apply to modern cryptography?

A: Random permutation generators are tested for bias by checking derangement frequency. A bias in derangement probability indicates non-uniformity, which could weaken cryptographic security.

Conclusion

The mismatched letters and envelopes problem—the original problème des rencontres—is the historical foundation of derangement theory. You have learned:

• How Montmort derived the recurrence M(N) = (N-1) × (M(N-1) + M(N-2))

• How Euler's inclusion-exclusion gives the closed form !N = N! × Σ (-1)^k/k!

• How the probability converges to 1/e ≈ 36.79%

• How to implement the recurrence in four ways, from naive recursion to O(1) space optimization

• How to generate random mismatched stuffings for testing

• How derangements can be used in simple cryptographic ciphers

The next time you stuff envelopes (or test a random number generator), you will remember Montmort and Euler—and the beautiful mathematics that has fascinated mathematicians for over 300 years.

Ready to master combinatorial algorithms like the 18th-century mathematicians?
Want to learn dynamic programming from the ground up? 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!

Where to Go Next

If you found this guide helpful, you might also enjoy these related resources:

• Return to the anchor article: Counting Derangements: Main Guide – For a complete overview of derangement theory, including the full recurrence derivation, base cases, and a comparison of all four DP approaches.

• Derangement Probability Algorithm Evaluation – Learn how to evaluate the probability that a random shuffle produces a derangement, with Monte Carlo simulations and convergence analysis.

• Solving the Secret Santa Problem with Dynamic Programming – Apply the same mathematics to holiday gift exchanges with practical random assignment generation.

• History of Combinatorics – Read our blog post on Montmort, Euler, and the birth of probability theory .

• Cryptographic Randomness Testing – Explore statistical tests for random permutation generators.