Order Polynomials and Pólya's Enumeration Theorem

  • Katharina Jochemko
Keywords: Pólya enumeration, group actions, partially ordered sets, order preserving maps, graph colorings


Pólya’s enumeration theorem states that the number of labelings of a finite set up to symmetry is given by a polynomial in the number of labels. We give a new perspective on this theorem by generalizing it to partially ordered sets and order preserving maps. Further we prove a reciprocity statement in terms of strictly order preserving maps generalizing a classical result by Stanley (1970). We apply our results to counting graph colorings up to symmetry.
Article Number