Number of rotation subgroups of S_n

Christian G.Bower bowerc at usa.net
Tue Oct 11 23:45:30 CEST 2005


> A friend suggested the following set of sequences

> Let S_n be the symmetric group of all perms of n letters,
> of order n!

> A transposition is a permutation like (3,5).
> A reflection is any element of order 2, that is, a product
>    of disjoint transpositions
> A "rotation" is a product of two transpositions, not necessarily disjoint,
>    so either (1,2,3) or (1,2)(3,4), etc.

> Questions:
> How many subgroups of S_n have the property that they are
> generated by rotations?
> How many non-isomorphic ones?

Let's start with some basics.  I'll abbreiviate permutation group as
PRG.

The relevant sequences are:
Unlabeled PRGs
http://www.research.att.com/projects/OEIS?Anum=A000638

Labeled PRGs
http://www.research.att.com/projects/OEIS?Anum=A005432

Unlabeled even PRGs
http://www.research.att.com/projects/OEIS?Anum=A029726

Labeled even PRGs
http://www.research.att.com/projects/OEIS?Anum=A029725

All of these are hard sequences, thus it is likely that these new
sequences are also hard.  I mention the even cases because the
"rotation" is necessarily limited to even permutations.
For non-isomorphic (my unlabeled case) I'm considering isomophism
as PRGs rather than as groups.  The PRGs <(12),(12)(34)> and
<(12)(34),(13)(24)> are isomophic as groups (to the Klein-4 group)
but not as PRGs.  This seems more natural to me, but if the
correspondent is specifically interested in group isomorphism,
they should specify.

I counted by hand cases up to n=5

Unlabeled: 1,1,2,5,8
Labeled:   1,1,2,10,53

Obviously the unlabeled case is way to short to check the EIS for.
I checked for the labeled case and got some hits that appear
unlikely to be the sequence in question.

> How many subgroups of S_n have the property that they are
> generated by reflections?  (Is this the Bell numbers, A000110 ?)
> How many non-isomorphic ones?  (Again, this may be a well-known sequence)

Unlabeled: 1,2,3,8,13
Labeled:   1,2,5,22,104

Several hits for unlabeled (none are likely matches)
No hits for labeled.

I have a list of PRGs of order 6 and 7 but I've never had a chance
to study the list carefully.  Thus extending this list will be very
cumbersome with my resources.  8 and beyond is out of the question for
me.  Is this something GAP or MAGMA can do?  Anyone here use those?

> Same two questions for groups generated by rotations AND reflections?

I haven't looked at that yet.

Christian








More information about the SeqFan mailing list