This is a list of topics on mathematical

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pr ...

Particular kinds of permutations

Alternating permutation In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. For example, the five alt ...

Circular shift In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse ope ...

Cyclic permutation In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set ''X'' which maps the elements of some subset ''S'' of ''X'' to each other in a cyclic fashion, while fixing (that is, ...

* Derangement *Even and odd permutations—see

Parity of a permutation In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total o ...

Josephus permutation In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. A number of people are standing in a circle waiting to be executed. Counting begins at a specif ...

Separable permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 31 ...

* Stirling permutation *

Superpattern In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns ...

* Transposition (mathematics) * Unpredictable permutation

Combinatorics of permutations

Bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

Combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are t ...

Costas array In mathematics, a Costas array can be regarded geometrically as a set of ''n'' points, each at the center of a square in an ''n''×''n'' square tiling such that each row or column contains only one point, and all of the ''n''(''n'' &minu ...

Cycle index Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...

Cycle notation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...

Cycles and fixed points In mathematics, the cycles of a permutation ''π'' of a finite set S correspond bijectively to the orbits of the subgroup generated by ''π'' acting on ''S''. These orbits are subsets of S that can be written as , such that : for , and . T ...

Cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. In ...

Direct sum of permutations In combinatorics, the skew sum and direct sum of permutations are two operations to combine shorter permutations into longer ones. Given a permutation ''π'' of length ''m'' and the permutation ''σ'' of length ''n'', the skew sum of ''π'' and '' ...

* Enumerations of specific permutation classes *

Factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...

Falling factorial In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \ ...

* Permutation matrix **

Generalized permutation matrix In mathematics, a generalized permutation matrix (or monomial matrix) is a matrix with the same nonzero pattern as a permutation matrix, i.e. there is exactly one nonzero entry in each row and each column. Unlike a permutation matrix, where the non ...

Inversion (discrete mathematics) In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. Definitions Inversion Let \pi be a permutation. There is an inversion of \pi between i and j if i \pi(j). ...

Major index In mathematics (and particularly in combinatorics), the major index of a permutation is the sum of the positions of the descents of the permutation. In symbols, the major index of the permutation ''w'' is : \operatorname(w) = \sum_ i. For ex ...

Ménage problem In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits ...

Permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be d ...

* Permutation pattern *

Permutation polynomial In mathematics, a permutation polynomial (for a given ring) is a polynomial that acts as a permutation of the elements of the ring, i.e. the map x \mapsto g(x) is a bijection. In case the ring is a finite field, the Dickson polynomials, which ...

Permutohedron In mathematics, the permutohedron of order ''n'' is an (''n'' − 1)-dimensional polytope embedded in an ''n''-dimensional space. Its vertex coordinates (labels) are the permutations of the first ''n'' natural numbers. The edges iden ...

Rencontres numbers In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set with specified numbers of fixed points: in other words, partial derangements. (''Rencontre'' is French for ''encounter' ...

Robinson–Schensted correspondence In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many rema ...

*Sum of permutations: **

** Skew sum of permutations *

Stanley–Wilf conjecture The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by and is no longer a conjecture. ...

Symmetric function In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f ...

* Szymanski's conjecture * Twelvefold way

Permutation groups and other algebraic structures

Groups

Alternating group In mathematics, an alternating group is the group of even permutations of a finite set. The alternating group on a set of elements is called the alternating group of degree , or the alternating group on letters and denoted by or Basic pr ...

Automorphisms of the symmetric and alternating groups In group theory, a branch of mathematics, the automorphisms and outer automorphisms of the symmetric groups and alternating groups are both standard examples of these automorphisms, and objects of study in their own right, particularly the exception ...

Block (permutation group theory) In mathematics and group theory, a block system for the action of a group ''G'' on a set ''X'' is a partition of ''X'' that is ''G''-invariant. In terms of the associated equivalence relation on ''X'', ''G''-invariance means that :''x'' ~ '' ...

Cayley's theorem In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group. More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose element ...

* Frobenius group *

Galois group of a polynomial In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...

* Jucys–Murphy element *

Landau's function In mathematics, Landau's function ''g''(''n''), named after Edmund Landau, is defined for every natural number ''n'' to be the largest order of an element of the symmetric group ''S'n''. Equivalently, ''g''(''n'') is the largest least common mul ...

Oligomorphic group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...

O'Nan–Scott theorem In mathematics, the O'Nan–Scott theorem is one of the most influential theorems of permutation group theory; the classification of finite simple groups is what makes it so useful. Originally the theorem was about maximal subgroups of the symmetric ...

Parker vector The Parker Pen Company is a French manufacturer of luxury writing pens, founded in 1888 by George Safford Parker in Janesville, Wisconsin, United States. In 2011 the Parker factory at Newhaven, East Sussex, England, was closed, and its producti ...

Permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to i ...

* Place-permutation action *

Primitive permutation group In mathematics, a permutation group ''G'' acting on a non-empty finite set ''X'' is called primitive if ''G'' acts transitively on ''X'' and the only partitions the ''G''-action preserves are the trivial partitions into either a single set or i ...

* Rank 3 permutation group *

Representation theory of the symmetric group In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from sy ...

* Schreier vector *

Strong generating set In abstract algebra, especially in the area of group theory, a strong generating set of a permutation group is a generating set that clearly exhibits the permutation structure as described by a stabilizer chain. A stabilizer chain is a sequence of ...

Symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \ ...

* Symmetric inverse semigroup * Weak order of permutations *

Wreath product In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used i ...

* Young symmetrizer * Zassenhaus group *

Zolotarev's lemma In number theory, Zolotarev's lemma states that the Legendre symbol :\left(\frac\right) for an integer ''a'' modulo an odd prime number ''p'', where ''p'' does not divide ''a'', can be computed as the sign of a permutation: :\left(\frac\right) ...

Other algebraic structures

Burnside ring In mathematics, the Burnside ring of a finite group is an algebraic construction that encodes the different ways the group can act on finite sets. The ideas were introduced by William Burnside at the end of the nineteenth century. The algebraic r ...

Mathematical analysis

* Conditionally convergent series *

Riemann series theorem In mathematics, the Riemann series theorem (also called the Riemann rearrangement theorem), named after 19th-century German mathematician Bernhard Riemann, says that if an infinite series of real numbers is conditionally convergent, then its term ...

Lévy–Steinitz theorem In mathematics, the Lévy–Steinitz theorem identifies the set of values to which rearrangements of an infinite series of vectors in R''n'' can converge. It was proved by Paul Lévy in his first published paper when he was 19 years old. In 1913 Er ...

Mathematics applicable to physical sciences

Antisymmetrizer In quantum mechanics, an antisymmetrizer \mathcal (also known as antisymmetrizing operatorP.A.M. Dirac, ''The Principles of Quantum Mechanics'', 4th edition, Clarendon, Oxford UK, (1958) p. 248) is a linear operator that makes a wave function of ...

Identical particles In quantum mechanics, identical particles (also called indistinguishable or indiscernible particles) are particles that cannot be distinguished from one another, even in principle. Species of identical particles include, but are not limited to, ...

Levi-Civita symbol In mathematics, particularly in linear algebra, tensor analysis, and differential geometry, the Levi-Civita symbol or Levi-Civita epsilon represents a collection of numbers; defined from the sign of a permutation of the natural numbers , for som ...

Number theory

Permutable prime A permutable prime, also known as anagrammatic prime, is a prime number which, in a given base, can have its digits' positions switched through any permutation and still be a prime number. H. E. Richert, who is supposedly the first to study the ...

Algorithms and information processing

Bit-reversal permutation In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n=2^k is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to n-1, representing each of these numbers by ...

Claw-free permutation In the mathematical and computer science field of cryptography, a group of three numbers (''x'',''y'',''z'') is said to be a claw of two permutations ''f''0 and ''f''1 if :''f''0(''x'') = ''f''1(''y'') = ''z''. A pair of permutations ''f''0 and '' ...

Heap's algorithm Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; th ...

* Permutation automaton * Schreier vector *

Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is importa ...

Sorting network In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such ne ...

Substitution–permutation network In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square. Su ...

Steinhaus–Johnson–Trotter algorithm The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. E ...

* Tompkins–Paige algorithm

Cryptography

* Permutation box *

Substitution box In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shan ...

Permutation cipher In cryptography, a transposition cipher is a method of encryption which scrambles the positions of characters (''transposition'') without changing the characters themselves. Transposition ciphers reorder units of plaintext (typically characters or ...

Substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, tri ...

* Transposition cipher

Probability, stochastic processes, and statistics

* Combinatorial data analysis * Ewens' sampling formula *

Fisher–Yates shuffle The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the ...

* Order statistic *

Permutational analysis of variance Permutational multivariate analysis of variance (PERMANOVA), is a non-parametric multivariate statistical permutation test. PERMANOVA is used to compare groups of objects and test the null hypothesis that the centroids and dispersion of the groups ...

Rankit In statistics, rankits of a set of data are the expected values of the order statistics of a sample from the standard normal distribution the same size as the data. They are primarily used in the normal probability plot, a graphical technique for ...

Resampling (statistics) In statistics, resampling is the creation of new samples based on one observed sample. Resampling methods are: # Permutation tests (also re-randomization tests) # Bootstrapping # Cross validation Permutation tests Permutation tests rely on re ...

Seriation (statistics) In combinatorial data analysis, seriation is the process of finding an arrangement of all objects in a set, in a linear order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total ...

Random permutations

Golomb–Dickman constant In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is :\lambda = 0.62432 99885 43550 87099 29363 83100 83724\dots It is not known whether this constant is rational or irratio ...

Random permutation A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...

Random permutation statistics The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, t ...

Music

{{main, Permutation (music) *

Change ringing Change ringing is the art of ringing a set of tuned bells in a tightly controlled manner to produce precise variations in their successive striking sequences, known as "changes". This can be by method ringing in which the ringers commit to memor ...

Method ringing Method ringing (also known as scientific ringing) is a form of change ringing in which the ringers commit to memory the rules for generating each change of sequence, and pairs of bells are affected. This creates a form of bell music which is cont ...

Permutation (music) In music, a permutation (order) of a set is any ordering of the elements of that set. A specific arrangement of a set of discrete entities, or parameters, such as pitch, dynamics, or timbre. Different permutations may be related by transforma ...

Games

* Faro shuffle *

Fifteen puzzle The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle having 15 square tiles numbered 1–15 in a frame that is 4 tiles high and 4 tiles wide, leaving one unoccupied tile position ...

Shuffling Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome. __TOC__ Techniques Over ...

Permutations In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...