Derangement count

Count permutations where no element stays in its original position.

dynamic-programming combinatorics recursion math

A derangement is a permutation of n elements where no element appears in its original position. For example, for n = 3, the only derangements are [2, 3, 1] and [3, 1, 2], so the count is 2.

Write a function `derangement_count(n)` that returns the number of derangements of n distinct items.

The count follows the recurrence:
- D(0) = 1 (empty permutation is considered a derangement)
- D(1) = 0
- For n >= 2: D(n) = (n - 1) * (D(n-1) + D(n-2))

Your function should handle n up to 1000 efficiently and return the result as an integer (Python's arbitrary-precision integers are fine).

Constraints

0 <= n <= 1000. Time complexity must be O(n) or better. Recursion depth is limited, so use an iterative approach.

Example

>>> derangement_count(0)
1
>>> derangement_count(1)
0
>>> derangement_count(3)
2
>>> derangement_count(4)
9

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use the given recurrence and compute iteratively from 0 up to n.

Keep only the last two values: D(n-1) and D(n-2) to compute D(n).

Remember D(0)=1 and D(1)=0 as base cases.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.