329. Count Derangements

A derangement of n distinct items is a permutation in which no item ends up in its original position. Given n, count the number of distinct derangements.

Input: A single line contains the integer n. Output: Print a single integer - the number of derangements of n items.

0 <= n <= 20

Derangements are also called 'permutations with no fixed points' in combinatorics - recognizing this connects the problem to the broader mathematical concept of the subfactorial (denoted !n), useful context if the problem is phrased differently elsewhere.

Count the number of permutations of n items where no item ends up in its original position. Brute force: Generate all n! permutations directly and check each for the no-fixed-point property - this is factorial time, impractical beyond very small n. Optimised: The recurrence D(n)=(n-1)*(D(n-1)+D(n-2)) captures a clean combinatorial argument (fixing item 1's new position, then splitting on whether a specific 'swap-back' happens) that avoids ever generating actual permutations - building this bottom-up computes D(n) in linear time.

Compute D(0) = 1 and D(1) = 0 directly, then iterate k from 2 up to n applying D(k) = (k-1) * (D(k-1) + D(k-2)), keeping only the two most recently computed values in ordinary variables rather than a full array of all D(0..n). Since each new value only ever depends on the two immediately preceding ones, there is no need to retain the whole history the way the memoized version does, dropping the auxiliary space from linear down to constant while keeping the same linear time. Time: O(n) Space: O(1)

Use the recurrence D(n) = (n-1) * (D(n-1) + D(n-2)), which comes from considering where item n goes: it must go to one of the other n-1 positions, and depending on whether that displaced item's own original slot is filled or not, the rest of the arrangement reduces to a derangement of n-2 or n-1 items. Compute D(n) recursively and cache each D(k) the first time it is computed, so that the recursion evaluates each of the n distinct subproblems only once instead of re-deriving them from scratch or falling back to permutation enumeration. Time: O(n) Space: O(n)

Generate every permutation of the n items via backtracking and, for each one, check whether any item ended up in its original position; count the permutation as a derangement only if none did. This directly implements the definition of a derangement, but generating and checking all n! permutations is extremely wasteful for something that has a much simpler closed recursive structure. Time: O(n! * n) Space: O(n)

1. D(0)=1 and D(1)=0 as base cases. 2. D(n) = (n-1) * (D(n-1) + D(n-2)) - fix where the FIRST item goes (n-1 possible other positions), then consider whether the DISPLACED item's original slot gets item 1 back in a swap-like way (D(n-2)) or not (D(n-1)). 3. Build the DP bottom-up in a 1D array from D(0) and D(1).

Time: O(n) - building the sequence bottom-up from D(0) and D(1). Space: O(1) if only the previous two values are kept, or O(n) if the full sequence is stored.

Test n = 0 (D(0) = 1) and n = 1 (D(1) = 0), plus n = 20 (upper bound) for the growing count.

Be ready to explain the combinatorial derivation behind the recurrence briefly (fixing where item 1 goes, then considering the two sub-cases for what happens to the displaced item's slot) - this shows genuine understanding rather than just reciting a memorized formula.