Derangement

A fixed-point- free permutation or derangement (from French déranger " mess up " ) is in combinatorics a permutation of the elements of a set, so that no element will keep its position. The number of possible permutations of a fixed-point- free quantity of items specified by the Subfakultät. For increasing the proportion of fixed-point- free permutations strives very fast against the reciprocal of the Euler's number. If in a permutation, the items remain in their original location, it is called a partial derangement, whose number can be determined by the Rencontres numbers.

Initial problem

The French mathematician Pierre Remond de Mont Mort turned the early 18th century in his book Essai d'analyze sur les jeux de hazard a game called Treize ( " Thirteen " ) before that can be described in a simplified form as follows:

A player shuffles a set of 13 playing cards of one color and puts it in a stack in front of him. Now he covers the cards up one after another, which he calls each card according to the following order: Ace, Two, Three or king. If at some point the called card with the face up card match, he wins the game; This applies for any of the 13 cards, he loses.

Now de Mont Mort raises the question of the probability with which the player wins the game. In the first edition of his book from 1708 Mont de Mort are indeed at the correct result, but without detailed derivation. In the second edition of 1713, he presents two proofs, one 's own, based on a recursive representation, and another from a correspondence with Nicholas Bernoulli, based on the inclusion-exclusion principle. De Mont Mort further 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 the groundwork to know analyzed Leonhard Euler in 1753 a related gambling called Rencontre ( " return" ), which runs as follows:

Two players each have a full deck of 52 cards. They shuffle their cards and place them in a stack in front of him. Now both players move at the same time over and over again at the top card of their stack. Appear at any time the same card twice, then one player wins, otherwise the other.

Again, there is the question of the probability of winning. Euler derives the solution is prepared with the help of other Rekurrenzformeln, where he may assume that only one of the player shuffles his cards and the other player reveals his cards in a predetermined order. Further variants and generalizations of the question have been studied, among others, de Moivre, Lambert and Laplacian.

In modern textbooks on combinatorics, the problem is often called " problem of swapped hats " (also coats, suitcases, letters or similar) formulated like this:

At a reception guests give their hats at the door. The wardrobe woman is very scattered this evening and are leaving every guest returns a random hat. What is the probability that at least one guest receives the correct hat?

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

Definition

Is the symmetric group of all permutations of the set, then is called a permutation of fixed-point- free if

Applies to all. A fixed-point- free permutation is thus a permutation where no element will keep its position, ie there occurs no cycle of length one. Identifies the set of all fixed point free permutations and their number corresponds to the percentage

According to the Laplace formula just the probability of the occurrence of a fixed-point free permutation, if it is assumed that all possible permutations are equally likely. More generally, even permutations of arbitrary finite quantities, for example alphabets are 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 in that in its two-line form twice the same number is under each other. The only permutation in

Has a fixed point and it is so and. The two permutations are

The first two fixed points and the second has not. It is therefore and. Of the six permutations in

Are only the fourth and fifth fixed points, it is so and.

In the amount of support from the empty set is the single permutation to map the empty set to the empty set. Because of the empty set is not an element can be selected, this permutation is fixed-point- free and it is true and.

Number

The number of fixed-point- free permutations can be achieved by using the Subfakultät

Express. The proportion of fixed-point- free permutations is in accordance with

The number of fixed-point- free permutations and their share in the total number of permutations are summarized up in the adjacent table.

For so is the proportion of fixed-point- free permutations at about 37 % (see 37 % rule ). Asymptotically valid for this share

The Euler number.

Derivations

Derivation via the inclusion-exclusion principle

Refers to

The set of permutations which have a fixed point at the location then has the amount of the fixed-point representation the free permutations

This is the number of fixed-point- free permutations by

Given. According to the principle of inclusion and exclusion now applies to the cardinality of a union of

Each of the intersection consists of the permutations with least fixed points and therefore applies

Since there are ways to select fixed points, one obtains

And further

Derivation on recurrences

It has a fixed-point- free permutation, then applies by definition. Now the following two cases:

• Located at the number on the site, then the remaining numbers can be distributed to facilities no fixed point on the remaining seats.
• Otherwise, you look at the crowd. These figures must now assume the positions, so that none of the numbers remains firm and also which is not in place. The number of possibilities is to achieve this straight.

Since there are possible values ​​for, it follows the linear recurrence

With and. This recurrence can be now

Reshape. With the substitution can be seen, therefore, and thus

The explicit sum formula can then be verified by induction:

Said.

Partial derangements

If in a permutation exactly numbers remain in place, it is called an incomplete or partial derangement. For example, the three partial derangements in, in exactly one number remains in place

Now denotes the set of partial derangements in where exactly numbers remain in place, then the number is determined by the Rencontres numbers

Specified ( A008290 in OEIS sequence ). As a special case for obtained with the set of fixed-point- free permutations and with the Subfakultät.

Applications

The German Enigma encryption machine which was used during the Second World War, led by their design fixed-point- free (and even inverse ) permutations. A special roll, reverse roll, caused the current flowed through the roller set twice, once in the forward direction and once in the reverse direction. This could not be encrypted in itself a letter, however, which was a significant weakening of the cryptographic engine.

The Secret Santa is a pre-Christmas tradition, in which a group of people exchanging gifts at random. Assuming this is that there are no blessed person himself, the exchange of gifts can be mathematically described as a fixed-point- free permutation of the people.