# Cycle index of a permutation group acting on k-subsets

I am looking for an explanation of how to find the cycle index of a permutation group on a set X acting on the collection $\binom{X}{k}$ of k-subsets of X.

Can it be found solely from k and the cycle index on X?

If not, then how can one effectively compute it for small k and for |X| ≤ 100 for the cyclic, dihedral, alternating, and symmetric groups (in their natural permutation representations).

If X is a vector space, are there more efficient methods of calculating the cycle index? What if the group is the general linear group (or one of the other classical groups)?

• I don't think that this is a reference request. – Phira Apr 24 '11 at 23:33
• I am looking for a textbook or article that discusses cycle indices. The discussion should very specifically address computing the cycle index of the subset action from the cycle index of the natural action. If such a calculation can't be done in general, then how does one do it for the specific families (I know this can be done relatively efficiently, I have hard to read code that does so). It'd be nice if it also happened to work for linear groups, but I have no specific reason to believe it does. I know that at least one article exists for k=3, but I don't have access to it. – Jack Schmidt Apr 24 '11 at 23:42
• Maybe you could tell us what article it is. – Phira Apr 24 '11 at 23:46
• I linked the Kamuti–Obon'go (2002) article and gave sort of a sample answer, "Here is a description of some references and how they relate to your question." – Jack Schmidt Apr 25 '11 at 0:22

Here are some references which somewhat address the problem, but so far without providing me any computational help:

Polya (1937) introduced the cycle index and showed how to use it to count things, but I think does not really describe how to get X choose 2 from X (rather he just does |X|=4 explicitly). Palmer (1973) indicates how to use cycle indices to count simplicial complexes, and computes (mostly correctly) the relevant cycle indices for small numbers of vertices and small dimension. Kamuti–Obon'go (2002) corrects some mistakes and presumably solves one of the open questions in the Palmer article, but I don't have access to it. Fullman (1999) and some other similar papers describe the cycle indices of classical groups in their natural action, so if the cycle index on X choose k can be computed form the cycle index on X, then my question is answered for classical groups. As far as cyclic, dihedral, alternating, and symmetric groups are concerned, the Mathematica package "Combinatorica" by Pemmaraju–Skiena (2003) has relatively efficient methods, and I believe Brendan McKay has quite efficient methods (that I have not found yet).

What I really lack is some sort of simple textbook treatment of this. Surely k-subset actions are important to study (permutation group books certainly treat such things, but so far I haven't noticed any that address cycle indices).

• G. Pólya. "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen". Acta Mathematica 68 (1937), 145–254. DOI:10.1007/BF02546665
• Palmer, Edgar M. "On the number of n-plexes." Discrete Math. 6 (1973), 377–390. MR335345 DOI:10.1016/0012-365X(73)90069-1
• Kamuti, I. N.; Obon'go, J. O. "The derivation of cycle index of $S^{[3]}_n$." Quaest. Math. 25 (2002), no. 4, 437–444. MR1946921 DOI:10.2989/16073600209486028
• Fulman, Jason. "Cycle indices for the finite classical groups." J. Group Theory 2 (1999), no. 3, 251–289. MR1696313 DOI:jgth.1999.017
• Pemmaraju, Sriram; Skiena, Steven. Computational discrete mathematics. Combinatorics and graph theory with Mathematica. Cambridge University Press, Cambridge, 2003. ISBN: 0-521-80686-0 URL:combinatorica.com

It is better to look at all cycle indices of a family of groups at once and regard unlabelled species:

http://en.wikipedia.org/wiki/Combinatorial_species#Types_and_unlabelled_structures

What you want is a special case of composition of the Z's in the above link and you can see that a formula exists, but is complicated.

• I'm not sure this addresses any of the questions. How does this help compute the cycle index of M24 acting on 3-sets (naive conjugacy class method takes 10 seconds to compute, 4-sets is probably a few minutes)? What about GL(6,2) acting on 4-sets of vectors? – Jack Schmidt Apr 24 '11 at 23:45