Customer Reviews

Combinatorial Enumerations of Groups, Graphs, and Chemical Compounds

5 star:		(0)
4 star:		(1)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

This is a translation of the 1937 paper by Polya where he showed his theorem on enumeration modulo a group. This is his prototypical example: one colours the vertices of an octahedron (say, three red, two blue, one yellow); in how many ways can this be done, taking into account rotational equivalence? All problems of this type are solved in a single sweep. All we need to know about the group is read off the cycle decomposition of the elements and easily encoded in a single polynomial expression, the "cycle index". The generating function that solves the general problem is then obtained by simply substituting the generating function for the stuff that is to be assigned (i.e. the colours) into this cycle index expression. With this powerful theorem Polya attacks enumeration problems for graphs and trees, which, he eagerly points out, "presents a continuation of work done by Cayley" (first sentence of the paper). As Cayley knew, one gets for free some very picturesque applications in terms of chemical compounds---the order of a vertex in a graph corresponds to the valency of an atom in a molecule. Accordingly, we can now enumerate "structurally isomeric alcohols C_nH_(2n+1)OH" and the like. The book also contains a forty-page supplement by Read on "The legacy of Polya's paper".