[GAP Forum] Fixed point free permutations of specific order

[Dmitrii Pasechnik]

Dear Aner,

On 30 January 2014 19:34, Aner Ben-Efraim <aner_2005 at hotmail.com> wrote:
> Dear Forum,
> I am interested in getting all permutations of order n (order 2 is
> also good) in the group SymmetricGroup([2..m]), which keep no point in
> place.
> I have tried to use Filtered(SymmetricGroup([2..m]),x->Order(x)=n and
> NrMovedPoints(x)=m-1), but this gets extremely slow when m is double
> digit. I was wondering if there is a way to do this in reasonable time
> on my PC, at least for m up to say 17, or even 33 if possible.

You probably will have to stop earlier than 33; indeed,
for order 2 case you essentially ask for the list of 1-factors of the
complete graph on m vertices (here m must be even). The number of these
things
grows quite fast, in fact it is equal to (n/2-1)!! (double factorial of
n/2-1). See
http://oeis.org/A001147

Going through them one by one would really take quite a long time on any
"ordinary" modern computer in reasonable time for m=32 (the number would
be 191898783962510625).

Anyhow, to do this as fast as possible you (IMHO) should not rely on
GAP, but rather write your
own code (or find it somewhere). Namely, for a given partition
m_1+...+m_k=m of m, with all m_j>1 and dividing n, you just have to fill
in the k vectors of lengths m_1,..,m_k with numbers from 1,...,m such
that in each vector you have a cyclically minimal sequence.
Now, do this for all such partitions (they represent possible cyclic
structures of fixed point free elements of order n). This will give you
all the permutations you are after, in cyclic notation.

HTH,
Dmitrii