Fixed point free permutation
A fixed pointfree permutation or derangement (from French déranger “to mess up”) is in combinatorics a permutation of the elements of a set, so that no element retains its starting position. The number of possible fixedpointfree permutations of a set with elements is given by the subfaculty . For growing of permutations of aims within the set elements, the share of fixedpoint free permutations quickly against the reciprocal of the Euler's number . If some of the elements in a permutation are to remain in their old place, one speaks of a partial derangement , the number of which can be determined using the Rencontres numbers .
Initial problem

The French mathematician Pierre Rémond de Montmort introduced a game called Treize (“Thirteen”) in his book Essai d'analyse sur les jeux de hazard at the beginning of the 18th century , which can be described in simplified form as follows:
A player shuffles a set of 13 playing cards of one color and puts it in front of him as a pile. Now he reveals the cards in turn, calling each card in the order Ace, Two, Three to King. If at any point the called card matches the revealed card, he wins the game; if this does not apply to any of the 13 cards, he loses.
Now de Montmort asks the question of the probability that the player will win the game. In the first edition of his book from 1708 de Montmort gives the correct result, but without a more precise derivation. In the second edition of 1713 he then presents two proofs, one of his own, which is based on a recursive representation , and another from an exchange of letters with Nikolaus I Bernoulli , which is based on the inclusionexclusion principle . De Montmort also shows that the probability of winning is very close to the value of . Presumably this represents the first use of the exponential function in probability theory.
Without knowing the preliminary work, Leonhard Euler analyzed a related game of chance called Rencontre ("return") in 1753 , which proceeds as follows:
Two players each have a full deck of 52 cards. You shuffle your cards and place them in a pile in front of you. Now both players draw the top card from their pile at the same time. If at any time the same card appears twice, one player wins, otherwise the other.
Again the question of the probability of winning arises. Euler derives the solution with the help of further recurrence formulas, whereby he can assume that only one of the players shuffles his cards and the other player reveals his cards in a given order. Further variants and generalizations of the question were examined by de Moivre , Lambert and Laplace , among others .
In modern textbooks on combinatorics, the problem is often formulated as the "problem of interchanged hats" (also coats, suitcases, letters or the like) something like this:
At a reception, guests leave their hats in the cloakroom. However, the cloakroom lady is very absentminded that evening and gives each guest a randomly chosen hat when they leave. What is the probability that at least one guest will receive the right hat?
The three math problems are equivalent to each other and can be solved by studying fixedpointfree permutations.
definition
If the symmetric group of all permutations of the set , then a permutation is called free of fixed points if
applies to all . A fixedpointfree permutation is thus a permutation in which no element retains its starting position, i.e. no cycle of length one occurs. Describes the set of all fixed pointfree permutations in and their number, then the proportion corresponds to
 .
according to the Laplace formula , the probability of the occurrence of a fixedpointfree permutation, assuming that all possible permutations in are equally probable . In a more general way, permutations of any finite sets , for example alphabets , can be considered, but the analysis of the mathematical properties can be limited to the first natural numbers.
Examples
A fixed point of a permutation is characterized by the fact that in its twoline form the same number appears twice below one another. The only permutation in
has a fixed point and it applies with it and . The two permutations are in
 and ,
where the first has two fixed points and the second none. So it is and . Of the six permutations in
 and
only the fourth and fifth are free of fixed points, so and .
In Fig. 4, the carrier set consists of the empty set with the only permutation being to map the empty set onto the empty set. Because of the empty set, no element can be selected, this permutation is fixed points and it holds and .
number
Fixed point free permutations 
all permutations 
proportion of  

0  1  1  1 
1  0  1  0 
2  1  2  0.5 
3  2  6th  0.33333333 ... 
4th  9  24  0.375 
5  44  120  0.36666666 ... 
6th  265  720  0.36805555 ... 
7th  1,854  5,040  0.36785714 ... 
8th  14,833  40,320  0.36788194 ... 
9  133,496  362.880  0.36787918 ... 
10  1,334,961  3,628,800  0.36787946 ... 
The number of fixedpoint free permutations can be using the Subfakultät by
express. The proportion of fixed pointfree permutations in is corresponding
 .
The number of fixedpoint free permutations and their share in the total number of permutations are for up summarized in the adjacent table.
For , the proportion of fixed pointfree permutations is around 37% (hence the 37% rule ). Asymptotically applies to this portion
 ,
where is Euler's number .
Derivations
Derivation via the inclusionexclusion principle
Designated
the set of permutations that have a fixed point at that point , then the set of fixed pointfree permutations has the representation
 .
The number of fixedpointfree permutations is through
given. According to the principle of inclusion and exclusion , the power of a union now applies
 .
Each of the intersections consists of the permutations with at least the fixed points and therefore applies
 .
Since there are ways to select fixed points, this is how you get
and further
 .
Derivation via recurrences

If with is a fixed pointfree permutation, then by definition applies . A distinction is made between the following two cases:
 If the number is at the position , then the remaining numbers can be distributed to the remaining positions without any fixed points.
 Otherwise, look at the crowd . These numbers must now take the positions , so that none of the numbers remains fixed and also that is not in place . The number of ways to achieve this is even .
