# Number of elements in the symmetric group with a particular transposition decomposition

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.

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$$.
• 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. – vidyarthi Jun 22 at 12:34