Let $S_n$ be the symmetric group over $\{1,2,\ldots,n\}$. How to return elements of length $m$ in $S_n$ using Sage? I try to find such function in Sage but didn't find one. Thank you very much.

Edit: $S_n$ is the Coxeter group of type $A$ generated by $s_1=(12), \ldots, s_{n-1}=(n-1,n)$. The length of an element $w \in S_n$ is the least number of simple reflections $s_i$ occurring in any expression for $w$.

  • $\begingroup$ What do you mean by "length"? $\endgroup$ – Igor Rivin Jan 23 '17 at 14:42
  • $\begingroup$ @Igor Rivin, I will edit the post. $\endgroup$ – Jianrong Li Jan 23 '17 at 14:44
  • $\begingroup$ It is not clear what you mean with length, but one way to find out is to go to findstat.org/StatisticFinder/Permutations, enter a few values and click the search button. Incindentally, you're chances of finding sage code there are quite good, too. $\endgroup$ – Martin Rubey Jan 23 '17 at 14:45

You can enumerate words of a given length in any Coxeter group using the function elements_of_length. Here is an example of using this for a Coxeter group I studied recently:

sage: CM = CoxeterMatrix([[1,2,-1,-1,2],[2,1,2,-1,-1],[-1,2,1,2,-1],[-1,-1,2,1,2],[2,-1,-1,2,1]])
sage: G = CoxeterGroup(CM, base_ring=ZZ)
sage: G.elements_of_length(3)
<generator object _elements_of_depth_iterator_rec at 0x1af3f0eb0>

The returned object is an iterator. So you can do things like

sage: for g in G.elements_of_length(1): print G
  • $\begingroup$ thank you very much. Your method solved the problem. But when the group is very large, for example, $S_{16}$. It will take a long time to compute G = CoxeterGroup(CM, base_ring=ZZ). Is it possible to list the elements of length $m$ directly? $\endgroup$ – Jianrong Li Jan 23 '17 at 15:13
  • $\begingroup$ Lehmer codes with given sum might be quick to generate. $\endgroup$ – Martin Rubey Jan 23 '17 at 15:25
  • $\begingroup$ @Martin Rubey, thank you very much. Are there some software for Lehmer codes? $\endgroup$ – Jianrong Li Jan 23 '17 at 15:32
  • $\begingroup$ doc.sagemath.org/html/en/reference/combinat/sage/combinat/… $\endgroup$ – Martin Rubey Jan 24 '17 at 9:01

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.