Counting derangements

Binary Tree Problems books

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 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.