Permutation

Under a permutation (from the Latin permutare swap ) is understood in combinatorics, an arrangement of objects in a particular order. Depending on whether some objects may occur several times or not, it is called a permutation with repetition or a permutation without repetition. The number of permutations without repetition is calculated as the faculty, while the number of permutations is specified with repetition through multinomial.

In group theory, a permutation without repetition a bijective self-map of a normally finite set, which are used as reference quantities usually the first natural numbers. The set of permutations of the first natural numbers together with the sequential execution as a link, the symmetric group of degree. The neutral element of this group is the identity permutation, while the inverse element is the inverse permutation. The subgroups of the symmetric group are the permutation groups.

Important characteristics of permutations are their Zykeltyp, its order and its sign. Using the wrong items of a permutation can be defined on the set of permutations of fixed length a partial order. Through its inversion table can also be assigned a unique number in a faculty- based number system each permutation. Important classes of permutations are cyclic, fixed-point- free, self- inverse and alternating permutations.

Permutations have wide range of applications both inside and outside of mathematics, for example, in linear algebra (Leibniz formula ), the Analysis ( reordering of rows ), graph theory and game theory, cryptography (encryption method), computer science ( sorting method ) and quantum mechanics ( Pauli principle).

3.1 Two lines form
3.2 Tupelschreibweise
3.3 Zykelschreibweise

4.1 Graph representation
4.2 permutation matrices

5.1 composition
5.2 Identical permutation
5.3 Inverse permutation

6.1 Zykeltyp
6.2 Procedure
6.3 faulty items
6.4 sign
6.5 ascents and descents

7.1 arrangement
7.2 enumeration
7.3 symmetries

8.1 Cyclic permutations
8.2 fixed point free permutations
8.3 self- inverse permutations
8.4 Alternating permutations
8.5 Separable permutations
8.6 Random permutations

Combinatorial foundations

Problem

A permutation is an arrangement of objects in a certain order or rearrangement of objects from a given ranking. Examples of permutations are:

An anagram is a permutation of the letters of a word, such as GRANDSON and carnation.
Shuffling the cards of a card game is ( ideally) a random permutation of the map.
In volleyball the change of position is after the conquest of the impact law is a cyclic permutation of the players.
Many sorting algorithms working with successive transpositions, ie, permutations that interchange exactly two objects.

If not all objects are selected in such a configuration, it is called instead of a permutation of a variation, the order does not matter from a combination with the selection. In the enumerative combinatorics now arises the question of the number of possible permutations. A distinction is made in the event that all of the objects are different from the case that some of the properties are identical.

Permutation without repetition

A permutation without repetition is an arrangement of objects, which are all distinguishable. Since there are placement options for the first object to come for the second object only options to be considered for the third object only more and so on until the last object, the only thing left an empty seat. The number of possible permutations of objects is accordingly by the faculty

Specified.

For example, there are four possible arrangements of different colored beads in a row.

Permutation with repetition

A permutation with repetition is an array of objects, some of which are indistinguishable. Are objects exactly identical, then they are interchangeable in their seats without this results in a new order. In this way, arrangements are exactly alike. The number of permutations of objects, which are identical, therefore, is by the falling factorial

Given. Is there not just one, but groups of identical objects, so all these objects can be swapped in their seats, without incurring new arrangements. Counting also the objects that appear only once, with multiplicity, then applies and the number of possible permutations is the multinomial coefficient

Specify.

For example, there are four possible arrangements of colored balls in a row, if exactly two of the balls of the same color, and possible arrangements, when two spheres are the same color.

Definition

Be a lot of items, then a digit permutation ( without repetition ) is a bijective map

To each element of the set assigns an element of the same amount. It clearly, by the permutation of each element of the square of its associated element. Due to the bijective mapping Two different elements are never displayed on the same element. The case is also approved and then the empty set.

Since at any finite set a linear order can be defined ( for example, be caused by the indexing of the elements ), you can always limit in the mathematical consideration of permutations on the first natural numbers as a reference quantity. A permutation is then a bijective mapping

Which every natural number between and accurately assigns a number in the same area. If you imagine all the numbers in a list lined up before then, the number of the permutation space with the number.

Notation

Two lines form

In the detailed view of a digit permutation to write this as a matrix with two rows and columns. In the top row are the numbers of up ( in any order). Under each number then available in the second line of the function value:

Thus is also in the second line of each number to exactly once.

Example

The permutation, and is in the form of two rows by

Noted.

In the compact Tupelschreibweise to write only the function values in one line:

This notation is used so only the second row of the two rows form. As such the information on the number which is displayed on, is lost, the Tupelschreibweise can be used only if the sequence of numbers set in the first row. Usually this is the natural order. The Tupelschreibweise can be easily confused with the following Zykelschreibweise, especially since some authors omit the commas.

Example

For the above Beispielpermutation you get the Tupelschreibweise

Zykelschreibweise

