Worst-case number of transpositions needed to generate a permutation

Question

For a permutation on $n$ elements, what is the worst-case minimal number of transpositions that need to be multiplied to give the permutation? The transpositions do not need to be adjacent.

Answer 1

The number is indeed $n- s$, where $s$ is the number of disjoint cycles, or, equivalently: $$L(\sigma)=\sum_{c_i} ( l(c_i) -1) $$ if $\sigma= c_1 c_2 \ldots $ is the expression of $\sigma$ as a product of disjoint cycles.

The decomposition of a permutation into product of disjoint cycles changes by passing from $\sigma$ to $\tau \sigma$, where $\tau$ is a transposition as follows: if the support of $\tau$ is contained in the support of one of the $c$ then $\tau c = c' c''$, where the supports of $c$ is partitioned into the support of $c'$ and $c''$, while if the support of $\tau$ is contained in the union of $c'$, $c''$, then $\tau c' c''= \tau c$. Therefore: $$L(\tau \sigma) = \begin{cases} L(\sigma) -1 \textrm{ if $\tau$ slices a cycle of $\sigma$ } \\ L(\sigma) + 1 \textrm{ if $\tau$ joins two cycles of $\sigma$}\end{cases} $$

We see now that any permutation can be written as a product of $L(\sigma)$ ( and no less) transpositions ( we can decrease the $L$ by multiplying on the left with transpositions, till $L$ gets to $0$, that is, till we get the identity permutation), and moreover, the number of such transpositions is $\equiv L(\sigma) \mod 2$.

$\bf{Added:}$ How many transpositions has one to multiply a permutation by to obtain the identity permutation? Every time we multiply by a transposition the number of cycles can increase by at most $1$ ( and the number does vary by $1$). To get $n$ cycles from the original one, we need to multiply by $n-s$ transpositions -- properly chosen.

Answer 2

Hint: each transposition can put an element in its place, but the answer is not $n$