Derangements

Why Derangements Matters

Four letters are placed into four addressed envelopes, one letter per envelope. How many assignments put every letter into the wrong envelope? There are $4!=24$ unrestricted assignments, but only nine satisfy the condition. Those nine permutations are derangements.

A derangement is a permutation with no fixed points: no object remains in its original position. The same model counts gift assignments with no self-recipient, reassignment test cases that avoid every original pairing, and perfect matchings in a complete bipartite assignment graph with its diagonal removed. It assumes distinct objects, a one-to-one assignment, and no forbidden pairs beyond the original matches.

This lesson derives a recurrence that counts derangements in linear time while storing only two previous values. You will trace every update through $D(5)=44$, implement the same method in Python, C++, and Java, and recognize when extra restrictions require a different counting problem.

Core Concepts and Terminology

A permutation $\pi$ assigns each position $i$ exactly one label $\pi(i)$, using every label exactly once. A fixed point is a position satisfying $\pi(i)=i$. A derangement satisfies $\pi(i)\ne i$ for every position. For example, $[2,3,1]$ is a derangement of $[1,2,3]$, while $[2,1,3]$ is not because position $3$ still contains label $3$.

The input $n$ is a nonnegative integer. The output $D(n)$, also called the subfactorial and sometimes written $!n$, counts these permutations. The sequence begins 1, 0, 1, 2, 9, 44, 265, 1854 for $n=0$ through $7$. The empty permutation is the one derangement of zero objects, so $D(0)=1$. One object cannot move anywhere else, so $D(1)=0$.

To derive the recurrence for $n\ge 2$, choose the image $j=\pi(n)$. It must differ from $n$, giving $n-1$ choices. Now inspect the cycle containing $n$.

• If that cycle has length two, then $n$ maps to $j$ and $j$ maps back to $n$. Remove both labels; the remaining permutation is a derangement on $n-2$ labels. This contributes $D(n-2)$ for the chosen $j$.
• If that cycle has length at least three, delete $n$ from the cycle and connect its predecessor directly to $j$. The shortened cycle still has length at least two, so the result is a derangement on $n-1$ labels. Conversely, in any such smaller derangement, inserting $n$ immediately before $j$ uniquely reconstructs the original cycle. This contributes $D(n-1)$ for the chosen $j$.

The cases are disjoint and exhaustive. Adding them and multiplying by the $n-1$ choices of $j$ gives the recurrence. Notice that two-cycles are allowed: exchanging two objects creates no fixed point.

How Derangements Works, Step by Step

For $n=0$, return $1$; for $n=1$, return $0$. Reject negative $n$. For larger inputs, initialize older = 1 and previous = 0, representing $D(0)$ and $D(1)$.

For each size $i$ from $2$ through $n$, compute the new value using the recurrence:

$$D(i)=(i-1)\bigl(D(i-1)+D(i-2)\bigr).$$

Store it in next_value. Only after computing next_value should you shift the stored state: set older to the old previous value, then set previous to next_value. After the last iteration, previous represents $D(n)$.

The order matters because the recurrence needs two values from the preceding state. Overwriting older too early replaces $D(i-2)$ with $D(i-1)$. Computing next_value in a separate variable avoids that mistake and makes the invariant visible.

For example, before computing $D(5)$, the state is $\mathtt{older}=D(3)=2$ and $\mathtt{previous}=D(4)=9$. The sum is $11$, the multiplier is $4$, and next_value is $44$. The new state becomes older = 9 and previous = 44.

The implementations calculate residues modulo $M=1\,000\,000\,007$. They reduce the sum and multiplier before multiplying, then reduce the product. This preserves the recurrence modulo $M$ and keeps C++ multiplication safely bounded. The diagrams use small full counts, so their values coincide with the residues.