The Zykelschreibweise also requires only one line. You start with any number and writes

The times designated by successive application and the smallest natural number with. Such a bracket is called cycle and its length. Are there any other numbers that were not yet listed, just select such a number and writes another cycle of length behind. One process is continued until each number was recorded only once. Brackets, in which only one number stands, can then be painted again. This representation is not unique, since the order of cycles can be selected arbitrarily, and in each cycle, the numbers may be cyclically interchanged.

Example

For the above Beispielpermutation using the following Zykelschreibweisen:

Further illustrations

Graph representation

The graph of a digit permutation is a directed graph with vertex set and edge set

In such a graph, each node has exactly one outgoing and exactly one incoming edge. The cycles of the graph are precisely the cycles of the permutation, with those numbers which are held by the permutation generate loops on the corresponding node. The graph of a permutation is only connected if the permutation is a single cycle of length.

Permutation matrices

The permutation matrix of a digit permutation is

Defined. Is a permutation of the number mapped to the number, then has the corresponding permutation matrix in the -th row in a column. The elements of a vector are thus permuted in linear algebra that the vector is multiplied from the left with the permutation matrix:

Permutations as a group

The permutations of the set form with the sequential execution as a link a group, the symmetric group. The symmetric groups play an important role in mathematics. For example, by the theorem of Cayley every finite group is isomorphic to a subgroup of a symmetric group. The subgroups of the symmetric group are called permutation groups.

Composition

Two - digit permutations can be executed consecutively by first applying the first permutation and the result then the second permutation. One writes the Hintereinderausführung as

Said first and is then applied. This sequential execution is also called composition, link or product of two permutations and the result is again a digit permutation. The composition of the permutations is not commutative, i.e., in general provide different results and. The symmetric group is therefore for not abelian. However, the composition is associative, ie for all permutations applies

Examples

It is, for example,

To obtain the result Applying the permutations of the right to the left, and follows the path of the individual numbers. The in the second permutation mapped to itself and in the first permutation then the, that is, as a whole. The path is correspondingly so. The finally goes the way, in the result.

In the cyclic notation one proceeds analogously with numbers that do not occur in a cycle, are recorded. For example, is

Identical permutation

The neutral element of the symmetric group is the identity permutation

So that permutation which leaves all the numbers in place. Applies so that for each permutation

The identity permutation is also listed as an empty clip, as or as. The permutation of the identical permutation is the identity matrix. The graph of the identical permutation has only one loop at each node. The identity permutation of length one is also referred to as a permutation trivial.

Inverse permutation

For every permutation is exactly one inverse element, the inverse permutation, with

The inverse permutation is obtained by the upper two lines in the reversed shape of the bottom line:

In Zykelschreibweise obtained the inverse permutation, by the numbers in the reverse order to write on each cycle. In the graph representation of the inverse permutation of only the directions of all edges to be turned over. The permutation matrix of the inverse permutation is the transposed matrix of Ausgangspermutation.

Example

The inverse permutation to

Parameters

Zykeltyp

Denotes the number of cycles of the length in a permutation, the Zykeltyp this permutation is the formal expression

Where the terms do not have to be listed with. Formal here means that the product and the powers not actually be calculated. The number of possible permutations Zykeltypen -digit corresponds exactly to the number of partitions of the number. The number of permutations per Zykeltyp can be calculated from the type description. Inverse permutation always has the same as the Zykeltyp Ausgangspermutation. In addition, the result of the composition of two permutations is independent of the order of the operands is also the same Zykeltyp. Two permutations are therefore exactly then conjugated to each other if they are of the same Zykeltyp. Thus, the permutations same Zykeltyps form the conjugacy classes of the symmetric group. The permutations with the same number of cycles counted by the Stirling numbers of the first kind.

Order

The order of the permutation is the smallest integer such that the -time sequential execution of the identity permutation results:

The order of a permutation is thus the element order of a group element of the symmetric group. From the cyclic notation of a permutation, the order can be determined as the least common multiple of the lengths of the disjoint cycles. For example, the order of the permutation is the least common multiples of three and two, six.

Incorrect items

We call a pair of numbers faulty state or inversion of a permutation, if and to apply. So two numbers form iff a failure state if, after applying the permutation the larger faces of the smaller. The number of missing objects of a permutation is thus by

Given. The number of failed objects is called a permutation wrong state number or inversion number of the permutation. The failure state number can be viewed as a measure of the disorder of the permuted by the permutation numbers.

Sign

The sign or sign of a permutation is the number

A permutation is thus the sign if its faulty state number is even, otherwise the sign. In the first case we speak of a straight and in the second case of an odd permutation. The set of even permutations forms a subgroup of the symmetric group, the alternating group.

Ascents and descents

An increase in the permutation is an integer for which holds. The amount of ascents in a permutation is thus by

Given. Corresponding to this is for a descent. The number of permutations with exactly ascents and descents is given by the Euler numbers. A maximum, which is no longer called on both sides extendable sequence

