Permutations

Arturo Arriaga
Dec 1, 2021
1 min read

Updated: Dec 16, 2021

A permutation is a bijective function f from a set X to itself. We represent permutations in cycle notation.

As an example, if X = {1, 2, 3, 4, 5}, the permutation (1345) represents the function where f (1) = 3, f (3) = 4, f(4) = 5, f(5) = 1, and f(2) = 2. A composition h = f g of two permutations is obtained by applying g first and then applying f to the result of g. In this class, we apply permutations from right to left: in other words, the permutation (12)(13) is equivalent to the permutation (132).

More details about permutations:

The inverse a1 of a permutation a is the permutation such that aa1 = a1a = I, where I is the identity permutation that maps every element back to itself.
The conjugate permutation of b with respect to a is aba1.
aba1 has the same cycle structure as b.
ab and ba have the same cycle structure.
An odd permutation is a permutation with an odd number of transpositions (a transposition is swap- ping two elements).
An even permutation has an even number of transpositions.