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.

  • 2
    $\begingroup$ findstat.org/St000216 $\endgroup$ – Martin Rubey May 11 at 19:49
  • $\begingroup$ @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. $\endgroup$ – Carlo Beenakker May 11 at 20:24
  • 1
    $\begingroup$ 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! $\endgroup$ – Martin Rubey May 11 at 20:34
  • 2
    $\begingroup$ you might just enter this in the answer box so that I can accept it... $\endgroup$ – Carlo Beenakker May 11 at 20:42
  • 4
    $\begingroup$ 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. $\endgroup$ – 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].

[1] Petersen, T. Kyle, Eulerian numbers, Birkhäuser Advanced Texts. Basler Lehrbücher. New York, NY: Birkhäuser/Springer (ISBN 978-1-4939-3090-6/hbk; 978-1-4939-3091-3/ebook). xviii, 456 p. (2015). ZBL1337.05001.


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.