HomePage | Recent Changes | Preferences | Receive an article a day!
You can edit this page right now!
In combinatorics, a permutation is a sequence of elements in which no element appears more than once. In a sequence, unlike in a set, the order in which the elements are written down matters. Suppose you have a total of n distinct objects at your disposal and you want to create permutations of k elements selected from those n, where k≤n.
In how many ways can that be done?
- We can select the first member of the list in n ways because there are n distinct elements.
- The second member of the list can be filled in (n-1) ways since we have used up one of the n elements already.
- The third member can be filled in (n-2) ways since 2 have been used already.
- This pattern continues until there are k names on the list. This means that the last member can be filled in (n-k+1)'' ways.
Summarizing, we find that a total of
- n * (n-1) * (n-2) * ... * (n-k+1)
different permutations of k objects, taken from a pool of n objects, exist. If we denote this number
by P(n, k) and use the factorial notation, we can write
- P(n, k) = n! / (n-k)!
In abstract algebra and other fields, the term permutation is usually reserved for a bijective map from a finite set to itself.
There are two main notations for such permutations:
- one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row:
1 2 3 4 5
2 5 4 3 1
- or one can write the cycles induced by the permutation; that is, one takes any element (say 1); then the element the first one is being sent to (here 2); then the element this one is sent to (here 5), and so on, until one comes back to the first. This is a cycle. The next cycle begins with any other element not considered till now, until every element appears in a cycle. So the previous permutation has cycle form (1 2 5)(3 4). Of course, the same permutation could be written as (4 3)(2 5 1), or any other variant.
Two permutations of a set of n elements (often, {1, 2, 3, ..., n}) can be composed, i.e. applied successively to the set. For instance, if a = (125)(34), and b = (13)(2)(45), applying b after a maps 1 to 2, and then to itself; 2 to 5 to 4; 3 to 4 to 5, and so on. So composing b and a gives ba = (124)(35). It is a matter of notation whether applying a and then b is to be denoted by ba (as here) or by ab: the first convention agrees with a functional notation (ba(2) meaning b(a(2)) ); the second one with an exponential notation (2ab = (2a)b).
Under this operation of composition, all the permutations of a set, or a suitable set of them, form a mathematical group, called a permutation group.
See also Combinations.
HomePage | Recent Changes | Preferences | Receive an article a day!
You can edit this page right now! It's a free, community project
Edit text of this page | View other revisions
Last edited November 24, 2001 1:24 pm (diff)