# How to prove by induction number of disjoint cycles in $\tau_1\tau_2\cdots\tau_m$ in $S_n$ is even or odd if $n+m$ is even or odd?

Question:

If $\tau_1$ is a transposition in $S_n$, check that $\tau_1$ consists of $n-1$ cycles and that $n-1$ is even or odd according as $n+1$ is even or odd. If $\tau_1,\tau_2,\cdots,\tau_m$ are transpositions in $S_n$, prove by induction on $m$ that the product $\tau_1\tau_2\cdots\tau_m$ is expressed in disjoint cycles, the number of disjoint cycles is even or odd according as $n+m$ is even or odd.

My first problem is that I don't understand the first sentence. It says to check if a transposition has $n-1$ cycles but transpositions are defined as cycles of length 2. It seems to make more sense to me if it was asking to check if the number of cycles in the permutation $\alpha$ of which $\tau_1$ is a transposition consists of $n-1$ disjoint cycles.

Secondly, I am having difficulty with the inductive proof.

I start out by assuming the number of disjoint cycles, $c$, in $\tau_1\tau_2\cdots\tau_m$ is even or odd depending on if n+m is even or odd.

The number of disjoint cycles in $\tau_1\tau_2\cdots\tau_m\tau_{m+1}$ is $c+1$ or $c-1$ depending on if for $\tau_{m+1}=(ab)$, $a$ and $b$ were in the same cycle or disjoint cycles for the simplified product of transpositions. So if $c$ is even $c\pm1$ are odd and if $c$ is odd then $c\pm1$ is even. Does this directly imply $n+m+1$ is even or odd depending on if $c\pm1$ is even or odd?

• What they mean is that, for instance, in $S_4$, the transposition that swaps the first two elements may be written in fishing cycle form as $(12)(3)(4)$, which is three cycles. – Arthur Jan 27 '17 at 16:20
• @Arthur I tried similar numerical examples, which is why in $S_3$, say for the permutation $(123)$, the product $(123)(12)$ gives $(1)(23)$ which is $n-1=3-1=2$ cycles. – shredalert Jan 27 '17 at 16:27
• But $(123)(12)$ is not a product of transpositions. – Arthur Jan 27 '17 at 16:31
• I meant to write (123)(12)=(12)(13)(12)=(1)(23), my apologies. I looked at the wrong part of my rough notes. – shredalert Jan 27 '17 at 16:34

It's including trivial cycles, so in $S_3$ for example $(1,2)$ has cycle $(1,2)$ and cycle $(3)$, hence $2=n-1$ cycles.
For the second part of your question, the assumption gives you that $c$ is even if and only if $m+n$ is even.
• I have showed that $c\pm1$ is either odd or even. Since we have our assumption, this implies $n+m+1$ is even iff $c\pm1$ is even. This completes our proof by induction on $m$. I think I get the idea now. – shredalert Jan 27 '17 at 16:43
• Well, the inductive hypothesis is that $c$ is even if and only if $n+m$ is even, which is equivalent to $c\pm 1$ even if and only if $n+m+1$ is even, so showing that $\tau_1\ldots\tau_{m+1}$ has $c\pm 1$ cycles completes the proof – Robert Chamberlain Jan 27 '17 at 17:00