Permutations appear often enough that it's worth being able to write them down. There are two popular forms you may see, each useful for different purposes. You can calculate the products (compositions; see above) of permutations with each form quite easily.

Permutations can be on any set consisting of `n` elements. For clarity, we adopt here the usual convention of permuting the set {1,...,`n`}.

#### The direct representation

Recall that a permutation is merely a function {1,...,`n`}→{1,...,`n`} which is one to one and onto. The first way to write down a permutation merely lists the value of the function at each element. For instance, the permutation π(1)=5, π(2)=1, π(3)=4, π(4)=3, π(5)=2 can be written down as

/ 1 2 3 4 5 \
\ 5 1 4 3 2 /

Round parentheses should appear at each side, but don't, due to the limitations of my ASCII art sk111z. Also, sometimes all spaces will be omitted.
To multiply two permutations in this form, trace the value of each argument through each permutation, *going from right to left*. For instance,

/ 1 2 3 4 5 \ / 1 2 3 4 5 \ _ / 1 2 3 4 5 \
\ 5 1 4 3 2 / \ 5 4 1 2 3 / - \ 2 3 5 1 4 /

Think "

*1 goes to 5, and 5 goes to 2; 2 goes to 4, and 4 goes to 3; ...*".

To *invert* a permutation written in this form, just swap the top and bottom rows, and re-sort by the top row.

#### The disjoint cycles representation

A nicer way is to write down each permutation as a product of disjoint cycles. A cycle (b_{1} ... b_{j}) is the permutation translating b_{1} to b_{2}, b_{2} to b_{3}, ..., and b_{j} to b_{1}. Cycles are disjoint if they affect different elements. It turns out you can write any permutation in this manner. Note that disjoint cycles commute, so the above is fully specified. We omit any fixed points of the permutation; these could appear as single element cycles "(6)", but writing them down adds nothing. For instance, the first permutation is

(152)(34)

Here, we have omitted the spaces between the elements. Of course, this only works if we require no two digit elements.

Multiplication proceeds as before: step each element through each cycle, going *from right to left* as before. It makes sense to "chain" the elements together, so we can immediately write down a whole cycle. After finishing one cycle, we start the next by considering the first element which has not yet appeared. The previous multiplication could be written as

(152)(34)(153)(24) = (12354)

("1 goes to 5, and 5 goes to 2; 2 goes to 4, and 4 goes to 3; 3 goes to 1, and 1 goes to 5; 5 goes to 3, and 3 goes to 4; 4 goes to 2, and 2 goes to 1.") Note that the final step -- showing that 4 goes to 1 -- was inevitable; it's still a good idea to perform it, as a safety check.

The cycle representation is very concise, and gives a good "feel" for the permutation. It also has a nice property: to conjugate a cycle representation by some permutation (i.e. to compute τπτ^{-1}; note that some authorities would call this conjugation by τ^{-1}), apply the permutation τ to the elements of the permutation π *as written down in the cycles*. Thus to conjugate (123) by (142),

(142)(123)(142)^{-1} = (134)

(Replace "1" by "4" and "2" by "1" in "(123)", to get "(413)"; rewrite the cycle as "(134)" so as to start with a "1").

Note that the reason this works (or alternatively, a direct conseuqence from the easy proof that it does) is that all conjugations have the same "cycle structure". In fact, the Polish "bombes", and later Alan Turing and others' methods for breaking Enigma, relied precisely on this fact; they called "cycles" by the name "chains".

To invert a permutation, invert each of its cycles. To invert a cycle, write its elements backwards. And to make things nicer, rotate the representation of each cycle to start with its lowest element.