There is a theorem says if $A$ in $S_n$ is a $k$ cycle, and $A = a_1 a_2 a_3 \dots a_m$, where $a_i$ are transpositions, then $m \geq k-1$.
But how to show there are at least $k-1$ distinct transpositions in there?
I know $(1\ 2\ 3\ \dots\ n) = (1, n)(1,n-1) \dots (1,2)$, but I still not sure how to prove it.
On
A related general fact is the following. Let $\alpha\in S_n$ be a permutation such that it has exactly $m$ cycles - including 1-cycles (i.e. fixed points). Let $(ab)\in S_n$ be a 2-cycle, then the product $(ab)\alpha$ has either $m+1$ or $m-1$ cycles. All according to whether $a$ and $b$ appear in different cycles of $\alpha$ or not.
The identity permutation of $S_n$ has $n$ 1-cycles. A $k$-cycle has only $n-k+1$. Therefore you need (at least) $(k-1)$ factors.
Proof of the fact? Leaving that as an exercise. The idea is that multiplying by $(ab)$ either splits a cycle containg both $a$ and $b$ into two, or glues together the disjoint cycles containing them.
An aside: this gives an alternative proof of the fact that in a presentation of a permutation as a product of 2-cycles the parity of the number factors is determined by the sign of the permutation.
It's actually the other order $(a_{1} a_{2} ... a_{n}) = (a_{1} a_{n}) (a_{1} a_{n-1}) ... (a_{1} a_{2})$.
I would prove this combinatorially or by algorithm. Induction would also be valid. Step through the multiplication process. We start by taking $a_{1} \to a_{2}$. We note $a_{2}$ does not appear to the left, so we mark both down $(a_{1} a_{2}$. Then starting from the right, we see $a_{2} \to a_{1}$ and then $a_{1} \to a_{3}$. As $a_{3}$ does not appear to the left, mark down $a_{3}$. So we have $(a_{1} a_{2} a_{3}$ thusfar.
Hopefully this will get you going in a good direction.