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 <[EMAIL PROTECTED]> * 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. _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
