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$.
$\begingroup$
$\endgroup$
4
-
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 HopkinsCommented Nov 4, 2013 at 14:43
-
$\begingroup$ Thanks, this is exactly the type of answer that I was hoping for. $\endgroup$– StephenJCommented Nov 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 StumpCommented Nov 4, 2013 at 16:49
-
$\begingroup$ @ChristianStump: It's an interesting question to which I don't know the answer. $\endgroup$– Sam HopkinsCommented Nov 4, 2013 at 20:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Nov 4, 2013 at 14:52
-
$\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$– StephenJCommented Nov 4, 2013 at 16:20
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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.) $\endgroup$ Commented Nov 10, 2013 at 17:28