How many ways can a given permutation be obtained as a product of k 2-cycles? Let $\sigma_1, \ldots, \sigma_b$ be all the 2-cycles in $S_n$. (So, $b = \binom{n}{2}$.) Given $\pi \in S_n$, what is known about how many ways $\pi$ can be obtained as a product of $k$ (not necessarily distinct) elements of $\{\sigma_1,\ldots, \sigma_b\}$? Of course, if $k$ is too small than this number can be zero. It is clear that this depends on $\pi$ only through its conjugacy class. Thus, I was wondering whether there is a nice formula in terms of $n$, $k$ and the sizes of the cycles in the cycle-decomposition of $\pi$.
 A: For small enough $n$, an efficient way to perform this enumeration is described
in the solution to a GAP exercise I posed a few years ago.
It basically amounts to setting up a suitable matrix, raising it to the $k$-th power
and reading off a specified entry. 
Using this method, one can find for example that the identity in ${\rm S}_4$ can be
written as a product of exactly 100 transpositions in 54443218625005908841390855596504818378095309207030310578760502581913955860480 ways.
A: A single cycle of length $n$ will have $n^{n-2}$ different ways to be decomposed into $n-1$ transpositions (Hurwitz). For a permutation in $S_n$ which is a product of distinct $l$ cycles $\{C_i\}_{i=1}^{l}$ we have a multinomial to interleave the transpositions. 
$$
{n-l \choose n(C_1),\dots,n(C_l)} \prod_{i=1}^{l}\left(n(C_i)+1\right)^{n(C_i)-1}
$$
Where $n(C_i)=length(C_i) - 1$ is the number of transpositions within the cycle $C_i$. And the binomial coefficient ${n-l \choose n(C_1),\dots,n(C_l)}$ counts the ways to interlace insertions between the cycles.
In this link is a review and generalizations of Hurwitz's result by Strehl.
I know this only deals with the minimal decompositions and you were asking about a general $k$ that could be greater. Hope this helps anyway.
