Ways to express the identity permutation as precisely $2r$ transpositions in $S_n$

Question

The question is as stated in the title. We know the identitiy permutation can be expressed as the product of even numbers of transpositions, but fixing the number of transpositions and asking how many solutions there are seems a less answered question. The closest answer I found is a GAP exercise and solution as mentioned in this MO post but I would like to know the status of this problem from the analytical side.

Answer 1

The typical way to write down formulas is using the representation theory of $S_n$. For the same amount of effort, this can be done for a single value of $r$ or for all $r$ simultaneously (e.g., in the form of an exponential generating function). Perhaps the standard book reference for this is

• S.K. Lando and A.K. Zvonkin, Graphs on surfaces and their applications, volume 141 of Encyclopaedia of Mathematical Science, Springer-Verlag, Berlin, 2004.

A very quick overview of the theory can be found in section 4 of this paper of Chapuy and Stump (arXiv version) -- they work in the context of complex reflection groups, but that shouldn't matter.

People interested in factorization enumeration in the symmetric group are used to making the following observation: the factors in each transposition factorization of the identity in $S_n$ generates a Young subgroup (i.e., one isomorphic in the natural way to $S_{\lambda_1} \times \cdots \times S_{\lambda_k}$ for some integer partition $\lambda$ of $n$); the numbers of factorizations that generate particular subgroups are related to the number that generate $S_n$ by both a simple product formula and an inclusion-exclusion formula (over all set partitions of $\{1, \ldots, n\}$), and so it is natural to study (i.e., enumerate) specifically those factorizations whose factors generate the entire group $S_n$. These enumerations are called Hurwitz numbers after the 19th century mathematician Adolf Hurwitz; they also (up to tame factors) count coverings of the sphere by Riemann surfaces, embedded maps on surfaces, and other interesting things. There's a huge body of work on this & related questions; again I think Lando--Zvonkin is the standard book reference. In general these numbers are very difficult to compute, but for the special case of the identity element (which you ask about) a lot more is known; see Remark 3.4 in this paper, which gives a recurrence relation (on $n$) for the generating function (by number of factors) for transposition factorizations of the identity in $S_n$ with the property that the factors generate the whole group $S_n$.