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

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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .