FACTOID # 23: Wisconsin has more metal fabricators per capita than any other state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Permutation" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Permutation

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation.[1] For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: "4, 5, 6, 1, 2, 3". In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ... A numeral is a symbol or group of symbols that represents a number. ...


The general concept of permutation can be defined more formally in different contexts:

  • In set theory, a permutation is an ordered sequence containing each symbol from a set once, and only once. Neither "1, 2, 2, 3, 4, 5, 6" nor "1, 2, 4, 5, 6" are permutations of the sequence "1, 2, 3, 4, 5, 6". A permutation is distinct from a set or combination, in that the ordering of elements in a set is not considered relevant. In other words, the set-theoretic definition of permutation is that of a one-to-one correspondence, or bijection, of labeled elements with "positions" or "places" which are arranged in a straight line.
  • In abstract algebra and related areas, the elements of permutation may not be arranged in a linear order, or indeed in any order at all. Under this refined definition, a permutation is a bijection from a finite set, X, onto itself. This allows for the definition of groups of permutations; see permutation group.
  • In combinatorics, the term permutation also has a traditional meaning which includes ordered lists without repetition and where one or more elements from the list are omitted from the distinguishable orderings; for example, a permutation of "1,2,4,3" with "5" and "6" omitted.

Contents

Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ... A bijective function. ... A line, or straight line, is, roughly speaking, an (infinitely) thin, (infinitely) long, straight geometrical object, i. ... Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... A bijective function. ... In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ...

Counting permutations

In this section only, the traditional definition is used: a permutation is an ordered list without repetitions, perhaps missing some (n-r) elements. The number of permutations of a sequence is:

P_r^n = frac{n!}{(n-r)!}

where:

  • r is the size of each permutation,
  • n is the size of the sequence from which elements are permuted, and
  • ! is the factorial operator.

For example, if we have a total of 10 elements, the integers {1, 2 .. 10}, one sequence of three elements from this set would be (5, 3, 4). In this case, n = 10 and r = 3. To find out how many unique sequences we can find, we need to calculate P(10,3) = 10! / (10-3)! = (1·2·3·4·5·6·7·8·9·10) / (1·2·3·4·5·6·7) = 8·9·10 = 720 For factorial rings in mathematics, see unique factorisation domain. ...


In the example given in the header of this article, with 6 integers {1..6}, this would be; P(6,6) = 6! / (6-6)! = (1·2·3·4·5·6·) / 0! = 720 / 1 = 720


Other, older notations include nPr, Pn,r, or nPr. A common modern notation is (n)r which is called a falling factorial. However, the same notation is used for the rising factorial (also called Pochhammer symbol) In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial To distinguish the two, the notations and are commonly used...

n(n + 1)(n + 2)...(n + r − 1)r.

With the rising factorial notation, the number of permutations is (nr + 1)r.


Abstract algebra

As explained in a previous section, in abstract algebra and other mathematical fields, the term permutation (of a set) is now reserved for a bijective map (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, …, 10} to itself. Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... A bijective function. ...


Notation

There are two main notations for such permutations. In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:

begin{bmatrix} 1 & 2 & 3 & 4 & 5  2 & 5 & 4 & 3 & 1end{bmatrix}

stands for the permutation s of the set {1,2,3,4,5} defined by s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1.


If we have a finite set E of n elements, it is by definition in bijection with the set {1,...,n}, where this bijection f corresponds just to numbering the elements. Once they are numbered, we can identify the permutations of the set E with permutations of the set {1,...,n}. (In more mathematical terms, the function that maps a permutation s of E to the permutation f o s o f-1 of {1,...,n} is a morphism from the symmetric group of E into that of {1,...,n}, see below.) A bijective function. ... In mathematics, a morphism is an abstraction of a structure-preserving process between two mathematical structures. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ...


Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. This is referred to as the permutation's decomposition in a product of disjoint cycles. It works as follows: starting from one element x, we write the sequence (x s(x) s²(x) ...) until we get back the starting element (at which point we close the parenthesis without writing it for a second time). This is called the cycle associated to x's orbit following s. Then we take an element we did not write yet and do the same thing, until we have considered all elements. In the above example, we get: s = (1 2 5) (3 4). Let be a set. ... Let be a set. ... In mathematics, groups are often used to describe symmetries of objects. ...


