Elements of $S_n$ which can not be product of $\leq n-2$ transpositions It is well known that every element of $S_n$ can be written as a product of at most $n-1$ transpositions. This theorem is proved in all the books which discuss the permutation groups. But, I find that the following natural question is usually neither discussed nor put in Exercise Section in the book. 

Question: Does there always exists an element in $S_n$ which can not be product of $\leq n-2$ transpositions? Can we list the cycle-type of such elements?

The natural guess would be the $n$-cycles in $S_n$ would be the elements which answer the question. But I couldn't prove it. Can you help me? A hint would also be sufficient.
 A: We first note two simple facts.
1) If $\sigma=(a_1 \ \ldots\ a_n)$ is an $n$-cycle, then $\sigma(a_i \ a_j)$ is a product of two disjoint cycles, the sum of whose lengths is $n$.
2) If $\sigma=(a_1\ \ldots\ a_k)$ and $\theta=(b_1 \ \ldots\ b_l)$ are two disjoint $k$ and $l$ cycles respectively, then $\sigma\theta(a_i\ b_j)$ is a $k+l$ cycle.
Now suppose we have an $n$-cycle $\sigma$ which can be written as as a product of $t$ transpositions $\tau_1,\ldots, \tau_t$, where $t\leq n-2$.
Note that, using $(1)$ and $(2)$, we see that $\sigma \tau_t\cdots\tau_{1}$ is a product of no more than $t+1\leq n-1$  disjoint cycles, then sum of whose lengths is $n$.
Thus some cycle amongst these disjoint cycles should have length at least $2$, and therefore this permutation is non-trivial.
On the other hand, the permutation $\tau_1\cdots\tau_t\cdot\tau_t\cdots \tau_1$ is clearly trivial.
A: It can be shown that: An element in $S_n$ can be written as a product of $\leq n-2$ transpositions if and only if the element is not an $n$-cycle.  So the answer to your question is: yes, there always exists elements in $S_n$ that cannot be written as a product of $\le n-2$ transpositions, and these elements are precisely the $n$-cycles.
To prove the above statement, you can examine how the number of cycles in a permutation changes when we compose the permutation with a transposition. If $g=(123)(45)(6) \in S_6$, then the number of cycles in $g$ is $c(g)=3$. You can work out examples to see that composing $g$ with any transposition $(i,j)$ reduces $c$ by 1 or increases $c$ by 1, according as whether $i$ and $j$ are in different or same cycles of $g$. For example, composing $g$ with $(14)$ will merge the two cycles in $g$ that contain 1 and 4, thereby reducing $c$ by 1, while composing $g$ with $(12)$ will split the cycle $(123)$ in $g$, thereby increasing $c$ by 1.  
Now, $g \in S_n$ is a product $g=t_1 \cdots t_k$ of transpositions iff $g t_k \cdots t_1$ is the identity (recall that a transposition is its own inverse).  By the argument in the previous paragraph, composing $g$ with $k$ transpositions can reduce or increase $c$ by at most $k$.  The identity permutation has $c=n$. We need to compose an $n$-cycle with transpositions until we get the identity permutation.  Starting with an $n$ cycle, which has $c=1$, the number of transpositions needed to split the $n$ cycle into $n$ 1-cycles (and thereby increase $c$ to $n$) is at least $n-1$ (by the argument in the previous paragraph).  Hence, an $n$-cycle cannot be expressed as a product of fewer than $n-1$ transpositions.
A: If $\sigma \in S_n$ is a permutation, let $f(\sigma)$ be the number of cycles in the cycle decomposition of $\sigma$, including the 1-cycles as fixed points.  Then for any transposition $\tau = (i j)$, we have $f(\sigma\tau)=f(\sigma)\pm 1$, where the sign is $+$ if $i$ and $j$ are in the same cycle in $\sigma$, and $-$ if they are in different cycles in $\sigma$.
From this, and the fact that $f(\mathrm{id}) = n$, it follows that if $\sigma$ is the product of $\le n-2$ transpositions, then $f(\sigma) \ge 2$.  Since $f(\text{$n$-cycle}) = 1$, it follows that an $n$-cycle is not the product of $\le n-2$ transpositions.
