Count number of derangements

Given a number n, find number of derangements in a set of n elements. A Derangement is a permutation with no element appears in its original position. For example, a derangement of [0, 1, 2] is [2, 0, 1].

Hint

Choose any item from its initial position 'i'. This item can be placed in any of the remaining 'n-1' positions. There are two possible scenarios:

Scenario 1: The item is placed in the position 'i' (where another item originally resided). This effectively removes two items from consideration, leaving 'n-2' items to be arranged.
Scenario 2: The item is placed in any other position besides 'i'. This leaves 'n-1' items to be arranged.

Since there are 'n-1' possible positions for the selected item, the total number of arrangements is calculated as follows: (n - 1) * (number of arrangements of n-1 items + number of arrangements of n-2 items).

Python
Javascript

# Python implementation

def placement(n):
  if n == 1:
    return 0

  if n == 2:
    return 1

  return (n - 1) * (placement(n - 1) + placement(n - 2))

n = 4

print(placement(n))

// Javascript implementation

function placement(n) {
  if (n == 1) {
    return 0;
  }

  if (n == 2) {
    return 1;
  }

  return (n - 1) * (placement(n - 1) + placement(n - 2));
}

const n = 4;

console.log(placement(n));