Derangement
Encyclopedia
In combinatorial
mathematics
, a derangement is a permutation
of the elements of a set such that none of the elements appear in their original position.
The numbers of derangements !n for sets of size n are called "de Montmort numbers" or "derangement numbers" (and can be 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, and 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.
In every other permutation of this 4-member set, at least one student gets the right test.
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.
From this, the following relation is derived:
Notice that this same recurrence formula also works for factorials with different starting values. That is 0! = 1, 1! = 1 and
which is helpful in proving the limit relationship with e below.
Also, the following formulas are known:
where
is the floor function
. Starting with n = 0, the numbers of derangements of n are:
These numbers are also called subfactorial or rencontres numbers.
Perhaps a more well-known method of counting derangements uses the inclusion-exclusion principle.
This is the limit of the probability
pn = dn/n! that a randomly selected permutation is a derangement. The probability approaches this limit quite quickly.
More information about this calculation and the above limit may be found on the page on the
statistics of random permutations.
Derangements are an example of the wider field of constrained permutations. For example, the ménage problem
asks if n married couples are seated boy-girl-boy-girl-... around a circular table, how many ways can they be seated so that no man is seated next to his wife?
More formally, given sets A and S, and some sets U and V of surjections A → S, we often wish to know the number of pairs of functions (f, g) such that f is in U and g is in V, and for all a in A, f(a) ≠ g(a); in other words, where for each f and g, there exists a derangement φ of S such that f(a) = φ(g(a)).
Another generalization is the following problem:
For instance, for a word made of only two different letters, say n letters A and m letters B, the answer is, of course, 1 or 0 according whether n = m or not, for the only way to form an anagram without fixed letters is to exchange all the A with B, which is possible if and only if n = m. In the general case, for a word with n1 letters X1, n2 letters X2, ..., nr letters Xr it turns out (after a proper use of the inclusion-exclusion formula) that the answer has the form:
for a certain sequence of polynomials Pn, where Pn has degree n. But the above answer for the case r = 2 gives an orthogonality relation, whence the Pn' s are the Laguerre polynomials
(up to
a sign that is easily decided).
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a derangement is a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of the elements of a set such that none of the elements appear in their original position.
The numbers of derangements !n for sets of size n are called "de Montmort numbers" or "derangement numbers" (and can be generalized to rencontres numbers); the subfactorial function (not to be confused with the factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
n!) maps n to !n. No standard notation for subfactorials is agreed upon, and n¡ is sometimes used instead of !n.
The problem of counting derangements was first considered by Pierre Raymond de Montmort
Pierre Raymond de Montmort
Pierre Rémond de Montmort, a French mathematician, was born in Paris on 27 October 1678, and died there on 7 October 1719. His name was originally just Pierre Rémond or Raymond...
in 1708; he solved it in 1713, as did Nicholas Bernoulli
Nicolaus I Bernoulli
Nicolaus Bernoulli , was a Swiss mathematician and was one of the many prominent mathematicians in the Bernoulli family....
at about the same time.
Example
Suppose that a professor has graded 4 tests for 4 students -- student A, student B, student C, and student D. However, the professor mixed up the tests when handing them back, and now none of the students has the correct test. How many ways could the professor have mixed them all up in this way? Out of 24 possible permutations for handing back the tests, there are only 9 derangements:- BADC, BCDA, BDAC,
- CADB, CDAB, CDBA,
- DABC, DCAB, DCBA.
In every other permutation of this 4-member set, at least one student gets the right test.
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.
Counting derangements
Suppose that there are n persons 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 his/her number. Let us assume that first person takes the hat i. There are n − 1 ways for the first person to choose the number i. Now there are 2 options:- Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (is forbidden choice is hat 1).
- Person i takes the hat of 1. Now the problem reduces to n − 2 persons and n − 2 hats.
From this, the following relation is derived:
Notice that this same recurrence formula also works for factorials with different starting values. That is 0! = 1, 1! = 1 and
which is helpful in proving the limit relationship with e below.
Also, the following formulas are known:
where
is the floor functionFloor function
In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
. Starting with n = 0, the numbers of derangements of n are:
- 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... .
These numbers are also called subfactorial or rencontres numbers.
Perhaps a more well-known method of counting derangements uses the inclusion-exclusion principle.
Limit as n approaches ∞
Using this recurrence, it can be shown that, in the limit,This is the limit of the probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
pn = dn/n! that a randomly selected permutation is a derangement. The probability approaches this limit quite quickly.
More information about this calculation and the above limit may be found on the page on the
statistics of random permutations.
Generalizations
The problème des rencontres asks how many permutations of a size-n set have exactly k fixed points.Derangements are an example of the wider field of constrained permutations. For example, the ménage problem
Ménage problem
In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of heterosexual couples at a dining table so that men and women alternate and nobody sits next to his or her partner...
asks if n married couples are seated boy-girl-boy-girl-... around a circular table, how many ways can they be seated so that no man is seated next to his wife?
More formally, given sets A and S, and some sets U and V of surjections A → S, we often wish to know the number of pairs of functions (f, g) such that f is in U and g is in V, and for all a in A, f(a) ≠ g(a); in other words, where for each f and g, there exists a derangement φ of S such that f(a) = φ(g(a)).
Another generalization is the following problem:
- How many anagrams with no fixed letters of a given word are there?
For instance, for a word made of only two different letters, say n letters A and m letters B, the answer is, of course, 1 or 0 according whether n = m or not, for the only way to form an anagram without fixed letters is to exchange all the A with B, which is possible if and only if n = m. In the general case, for a word with n1 letters X1, n2 letters X2, ..., nr letters Xr it turns out (after a proper use of the inclusion-exclusion formula) that the answer has the form:
for a certain sequence of polynomials Pn, where Pn has degree n. But the above answer for the case r = 2 gives an orthogonality relation, whence the Pn
Laguerre polynomials
In mathematics, the Laguerre polynomials, named after Edmond Laguerre ,are the canonical solutions of Laguerre's equation:x\,y + \,y' + n\,y = 0\,which is a second-order linear differential equation....
(up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
a sign that is easily decided).