In several fields of mathematics the term permutation is used with different but closely related meanings. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and They all relate to the notion of mapping the elements of a set to other elements of the same set, i. In Mathematics, the elements or members of a set (or more generally a class) are all those objects which when collected together make up the e. , exchanging (or "permuting") elements of a set.

Contents 1 Definitions 1.1 In combinatorics 1.2 In group theory 2 Counting permutations 3 Permutations in group theory 4 Notation 5 Product and inverse of permutations 6 Special permutations 7 Permutations in computing 8 Numbering permutations 8.1 Algorithms to generate permutations 8.1.1 Unordered generation 8.1.2 Lexicographical order generation 9 Software and hardware implementations 9.1 Calculator functions 9.2 Spreadsheet functions 10 See also 11 Notes 12 References 13 External links

Definitions

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

In combinatorics

In combinatorics, a permutation is usually understood to be a sequence containing each element from a finite set once, and only once. Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects In Mathematics, a sequence is an ordered list of objects (or events The concept of sequence is distinct from that of a set, in that the elements of a sequence appear in some order: the sequence has a first element (unless it is empty), a second element (unless its length is less than 2), and so on. In contrast, the elements in a set have no order; {1, 2, 3} and {3, 2, 1} are different ways to denote the same set.

However, there is also a traditional more general meaning of the term "permutation" used in combinatorics. In this more general sense, permutations are those sequences in which, as before, each element occurs at most once, but not all elements of the given set need to be used.

For a related notion in which the ordering of the selected elements form a set, for which the ordering is irrelevant, see Combination. In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set

In group theory

In group theory and related areas, the elements of a permutation need not be arranged in a linear order, or indeed in any order at all. Group theory is a mathematical discipline the part of Abstract algebra that studies the Algebraic structures known as groups. In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation Under this refined definition, a permutation is a bijection from a finite set onto itself. In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2. This allows for the definition of groups of permutations; see Permutation group. In Mathematics, a permutation group is a group G whose elements are Permutations of a given set M, and whose group operation

Counting permutations

In this section only, the traditional definition from combinatorics is used: a permutation is an ordered sequence of elements selected from a given finite set, without repetitions, and not necessarily using all elements of the given set. For example, given the set of letters {C, E, G, I, N, R}, some permutations are RING, RICE, NICER, REIGN and CRINGE, but also RNCGI – the sequence need not spell out an existing word. ENGINE, on the other hand, is not a permutation, because it uses the elements E and N twice.

If n  denotes the size of the set – the number of elements available for selection – and only permutations are considered that use all n  elements, then the total number of possible permutations is equal to n!, where "!" is the factorial operator. Definition The factorial function is formally defined by n!=\prod_{k=1}^n k This can be shown informally as follows. In constructing a permutation, there are n  possible choices for the first element of the sequence. Once it has been chosen, n − 1 elements are left, so for the second element there are only n − 1 possible choices. For the first two elements together, that gives us

n × (n − 1) possible permutations.

For selecting the third element, there are then n − 2 elements left, giving, for the first three elements together,

n × (n − 1) × (n − 2) possible permutations.

Continuing in this way until there are only 2 elements left, there are 2 choices, giving for the number of possible permutations consisting of n − 1 elements:

n × (n − 1) × (n − 2) × . . . × 2.

The last choice is now forced, as there is exactly one element left. In a formula, this is the number

n × (n − 1) × (n − 2) × . . . × 2 × 1

(which is the same as before because the factor 1 does not make a difference). This number is, by definition, the same as n!.

In general the number of permutations is denoted by P(n, r), _nP_r, or sometimes , where:

• n  is the number of elements available for selection, and
• r  is the number of elements to be selected (0 ≤ r ≤ n).

For the case where r = n  it has just been shown that P(n, n) = n!. The general case is given by the formula:

As before, this can be shown informally by considering the construction of an arbitrary permutation, but this time stopping when the length r  has been reached. The construction proceeds initially as above, but stops at length r.   The number of possible permutations that has then been reached is:

P(n, r) = n × (n − 1) × (n − 2) × . . . × (n − r + 1).

So:

n! = n × (n − 1) × (n − 2) × . . . × 2 × 1

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

     = P(n, r) × (n − r) × . . . × 2 × 1

     = P(n, r) × (n − r)!.

But if n! = P(n, r) × (n − r)!, then P(n, r) = n! / (n − r)!.

For example, if there is a total of 10 elements and we are selecting a sequence of three elements from this set, then the first selection is one from 10 elements, the next one from the remaining 9, and finally from the remaining 8, giving 10 × 9 × 8 = 720. In this case, n = 10 and r = 3. Using the formula to calculate P(10,3),

In the special case where n = r  the formula above simplifies to:

The reason why 0! = 1 is that 0! is an empty product, which always equals 1. In Mathematics, an empty product, or nullary product, is the result of multiplying no numbers

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.

Since it may be impractical to calculate n! if the value of n  is very large, a more efficient algorithm is to calculate:

P(n, r) = n × (n − 1) × (n − 2) × . . . × (n − r + 1).

Other, older notations include ⁿP_r, P_n,r, or _nP_r. A common modern notation is (n)_r which is called a falling factorial. In Mathematics, the Pochhammer symbol (x_{n}\ introduced by Leo August Pochhammer, represents either the rising or the falling However, the same notation is used for the rising factorial (also called Pochhammer symbol)

n(n + 1)(n + 2)⋯(n + r − 1)r. In Mathematics, the Pochhammer symbol (x_{n}\ introduced by Leo August Pochhammer, represents either the rising or the falling In Mathematics, the Pochhammer symbol (x_{n}\ introduced by Leo August Pochhammer, represents either the rising or the falling

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

Permutations in group theory

As explained in a previous section, in group theory the term permutation (of a set) is reserved for a bijective map (bijection) from a finite set onto itself. In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property 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.

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:

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. In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property 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⁻¹ of {1,…,n} is a morphism from the symmetric group of E into that of {1,…,n}, see below. The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function In Mathematics, a morphism is an abstraction derived from structure-preserving mappings between two Mathematical structures The study of morphisms and In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying )

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. Let S be a set A cycle is a Permutation ( bijective function of a set onto itself such that there exist distinct elements a_1 a_2\ldotsa_k 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. Let S be a set A cycle is a Permutation ( bijective function of a set onto itself such that there exist distinct elements a_1 a_2\ldotsa_k In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. 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).

Each cycle (x₁ x₂ … x_L) stands for the permutation that maps x_i on x_i+1 (i=1…L−1) and x_L on x₁, and leaves all other elements invariant. L is called the length of the cycle. Since these cycles have by construction disjoint supports (i. In Mathematics, the support of a function is the set of points where the function is not zero or the closure of that set e. they act non-trivially on disjoint subsets of E), they do commute (for example, (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 (up to cyclic change; see also cycles and fixed points). 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

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 does not include cycles of length 1.

Cycles of length two are called transpositions; such permutations merely exchange the place of two elements. In informal language a transposition is a function that swaps two elements of a set (Conversely, a matrix transposition is itself an important example of a permutation. In-place matrix transposition, also called in-situ matrix transposition, is the problem of transposing an N \times M matrix In-place )

Product and inverse of permutations

Main article: Symmetric group

One can define the product of two permutations as follows. In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying If we have two permutations, P and Q, the action of first performing P and then Q will be the same as performing some single permutation R. The product of P and Q is then defined to be that permutation R. Viewing permutations as bijections, the product of two permutations is thus the same as their composition as functions. In Mathematics, a composite function represents the application of one function to the results of another There is no universally agreed notation for the product operation between permutations, and depending on the author a formula like PQ may mean either P ∘ Q or Q ∘ P. Since function composition is associative, so is the product operation on permutations: (P ∘ Q) ∘ R = P ∘ (Q ∘ R). In Mathematics, associativity is a property that a Binary operation can have

Likewise, since bijections have inverses, so do permutations, and both P ∘ P⁻¹ and P⁻¹ ∘ P are the "identity permutation" (see below) that leaves all positions unchanged. In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property In Mathematics, if &fnof is a function from A to B then an inverse function for &fnof is a function in the opposite direction from B Thus, it can be seen that permutations form a group. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element

As for any group, there is a group isomorphism on permutation groups, obtained by assigning to each permutation its inverse, and this isomorphism is an involution, giving a dual view on any abstract result. In Abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in Since (P ∘ Q)⁻¹ = Q⁻¹ ∘ P⁻¹, from an abstract point of view it is immaterial whether PQ represents "P before Q" or "P after Q". For concrete permutations, the distinction is, of course, quite material.

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. In Mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that Conversely, a permutation which changes the position of all elements (no element is mapped to itself) is called a derangement. In combinatorial Mathematics, a derangement is a Permutation in which none of the elements of the set appear in their original positions

If one has some permutation, called P, one may describe a permutation, written P⁻¹, which undoes the action of applying P. In essence, performing P then P⁻¹ 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. It is computed by exchanging each number and the number of the place which it occupies.

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). In Mathematics, the Permutations of a Finite set (ie the bijective mappings from the set to itself fall into two classes of equal size the even An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. In Mathematics, the Permutations of a Finite set (ie the bijective mappings from the set to itself fall into two classes of equal size the even It can be shown that every permutation is either odd or even and can't be both.

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=(i₁ i₂ … i_n) and a permutation P, then PQP⁻¹ = (P(i₁) P(i₂) … P(i_n)).

We can also represent a permutation in matrix form; the resulting matrix is known as a permutation matrix. In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally In Mathematics, in Matrix theory, a permutation matrix is a square (01-matrix that has exactly one entry 1 in each row and each column and 0's 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

1, 2, …, n

assigned to variables

x₁, x₂, …, x_n. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Computer science the assignment statement sets or re-sets the value stored in the storage location(s denoted by a Variable Name.

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. In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and In Computer science, imperative programming is a Programming paradigm that describes computation in terms of statements that change a program state The mathematics convention is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In Mathematics, a composite function represents the application of one function to the results of another In the assignment language a substitution is an instruction to switch round the values assigned, simultaneously; a well-known problem.

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. In Combinatorics, factoradic is a specially constructed number system

Algorithms to generate permutations

Unordered generation

For every number k, with 0 ≤ k < n!, the following algorithm generates a unique permutation of the initial sequence s_j, j=1…n:

 function permutation(k, s) {
     for j= 2 to length(s) {
        k:= k/ (j-1);        // integer division cuts off the remainder
        swap s[(k mod j)+ 1] with s[j];
     }
     return s;
 }

The first line in the for loop is constructing the Factorial base representation of k -- the important thing here is that for each k, it generates a unique corresponding sequence of n integers where the first number is in {0,1}, the second is in {0,1,2}, etc. In Combinatorics, factoradic is a specially constructed number system Thus what the second line is doing is , at each step, swapping the jth element with one of the elements that are currently before it. If we consider the swaps in reverse order, we see that it implements a backwards Selection sort, first putting the nth element in the correct place, then the n-1st, etc. Selection sort is a Sorting algorithm, specifically an in-place Comparison sort. Since there is exactly one way to selection sort a permutation, this algorithm generates a unique permutation for each choice of k.

The Fisher-Yates shuffle is based on the same principle as this algorithm. The Fisher-Yates shuffle, named after Ronald Fisher and Frank Yates, also known as the Knuth shuffle, after Donald Knuth, is an Algorithm

Lexicographical order generation

For every number k, with 0 ≤ k < n!, the following algorithm generates the corresponding lexicographical permutation of the initial sequence s_j, j= 1…n:

 function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- 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 result of a division. For example when dividing 6 by 3 the quotient is 2 while 6 is called the dividend, and 3 the In Arithmetic, when the result of the division of two Integers cannot be expressed with an integer Quotient, the remainder is the amount "left In Arithmetic, when the result of the division of two Integers cannot be expressed with an integer Quotient, the remainder is the amount "left
• s[n] denotes the nth element of sequence s.

Software and hardware implementations

Calculator functions

Most calculators have a built-in function for calculating the number of permutations, called nPr or PERM on many. A calculator is device for performing mathematical calculations distinguished from a Computer by having a limited problem solving ability and an interface optimized for interactive The permutations function is often only available through several layers of menus; how to access the function is usually indicated in the documentation for calculators that support it.

Spreadsheet functions

Most spreadsheet software also provides a built-in function for calculating the number of permutations, called PERMUT in many popular spreadsheets. A spreadsheet is a Computer application that simulates a paper worksheet Apple's Numbers software notably does not currently include such a function. Apple Inc, ( formerly Apple Computer Inc, is an American Multinational corporation with a focus on designing and manufacturing Consumer electronics Numbers is a Spreadsheet application developed by Apple Inc as part of the IWork productivity suite alongside Keynote and Pages. ^[1]

See also

Notes

References

• Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
• Donald Knuth. Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer 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. Donald Ervin Knuth (kəˈnuːθ (born 10 January 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer 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.

External links

• A review of permutations from plainmath.net
• 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)
• Web-based calculator of permutations and combinations

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic