Fixed point free permutation
A fixed point-free 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 fixed-point-free permutations of a set with elements is given by the sub-faculty . For growing of permutations of aims within the set elements, the share of fixed-point 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 .
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 inclusion-exclusion 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 absent-minded 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 fixed-point-free permutations.
If the symmetric group of all permutations of the set , then a permutation is called free of fixed points if
applies to all . A fixed-point-free 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 point-free permutations in and their number, then the proportion corresponds to
according to the Laplace formula , the probability of the occurrence of a fixed-point-free 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.
A fixed point of a permutation is characterized by the fact that in its two-line 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
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 .
|Fixed point free
The number of fixed-point free permutations can be using the Subfakultät by
express. The proportion of fixed point-free permutations in is corresponding
The number of fixed-point free permutations and their share in the total number of permutations are for up summarized in the adjacent table.
For , the proportion of fixed point-free permutations is around 37% (hence the 37% rule ). Asymptotically applies to this portion
where is Euler's number .
Derivation via the inclusion-exclusion principle
the set of permutations that have a fixed point at that point , then the set of fixed point-free permutations has the representation
The number of fixed-point-free 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
Derivation via recurrences
If with is a fixed point-free 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 :
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 point-free permutations and the sub-faculty with.
The German key machine ENIGMA , which was used during the Second World War, carried out fixed-point-free (and self-inverse ) 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 point-free permutation of persons.
- Martin Aigner : Discrete Mathematics . Vieweg, 2006, ISBN 3-8348-0084-8 , pp. 38-39 .
- Albrecht Beutelspacher , Marc-Alexander Zschiegner: Discrete Mathematics for Beginners . Springer, 2007, ISBN 3-8348-9182-7 , pp. 57-59 .
- Julian Havil : Amazed ?! Mathematical proof of incredible ideas . Springer, 2009, ISBN 978-3-540-78235-3 , pp. 45-58 .
- Norbert Henze : Stochastics for beginners. 10th edition. Springer Spectrum, Wiesbaden 2013, ISBN 978-3-658-03076-6 , p. 75 ff.
- Herbert Kütting, Martin J. Sauer: Elementary stochastics: Mathematical foundations and didactic concepts . Springer, 2011, ISBN 3-8274-2759-2 , pp. 155-162 .
- Matthias Löwe, Holger Knöpfel: Stochastics - structure by chance . Oldenbourg, 2011, ISBN 3-486-70676-4 , pp. 59-60 .
- Jiří Matoušek , Jaroslav Nešetřil : Discrete Mathematics: A Journey of Discovery . Springer, 2002, ISBN 3-540-42386-9 , pp. 100-102 .
- 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 ).
- VM Mikheev: Derangements . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
- Montmort matching problem . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (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 .
- ^ 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. 109-117 .
- ^ 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 Belles-Lettres . 1771, p. 411-420 .
- ↑ Pierre-Simon Laplace : Théorie Analytic des Probabilities . Courcier, Paris 1812.
- ↑ Jiří Matoušek , Jaroslav Nešetřil : Discrete Mathematics: A Journey of Discovery . S. 100-101 .
- ↑ Herbert Kütting, Martin J. Sauer: Elementary Stochastics: Mathematical Foundations and Didactic Concepts . S. 155 .
- ^ Albrecht Beutelspacher , Marc-Alexander Zschiegner: Discrete Mathematics for Beginners . S. 57 .
- ↑ Stefan Bartz: Self-watering in 2 of 3 games . In: Stochastics in School . No. 33 , 2013 ( stefanbartz.de [PDF; 684 kB ]).