Each cycle (x1 x2 ... xL) stands for the permutation that maps xi on xi+1 (i=1...L-1) and xL on x1, and leaves all other elements invariant. L is called the length of the cycle. Since these cycles have by construction disjoint support)s (i.e. they act non-trivially on disjoint subsets of E), they do commute (i.e. (1 2 5) (3 4) = (3 4)(1 2 5)): the order of the cycles in the (composition) product does not matter, while the order of the elements in each cycles does matter, of course (up to cyclic change, see also cycles and fixed points). In mathematics, two sets are said to be disjoint if they have no element in common. ... In mathematics, the support of a real-valued function f on a set X is sometimes defined as the subset of X on which f is nonzero. ... Look up Up to on Wiktionary, the free dictionary In mathematics, the phrase up to xxxx indicates that members of an equivalence class are to be regarded as a single entity for some purpose. ... In combinatorial mathematics, a cycle of length n of a permutation P over a set S is a subset { c1, ..., cn } of S on which the permutation P acts in the following way: P(ci) = ci + 1 for i = 1, ..., n âˆ’ 1, and P(cn) = c1. ...


Obviously, a 1-cycle (cycle of length 1) is the same as fixing the element contained in it, so there is no use in writing it explicitly. Some authors' definition of a cycle do not include cycles of length 1.


Cycles of length two are called transpositions; such permutations merely exchange ("the place of") two elements. (Conversely, a matrix transposition is itself an important example of a permutation.) In informal language, a transposition is a function that swaps two elements of a set. ... In-place matrix transposition, also called in-situ matrix transposition, refers to the problem of transposing an matrix in-place in computer memory: with additional storage, or at most with additional storage much less than . ...


Special permutations

If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the identity permutation because it acts as an identity function. An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ...


If one has some permutation, called P, one may describe a permutation, written P−1, which undoes the action of applying P. In essence, performing P then P−1 is equivalent to performing the identity permutation. One always has such a permutation since a permutation is a bijective map. Such a permutation is called the inverse permutation. Look up inverse in Wiktionary, the free dictionary. ...


One can define the product of two permutations. If we have two permutations, P and Q, the action of performing P and Q will be the same as performing some other permutation, R, itself. Note that R could be P or Q. The product of P and Q is defined to be the permutation R. For more, see symmetric group and permutation group. In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ... In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). ...