Since there are possible values for , linear recurrence follows from this
with and . This recurrence is now possible
 .
reshape. With the substitution one recognizes , well , and thus
 .
The explicit empirical formula can then be verified by complete induction :
whereby .
Partial derangements
0  1  2  3  4th  5  total  
0  1  1  
1  0  1  1  
2  1  0  1  2  
3  2  3  0  1  6th  
4th  9  8th  6th  0  1  24  
5  44  45  20th  10  0  1  120 
If exactly numbers are to remain in place in a permutation , one speaks of an incomplete or partial derangement. For example, the three partial derangements are in , where exactly one number stays in place
 and .
Now denotes the set of partial derangements in which the exact numbers remain in place, then the number is given by the Rencontres numbers
specified (sequence A008290 in OEIS ). As a special case for , one receives the set of fixed pointfree permutations and the subfaculty with.
Applications
The German key machine ENIGMA , which was used during the Second World War, carried out fixedpointfree (and selfinverse ) permutations due to its design. A special roller, namely the reversing roller on the far left , caused the current to flow through the roller set twice, once in the direction of execution and once in the reverse direction. As a result, a letter could no longer be encrypted in itself, which indeed simplified the construction and operation of the machine, since encryption and decryption were the same, but at the same time resulted in a significant cryptographic weakening (see also: Cryptographic weaknesses of ENIGMA ).
The Secret Santa is a Christmas custom in which a group of people on a random manner exchanging gifts. If one assumes that no person gives presents to themselves, the exchange of presents can be mathematically described as a fixed pointfree permutation of persons.
literature
 Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3834800848 , pp. 3839 .
 Albrecht Beutelspacher , MarcAlexander Zschiegner: Discrete Mathematics for Beginners . Springer, 2007, ISBN 3834891827 , pp. 5759 .
 Julian Havil : Amazed ?! Mathematical proof of incredible ideas . Springer, 2009, ISBN 9783540782353 , pp. 4558 .
 Norbert Henze : Stochastics for beginners. 10th edition. Springer Spectrum, Wiesbaden 2013, ISBN 9783658030766 , p. 75 ff.
 Herbert Kütting, Martin J. Sauer: Elementary stochastics: Mathematical foundations and didactic concepts . Springer, 2011, ISBN 3827427592 , pp. 155162 .
 Matthias Löwe, Holger Knöpfel: Stochastics  structure by chance . Oldenbourg, 2011, ISBN 3486706764 , pp. 5960 .
 Jiří Matoušek , Jaroslav Nešetřil : Discrete Mathematics: A Journey of Discovery . Springer, 2002, ISBN 3540423869 , pp. 100102 .
 Pierre Rémond de Montmort : Essai d'analyse sur les jeux de hazard . 1st edition. Jacque Quillau, Paris 1708 ( Google Books ).
 Pierre Rémond de Montmort : Essay d'analyse sur les jeux de hazard . 2nd Edition. Jacque Quillau, Paris 1713, p. 130–143 ( gallica.bnf.fr  including letters from Nikolaus Bernoulli ).
Web links
 VM Mikheev: Derangements . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . SpringerVerlag , Berlin 2002, ISBN 9781556080104 (English, online ).
 Montmort matching problem . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . SpringerVerlag , Berlin 2002, ISBN 9781556080104 (English, online ).
 Eric W. Weisstein : Derangement . In: MathWorld (English).
 Chi Woo, J. Pahikkala: Derangement . In: PlanetMath . (English)
 Matroid: Derangements revisited. In: Matroids Math Planet. May 31, 2003, accessed December 26, 2012 .
Individual evidence
 ^ Pierre Rémond de Montmort : Essai d'analysis sur les jeux de hazard . Jacque Quillau, Paris 1708, p. 58 f . (first edition 1708, second edition 1713, including letters from Nikolaus I Bernoulli ).
 ↑ Florence Nightingale David: Games, Gods and Gambling . Griffin, London 1962, p. 162 .
 ^ Leonhard Euler : Calcul de la probabilité dans le jeu de rencontre . In: Memoirs de l'academie des sciences de Berlin . tape 7 , 1753.
 ↑ Abraham de Moivre : Doctrine of Chances . W. Pearson, London 1718, p. 109117 .
 ^ Johann Heinrich Lambert : Examen d'une espèce de Superstition ramenée au calcul des probabilités . In: Nouveaux Mémoires de l'Académie Royale des Sciences et des BellesLettres . 1771, p. 411420 .
 ↑ PierreSimon Laplace : Théorie Analytic des Probabilities . Courcier, Paris 1812.
 ↑ Jiří Matoušek , Jaroslav Nešetřil : Discrete Mathematics: A Journey of Discovery . S. 100101 .
 ↑ Herbert Kütting, Martin J. Sauer: Elementary Stochastics: Mathematical Foundations and Didactic Concepts . S. 155 .
 ^ Albrecht Beutelspacher , MarcAlexander Zschiegner: Discrete Mathematics for Beginners . S. 57 .
 ↑ Stefan Bartz: Selfwatering in 2 of 3 games . In: Stochastics in School . No. 33 , 2013 ( stefanbartz.de [PDF; 684 kB ]).