Fixed point free permutation

Graph of a fixed point-free permutation of the numbers from 1 to 8. None of the numbers is recorded by the 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 ${\displaystyle n}$ ${\displaystyle {!}n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle e}$. 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

In the Treize game, the player wins if at least one card appears in the correct order (top row) out of 13 cards of the same color (bottom row), here the ten.

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. ${\displaystyle 1-e^{-1}\approx 0{,}6321}$

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? ${\displaystyle n}$

The three math problems are equivalent to each other and can be solved by studying fixed-point-free permutations.

definition

If the symmetric group of all permutations of the set , then a permutation is called free of fixed points if ${\displaystyle S_{n}}$ ${\displaystyle \{1,\ldots ,n\}}$ ${\displaystyle \pi =(\pi (1),\pi (2),\ldots ,\pi (n))\in S_{n}}$

${\displaystyle \pi (i)\neq i}$

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 ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle D_{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle d_{n}=|D_{n}|}$

${\displaystyle p_{n}={\frac {|D_{n}|}{|S_{n}|}}={\frac {d_{n}}{n!}}}$.

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. ${\displaystyle n!}$ ${\displaystyle S_{n}}$ ${\displaystyle n}$

Examples

The nine fixed point free permutations of four elements are highlighted

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 ${\displaystyle S_{1}}$

${\displaystyle {\begin{pmatrix}1\\1\end{pmatrix}}}$

has a fixed point and it applies with it and . The two permutations are in ${\displaystyle d_{1}=0}$ ${\displaystyle p_{1}=0}$ ${\displaystyle S_{2}}$

${\displaystyle {\begin{pmatrix}1&2\\1&2\end{pmatrix}}}$   and   , ${\displaystyle {\begin{pmatrix}1&2\\2&1\end{pmatrix}}}$

where the first has two fixed points and the second none. So it is and . Of the six permutations in ${\displaystyle d_{2}=1}$ ${\displaystyle p_{2}={\tfrac {1}{2}}}$ ${\displaystyle S_{3}}$

${\displaystyle {\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}},{\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}},{\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}},{\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}},{\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}}$   and   ${\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$

only the fourth and fifth are free of fixed points, so and . ${\displaystyle d_{3}=2}$ ${\displaystyle p_{3}={\tfrac {2}{6}}={\tfrac {1}{3}}}$

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 . ${\displaystyle S_{0}}$ ${\displaystyle d_{0}=1}$ ${\displaystyle p_{0}=1}$

number

${\displaystyle n}$	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 fixed-point free permutations can be using the Subfakultät by ${\displaystyle S_{n}}$

${\displaystyle d_{n}={!}n=n!\cdot \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$   (Follow A000166 in OEIS )

express. The proportion of fixed point-free permutations in is corresponding ${\displaystyle S_{n}}$

${\displaystyle p_{n}={\frac {{!}n}{n!}}=\sum _{k=0}^{n}{\left(-1\right)^{k} \over k!}}$.

The number of fixed-point free permutations and their share in the total number of permutations are for up summarized in the adjacent table. ${\displaystyle d_{n}}$ ${\displaystyle p_{n}}$ ${\displaystyle n=0}$ ${\displaystyle 10}$

For , the proportion of fixed point-free permutations is around 37% (hence the 37% rule ). Asymptotically applies to this portion ${\displaystyle n\geq 4}$

${\displaystyle \lim _{n\to \infty }p_{n}=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}={\frac {1}{e}}}$,

where is Euler's number . ${\displaystyle e}$

Derivations

Derivation via the inclusion-exclusion principle

According to the principle of inclusion and exclusion, the thickness of the union of three sets results from the sum of the thicknesses of the individual sets minus the sum of the thicknesses of the intersections of two sets plus the thickness of the intersection of the three sets . ${\displaystyle |A\cup B\cup C|}$ ${\displaystyle |A|+|B|+|C|}$ ${\displaystyle |A\cap B|+|A\cap C|+|B\cap C|}$ ${\displaystyle |A\cap B\cap C|}$

Designated

${\displaystyle A_{i}=\{\pi \in S_{n}\mid \pi (i)=i\}}$

the set of permutations that have a fixed point at that point , then the set of fixed point-free permutations has the representation ${\displaystyle i}$

${\displaystyle D_{n}=S_{n}\setminus (A_{1}\cup \ldots \cup A_{n})}$.

The number of fixed-point-free permutations is through

${\displaystyle d_{n}=n!-|A_{1}\cup \ldots \cup A_{n}|}$

given. According to the principle of inclusion and exclusion , the power of a union now applies

${\displaystyle |A_{1}\cup \ldots \cup A_{n}|=\sum _{k=1}^{n}(-1)^{k-1}\sum _{1\leq i_{1}<\ldots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|}$.

Each of the intersections consists of the permutations with at least the fixed points and therefore applies ${\displaystyle |A_{i_{1}}\cap \ldots \cap A_{i_{k}}|}$ ${\displaystyle k}$ ${\displaystyle i_{1},\ldots ,i_{k}}$

${\displaystyle |A_{i_{1}}\cap \ldots \cap A_{i_{k}}|=(n-k)!}$.

Since there are ways to select fixed points, this is how you get ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k}$

${\displaystyle |A_{1}\cup \ldots \cup A_{n}|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}(n-k)!=\sum _{k=1}^{n}(-1)^{k-1}{\frac {n!}{k!}}}$

and further

