Counting derangements

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 N-1 elements that can be placed in the starting position.

In each of these N-1 possibilities, there are 2 categories of derangements -

1. 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 N-2 elements.
   In our example, if we swap 0 and 1, we will get one derangement - {1, 0, 3, 2}. Here, Der(N-2) = Der(2) = 1.

2. When the elements are not swapped, we need to find the number of derangements for remaining N-1 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(N-1) = 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 -
(N-1) * [Der(N-2) + Der(N-1)]
Hence, Der(4) = 3 * (2 + 1) = 9

Der(N) = (N-1) * [Der(N-2) + Der(N-1)]

-> Recursive Approach -

We can solve this using a recursive function Der(N), as we need to calculate Der(N-1) and Der(N-2) 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) = (N-1)[Der(N-1) + Der(N-2)]
  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(n-1) + T(n-2) which is exponential
• Space Complexity: O(1)

-> DP Approach -

We can solve this problem more efficiently by storing the results of Der(N-1) and Der(N-2) 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.