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