2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ actually, i got the question while studying the cayley graph on $S_n$ generated by transpositions, in an attempt tn color (total coloring) the graph is easily seen to be bipartite. $\endgroup$ – vidyarthi Jun 22 at 12:34
  • $\begingroup$ Yes, with the bipartition being the even and odd permutations. $\endgroup$ – mo2019 Jun 22 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.