Medium Problemscountingcombinatoricslinear

Count Derangements

Given n distinct objects, each with one designated original position, count the permutations in which no object ends up back in its own original position.

Do this lesson first: climbing stairs

Example input

n = 6

Expected output

265

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = (i - 1) × (dp[i - 1] + dp[i - 2])

Ask what happens to the object that ends up in position 1: it cannot be object 1 itself, so there are i-1 choices for it. Say object k lands there. Now ask what object k's own position does: either object 1 moves into it, closing a 2-cycle and leaving a derangement of the remaining i-2 objects (dp[i-2] ways), or object 1 goes anywhere else that is not its own spot, which is exactly a derangement of the remaining i-1 objects with object k's slot relabeled as object 1's (dp[i-1] ways). Both cases are multiplied by the same i-1 choices for the first step, so they factor out as one multiplication over a sum.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1 and dp[1] = 0 are given directly: an empty arrangement is vacuously deranged, and the one permutation of a single object necessarily fixes it, so zero derangements exist. Every other cell, including dp[2], depends only on smaller indices and falls out of the very same transition (see the pitfall); filling left to right guarantees both dependencies exist before they are read.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

1

0

1

2

9

44

265

count-derangements.ts

1function countDerangements(n) {
2 const dp = [1, 0];
3 for (let i = 2; i <= n; i++) {
4 dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
5 }
6 return dp[n];
7}

Base caseComputedBeing readAnswer

The code, the trap, the variations

count-derangements.ts

1function countDerangements(n) {
2 const dp = [1, 0];
3 for (let i = 2; i <= n; i++) {
4 dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
5 }
6 return dp[n];
7}

Where people go wrong

Assuming dp[1] = 0 means the recurrence has broken, or that dp[2] needs a hand-written special case the way painting-fence's dp[2] does. Neither is true here: dp[1] = 0 is the honest count of derangements of one object (none exist, since the lone object has nowhere else to go), and feeding dp[0] = 1 and dp[1] = 0 through that very same transition at i = 2 already produces the correct dp[2] = 1. No third base case is needed once the two seeds are right.

Return the count modulo 1e9+7 instead of the exact value.
The recurrence does not change at all; only the combine step gains a modulo, which matters here more than most, since dp[i] grows roughly as fast as i! itself.
Count permutations with at least one fixed point instead of none.
That is the complement of this whole table: n! minus dp[n]. The one-dimensional dp[i] table for derangements is untouched; only what happens to dp[n] at the very end changes.

All distinct subset (or subsequence) sums Minimum insertions for palindrome