flowchart TD
    A["Read n"] --> B{"n negative?"}
    B -->|Yes| X["Reject input"]
    B -->|No| C{"n = 0?"}
    C -->|Yes| O["Return 1"]
    C -->|No| D{"n = 1?"}
    D -->|Yes| Z["Return 0"]
    D -->|No| E["older = 1; previous = 0; i = 2"]
    E --> F{"i at most n?"}
    F -->|No| R["Return previous"]
    F -->|Yes| G["sum = (previous + older) mod M"]
    G --> H["weight = (i - 1) mod M"]
    H --> I["next_value = weight times sum mod M"]
    I --> J["older = previous"]
    J --> K["previous = next_value; i = i + 1"]
    K --> F

Worked Example with a Full Trace

Compute $D(5)$. Begin with the base values $D(0)=1$ and $D(1)=0$, stored as older = 1, previous = 0. There are four recurrence iterations.

1. $i=2$: multiplier $=1$; sum $=0+1=1$; new value $=1\times 1=1$. Shift to older = 0, previous = 1. Therefore $D(2)=1$: the two objects must exchange places.
2. $i=3$: multiplier $=2$; sum $=1+0=1$; new value $=2\times 1=2$. Shift to older = 1, previous = 2. Therefore $D(3)=2$, matching the two permutations in the first diagram.
3. $i=4$: multiplier $=3$; sum $=2+1=3$; new value $=3\times 3=9$. Shift to older = 2, previous = 9. Therefore $D(4)=9$.
4. $i=5$: multiplier $=4$; sum $=9+2=11$; new value $=4\times 11=44$. Shift to older = 9, previous = 44. Return $44$.

An independent Inclusion–Exclusion check starts from all $5!=120$ permutations. Subtract permutations fixing one specified position, add those fixing two specified positions, and continue alternating. This gives $D(5)=120-120+60-20+5-1=44$. Each term chooses which positions are fixed and freely permutes the others.

For $D(4)$, the cycle description gives another check. A derangement on four labels has either one cycle of length four or two cycles of length two. There are $3!=6$ four-cycles and three ways to pair the labels into two two-cycles, totaling $6+3=9$. A restriction to a single cycle would count only six and would not be the derangement problem.

Implementation in Python, C++, and Java

Each panel is a complete standalone program with the same function logic and sample queries. The returned value is $D(n)\bmod M$, where $M=1\,000\,000\,007$. It is the full count only when $D(n)\lt M$. All displayed values through $D(10)$ are full counts; the $D(20)$ line is a remainder.

Python uses arbitrary-precision integers. C++ uses long long and reduces both the sum and multiplier before multiplication, so each factor is below $M$. The largest possible product is $(M-1)^2=1\,000\,000\,012\,000\,000\,036$, safely within signed 64-bit range. Java uses BigInteger arithmetic and explicit remainders. Changing the modulus requires reconsidering the C++ multiplication bound.

All versions reject negative $n$ and return the two base cases directly. C++ and Java use a signed 32-bit $n$, while their loop counters use a wider type. The algorithms store only the two prior residues and a few temporary values; they do not allocate an array proportional to $n$.

MOD = 1_000_000_007


def derangements_mod(n: int) -> int:
    if n < 0:
        raise ValueError("n must be nonnegative")
    if n == 0:
        return 1
    if n == 1:
        return 0
    older = 1
    previous = 0
    for size in range(2, n + 1):
        total = (previous + older) % MOD
        weight = (size - 1) % MOD
        next_value = (weight * total) % MOD
        older = previous
        previous = next_value
    return previous


def main() -> None:
    samples = [0, 1, 2, 3, 4, 5, 6, 10, 20]
    print(f"modulus = {MOD}")
    for n in samples:
        print(f"D({n}) = {derangements_mod(n)}")


if __name__ == "__main__":
    main()

#include <iostream>
#include <stdexcept>
#include <vector>

constexpr long long MOD = 1'000'000'007LL;

long long derangements_mod(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be nonnegative");
    }
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 0;
    }
    long long older = 1;
    long long previous = 0;
    for (long long size = 2; size <= n; ++size) {
        const long long total = (previous + older) % MOD;
        const long long weight = (size - 1) % MOD;
        const long long next_value = (weight * total) % MOD;
        older = previous;
        previous = next_value;
    }
    return previous;
}

