Derangement Count

Problem

Count the permutations of n items with no fixed point (derangements).

Use the recurrence D(0) = 1, D(1) = 0 and D(n) = (n - 1) * (D(n - 1) + D(n - 2)). Return 0 for negative n.

Hint

Start from the two base cases and build up; the counts grow fast.

case 1

in: [0]

expected: 1

case 2

in: [1]

expected: 0

case 3

in: [4]

expected: 9

case 4

in: [5]

expected: 44

case 5

in: [10]

expected: 1334961

Starter codePython

def derangement_count(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor