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$

1 Answer 1

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$
2
  • $\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, 2019 at 12:34
  • $\begingroup$ Yes, with the bipartition being the even and odd permutations. $\endgroup$
    – mo2019
    Jun 22, 2019 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .