Order Polynomials and Pólya's Enumeration Theorem

Katharina Jochemko


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.


Pólya enumeration; group actions; partially ordered sets; order preserving maps; graph colorings

Full Text: