Fixed point free permutation

from Wikipedia, the free encyclopedia
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 . 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

Playing card spade A - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade 4 - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 7 - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade K.svg

Playing card spade 7 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade A - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade K - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 4.svg

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.

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.

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

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

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 fixed-point free permutations can be using the Subfakultät by

  (Follow A000166 in OEIS )

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 .

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 .

Designated

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

and further

.

Derivation via recurrences

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 .

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 :

whereby .

Partial derangements

Rencontres numbers d n, 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

  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.

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

Web links

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