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