# Counting derangements

#### Algorithms List of Mathematical Algorithms

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.