# The Unapologetic Mathematician

## Cycle Type

One concept I’d like to introduce is that of the “cycle type” of a permutation. This simply counts the number of cycles of various length in a permutation. For example — using the sample permutations from last time $\alpha=(1\,2)(3\,4)$ has two cycles of length two, while $\beta=(1\,4\,3)(2)$ has one cycle of length three and one “fixed point” — a cycle of length one. No cycle in a permutation in $S_n$ can be longer than $n$, so we only need to count up to $n$. We collect the information in a cycle type into a tuple of the form $(1^{m_1},2^{m_2},\dots,n^{m_n})$. The cycle type of $\alpha$ is $(1^0,2^2,3^0)$, and that of $\beta$ is $(1^1,2^0,3^1)$.

It should be clear that the sum of the cycle lengths is $n$. In a formula: $\displaystyle\sum\limits_{k=1}^nkm_k=n$

That is, the cycle type breaks up or “partitions” $n$ into chunks whose total size adds up to $n$. In general, a partition $\lambda$ of $n$ is a sequence of numbers $(\lambda_1,\dots,\lambda_l)$ in nonincreasing order, whose sum is $n$. Thus the cycle type of $\alpha$ gives us the partition $(2,2)$, while the cycle type of $\beta$ gives us the partition $(3,1)$.

One more example, from the beginning: the two-line notation $\displaystyle\left\lvert\begin{matrix}1&2&3&4&5\\2&3&1&4&5\end{matrix}\right\rvert$

describing a permutation in $S_5$ has the cycle notation $(1\,2\,3)(4)(5)$. Its cycle type is $(1^2,2^0,3^1,4^0,5^0)$, which corresponds to the partition $(3,1,1)$.

September 9, 2010 -

## 1 Comment »

1. […] to each symbol in the cycle notation. In particular, any two conjugate permutations have the same cycle type. In fact, the converse is also true: given any two permutations with the same cycle type, we can […]

Pingback by Conjugates « The Unapologetic Mathematician | September 10, 2010 | Reply