What is the Formula for Derangement?

Derangement is a concept in combinatorial mathematics that deals with the arrangement of objects in such a way that no object appears in its original position. In other words, it is a permutation without fixed points. The formula for derangement, also known as the subfactorial or the derangement number, gives the number of such arrangements.

Formula for Derangement (n!)

The formula for derangement is given by:

!n = n! * (1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)

where:
- n represents the total number of objects to be arranged.

Explanation:

The formula for derangement is derived using the principle of inclusion-exclusion. It involves subtracting the number of arrangements with at least one fixed point from the total number of possible arrangements.

1. n!: The total number of possible arrangements of n objects is given by n!.

2. (1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!): This term represents the number of arrangements with at least one fixed point.

- The term 1/0! represents the number of arrangements with exactly 0 fixed points, which is 1.
- The term 1/1! represents the number of arrangements with exactly 1 fixed point, which is n!/1.
- The term 1/2! represents the number of arrangements with exactly 2 fixed points, which is n!/(2!).
- The term 1/3! represents the number of arrangements with exactly 3 fixed points, which is n!/(3!), and so on.
- The term (-1)^n/n! alternates between positive and negative values, representing the principle of inclusion-exclusion.

By subtracting the number of arrangements with at least one fixed point from the total number of possible arrangements, we obtain the number of derangements.

Example:

Let's consider an example with n = 4.

Total number of possible arrangements (n!) = 4! = 24

Number of arrangements with at least one fixed point = 4! * (1/0! - 1/1! + 1/2! - 1/3! + 1/4!) = 15

Number of derangements = Total number of possible arrangements - Number of arrangements with at least one fixed point = 24 - 15 = 9

Therefore, there are 9 derangements for the given example.

In conclusion, the formula for derangement (n!) gives the number of arrangements in which no object appears in its original position. It is derived using the principle of inclusion-exclusion and involves subtracting the number of arrangements with at least one fixed point from the total number of possible arrangements.