Gradually rising or falling numbers in a permutation is called ascending or descending run length. For such a sequence can consist of just a number. Assigns a permutation ascents or descents on a whole, it is composed of descending and ascending runs. Thus, the number of permutations with exactly in rising or descending runs is given by.

Order properties

Arrangement

Using the incorrect items can be on the set of digit permutations a partial order by

Define being. The minimum element with respect to this order is the identity permutation, while the maximal element is the one permutation which reverses the order of all the numbers. In the associated Hasse diagram of two permutations are connected by an edge if they proceed through a Nachbarvertauschung apart. The nodes and edges of the Hasse diagram form a Cayley graph which is isomorphic to the line graph of the corresponding Permutaeders. The Permutaeder is a convex polytope in -dimensional space, which arises from the fact that the permutations of the set are interpreted as coordinate vectors, then the convex hull of these points is formed.

Enumeration

The inversion table or inversion vector of a permutation maps each number to the number of incorrect items that it produces. Specifies the number of numbers that are in the Tupeldarstellung in towards and greater than, then the inversion vector of a permutation by

Given. From the inversion vector, the underlying permutation can be reversed precisely identified. Summing up the inversion vector as a number in a faculty- based number system, each permutation can be a unique number by

. assign Instead of the inversion vector and the Lehmer code for numbering the permutations will be used.

Symmetries

The complementary to a permutation permutation

The complementary permutation generated by horizontal mirroring of the permutation matrix. The reverse permutation is accordingly

And is caused by vertical mirroring. Complementary and reverse permutations they have the same Zykeltyp and the same order as the Ausgangspermutation. The sign, however, is reversed in complementary and reverse permutations and the number of ascents and descents are swapped. The inverse of the complementary permutation is equal to the inverse of revertant and the inverse of the reverse permutation is equal to the inverse complementary.

Special permutations

Cyclic permutations

A permutation, the numbers cyclically permuted and the remaining numbers can be stated, ie cyclic permutation or cycle and is written as a single cycle of length. A cycle, ie a transposition of two numbers is also called transposition. The concatenation of cyclic permutations is commutative if these have disjoint support. The inverse of a cyclic permutation is always also cyclically, as powers of a cyclic permutation, whose length is a prime number. Any cyclic permutation can be decomposed into individual ( not disjoint ) transpositions and then just has a straight sign if its length is odd.

Fixed point free permutations

Numbers which are held by a permutation is called fixed points of the permutation. In the two-line form can be recognized fixed points in mind that the top and bottom entry of each column is the same. In the Zykelschreibweise fixed points are exactly the one cycles or the numbers do not appear. In the permutation are the fixed points assigned to entries in the main diagonal. A fixed-point- free permutation holds none of the numbers and is also called Derangement. The number of fixed-point free permutations of the numbers to be calculated 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.

Self- inverse permutations

A permutation with or equivalently called involution or self-inverse. The involutions are exactly the permutations of order two and the identity itself ( the only permutation of order one). A permutation is an involution if and only if their cyclic notation contains a maximum of cycles of length two, so transpositions. The permutation matrix of a self- inverse permutation is always symmetric. Self- inverse permutations play an important role in cryptography, is in fact a message using a self- inverse permutation encrypted, can the message using the same permutation also decrypt it again.

Alternating permutations

This is called a permutation alternately, if not a number of a scale is in its Tupeldarstellung between the previous number and the following number. In an alternating permutation therefore the interchanged by the permutation numbers are alternately larger and smaller than the corresponding previous number. Begins the sequence of numbers with an increase, one speaks of an up -down permutation, it begins with a descent from a down -up permutation. Each alternating permutation of odd length corresponds to a full partially ordered binary tree and each alternating permutation straight length a nearly full such a tree. The numbers of alternating permutations of fixed length occur as coefficients in the Maclaurin series of the secant and the tangent function and are closely related to the Euler and Bernoulli numbers.

Separable permutations

Separable permutations are permutations that can be represented as a direct or oblique sum trivial permutations. A sum of two permutations resulting in a new permutation whose length is the sum of the lengths of the two Ausgangspermutationen. In a direct sum while the second permutation of the second is appended moved to the top, moved the first permutation in an oblique sum prefixed. The number of permutations of separable fixed length specified by Schroder numbers. Separable permutations are characterized by a special recursive block structure of the corresponding permutation matrices. You are investigated, among others, in the sort theory.

Random permutations

A random permutation based on a random permutation of the set of permutations. In the stochastic random permutations are considered as random variables from a discrete probability space. Such indicators can also random permutations, as the number of fixed points, missing objects or cycles, be viewed as a discrete random variable, the probability distributions are then examined. In computer random permutations can be generated efficiently with the Fisher -Yates method. Random permutations are examined, among others, in the analysis of sorting algorithms in cryptography and coding theory, and in randomized algorithms.

407398