An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both. In mathematics, the permutations of a finite set (i. ... In mathematics, the permutations of a finite set (i. ...


One theorem regarding the inverse permutation is the effect of a conjugation of a permutation by a permutation in a permutation group. If we have a permutation Q=(i1 i2 ... in) and a permutation P, then PQP-1 = (P(i1) P(i2) ... P(in)).


We can also represent a permutation in matrix form - the resulting matrix is known as a permutation matrix. Look up matrix in Wiktionary, the free dictionary. ... In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. ...


Permutations in computing

Some of the older textbooks look at permutations as assignments, as mentioned above. In computer science terms, these are assignment operations, with values Computer scaence, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In most imperative computer programming languages, the assignment operation is one of the basic operations. ...

1, 2, ..., n

assigned to variables

x1, x2, ..., xn.

Each value should be assigned only once.


The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem. Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. ... In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ... In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...


Numbering permutations

Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic of k one can quickly find the corresponding permutation. The factorial based radix or factoradic is a factorial based mixed radix numeral scheme: radix: 5! 4! 3! 2! 1! decimal: 120 24 6 2 1 In this numbering system, the rightmost digit may be 0 or 1, the next 0, 1, or 2, and so on. ...


Algorithm to generate permutations

For every number k (0 le k < n!) this following algorithm generates the corresponding permutation of the initial sequence left( s_j right)_{j=1}^n:

 function permutation(k, s) { var int factorial:= 1; for j = 2 to length(s) { factorial := factorial* (j-1); swap s[j - ((k / factorial) mod j)] with s[j]; } return s; } 

Notation

  • k / j denotes integer division of k by j, i.e. the integral quotient without any remainder, and
  • k mod j is the remainder following integer division of k by j.

In mathematics, a quotient is the end result of a division problem. ... In mathematics, the result of the division of two integers usually cannot be expressed with an integer quotient, unless a remainder —an amount left over— is also acknowledged. ... In mathematics, the result of the division of two integers usually cannot be expressed with an integer quotient, unless a remainder —an amount left over— is also acknowledged. ...

How to use with a calculator

Most calculators have an nPr key. In most advanced desktop calculators, however, the key is hidden. Example: in TI-83, press MATH, right three times, and press 2. For Casio graphing calculators, press OPTN, right once (F6), PROB (F3), nPr (F2). A calculator is a device for performing calculations. ... The TI-83 series graphing calculators are manufactured by Texas Instruments. ... Casio Computer Co. ... A typical graphing calculator. ...


Using spreadsheets

In most spreadsheets a function PERMUT(number,number chosen) allows calculation of permutations. Number is an integer that describes the number of objects. Number chosen is an integer that describes the number of objects in each permutation. Screenshot of a spreadsheet made with OpenOffice. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A...


References

  1. ^ For cases wherein the ordering of elements is irrelevant, compare combination and set.

Look up element in Wiktionary, the free dictionary. ... In combinatorial mathematics, a combination is an un-ordered collection of unique elements. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...

See also

In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ... In combinatorial mathematics, a combination is an un-ordered collection of unique elements. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ... In mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face, for an n-hour clock. ... A cyclic permutation is a permutation that shifts all elements of given ordered set by a fixed offset, with the elements shifted off the end inserted back at the beginning in the same order, i. ... In mathematics, the permutations of a finite set (i. ... The factorial based radix or factoradic is a factorial based mixed radix numeral scheme: radix: 5! 4! 3! 2! 1! decimal: 120 24 6 2 1 In this numbering system, the rightmost digit may be 0 or 1, the next 0, 1, or 2, and so on. ... A k-superpattern is a smallest combinatorial pattern that contains all k-subpatterns. ... In computer science, the Josephus permutation is defined as follows: Suppose n people are arranged in a circle and we are given a positive integer m < n. ... This is a list of topics on mathematical permutations. ... In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). ... Probability is the chance that something is likely to happen or be the case. ... A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. ... 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. ... A sorting network is a circuit with n input connections for data items to be presented in an arbitrary order, and n output connections on which the items are to be output in sorted order. ... In cryptography, a substitution cipher is a method of encryption by which units of plaintext are substituted with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ... In combinatorics, a branch of mathematics, the twelvefold way provides a unified framework for counting permutations, combinations and partitions. ... In mathematics, the symmetric group, Sn, has a poset structure given by the weak order of permutations, given by u&#8804;v if Inv(u) is a subset of Inv(v). ...

Further reading

  • Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
  • Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ...

External links

  • Many Common types of permutation and combination math problems, with detailed solutions
  • Permutations and Puzzles on Graphs
  • Free Permutation/Combination/Factorial Calculator (with source code)

  Results from FactBites:
 
PlanetMath: permutation (175 words)
A permutation can also be seen as a bijective function of a set into itself.
Using the function approach, it can be proved that any permutation can be expressed as a composition of disjoint cycles and also as composition of (not necessarily disjoint) transpositions.
This is version 3 of permutation, born on 2001-10-20, modified 2002-02-19.
Permutation - Wikipedia, the free encyclopedia (1473 words)
In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself.
An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2).
An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m