The cycle polynomial of a permutation group (Q1700769)

Summary: The cycle polynomial of a finite permutation group \(G\) is the generating function for the number of elements of \(G\) with a given number of cycles: \[ F_G(x) = \sum_{g\in G}x^{c(g)}, \] where \(c(g)\) is the number of cycles of \(g\) on \(\Omega\). In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of \(G\); this is the \textit{orbital chromatic polynomial} of \(\Gamma\) and \(G\), where \(\Gamma\) is a \(G\)-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where \(\Gamma\) is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group.