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 …