Difference between revisions of "Permutation"
Archimedes1 (talk | contribs) (→See also) |
(category) |
||
| Line 1: | Line 1: | ||
| − | + | A '''permutation''' of a [[set]] of <math>r</math> objects is any rearrangement (linear ordering) of the <math>r</math> objects. There are <math>r!</math> (the [[factorial]] of <math>r</math>) permutations of a set with <math>r</math> distinct objects. | |
| − | |||
| − | |||
| − | A '''permutation''' of a [[set]] of <math>r</math> objects is any rearrangement (linear ordering) of the <math>r</math> objects. There are <math> | ||
One can also consider permutations of [[infinite]] sets. In this case, a permutation of a set <math>S</math> is simply a [[bijection]] between <math>S</math> and itself. | One can also consider permutations of [[infinite]] sets. In this case, a permutation of a set <math>S</math> is simply a [[bijection]] between <math>S</math> and itself. | ||
| Line 17: | Line 14: | ||
A permutation in which no obect remains in the same place it started is called a [[derangement]]. | A permutation in which no obect remains in the same place it started is called a [[derangement]]. | ||
| − | ==Picking | + | ==Picking Ordered Subsets of a Set== |
An important question is how many ways to pick an <math>r</math>-element [[subset]] of a set with <math>n</math> [[element]]s, where order matters. To find how many ways we can do this, note that for the first of the <math>r</math> elements, we have <math>n</math> different objects we can choose from. For the second element, there are <math>n-1</math> objects we can choose, <math>n-2</math> for the third, and so on. In general, the number of ways to permute <math>r</math> objects from a set of <math>n</math> is given by | An important question is how many ways to pick an <math>r</math>-element [[subset]] of a set with <math>n</math> [[element]]s, where order matters. To find how many ways we can do this, note that for the first of the <math>r</math> elements, we have <math>n</math> different objects we can choose from. For the second element, there are <math>n-1</math> objects we can choose, <math>n-2</math> for the third, and so on. In general, the number of ways to permute <math>r</math> objects from a set of <math>n</math> is given by | ||
<math>P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}</math>. | <math>P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}</math>. | ||
| Line 25: | Line 22: | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Derangement]] | * [[Derangement]] | ||
| + | |||
| + | [[Category:Combinatorics]] | ||
| + | [[Category:Definition]] | ||
Revision as of 13:23, 8 December 2007
A permutation of a set of 
objects is any rearrangement (linear ordering) of the objects. There are 
(the factorial of ) permutations of a set with distinct objects.
One can also consider permutations of infinite sets. In this case, a permutation of a set 
is simply a bijection between and itself.
Notations
A given permutation of a finite set can be denoted in a variety of ways. The most straightforward representation is simply to write down what the permutation looks like. For example, the permutations of the set 
are 
and 
. We often drop the brackets and commas, so the permutation 
would just be represented by 
.
Another common notation is cycle notation.
The Symmetric Group
The set of all permutations of an 
-element set is denoted 
. In fact, forms a group, known as the Symmetric group, under the operation of permutation composition.
A permutation in which no obect remains in the same place it started is called a derangement.
Picking Ordered Subsets of a Set
An important question is how many ways to pick an -element subset of a set with elements, where order matters. To find how many ways we can do this, note that for the first of the elements, we have different objects we can choose from. For the second element, there are 
objects we can choose, 
for the third, and so on. In general, the number of ways to permute objects from a set of is given by
.
