# How many permutations are there at a given Cayley distance from the identity?

Permutations $$\sigma$$ in the symmetric group $$S_n$$ can be characterized by their Cayley distance $$C_\sigma$$, being the minimal number of transpositions needed to convert $$\{1,2,3,\ldots n\}$$ into $$\sigma$$. The sign of the permutation is $$(-1)^{C_\sigma}$$.

For example, when $$\sigma=\{2, 3, 4, 5, 1\}$$, one has $$C_\sigma=4$$ and for $$\sigma=\{1, 2, 3, 5, 4\}$$ one has $$C_\sigma=1$$. Of the $$5!$$ permutations in $$S_5$$ there are, respectively, $$1,10,35,50,24$$ with Cayley distance $$C_\sigma=0,1,2,3,4$$.

Question: What is the general formula that counts the number of permutations at a given Cayley distance?

This question was motivated by my attempt to check an integral formula in the unitary group.

• findstat.org/St000216 – Martin Rubey May 11 at 19:49
• @MartinRubey --- wonderful, thank you for the rapid answer; so the number of permutations in $S_n$ at Cayley distance $k\in\{0,1,2,\ldots,n-1\}$ equals $|s_{n,n-k}|$, the Stirling number of the first kind. – Carlo Beenakker May 11 at 20:24
• I admit that I (sort of) knew the answer, but I do enjoy pointing out that filling in a handful of values at findstat.org/StatisticFinder/Permutations is easier than trying to remember! – Martin Rubey May 11 at 20:34
• you might just enter this in the answer box so that I can accept it... – Carlo Beenakker May 11 at 20:42
• It's worth noting that a permutation in $S_n$ with $k$ cycles has Cayley distance $n-k$. This is why Stirling numbers of the first kind appear. – Ira Gessel May 11 at 22:31

The Cayley distance of a permutation is also known as its absolute length, as can be found out by supplying a few values at https://findstat.org/StatisticFinder/Permutations, which yields https://findstat.org/St000216. There, we also find that for a permutation in $$\mathfrak S_n$$ with $$k$$ cycles it is simply $$n-k$$. This fact is, for example, Problem 5.6 in [1].