Revision as of 17:08, 13 November 2006 by Mysmartmouth (talk | contribs)

This article is a stub. Help us out by expanding it.

A permutation of a set of $r$ objects is any rearrangement (linear ordering) of the $r$ objects. There are $\displaystyle r!$ (the factorial of $r$) permutations of a set with $r$ distinct objects.

One can also consider permutations of infinite sets. In this case, a permutation of a set $S$ is simply a bijection between $S$ and itself.


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 $\{1, 2, 3\}$ are $\{1,2,3\}, \{1, 3,2\}, \{2,1,3\}, \{2,3,1\},\{3,1,2\}$ and $\{3,2,1\}$. We often drop the brackets and commas, so the permutation $\{2,1,3\}$ would just be represented by $213$.

Another common notation is cycle notation.

The Symmetric Group

The set of all permutations of an $n$-element set is denoted $S_n$. In fact, $S_n$ 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 $r$-element subset of a set with $n$ elements, where order matters. To find how many ways we can do this, note that for the first of the $r$ elements, we have $n$ different objects we can choose from. For the second element, there are $n-1$ objects we can choose, $n-2$ for the third, and so on. In general, the number of ways to permute $r$ objects from a set of $n$ is given by $P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}$.

See also

Invalid username
Login to AoPS