Enumeration with Symmetries

In the previous chapters we saw some powerful tools which allow us to count many objects, tools which were especially useful if we wanted to count labelled objects. But imagine we wanted to count unlabelled objects, the number of graph on n vertices, for example. This is somewhat complicated by the fact that one has to ascertain when two graph are essentially the same. That is, there is a bijective map from the vertices of one to the vertices of the other which induces a bijection between the edges. To be able to count such objects one must be able to account for these isomorphic copies. Similarly, suppose we wanted to colour the faces of the cube with a set of say r colours. We have to account for the fact that many colourings will essentially be the same colourings when we allow for the rotations of the cube. In this chapter, we will see that such colourings can be counted if we know the symmetries of the object concerned. Polya’s theorem tells us that we need only construct a certain polynomial to be able to not only count the number of r-colourings but also the number of colourings with a fixed number of elements coloured a certain colour.