Derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, derangement is a permutation that has no fixed points.
The number of derangements of a set of size n, usually written Dn, dn, or !n, is called the "derangement number" or "de Montmort number". (These numbers are generalized to rencontres numbers.) The subfactorial function (not to be confused with the factorial n!) maps n to !n. No standard notation for subfactorials is agreed upon; n¡ is sometimes used instead of !n.
The problem of counting derangements was first considered by Pierre Raymond de Montmort in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time.
Suppose that a professor has had 4 of his students – A, B, C, and D – take a test and wants to let his students grade each other's tests. Of course, no student should grade his or her own test. How many ways could the professor hand the tests back to the students for grading, such that no student received his or her own test back? Out of (4!) for handing back the tests:
there are only 9 derangements (shown in blue italics above). In every other permutation of this 4-member set, at least one student gets his or her own test back (shown in bold red).
Another version of the problem arises when we ask for the number of ways n letters, each addressed to a different person, can be placed in n pre-addressed envelopes so that no letter appears in the correctly addressed envelope.
Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:
From this, the following relation is derived:
where !n, known as the subfactorial, represents the number of derangements, with the starting values !0 = 1 and !1 = 0.
...
Wikipedia