Prove that $S_n$ satisfies the following property: if $g \in S_n$, then $g$ and $g^{-1}$ are conjugate in $S_n$. So I tried setting up an arbitrary $g$ such that $g(a_1)=b_1, ... g(a_k)=b_k$, and then I fizzled out. So I'm showing that for every a in $S_n,\ ag(a^{-1}) = g^{-1}$. I'm showing that they have the same cycle structure, but I'm not exactly sure how to show that in a rigorous, proofy type way.
 A: Suppose $(a_1~a_2~\cdots~a_m)$ is an $m$-cycle. Then $\sigma(a_1~a_2~\cdots~a_m)\sigma^{-1}=(\sigma(a_1)~\sigma(a_2)~\cdots~\sigma(a_m))$. So,
$$\begin{array}{ll} & \sigma(a_{1,1}~\cdots~a_{1,m_1})(a_{2,1}~\cdots~a_{2,m_2})\cdots(a_{l,1}~\cdots~a_{l,m_l})\sigma^{-1} \\ = & \sigma(a_{1,1}~\cdots~a_{1,m_1})\sigma^{-1}\sigma(a_{2,1}~\cdots~a_{2,m_2})\sigma^{-1}\cdots\sigma(a_{l,1}~\cdots~a_{l,m_l})\sigma^{-1} \\ = & (\sigma(a_{1,1})~\cdots~\sigma(a_{1,m_1}))(\sigma(a_{2,1})~\cdots~\sigma(a_{2,m_2}))\cdots(\sigma(a_{l,1})~\cdots~\sigma(a_{l,m_l})) \end{array}.$$
Therefore, conjugation of something by $\sigma$ simply relabels the entries of the disjoint cycle factorization via application by $\sigma$. Suppose we have two elements with the same cycle type:
$$g=(a_{1,1}~\cdots~a_{1,m_1})(a_{2,1}~\cdots~a_{2,m_2})\cdots(a_{l,1}~\cdots~a_{l,m_l}) \\ h=(b_{1,1}~\cdots~b_{1,m_1})(b_{2,1}~\cdots~b_{2,m_2})\cdots(b_{l,1}~\cdots~b_{l,m_l}).$$
Then $g$ and $h$ are conjugate by any $\sigma$ which replaces the $a_{i,j}$s with $b_{i,j}$s.
In particular, $g$ and $g^{-1}$ in $S_n$ have the same cycle type.
A: One way to show two permutations are conjugate is to show they have the same cycle structure, like you said. And it's pretty obvious a permutation and its inverse have the same cycle structure, since all we're doing is reversing the arrows—certainly nothing is changing about the structure. (see below) This might be messy to write out though.

Another common definition of conjugate is:  $x$ is conjugate to $y$ in $G$ iff there is some element $a \in G$ with $axa^{-1}=y$. So trying to show $g$ is conjugate to $g^{-1}$ amounts to finding some $a$ with $aga^{-1}=g^{-1}$, and this equation is readily solved for $a$.
