[GAP Forum] size of permutation groups

[Allan Adler]

Maybe I should say what my examples are. In section 1.3.3 of Knuth's
Art of Computer programming, Knuth mentions an unusual correspondence.
One takes a permutation p on n letters, as a list of n values, the i-th
value being p(i). E.g., consider 1435276. This has the cycle decomposition
(1)(245)(3)(67). We rearrange the cycle decomposition so that each cycle
begins with its smallest element and so that the cycles are listed in
decreasing order of their first elements: (67)(3)(245)(1). Knuth then
observes that one can safely remove the parentheses, since one can figure
out where they were: 6732451. Furthermore, without the parentheses, it
describes another permutation. So, basically, Knuth has defined a
bijection from the symmetric group on n objects to itself. Denote
that bijection K. I computed its orbits for a few values of n. On the
other hand, let * denote the bijection of the symmetric group to itself
which sends each permutation to its inverse. There are other nice
bijections to play with, but I'm just starting with K and *. For n=3,
K and * generate a group of order 72 on 6 = 3! objects. For n=4 and n=5
they generate the full symmetric group of order n!! on n! objects. It is
natural to speculate that this holds for all n > 3. I was computing
examples and couldn't compute past n=5.

I wrote K and * as permutations on List([1..Factorial(n)]) using a
C program I had written. Then I fed them to Gap3. Maybe it is convenient
to work directly in Gap. Anyway, if someone would like to compute more
examples, I'd be interested in their results.

I've written to Knuth to see if he has a reference for K. I've never seen
it before. Maybe my speculation above is already someone's theorem?

Steve Linton wrote:
>On my laptop this took 12 seconds for two random permutations of a million
>points.

If your laptop can handle Group(K,*) for n up to 9 or 10, maybe I should
offer to buy your laptop. :)
-- 
Ignorantly,
Allan Adler <ara at zurich.csail.mit.edu>
* Disclaimer: I am a guest and *not* a member of the MIT CSAIL. My actions and
* comments do not reflect in any way on MIT. Also, I am nowhere near Boston.