Let $\sigma_1, \ldots, \sigma_b$ be all the 2cycles 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 cycledecomposition of $\pi$.

5$\begingroup$ This is of course a famous (and solved) problem; see arxiv.org/pdf/1308.1468v1.pdf for the references at the beginning and for a $q$analog with many open questions. $\endgroup$– Sam HopkinsNov 4, 2013 at 14:43

$\begingroup$ Thanks, this is exactly the type of answer that I was hoping for. $\endgroup$– StephenJNov 4, 2013 at 16:21

$\begingroup$ @SamHopkins if I am not mistaken, that paper and its references only consider factorizations of Coxeter elements. For the symmetric group, it is known that every element is a Coxeter element in a suitable parabolic subgroup. But what about factorizations of elements in other reflection groups that are not parabolic Coxeter elements? (Such elements exist already in type $B_2$, so the question might still be interesting there.) Have you seen anything for those as well? $\endgroup$– Christian StumpNov 4, 2013 at 16:49

$\begingroup$ @ChristianStump: It's an interesting question to which I don't know the answer. $\endgroup$– Sam HopkinsNov 4, 2013 at 20:52
2 Answers
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.

$\begingroup$ Thanks, this is a nice answer, which I understand. What I actually had in mind was only formulas not algorithms, because I am trying to apply this to summing an infinite series. Nevertheless, I'm sure this answer could be useful for others who come across this question from google searches etc. $\endgroup$– StephenJNov 4, 2013 at 16:20
A single cycle of length $n$ will have $n^{n2}$ different ways to be decomposed into $n1$ 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. $$ {nl \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 ${nl \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.

$\begingroup$ The number of ways of decomposing an ncycle into n1 transpositions is the same as the number of spanning trees of a complete graph on n vertices. Indeed, given a such a decomposition of an ncycle, one can build a spanning tree by putting an edge {i,j} iff the transposition (i,j) is present. (Verifying that this correspondence is invertible seems to take a little more work.) $\endgroup$ Nov 10, 2013 at 17:28