int main() {
    const std::vector<int> samples = {0, 1, 2, 3, 4, 5, 6, 10, 20};
    std::cout << "modulus = " << MOD << '\n';
    for (int n : samples) {
        std::cout << "D(" << n << ") = " << derangements_mod(n) << '\n';
    }
}

import java.math.BigInteger;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger derangementsMod(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be nonnegative");
        }
        if (n == 0) {
            return BigInteger.ONE;
        }
        if (n == 1) {
            return BigInteger.ZERO;
        }
        BigInteger older = BigInteger.ONE;
        BigInteger previous = BigInteger.ZERO;
        for (long size = 2; size <= n; ++size) {
            BigInteger total = previous.add(older).mod(MOD);
            BigInteger weight = BigInteger.valueOf(size - 1).mod(MOD);
            BigInteger nextValue = weight.multiply(total).mod(MOD);
            older = previous;
            previous = nextValue;
        }
        return previous;
    }

    public static void main(String[] args) {
        int[] samples = {0, 1, 2, 3, 4, 5, 6, 10, 20};
        System.out.println("modulus = " + MOD);
        for (int n : samples) {
            System.out.println("D(" + n + ") = " + derangementsMod(n));
        }
    }
}

Run Python as a script, compile C++ with C++14 or later, and save Java as Main.java before running javac Main.java and java Main. Each program prints the following ten lines:

• modulus = 1000000007
• D(0) = 1
• D(1) = 0
• D(2) = 1
• D(3) = 2
• D(4) = 9
• D(5) = 44
• D(6) = 265
• D(10) = 1334961
• D(20) = 927799753

The full value is $D(20)=895\,014\,631\,192\,902\,121$. Reducing it modulo $1\,000\,000\,007$ gives $927\,799\,753$. To obtain unrestricted full counts in Python or Java, remove the reductions on the sum, multiplier, and product while retaining arbitrary-precision integers. C++ needs arbitrary-precision arithmetic or a proof that every intermediate operation fits; keeping only the final answer within range is not sufficient.

Complexity, Correctness, and Invariants

For $n\ge 2$, the loop performs exactly $n-1$ iterations. Each iteration uses a constant number of additions, reductions, multiplications, and assignments. Therefore the fixed-modulus implementation takes $\Theta(n)$ time and $O(1)$ auxiliary storage. The $n=0$ and $n=1$ cases take $\Theta(1)$ time and storage, and negative inputs are rejected immediately.

For a fixed $n$, best, average, and worst cases have identical iteration counts. There is no input-dependent branching inside the recurrence loop. The constant-storage statement counts bounded residues and a constant number of counters, in the usual word-RAM model. If $n$ itself is treated as an arbitrary-size integer, its counter also has a bit cost; if full derangement counts are stored, the counts' growing bit lengths must be included as well.

To prove correctness, use the cycle decomposition established earlier. After choosing $j=\pi(n)$, exactly $D(n-2)$ completions use the two-cycle $(n\ j)$, and exactly $D(n-1)$ completions use a longer cycle. There are $n-1$ choices of $j$, yielding the recurrence. The deletion and insertion operations are inverses, so no valid permutation is missed or counted twice.

The loop invariant states that, before iteration $i$, the stored values satisfy

$$\mathtt{older}\equiv D(i-2)\pmod M,\qquad \mathtt{previous}\equiv D(i-1)\pmod M.$$

The invariant holds initially for $i=2$ by the two base cases. The recurrence computes $\mathtt{next\_value}\equiv D(i)\pmod M$. Shifting the pair to the old previous and next_value establishes the invariant for $i+1$. After iteration $n$, previous is the nonnegative residue $D(n)\bmod M$, so returning it is correct.

For the Inclusion–Exclusion formula, choose $k$ fixed positions and freely permute the others:

$$D(n)=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)!=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.$$

Each unsimplified term counts actual permutations; the alternating sum removes every permutation with at least one fixed point. Factorial quotients are exact integers, but modular remainders cannot be divided as ordinary integers. Here $\varphi=(1+\sqrt{5})/2$ is the growth factor used for the plain-recursion call count in the table.

