Counting Derangements of an array of numbers(recursive)

Question

I came across this problem among interview questions.

Given an array of numbers, we have to calculate the total number of derangements that are possible for this array. Derangements of an array are those permuations where no element is in the original place. There is no restriction on the kind of numbers in the array. There could also be dupliates.

I know a solution using the inclusion-exclusion principle. I was looking for a recursive formulation, using DP. This approach probably uses memoization and bitmasks. Thanks.

Answer 1

Derangement from Wikipedia

Where !n is the number of derangements, assuming no duplicates though.