Symmetric Group & Permutations

permutation

Let $Ω$ be any nonempty set and let $S_{Ω}$ be the set of all bijectsion from $Ω$ to itself. Then $S_{Ω}$ is a Group under function composition $\circ$ . Note that $\circ$ is a binary operation since any $σ, τ : Ω \to Ω$ then $σ \circ τ$ is also a bijection from $Ω \to Ω$ . Note:

The identity is the permuation $1$ defined by $1 (a) = a$ for all $a \in Ω$
For each permutation $σ$ there is a 2-sided inverse function $σ^{- 1}$ such that $σ \circ σ^{- 1} = σ^{- 1} \circ σ = 1$
Thus all Group axioms hold for $(S_{Ω}, \circ)$

symmetric group on the set $Ω$

The group of permutations $S_{Ω}$ is called the symmetric group on the set $Ω$ .

For the special case $Ω = {1, 2, \dots, n}$ we use $S_{n}$ to denote this symmetric group.

Permutation Group

Consider the Permuation Group. Any finite set $X$ will have perumations:

permuation

A permutation of $X$ is a bijection $σ : X \to X$ . It's essentially a shuffling of the elements in $X$ .

X = {1, 2, 3, 4, 5}

Count the number of bijections $σ : X \to X$ . Using principles of proofs, this is the number of injections $σ : X \to X$ (since $X$ is finite). Once we know where $1$ goes we have 5 options, then for 2 we have 4 options, ... so then we have $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120$ possibilities.

There are some notational options here (which is where the old-timey modulo notation comes into play):

(Functional Notation:) one permuation is: $σ (1) = 2, σ (2) = 3, σ (3) = 5, σ (4) = 1, σ (5) = 4$ . This is obviously super slow so we don't want to do this one.
(Modified Functional Notation:) write it instead with $\to$ : $1 \mapsto 2, 2 \mapsto 3, \dots$ .
(Use A Table:) write where the top row maps to the bottom row:
$(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \end{matrix})$
("Cycle Notation":) write out a visual graph of what number maps to where:

We write this as:
$σ = (\begin{matrix} 1 & 2 & 3 & 5 & 4 \end{matrix})$
Another example would be:
$τ = (\begin{matrix} 1 & 3 & 5 \end{matrix}) (\begin{matrix} 2 & 4 \end{matrix})$
Creates the following:

Here $τ$ has a 3-cycle and a 2-cycle (or a transposition). This $τ$ is a product of disjoint cycles. Notice that since we have a cycle where $n \geq 3$ then the group isn't abelian with operation $τ$ .

Permutation Arithmetic

See this video: