Prove every non-trivial permutation of $\omega = {\{1,2,….,n}\}$ can be written as a composite of less than $n$ transpositions.
I have no idea where to start with this. I know every permutation can be written as a product of disjoint cycles and I know a transposition is a cycle of length $2$. But I honestly don't know where to start.
Best Answer
By induction - suppose any permutation of $[n]$ takes less than $n$ transpositions. Consider any permutation $w$ of $[n+1].$ Use one transposition to swap $n+1$ into the correct location, if $w_{n+1} \neq n+1$ . Now, you have less than $n$ transpositions for the rest, by inductive hypothesis. So the total required is less than $n+1$.