1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ What do you mean by "length"? $\endgroup$
    – Igor Rivin
    Jan 23, 2017 at 14:42
  • $\begingroup$ @Igor Rivin, I will edit the post. $\endgroup$ Jan 23, 2017 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$ Jan 23, 2017 at 14:45

1 Answer 1

2
$\begingroup$

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
$\endgroup$
4
  • $\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$ Jan 23, 2017 at 15:13
  • $\begingroup$ Lehmer codes with given sum might be quick to generate. $\endgroup$ Jan 23, 2017 at 15:25
  • $\begingroup$ @Martin Rubey, thank you very much. Are there some software for Lehmer codes? $\endgroup$ Jan 23, 2017 at 15:32
  • $\begingroup$ doc.sagemath.org/html/en/reference/combinat/sage/combinat/… $\endgroup$ Jan 24, 2017 at 9:01

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.