Transpositions and disjoint cycles I have to prove the following: Let $g\in S_n$. Let $z(g)$  the number of disjoint cycles necessary to write $g$ and $t(g)$ the minimum number of transpositions necessary to write $g$. Then $z(g)+t(g)=n$.
I really don't know how to solve this problem, because there are many ways to write a permutation as a product of transpositions, and I don't know which of them will be the minimum number possible, so can someone help me out?
 A: We have to show that $z(g)+t(g)\le n$ and $z(g)+t(g)\ge n.$ Suppose $z(g)=r$ and write $g=h_1h_2\cdots h_r$ where $h_1,h_2,\dots,h_r$ are disjoint cycles, $h_i$ being a cycle of length $n_i.$
$\underline{z(g)+t(g)\le n}$:
A cycle of length $n$ can be written as a product of $n-1$ transpositions, as in the example
$$(1\ 2\ 3\ 4\ 5)=(1\ 2)(2\ 3)(3\ 4)(4\ 5).$$
Thus
$$t(g)=t(h_1\cdots h_r)\le t(h_1)+\cdots+t(h_r)\le(n_1-1)+\cdots+(n_r-1)=n-r$$
and so $z(g)+t(g)\le r+(n-r)=n.$
$\underline{z(g)+t(g)\ge n}$:
Suppose $g$ is the product of $t=t(g)$ transpositions, say $g=e_1\cdots e_t$ where $e_j=(v_j\ w_j).$ Consider the graph $G=(V,E)$ with vertex set $V=\{1,\dots,n\}$ and edge set $E=\{v_1w_1,\dots,v_tw_t\}.$ Clearly, the support of each cycle $h_i$ must be contained in a single connected component of $G,$ so $G$ has at most $r$ components. Since the number of components is at least the number of vertices less the number of edges, it follows that $r\ge n-t,$ that is, $n\le r+t=z(g)+t(g).$
The argument for $t(g)\ge n-z(g)$ actually shows that any expression for $g$ as a product of transpositions must contain at least $n-z(g)$ distinct transpositions; in other words, $g$ does not belong to any group generated by fewer than $n-z(g)$ transpositions.
A: Notice that to write  $g $ as a product of disjoint cycles, every $a \leq n $ will appear exactly once in exactly one cycle.
When there is a number $k $ you know it has to be precisely in the cycle with its orbit. If you consider partitioning the set of first $n $ naturals in the orbits of $g $, you will get some number of orbits of some length. What is funny, is that the length of the orbit is equal to $1$ plus the number of transpositions required to write its cycle. Because adding up the lengths of all orbits gives  $n $, we have
$z(g) + t(g) = n $
