|
List Of Permutation Topics
This is a list of topics on mathematical permutations. Particular kinds of permutations *Alternating permutation *Circular shift *Cyclic permutation *Derangement *Even and odd permutations—see Parity of a permutation *Josephus permutation *Parity of a permutation *Separable permutation *Stirling permutation *Superpattern *Transposition (mathematics) * Unpredictable permutation Combinatorics of permutations *Bijection *Combination *Costas array *Cycle index *Cycle notation *Cycles and fixed points *Cyclic order *Direct sum of permutations *Enumerations of specific permutation classes *Factorial **Falling factorial *Permutation matrix **Generalized permutation matrix *Inversion (discrete mathematics) *Major index *Ménage problem *Permutation graph *Permutation pattern *Permutation polynomial *Permutohedron *Rencontres numbers *Robinson–Schensted correspondence *Sum of permutations: **Direct sum of permutations ** Skew sum of permutations *Stanley–Wilf conjecture *Sym ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutations are used in almost every branch of mathematics, and in many other fields of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 . The corresponding cycle of ''π'' is written as ( ''c''1 ''c''2 ... ''c''''n'' ); this expression is not unique since ''c''1 can be chosen to be any element of the orbit. The size of the orbit is called the length of the corresponding cycle; when , the single element in the orbit is called a fixed point of the permutation. A permutation is determined by giving an expression for each of its cycles, and one notation for permutations consist of writing such expressions one after another in some order. For example, let : \pi = \begin 1 & 6 & 7 & 2 & 5 & 4 & 8 & 3 \\ 2 & 8 & 7 & 4 & 5 & 3 & 6 & 1 \end = \begin 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 4 & 1 & 3 & 5 & 8 & 7 & 6 \end be a permutation that maps 1 to 2, 6 to 8, etc. Then one may w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are closely related to the Chebyshev polynomials, provide examples. Over a finite field, every function, so in particular every permutation of the elements of that field, can be written as a polynomial function. In the case of finite rings Z/''n''Z, such polynomials have also been studied and applied in the interleaver component of error detection and correction algorithms. Single variable permutation polynomials over finite fields Let be the finite field of characteristic , that is, the field having elements where for some prime . A polynomial with coefficients in (symbolically written as ) is a ''permutation polynomial'' of if the function from to itself defined by c \mapsto f(c) is a permutation of . Due to the finiteness of , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number pi), then π is said to ''contain'' σ as a ''pattern'' if some subsequence of the digits of π has the same relative order as all of the digits of σ. For instance, permutation π contains the pattern 213 whenever π has three digits ''x'', ''y'', and ''z'' that appear within π in the order ''x''...''y''...''z'' but whose values are ordered as ''y'' < ''x'' < ''z'', the same as the ordering of the values in the permutation 213. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition. Definition and characterization If \rho = (\sigma_1,\sigma_2,...,\sigma_n) is any permutation of the numbers from 1 to n, then one may define a permutation graph from \sigma in which there are n vertices v_1, v_2, ..., v_n, and in which there is an edge v_i v_j for any two indices i and j for which i\sigma_j. That is, two indices i and j determine an edge in the permutation graph exactly when they determine an inversion in the permutatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 next to his or her partner. This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is :12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... . Mathematicians have developed formulas and recurrence equations for computing these numbers and related sequences of numbers. Along with their applications to etiquette and knot theory, these numbers also have a graph theoretic interpretation: they count the numbers of matchings and Hamiltonian cycles in certain families of graphs. Touchard's formula Let ''M''''n'' denote the number of seating arrangements for ''n'' c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 example, if ''w'' is given in one-line notation by ''w'' = 351624 (that is, ''w'' is the permutation of such that ''w''(1) = 3, ''w''(2) = 5, etc.) then ''w'' has descents at positions 2 (from 5 to 1) and 4 (from 6 to 2) and so maj(''w'') = 2 + 4 = 6. This statistic is named after Major Percy Alexander MacMahon who showed in 1913 Events January * January 5 – First Balkan War: Battle of Lemnos (1913), Battle of Lemnos – Greek admiral Pavlos Kountouriotis forces the Turkish fleet to retreat to its base within the Dardanelles, from which it will not ven ... that the distribution of the major index on all permutations of a fixed length is the same as the distribution of inversions. That is, the number of permutations ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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). The inversion is indicated by an ordered pair containing either the places (i, j) or the elements \bigl(\pi(i), \pi(j)\bigr). The inversion set is the set of all inversions. A permutation's inversion set using place-based notation is the same as the inverse permutation's inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged. Inversions are usually defined for permutations, but may also be defined for sequences:Let S be a sequence (or multiset permutation). If i S(j), either the pair ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 nonzero entry must be 1, in a generalized permutation matrix the nonzero entry can be any nonzero value. An example of a generalized permutation matrix is :\begin 0 & 0 & 3 & 0\\ 0 & -7 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & \sqrt2\end. Structure An invertible matrix ''A'' is a generalized permutation matrix if and only if it can be written as a product of an invertible diagonal matrix ''D'' and an (implicitly invertible) permutation matrix ''P'': i.e., :A = DP. Group structure The set of ''n'' × ''n'' generalized permutation matrices with entries in a field ''F'' forms a subgroup of the general linear group GL(''n'', ''F''), in which the group of nonsingular diagonal matrices Δ(''n'', ''F'') forms a normal subgroup ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 , represents a permutation of elements and, when used to multiply another matrix, say , results in permuting the rows (when pre-multiplying, to form ) or columns (when post-multiplying, to form ) of the matrix . Definition Given a permutation of ''m'' elements, :\pi : \lbrace 1, \ldots, m \rbrace \to \lbrace 1, \ldots, m \rbrace represented in two-line form by :\begin 1 & 2 & \cdots & m \\ \pi(1) & \pi(2) & \cdots & \pi(m) \end, there are two natural ways to associate the permutation with a permutation matrix; namely, starting with the ''m'' × ''m'' identity matrix, , either permute the columns or permute the rows, according to . Both methods of defining permutation matrices appear in the literature and the properties expressed in one representation can be easily converted to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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) \,. \end The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, (A reprint of the 1950 edition by Chelsea Publishing Co.) rising sequential product, or upper factorial) is defined as :\begin x^ = x^\overline &= \overbrace^ \\ &= \prod_^n(x+k-1) = \prod_^(x+k) \,. \end The value of each is taken to be 1 (an empty product) when . These symbols are collectively called factorial powers. The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation , where is a non-negative integer. It may represent ''either'' the rising or the falling factorial, with different articles and authors using different conventions. Pochhammer himself actually used with yet another meaning, namely ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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) \times (n-3) \times \cdots \times 3 \times 2 \times 1 \\ &= n\times(n-1)!\\ \end For example, 5! = 5\times 4! = 5 \times 4 \times 3 \times 2 \times 1 = 120. The value of 0! is 1, according to the convention for an empty product. Factorials have been discovered in several ancient cultures, notably in Indian mathematics in the canonical works of Jain literature, and by Jewish mystics in the Talmudic book '' Sefer Yetzirah''. The factorial operation is encountered in many areas of mathematics, notably in combinatorics, where its most basic use counts the possible distinct sequences – the permutations – of n distinct objects: there In mathematical analysis, factorials are used in power series for the exponential functi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
