10.1 Preliminary for Symmetric Groups

Parity and Presentation of Symmetric Groups

parity

Each permutation in $S_n$ can be presented as a diagram permutation said to be odd (rep. even) if the number of crossing in this diagram is odd (rep. even). Define $\mathrm{sgn}:S_n\to \{\pm 1\}$ as $\mathrm{sgn}(\sigma )=1$ if $\sigma$ is even and $\mathrm{sgn}(\sigma )=-1$ if $\sigma$ is odd.

Equivalently, the parity of permutation $\sigma$ is the number of inversions $(i,j)$ in $\sigma$: $1⩽i<j⩽n$ such that $\sigma (i)<\sigma (j)$.

The adjacent transposition $s_i:=(ii+1)$ for all $1⩽i⩽n-1$, then $S_n$ is generated by $\{s_i:1⩽i⩽n-1\}$.

Proposition

The symmetric group has the following presentation

$$S_n=⟨s_1,\cdots ,s_{n-1}:s_i^2=1,s_i{s}_j=s_j{s}_i\text{mbox}with|i-j|>2,s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1}⟩.$$

\begin{proof} Define the LHS equals ${\Gamma }_n$. We have a surjective homomorphism ${\Gamma }_n\to S_n,s_i\mapsto (ii+1)$. It suffices to show $|{\Gamma }_n|⩽n!$. Note that the case of $n=1$ holds. Suppose that $|{\Gamma }_n|⩽n!$, and consider the subgroup $H<{\Gamma }_{n+1}$ generated by $s_1,\cdots ,s_{n-1}$where $|H|⩽n!$ by induction hypothesis. Note that

$${\Gamma }_{n+1}=H\cup s_{n}H\cup \cdots \cup s_1\cdots s_{n}H$$

and this composition is stable by the action of $n$. Therefore, $|{\Gamma }_{n+1}|⩽(n+1)!$ and so ${\Gamma }_n\simeq S_n$. \end{proof}

Definition

Any element of $S_n$ can be written as product of $s_i$‘s, and for $\sigma =s_{i_1}\cdots s_{i_{\ell }}$, then minimum value of $\ell$ is called the length of $\sigma$.

Cycle Types and Partitions

Definition

Any permutation $\sigma$ can be written as product of disjoint cycles. The cycle type is the set of length of cycles. For example, the cycle type of $(1234)(567)$ in $S_8$ is $\{1,3,4\}$.

As two permutations with the same cycle type belong to the same conjugacy class, the conjugacy classes of $S_n$ can be described as $\lambda =({\lambda }_1,\cdots ,{\lambda }_{\ell })$ with ${\lambda }_i>0,{\lambda }_i\in \mathbb{Z}$ and ${\lambda }_1+\cdots +{\lambda }_{\ell }=n$.

There are some properties of partition functions. Write partition in the multiplicity from $\lambda =\{1^{m_1},\cdots ,n^{m_n}\}$ with $n=m_1+2m_2+\cdots +n{m}_n$, then we have the following property.

Proposition

The cardinality of conjugacy class $C_{\lambda }$ of $S_n$ corresponding to partition $\lambda =\{1^{m_1},\cdots ,n^{m_n}\}$ is

$$|C_{\lambda }|=\frac{n!}{1^{m_1}{m}_1!\cdots n^{m_n}{m}_n!}.$$

\begin{proof} Note that

• $(123),(231),(312)$ are same cycles and there are $1^{m_1}\cdots n^{m_n}$ repetitions.
• $(123)(456)$ and $(456)(123)$ are same cycles and there are $m_1!\cdots m_n!$ repetitions.

Now we finish the proof. \end{proof}

For any given $n\in {\mathbb{N}}_{+}$, define $p(n)$ as the number of partitions of $n$. Then we can get its generating function.

Euler formula

The generating function for partition is

$$\sum _{n⩾0}p(n)t^n=\frac{1}{1-t}\frac{1}{1-t^2}\cdots \frac{1}{1-t^n}\cdots$$

where $p(n)$ is the number of partitions of $n$.