AlgoVerse

Derangements

Count the permutations where no item stays in its place; their share of all permutations approaches 1/e.

A derangement is a permutation where no item stays in its place (the classic problem: letters in the wrong envelopes).

Read the full explanation ↓
Input:
n=8PDF export

8 letters put in 8 envelopes at random; in D(8) = 14833 ways no letter is in its own envelope, about 36.8%.

  1. def derangements(n):
  2. # D(k) = (k − 1)·(D(k − 1) + D(k − 2)), with D(0) = 1 and D(1) = 0.
  3. d = [1, 0] + [0] * max(0, n - 1)
  4. fact = 1
  5. rows = [(0, 1, 1, 1.0)]
  6. for k in range(1, n + 1):
  7. fact = fact * k
  8. if k >= 2:
  9. d[k] = (k - 1) * (d[k - 1] + d[k - 2])
  10. rows.append((k, d[k], fact, round(d[k] / fact, 4)))
  11. return d[n]

Invariant: D[k] is the number of permutations of k items with no item in its own place.

Start

k—
fact—

The table is still empty.

Local variables

n8

Orange = changed in this step

Call stack

  1. derangements()line 1
Step 1 of 45
Black = derange · Orange = key stepderange: 0/8
    Explanation

    The idea

    A derangement is a permutation where no item stays in its place (the classic problem: letters in the wrong envelopes).

    Take item 1; it goes to one of the other k − 1 places, say place j. Now:

    • if j goes to place 1, the remaining k − 2 items are deranged: D(k − 2) ways;
    • if it does not, it is as if j must avoid its "forbidden place" (1): D(k − 1) ways.
    D(k) = (k − 1) · (D(k − 1) + D(k − 2)),   D(0) = 1,   D(1) = 0

    A nice fact

    By inclusion–exclusion, D(n) = n! · (1 − 1/1! + 1/2! − … ± 1/n!); so the share D(n)/n! reaches 1/e ≈ 0.3679 very fast. The last column of the table shows it.