Variants, Pitfalls, and Optimizations

Keep the empty case and singleton case distinct. $D(0)=1$ supplies the valid empty remainder when a two-cycle is removed from two objects. $D(1)=0$ expresses impossibility. Setting both base cases to one gives the wrong counts immediately.

Avoid fixed points, not all short cycles. A derangement forbids cycles of length one but permits cycles of length two. The permutation $[2,1,4,3]$ is valid. Requiring one long cycle is a stronger condition and gives $(n-1)!$ arrangements for $n\ge 2$, rather than $D(n)$. Additional forbidden recipients, pairs, or positions generally require an assignment-counting method instead of this scalar recurrence.

Update the stored state safely. A temporary next_value must be computed from the old older and previous values. Afterward, copy the old previous into older, then copy next_value into previous. A simultaneous tuple assignment is another option in Python, but the explicit three-step form keeps the logic identical across languages.

Use alternative formulas carefully. Another recurrence is

$$D(n)=nD(n-1)+(-1)^n\qquad(n\ge 1),\qquad D(0)=1.$$

It also gives linear-time computation and needs only one previous count, but modular subtraction must be normalized. The two-predecessor recurrence used here follows directly from the cycle proof and avoids an alternating sign.

For $n\ge 1$, $D(n)$ is the nearest integer to $n!/e$, and $D(n)/n!\to 1/e$ as $n\to\infty$. These facts explain the scale of the answer; evaluating a floating-point factorial divided by an approximate $e$ is not a reliable way to compute unrestricted exact counts. The $n=0$ case must still be handled separately.

Count a specified number of fixed points. Exactly $r$ fixed points among $n$ labels can be chosen in $\binom{n}{r}$ ways, after which the remaining labels must be deranged. The count is

$$\binom{n}{r}D(n-r),\qquad 0\le r\le n.$$

For $n=4$, counts for $r=0,1,2,3,4$ are $9,8,6,0,1$, which sum to $24$. Exactly $n-1$ fixed points are impossible, because the last remaining label would also be fixed.

Separate counting from sampling. For $n\ge 2$, generating a uniformly random permutation and rejecting it if it has a fixed point produces a uniform random derangement when accepted. The acceptance probability is $D(n)/n!$, so the expected number of trials approaches $e$. A generator that always produces one cycle also produces derangements, but samples only a subset of them when $n\ge 4$. For $n=1$ no derangement exists, so rejection sampling would never finish. Counting modulo $M$ does not by itself provide a sampler or an ordinary probability.

Practice Problems and Real-World Use

Start by identifying the original matching between positions and labels. Check that the new assignment is a permutation and that the only restriction is avoiding each original pair. If labels repeat, assignments are not one-to-one, or additional pairs are forbidden, the ordinary derangement formula may no longer count the desired objects.

For tiny inputs, enumerate every permutation and count it only if all positions differ from their original labels. This simple independent check makes the definition concrete and catches base-case mistakes, an incorrect multiplier, or accidentally counting only single-cycle permutations.

The probability row assumes every permutation is equally likely. Use full counts or suitable probability arithmetic; residues modulo $M$ cannot replace the numerator and denominator of that ordinary probability.

The gift example assumes that two participants may give to each other and that no additional household or recipient restrictions exist. If those rules change, build the allowed-pair graph and count its perfect matchings. A subset DP can handle a general $n\times n$ allowed-pair matrix in $O(n2^n)$ time and $O(2^n)$ storage, but that is a different algorithm from the two-value recurrence.

Before finishing, verify $D(0)=1$, $D(1)=0$, $D(2)=1$, the two derangements for $n=3$, and $D(4)=9$ including its three two-cycle pairings. Cross-check the recurrence with the exact Inclusion–Exclusion formula and the identity $\sum_{r=0}^{n}\binom{n}{r}D(n-r)=n!$. Include a large enough input for modular reduction to change the output, so both the combinatorial model and the arithmetic are tested.