${\displaystyle d_{n}=n!-\sum _{k=1}^{n}(-1)^{k-1}{\frac {n!}{k!}}=n!\cdot \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$.

Derivation via recurrences

${\displaystyle {\begin{pmatrix}1&\,2\,&3&\cdots &n\\2&\;1\;&\neq \!\!3&\cdots &\neq \!\!n\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\2&\neq \!\!1&\neq \!\!3&\cdots &\neq \!\!n\end{pmatrix}}}$ Two cases are to be distinguished in the derivation: is , then either there can be (above) and conditions remain or it is (below), conditions then remain . In the example is . ${\displaystyle \pi (1)=j}$ ${\displaystyle \pi (j)=1}$ ${\displaystyle n-2}$ ${\displaystyle \pi (j)\neq 1}$ ${\displaystyle n-1}$ ${\displaystyle j=2}$

If with is a fixed point-free permutation, then by definition applies . A distinction is made between the following two cases: ${\displaystyle \pi \in D_{n}}$ ${\displaystyle n\geq 3}$ ${\displaystyle \pi (1)\neq 1}$

• If the number is at the position , then the remaining numbers can be distributed to the remaining positions without any fixed points. ${\displaystyle 1}$ ${\displaystyle j=\pi (1)}$ ${\displaystyle n-2}$ ${\displaystyle d_{n-2}}$
• 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 . ${\displaystyle \{1,\ldots ,n\}\setminus \{j\}}$ ${\displaystyle 2,3,\ldots ,n}$ ${\displaystyle 1}$ ${\displaystyle j}$ ${\displaystyle d_{n-1}}$

Since there are possible values ​​for , linear recurrence follows from this ${\displaystyle n-1}$ ${\displaystyle j}$

${\displaystyle d_{n}=(n-1)(d_{n-1}+d_{n-2})}$

with and . This recurrence is now possible ${\displaystyle d_{1}=0}$ ${\displaystyle d_{2}=1}$

${\displaystyle d_{n}-nd_{n-1}=-(d_{n-1}-(n-1)d_{n-2})}$.

reshape. With the substitution one recognizes , well , and thus ${\displaystyle b_{n}=d_{n}-nd_{n-1}}$ ${\displaystyle b_{n}=-b_{n-1}}$ ${\displaystyle b_{n}=(-1)^{n}}$

${\displaystyle d_{n}=nd_{n-1}+(-1)^{n}}$.

The explicit empirical formula can then be verified by complete induction :

${\displaystyle d_{n}=n!\cdot \sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}=n!\cdot \sum _{k=0}^{n-1}{\left(-1\right)^{k} \over k!}+n!\cdot {\frac {(-1)^{n}}{n!}}=nd_{n-1}+(-1)^{n}}$

whereby . ${\displaystyle d_{2}=2({\tfrac {1}{2}}-{\tfrac {1}{1}}+{\tfrac {1}{1}})=2\cdot d_{1}+(-1)^{2}}$

Partial derangements

Rencontres numbers d _{n, k}

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	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 ${\displaystyle \pi \in S_{n}}$ ${\displaystyle k}$ ${\displaystyle S_{3}}$

${\displaystyle {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}},{\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$   and   . ${\displaystyle {\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}}$

Now denotes the set of partial derangements in which the exact numbers remain in place, then the number is given by the Rencontres numbers ${\displaystyle D_{n,k}}$ ${\displaystyle S_{n}}$ ${\displaystyle k}$ ${\displaystyle d_{n,k}=|D_{n,k}|}$

${\displaystyle d_{n,k}={!}(n-k){\binom {n}{k}}={\frac {n!}{k!}}\cdot \sum _{i=0}^{n-k}{\left(-1\right)^{i} \over i!}}$

specified (sequence A008290 in OEIS ). As a special case for , one receives the set of fixed point-free permutations and the sub-faculty with. ${\displaystyle k=0}$ ${\displaystyle D_{n}=D_{n,0}}$ ${\displaystyle d_{n}=d_{n,0}}$

Applications

Reversal of letters in the ENIGMA roller set

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.

literature

• 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 ).

Web links

Wikiversity: A lecture on fixed point-free permutations as part of a course on discrete mathematics  - course materials

• 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 . 

Individual evidence

1. ^ 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 ).
2. ↑ Florence Nightingale David: Games, Gods and Gambling . Griffin, London 1962, p. 162 .
3. ^ Leonhard Euler : Calcul de la probabilité dans le jeu de rencontre . In: Memoirs de l'academie des sciences de Berlin . tape 7 , 1753.
4. ↑ Abraham de Moivre : Doctrine of Chances . W. Pearson, London 1718, p. 109-117 .
5. ^ 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 .
6. ↑ Pierre-Simon Laplace : Théorie Analytic des Probabilities . Courcier, Paris 1812.
7. ↑ Jiří Matoušek , Jaroslav Nešetřil : Discrete Mathematics: A Journey of Discovery . S. 100-101 .
8. ↑ Herbert Kütting, Martin J. Sauer: Elementary Stochastics: Mathematical Foundations and Didactic Concepts . S. 155 .
9. ^ Albrecht Beutelspacher , Marc-Alexander Zschiegner: Discrete Mathematics for Beginners . S. 57 .
10. ↑ Stefan Bartz: Self-watering in 2 of 3 games . In: Stochastics in School . No. 33 , 2013 ( stefanbartz.de [PDF; 684 kB ]).