Count derangements

Challenge

Implement:

long long count_derangements(int n);

Return the number of derangements of n items (permutations with no element in its original position). D(0)=1, D(1)=0. 0 <= n <= 20.

Input format

n in [0,20].

Output format

D(n).

Constraints

Two base cases and a two-term recurrence.

Starter code

#include <stddef.h>
/* Number of derangements of n items (permutations with no fixed point). D(0)=1, D(1)=0. 0<=n<=20. */
long long count_derangements(int n){ (void)n; return 0; }

Common mistakes

Only one base case (you need both D(0) and D(1)).

Edge cases to handle

D(2)=1, D(3)=2, D(4)=9.

Background lessons

• Permutations & derangements