Article ID Journal Published Year Pages File Type
11001892 Discrete Mathematics 2019 15 Pages PDF
Abstract
Given a subgroup G of the symmetric group Sn, the cycle index polynomial cycG is the average of the power-sum symmetric polynomials indexed by the cycle types of permutations in G. By Pólya's Theorem, the monomial expansion of cycG 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 Sn, the alternating groups An, direct products, conjugate subgroups, and certain cyclic subgroups of Sn 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,