6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ findstat.org/St000216 $\endgroup$
    – Martin Rubey
    May 11, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 22:31

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.