2
$\begingroup$

Define the length of a permutation as the minimum number of adjacent transpositions needed to describe it. We know that there is only one element of length $0$ in $S_n$ and $n-1$ elements of length $1$ and one element of maximum length $\ell_n$. Is there a formula that give the number of elements in $S_n$ having a length $k$ where $0<k<\ell_n$?

$\endgroup$
2
  • 1
    $\begingroup$ It seems like something is missing here. Please edit. $\endgroup$ Apr 16, 2016 at 10:45
  • 4
    $\begingroup$ Actually, if you write a permutation as cycles, the length of a cycle of length $a$ is $a-1$, and the length of the whole thing is the sum of the lengths. So maximum length is acchieved if there is one cycle of length $n$, and there are $(n-1)!$ such elements. I guess, you are talking about transpositions of neighbours instead. $\endgroup$ Apr 16, 2016 at 15:28

1 Answer 1

11
$\begingroup$

I assume you are considering the symmetric groups ${\rm S}_n$ with generating sets $\{(i,i+1) \ | \ i < n\}$ (since in this case you have $n-1$ elements of length $1$ and one element of maximum length, as you state in your question), and ask for the number of elements of ${\rm S}_n$ of given length with respect to this set of generators. -- Then the numbers you are looking for are the so-called Mahonian numbers $M(r,c)$ which are the coefficients in the expansion of the product $$ \prod_{i=0}^{n-1} (1 + x + \dots + x^i). $$

$\endgroup$
4
  • 4
    $\begingroup$ I see that "Mahonian" = in honor of MacMahon; is that a common formation? (Cf. Descartes → cartesian, but Desargues → Desarguesian [though "Arguesian" is occasionally seen too].) $\endgroup$ Apr 16, 2016 at 16:05
  • 2
    $\begingroup$ This product is also called the Poincaré series of the Coxeter system $S_n$ ... $\endgroup$ Apr 16, 2016 at 18:32
  • $\begingroup$ Thank you all. Yes Stephan, this is exactly what I meant. Do you know a good reference for the information you posted? Thanks in advance $\endgroup$
    – M. T
    Apr 17, 2016 at 12:01
  • 1
    $\begingroup$ @M.T: A reference is for example: T. Kyle Petersen, Eulerian Numbers, Birkhäuser, 2015, Page 96. $\endgroup$
    – Stefan Kohl
    Apr 17, 2016 at 12:59

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.