# Permutations

The set of all permutations of \(n\) objects forms
a group \(S_n\) of order \(n!\). It is called the
\(n\)th *symmetric group*.

A permutation that interchanges \(m\) objects cyclically
is called *circular permutation* or a
*cycle* of degree \(m\). Denote the object
by the positive integers. Then the cycle that moves
1 to 2, 2 to 3, \(..., m-1\) to \(m\) and \(m\) to \(1\) is
written \((1 2 ... m)\).

Every permutation can be unique represented into cycles operating on disjoint sets.

**Example:**
\((1 2 3 4 5 6)^2 = (1 3 5)(2 4 6)\)

So we may write a given permutation \(P = C_1 ... C_r\) where
the \(C_i\) are cycles. Since cycles on disjoint sets commute,
we have \(P^m = C_1^m ... C_r^m\), and we see that the order
of a permutation is the lowest common multiple of the
orders of its component cycles. A permutation is *regular*
if all of its cycle are of the same degree.

Two permutations \(a, b \in S_n\) are *conjugate* or
*similar* if there exists \(t\in S_n\) with
\(b = t^{-1} a t\). Let \(a = C_1 ... C_r\) where the \(C_i\) are cycles.
Then the cycle decomposition of \(b\) is obtained by applying \(t\) to
the elements inside the brackets of the strings representing each cycle,
that is, if \(C_i = (a_1 a_2 ... a_m)\) then
\(t^{-1} C_i t = (t(a_1) t(a_2) ... t(a_m))\)
where \(t(a_i)\) represents the element \(t\) maps \(a_i\) to.

Let \(a\in S_n\), and write \(a = C_1 ... C_r\) such that
the cycles are arranged in non-decreasing order, that is, if
we write \(\mu_i\) for the cycle length of \(C_i\), then
\(1 \le \mu_1 \le ... \le \mu_r\), and \(\mu_1 +...+\mu_r = n\). Thus
every permutation is associated with a partition of \(n\) into positive
integers. Two permutations that belong to the same partition are said
to belong to the same *class* of \(S_n\).

It is clear that two permuations of \(S_n\) are conjugate if and only if they belong to the same class.

Now let us count how many partitions belong to a given class. Say a permutation has \(\alpha_i\) cycles of degree \(i\), so that \(\alpha_1 + 2 \alpha_2 + ... + n\alpha_n = n\). Then a set of nonnegative integers \(\{\alpha_1 ,..., \alpha_n\}\) determines a class which we shall denote \(\alpha\). When writing down the cycles, we need to use up \(n\) numbers, and there are \(n!\) ways to do this. But since for any \(i\), we may permute the \(i\)-cycles amongst themselves, we must divide by \(\alpha_1 ! ... \alpha_n !\) times. Lastly, a cycle of length \(i\) can be written in \(i\) different ways, so if \(h_\alpha\) denotes the number of permutations in the class \(\alpha\), we have

[Cauchy].

A 2-cycle is called a *transposition*.

Let \(x_1,...,x_n\) be indeterminates and consider the *product
of differences*

Then applying a permutation \(\pi \in S_n\) to the variables will either preserve this value or negate it. We write

A permutation \(\pi\) is said to be *even* if \(\zeta(\pi) = 1\),
and *odd* otherwise, that is, if \(\zeta(\pi) = {-1}\).
The function \(\zeta\) is called the *alternating character*
of \(S_n\).

**Theorem:** Let \(a,b \in S_n\). Then \(\zeta(a b) = \zeta(a)\zeta(b)\).

**Proof:** Write \(\Delta_\pi\) for \(\Delta(\pi(x_1,...,x_n))\).

Note all permutations of the same class have the same alternating character: by the theorem we have \(\zeta(b) \zeta(b^{-1}) = \zeta(1) = 1\), and \(\zeta(b^{-1}a b) = \zeta(a)\) after applying the theorem again.

**Theorem:** All transpositions are odd permutations.

**Proof:** The permutation \((1 2)\) negates the factor \((x_1 - x_2)\) in
\(\Delta\) but leaves the other factors unchanged, thus we have
\(\zeta((1 2)) = {-1}\). Then the results follows after using the
identities

Every permutation \(\pi\) can be written as a product of transpositions, because a cycle \((a_1 ... a_m)\) can be written as \((a_1 a_2)(a_1 a_3) ... (a_1 a_m)\). By the above theorem, the number of transpositions in such a representation is odd or even depending on whether \(\pi\) is odd or even.

Note \(S_n\) can be generated by the \(n-1\) transpositions \((1 2), (1 3),..., (1 n)\).

**Theorem:** In any group of permutations \(G\), either all or exactly
half the elements are even. The even permutations of \(G\) form a subgroup.

**Proof:**
It is clear that the even permutations form a subgroup.

