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$.

• 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. Nov 4, 2013 at 14:43
• Thanks, this is exactly the type of answer that I was hoping for. Nov 4, 2013 at 16:21
• @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? Nov 4, 2013 at 16:49
• @ChristianStump: It's an interesting question to which I don't know the answer. Nov 4, 2013 at 20:52

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.

• 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. Nov 4, 2013 at 16:20

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.

• The number of ways of decomposing an n-cycle into n-1 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 n-cycle, 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.) Nov 10, 2013 at 17:28