Quasisymmetric and Schur expansions of cycle index polynomials

Abstract Given a subgroup G of the symmetric group S n , the cycle index polynomial cyc G is the average of the power-sum symmetric polynomials indexed by the cycle types of permutations in G . By Polya’s Theorem, the monomial expansion of cyc G is the generating function for weighted colorings of n objects, where we identify colorings related by one of the symmetries in G . This paper develops combinatorial formulas for the fundamental quasisymmetric expansions and Schur expansions of certain cycle index polynomials. We give explicit bijective proofs based on standardization algorithms applied to equivalence classes of colorings. Subgroups studied here include Young subgroups of S n , the alternating groups A n , direct products, conjugate subgroups, and certain cyclic subgroups of S n generated by ( 1 , 2 , … , k ) . The analysis of these cyclic subgroups when k is prime reveals an unexpected connection to perfect matchings on a hypercube with certain vertices identified.