In general, a permutation is a rearrangement of objects. Frequently, a permutation is represented as an arrangement of the set \(\{1,2,\ldots , n\}\), where \(n\) is a positive integer called the size of the permutation. There are \(n!\) possible permutations of this set. For instance, the 6 permutations of the set \(\{1,2,3\}\) are \(\{1,2,3\}\), \(\{1,3,2\}\), \(\{2,1,3\}\), \(\{2,3,1\}\), \(\{3,1,2\}\), \(\{3,2,1\}\). A permutation \(\pi\) is a map, and we write \(\pi(x) = y\) if \(\pi\) sends the element \(x\) to the \(y\)th position.
A permutation \(\pi\) can be described using a variety of notations, several of which are seen in this applet:
- Matrix: A permutation matrix is a square \(n \times n\) matrix with exactly one entry of 1 in each row and in each column, where the entry in position \((i,j)\) is 1 if \(\pi(i) = j\). The remaining entries are zero.
- Two Line: The numbers 1 through \(n\) are listed in order from left to right, with \(\pi(i)\) written beneath \(i\) in the top row.
- One Line: A list of the numbers \(\pi(i)\) as \(i\) goes from 1 to \(n\). Note that the one line notation is the second row of the two line notation.
- Cycles: Suppose \(\pi\) sends \(x_1\) to \(x_2\), \(x_2\) to \(x_3\), and \(x_3\) back to \(x_1\). In this case, we say \(\pi\) has a 3-cycle, denoted \((x_1 \ \ x_2 \ \ x_3)\). We can write a permutation as a product of each of its cycles. Cycles of longer or shorter lengths are possible. The identity permutation on \(n\) letters being a product of \(n\) 1-cycles. The cycle notation is not unique; as long as the cycles are disjoint (that is, the same number does not appear in more than one cycle) their product commutes so they may be written in any order. Furthermore, each cycle can be written in multiple ways. For instance, the 3-cycle above could be written in 3 ways:
\[ (x_1 \ \ x_2 \ \ x_3) = (x_2 \ \ x_3 \ \ x_1) = (x_3 \ \ x_1 \ \ x_2) \]
- Diagrams: A permutation can be represented graphically in a variety of ways, one of which is displayed in this applet. A braid diagram is a two row diagram in which each number in the top row is connected to its image in the bottom row, and can be of use when counting the crossings of a permutation. In addition, the cycle diagram is shown. These are disjoint diagrams indicating which numbers appear in the same cycle, with arrows indicating the directions of the cycle. A cycle with only one number (a singleton cycle) indicates the permutation has a fixed point at that value.
A wide range of mathematical areas make use of permutations. Algebraists might study the symmetric group \(S_n\), whose elements are the permutations on \(n\) numbers. This group has identity \(\{1, 2, 3, \ldots, n\}\) and its operation is composition. Every permutation \(\pi\) has an inverse, defined by \(\pi^{-1}(j) =i\) if \(\pi(i) = j\).