Given an array with integer 0 to N, how many ways to arrange it such that array[i] cannot be i

Question

Given an array with integer 0 to N, how many ways to arrange it such that at position i of the array, we cannot have i inserted in it?

For example, N = 2

The following arrangements is valid:

• 1,2,0
• 2,0,1

Thus, the answer is 2 arrangements

I can't think of a non-brute force method to do this in O(1) time, can anyone help me out?

Answer 1

Such kind of permutations is called derangement. Wiki page contains a lot of formulas to count them. For example, recurrence:

!n=(n-1)(!(n-1)+!(n-2))

where !n, known as the subfactorial, represents the number of derangements, with the starting values !0 = 1 and !1 = 0