Counting derangements
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Given any integer N, we need to find out the number of Derangements for a set of N elements.
For this, we need to first understand what is a derangement.
 Derangement: A derangement is a permutation of N elements, such that no element occurs in its original position.
For example, if N = 4, and the elements are {0, 1, 2, 3} , then {1, 0, 3, 2} , {2, 3, 0, 1} , {3, 2, 0, 1} ... are some derangements, where the elements do not occur in their original position. So, 0 should not be present in the 0th position, 1 should not be present in the 1st position, and so on...
For example :
 If N = 1, then number of derangements will be 0 as the position of that element can't be changed.
Der(1) = 0
 If N = 2, then number of derangements will be 1 as the 2 elements can be interchanged only once.
For example, if the elements are {0, 1} , then the only possible derangement is {1, 0}.
Der(2) = 1
 If N = 3, let's say {0, 1, 2}
Then the possible derangements would be {1, 2, 0} , {2, 0, 1}. Hence, there are 2 derangements.
Der(3) = 2
But how do we calculate the number of derangements for larger values of N ?
 Let's take N = 4 and the elements to be {0, 1, 2, 3}.
In any derangement, we can't place 0 in the 0th position as it is its original position. However, we can place 1, 2 or 3 in the 0th position. So, for N elements , there can N1 elements that can be placed in the starting position.
In each of these N1 possibilities, there are 2 categories of derangements 

If we swap the starting element (here, 0) with any other element (1,2 or 3) , we would need to find the number of derangements for the remaining N2 elements.
In our example, if we swap 0 and 1, we will get one derangement  {1, 0, 3, 2}. Here, Der(N2) = Der(2) = 1. 
When the elements are not swapped, we need to find the number of derangements for remaining N1 elements 
For example, If we place 1 in the starting position, we will need to find derangements of {0, 3, 2} (As we have already considered {1, 0, 3, 2} ). There will be 2 such derangements  {1, 3, 0, 2} and {1, 2, 3, 0}. Here, Der(N1) = D(3) = 2.
These two categories will be repeated when 2 and 3 will be in the starting position.
Therefore, the total number of derangements will be 
(N1) * [Der(N2) + Der(N1)]
Hence, Der(4) = 3 * (2 + 1) = 9
Der(N) = (N1) * [Der(N2) + Der(N1)]
> Recursive Approach 
We can solve this using a recursive function Der(N), as we need to calculate Der(N1) and Der(N2) recursively.
Code 
// A Naive Recursive C++ program
// to count derangements
#include <bits/stdc++.h>
using namespace std;
int Der(int N)
{
// Base cases
if (N == 1) return 0;
if (N == 2) return 1;
// Der(N) = (N1)[Der(N1) + Der(N2)]
return (N  1) * (Der(N  1) + Der(N  2));
}
// Driver Code
int main()
{
int N = 5;
cout << "Number of Derangements : "
<< Der(N);
return 0;
}
Output 
Number of Derangements : 44
Complexity 
 Time Complexity: T(n) = T(n1) + T(n2) which is exponential
 Space Complexity: O(1)
> DP Approach 
We can solve this problem more efficiently by storing the results of Der(N1) and Der(N2) in an array for future use.
Code 
// A Dynamic programming based C++
// program to count derangements
#include <bits/stdc++.h>
using namespace std;
int Der(int N)
{
// Create an array to store
// counts for subproblems
int der[N + 1] = {0};
// Base cases
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up manner
// using above recursive formula
for (int i = 3; i <= N; ++i)
der[i] = (i  1) * (der[i  1] +
der[i  2]);
// Return result for n
return der[N];
}
// Driver code
int main()
{
int N = 5;
cout << "Number of Derangements : "
<< Der(N);
return 0;
}
Output 
Number of Derangements : 44
Complexity 
 Time Complexity: O(n)
 Space Complexity: O(n)
Efficient Approach 
Without using the extra space, we can find the count of derangements as we only need the previous two values i.e. they can be overwritten. Hence, we will use 2 variables to store these values instead of an array.
Code 
// C++ implementation
#include <iostream>
using namespace std;
int Der(int N)
{
// base case
if (N == 1 or N == 2) {
return N  1;
}
// Variable for just storing
// previous values
int a = 0;
int b = 1;
// using above recursive formula
for (int i = 3; i <= N; ++i) {
int cur = (i  1) * (a + b);
a = b;
b = cur;
}
// Return result for n
return b;
}
// Driver Code
int main()
{
int N = 5;
cout << "Number of Derangements : "
<< Der(N);
return 0;
}
Output 
Number of Derangements : 44
Complexity 
 Time Complexity: O(n)
 Space Complexity: O(1)
Conclusion 
Hence, we looked at 3 different approaches to find the number of Derangememts for any set of N elements.