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$?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ It seems like something is missing here. Please edit. $\endgroup$– Chris RamseyCommented 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$– Sebastian GoetteCommented Apr 16, 2016 at 15:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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). $$
answered Apr 16, 2016 at 16:01
-
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$ Commented Apr 16, 2016 at 16:05
-
2$\begingroup$ This product is also called the Poincaré series of the Coxeter system $S_n$ ... $\endgroup$ Commented 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. TCommented 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 ♦Commented Apr 17, 2016 at 12:59