12160 is an interesting number; but I didn’t know that until last night.

As part of the work on semigroups, we are looking at the following problem.

Given *n* and *k*, with *n* ≥ 2*k*, suppose that *G* is a *k*-homogeneous subgroup of *S _{n}*. How many orbits does

*G*have on partitions of {1,…,

*n*} with

*n*−

*k*parts?

First, some information. A permutation group is *k*-homogeneous if it acts transitively on the set of *k*-element subsets of {1,…,*n*}. Clearly *k*-homogeneous is equivalent to (*n*−k)-homogeneous, hence the restriction *n* ≥ 2*k* is sensible.

According to well-known results in permutation group theory (depending on the Classification of Finite Simple Groups), all the *k*-homogeneous groups with *k* ≥ 2 are known. For *k* ≥ 6, the only such groups are the symmetric and alternating groups; and for these, the number of orbits on (*n*−*k*)-partitions is *p*(*k*), the number of partitions of *k*, independent of *n*. For the shape of such a partition is obtained by taking a partition of *k*, extending it with zeros so that it has *n*−*k* parts, and then adding 1 to each part.

For *k* = 5, there are only two further groups to consider, the Mathieu groups M_{12} and M_{24}. Clearly these will have only a finite number of orbits, so again it is true that the number is bounded by a function of *k*, independent of *n*. Also, for *n* = 4, there are only finitely many further groups, though the list is a little bit longer.

For *k* = 3, there are two infinite families of groups, together with a finite number of further examples. For one of the families (the affine groups over the 2-element field) the number of orbits is bounded independent of the degree; but for the other, it grows as a cubic in *n*. For *k* = 2, the situation is similar but even more complicated.

So can we compute the numbers?

My first attempt was to write a little program to generate all the (*n*−*k*)-partitions of {1,…,*n*}, and count orbits under the group action. This worked fine up to about *n* = 12, and in particular showed that for *k* = 5, the Mathieu group M_{12} has 30 orbits on 7-partitions. But the program ran out of memory when I tried it on the large Mathieu group.

The second approach was to note that, if a partition of {1,…,*n*} has *n*−*k* parts, then the union of the parts of size greater than 1 has a number of points between *k*+1 and 2*k*. So I could compute orbits of the group on sets of these sizes; for each orbit, choose a representative, calculate the group induced on it by its setwise stabiliser, and count orbits of this group on appropriate partitions. This involves many orbit counts, but they are of small groups. (For example, for M_{24}, we have groups with degrees from 6 to 10 rather than 24.) This program ran for M_{24}, and showed that it has 77 orbits on 19-partitions.

However, it still ran out of memory for the one remaining group, PΓL(2,32), a 4-homogeneous group of degree 33. It worked fine for sets of sizes 5, 6 and 7, but ran into problems for 8-sets.

So finally I implemented the following rather baroque idea. Start with a list of all the 4-subsets of {5,…,33}. Take the first subset in the list, take its union with {1,2,3,4}, take the orbit of this set under the group, filter out the sets containing {1,2,3,4}, and remove them from the list, until the list is empty. Keep an auxiliary list of the chosen 4-sets during the process, and adjoin {1,2,3,4} to each of them. Now these are orbit representatives for the group on 8-sets, and the rest of the computation is plain sailing.

The final number of orbits turned out to be 12160. (For the other 4-homogeneous groups, they are 5 – for symmetric and alternating groups – 26, 12, 21, 13, 38, and 15.)

Of course, it would be nice to have independent confirmation of this number …

If you find yourself in need of having to enumerate representatives of each orbit of a permutation group on k-subsets, the SetOrbit package of Pech and Reichard might be useful.

Let a finite group act on a finite set .

The number of orbits of on is

where runs through the subgroups of and

is the number of points in whose stabilizer is .

So if we can find all we can compute the number of orbits.

Let be the number of elements of

fixed by the subgroup .

Then . If we can find the we can

compute , and so then the number of orbits.

In general, this computation can be quite nasty. The

subgroup lattice of a group can be very complicated, even for

fairly ordinary groups. But this is very practical in the case

where and is the set o

-partitions

of , the projective line over .

Three factors are in our favour in this example. The stabilizer

of an element of is a subgroup of with order at

most .

Also for a given all subgroups of with order

are conjugate in (even if not conjugate in ) and so

depends only on . Finally, if ,

the number of subgroups of order such that

for a given of order only depends on

and .

This is because has a very simple subgroup structure,

for instance every -subgroup is contained in a unique Sylow

subgroup.

Once we have noticed this, the computation of the number of

-orbits on is now a “back-of-an-envelope” job.

I get orbits, just the same as Peter!

Yes, and I have to say how relieved I was when Robin came up with the same answer!