Consider the symmetric group on $n$ symbols, $S_n$. Then, is there a way/ function to count the number of elements with a given number of transposition decomposition?
By transposition decomposition, I mean writing a permutation as a product of transpositions. So, for example, all transpositions have only one transposition factor, all $3$ cycles have exactly two transposition factors. But, the product of two disjoint transpositions also have a decomposition into two transposition factors. I think that counting the number of different cycle decompositions will help a lot. But has this been studied before and is there a function for eveluating it? Thanks beforehand.
Best Answer
This is an interesting question and I believe is an open problem in general. The literature on Cayley graphs of symmetric groups generated by transpositions would be relevant. The quantity you are interested in - the number of permutations that are a product of exactly $k$ (and no fewer) transpositions - is the number of vertices in the complete transposition graph whose distance to the identity vertex is exactly $k$.
More specifically, let $S$ be the set of all transpositions in $S_n$ ($n \ge 3)$. The complete transposition graph is the Cayley graph $G = Cay(S_n,S)$, which is defined to be the graph with vertex set $S_n$ and with edge set $\{(h, sh): h \in S_n, s \in S \}$. Define $G_i(v)$ to be the set of vertices in $G$ whose distance to vertex $v$ is exactly $i$. Let $e$ denote the identity permutation in $S_n$. Then $G_0(e) = \{e\}$, $G_1(e)$ is the set $S$ of all ${n \choose 2}$ transpositions in $S_n$, and $G_2(e)$ is the set of all permutations in $S_n$ which are either 3-cycles or a product of two disjoint transpositions.
The open source software SAGE (sagemath.org) contains, among other things, built-in functions to create Cayley graphs and output the size of the $i$th layer $G_i(v)$ in the distance partition of $G$ with respect to a vertex $v$.