# Category: Permutations

Stirling permutation
In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k (with two copies of each value from 1 to k) with the additional property that, fo
Ghost Leg
Ghost Leg (Chinese: 畫鬼腳), known in Japan as Amidakuji (阿弥陀籤, "Amida lottery", so named because the paper was folded into a fan shape resembling Amida's halo) or in Korea as Sadaritagi (사다리타기, literall
Bit-reversal permutation
In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , rep
100 prisoners problem
The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem, 100 numbered prisoners must find their own numbers in one of 100 drawers in order to survi
15 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
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 i
Transposition 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
Permutation automaton
In automata theory, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. Formally, a deterministic finite autom
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. T
Permutoassociahedron
In mathematics, the permutoassociahedron is an -dimensional polytope whose vertices correspond to the bracketings of the permutations of terms and whose edges connect two bracketings that can be obtai
Longest alternating subsequence
In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in altern
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 numb
Computing the permanent
In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of
Ring of symmetric functions
In algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in n indeterminates, as n goes to infinity. This ring
Young symmetrizer
In mathematics, a Young symmetrizer is an element of the group algebra of the symmetric group, constructed in such a way that, for the homomorphism from the group algebra to the endomorphisms of a vec
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 o
In-place matrix transposition
In-place matrix transposition, also called in-situ matrix transposition, is the problem of transposing an N×M matrix in-place in computer memory, ideally with O(1) (bounded) additional storage, or at
Tompkins–Paige algorithm
The Tompkins–Paige algorithm is a computer algorithm for generating all permutations of a finite set of objects.
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 box
In cryptography, a permutation box (or P-box) is a method of bit-shuffling used to permute or transpose bits across S-boxes inputs, retaining diffusion while transposing. In block ciphers, the S-boxes
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 t
Antisymmetrizer
In quantum mechanics, an antisymmetrizer (also known as antisymmetrizing operator) is a linear operator that makes a wave function of N identical fermions antisymmetric under the exchange of the coord
Order statistic
In statistics, the kth order statistic of a statistical sample is equal to its kth-smallest value. Together with rank statistics, order statistics are among the most fundamental tools in non-parametri
Telephone number (mathematics)
In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways n people can be connected by person-to-person telephone calls. These numbers also descri
Place-permutation action
In mathematics, there are two natural interpretations of the place-permutation action of symmetric groups, in which the group elements act on positions or places. Each may be regarded as either a left
Skew and direct sums 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,
Veronese bell ringing
Veronese bell ringing is a style of ringing church bells that developed around Verona, Italy from the eighteenth century. The bells are rung full circle (mouth uppermost to mouth uppermost), being hel
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
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 cycli
Zolotarev's lemma
In number theory, Zolotarev's lemma states that the Legendre symbol 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: where ε deno
Bender–Knuth involution
In algebraic combinatorics, a Bender–Knuth involution is an involution on the set of semistandard tableaux, introduced by , pp. 46–47) in their study of plane partitions.
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
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. Riche
Parastatistics
In quantum mechanics and statistical mechanics, parastatistics is one of several alternatives to the better known particle statistics models (Bose–Einstein statistics, Fermi–Dirac statistics and Maxwe
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 is a bijection. In case the ring is a finite field, the
Josephus problem
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
Mantel test
The Mantel test, named after Nathan Mantel, is a statistical test of the correlation between two matrices. The matrices must be of the same dimension; in most applications, they are matrices of interr
Lehmer code
In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of n numbers. It is an instance of a scheme for numbering permu
Transposition (mathematics)
No description available.
ELSV formula
In mathematics, the ELSV formula, named after its four authors , , , , is an equality between a Hurwitz number (counting ramified coverings of the sphere) and an integral over the moduli space of stab
Robinson–Schensted–Knuth correspondence
In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices A with non-negative integer entr
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.
Random number
In mathematics and statistics, a random number is either Pseudo-random or a number generated for, or part of, a set exhibiting statistical randomness.
Cayley's theorem
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of a symmetric group. More specifically, G is isomorphic to a subgroup of the
Boustrophedon transform
In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by an "addition" operation, implemented as if filling a triangular a
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
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
Permutation matrix
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say P, rep
Kendall tau distance
The Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are
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 Sn. Equivalently, g(n) is the larg
Pseudorandom permutation
In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the fam
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 {
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 co
Langford pairing
In combinatorial mathematics, a Langford pairing, also called a Langford sequence, is a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which the two 1s are one unit apart, the two
Rook polynomial
In combinatorial mathematics, a rook polynomial is a generating polynomial of the number of ways to place non-attacking rooks on a board that looks like a checkerboard; that is, no two rooks may be in
Superpermutation
In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every per
Stirling numbers of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is
Cycle notation
No description available.
Stirling number
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus
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.
Stirling numbers of the first kind
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according t
Rencontres numbers
In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points: in other words, par
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 algorith
Alternating permutation
In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set {1, 2, 3, ..., n} is a permutation (arrangement) of those numbers so that each entry is alternately greater
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
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
Derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no
List of permutation topics
This is a list of topics on mathematical permutations.
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 whi
Twelvefold way
In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combin
Permanent (mathematics)
In linear algebra, the permanent of a square matrix is a function of the matrix similar to the determinant. The permanent, as well as the determinant, is a polynomial in the entries of the matrix. Bot
Plain hunt
In method ringing, a branch of change ringing, the ringing pattern known as plain hunt is the simplest method of generating continuously changing sequences, and is a fundamental building-block of meth
Heap's algorithm
Heap's algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by
Circular permutation in proteins
A circular permutation is a relationship between proteins whereby the proteins have a changed order of amino acids in their peptide sequence. The result is a protein structure with different connectiv
Cyclic number
A cyclic number is an integer for which cyclic permutations of the digits are successive integer multiples of the number. The most widely known is the six-digit number 142857, whose first six integer
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 Rn can converge. It was proved by Paul Lévy in his first published pa
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, Kuznyech
Narayana number
In combinatorics, the Narayana numbers form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathematician T.
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
Immanant
In mathematics, the immanant of a matrix was defined by Dudley E. Littlewood and Archibald Read Richardson as a generalisation of the concepts of determinant and permanent. Let be a partition of an in
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 f0 and f1 if f0(x) = f1(y) = z. A pair of permutations f0 and
Golomb–Dickman constant
In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is (sequence in the OEIS) It is not known whether this constant is rational or i