If \(G\) contains no odd permutations, there is nothing to prove. Otherwise let \(q\in G\) be an odd permutation, so that \(\zeta{q} ={-1}\). Then as \(q G = G\), we have

Also, since \(\zeta\) is multiplicative we have

hence \(\zeta(g) = 0\), proving the result.

The set of all even permutation of degree \(n\) forms a group \(A_n\) of
order \(\frac{1}{2} n!\), called the *alternating group* of
degree \(n\).

Since \((1 i)(1 j) = (1 i j)\) for distinct \(1, i, j\), and since \((1 i j) = (1 2 j)(1 2 i)(1 2 j)\) we see that \(A_n\) may be generated from the \(n-2\) 3-cycles

**Cayley’s Theorem:** Let \(G = \{g_1,...,g_{|G|}\}\) be any group.
Each \(g_i \in G\) can be associated with the permutation of \(S_n\) that
takes \(g_j\) to \(g_j g_i\). The set of these permutations forms a subgroup
\(G'\) of \(S_n\), and \(G' \cong G\).

The permutation group \(G'\) associated with a group \(G\) is called the
*regular representation* of \(G\). In general, if an
abstract group \(G\) is isomorphic to some concrete mathematical group
(e.g. permutations, matrices) then we say we have a *faithful
representation* of \(G\).

A group of permutations \(G \subset S_n\)
is said to be *transitive* if
for every \(\alpha,\beta \in \{1,...,n\}\) there exists \(g\in G\) with
\(g(\alpha) = \beta\), that is, for any two objects, there exists a permutation
that maps one to the other.
Otherwise the group is *intransitive*.

**Example:**
\(\{(1), (1 2), (3 4), (1 2)(3 4)\}\)
is intransitive because
no permutations takes 1 to 3. It is isomorphic to the transitive group
\(\{ (1), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3) \}\).

Write \(G_\alpha\) for the subgroup of permutations of \(G\) that fix \(\alpha\).

**Theorem:** A group of permutations \(G \subset S_n\) is transitive if
and only if the subgroup \(G_1\) is of index \(n\) relative to \(G\).

**Proof:** If \(G\) is transitive, then there exists element

that map \(1\) to \(2,3,...,n\) respectively. Consider the sets

The sets are disjoint because each acts differently on the element 1. Futhermore, any \(q \in G\) transforms \(1\) to \(k\), say, hence \(q \in G_1 g_{1 k}\) because \(q g_{1 k}\) leaves 1 unchanged so must lie in \(G_1\). So these disjoint cosets partition \(G\), showing that \(G_1\) has index \(n\) in \(G\).

Conversely, if \(G_1\) has index \(n\), decompose \(G\) into cosets \(G_1 g_1,...,G_1 g_n\). Then if \(g_i , g_j\) transform 1 to the same object \(\alpha\), we have that \(g_i g_j^{-1} \in G_1\), implying that \(G_1 g_i = G_1 g_j\) and hence \(i = j\). Thus we may label the \(g_i\) such that \(g_i(1) = i\).

Lastly, if \(\alpha,\beta \in \{1,...,n\}\) then \(g_\alpha^{-1} g_\beta\) transforms \(\alpha\) into \(\beta\).

**Corollary:** The order of a transitive groups of permuations of degree
\(n\) is divisible by \(n\).

A group of permutations \(G\) is said to be *\(k\)-ply transitive*
if for any sets of size \(k\)
\(\{\alpha_1,...,\alpha_k\}, \{\beta_1,...,\beta_k\} \subset \{1,...,n\}\)
there exists \(g\in G\) with \(g(\alpha_i) = \beta_i\) for all \(i\).

The number of distinct subsets of size \(k\) in a set of size \(n\) is given by \(n(n-1)...(n-k+1)\). Thus we have:

**Theorem:** The order of a \(k\)-ply transitive group of degree \(n\) is
divisible by \(n(n-1)...(n-k+1)\).

**Theorem:** The group \(G\) is \(k\)-ply transitive if \(G\) is simply
transitive and \(G_1\) is \((k-1)\)-ply transitive with respect to
\(\{2,3,...,n\}\).

Let \(G\) be a transitive group in \(S_n\). Suppose it is possible to
place \(1,...,n\) in an \(r \times s\) matrix where \(r s = n, r,s\gt 1\)
such that the permutations of \(G\) either permute the objects of any one
row amongst themselves or else interchange objects of one row with another.
In other words, two objects that start in the same row are never transformed
to objects in different rows, and vice versa. Then \(G\) is said to be
*imprimitive*, and the rows are called *imprimitive
systems*. Otherwise \(G\) is said to be primitive. Note all
doubly-transitive groups are primitive, and in particular, \(S_n\) is
primitive.

*blynn@cs.stanford.edu*💡