Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds

This paper presents a continuation of work done by Cayley. Cayley has repeatedly investigated combinatorial problems regarding the determination of the number of certain trees¹, Some of his problems lend themselves to chemical interpretation: the number of trees in question is equal to the number of certain (theoretically possible) chemical compounds.

We begin by generalizing the problem which is at the root of the example in Sec. 2. There are two types of generalizations: on the one hand the colored balls discussed in Sec. 2 have to be replaced by more complex objects, which we will call figures; on the other hand, the special permutation group of the octahedron rotations will have to be replaced by a more general permutation group.

In the next sections we describe in axiomatic-combinatorial terms what the chemists call structure and stereoformulas. To enhance the clarity of the exposition I provide more than the bare essentials. I begin by repeating some known definitions in graph theory. Some problems touched upon in the Introduction are going to be presented “officially” later on. I will adhere as much as possible to the terminology used by D. König in his elegant text.¹ I will highlight where substantial departure seemed to better serve the special purpose of this paper.

The elements of a graph have their interpretation in chemistry, the vertices are atoms, the edges are bonds, the graph turns into a chemical (structural) formula. Conditions I and II in Sec. 29 become meaningful in chemical terms. Every edge terminating in two endpoints means that there are no free valences. The connectedness of a graph indicates that all atoms are tied together into a molecule. The number of edges ending in the same vertex corresponds to the valence of the atom: endpoints are atoms of valence one, vertices of degree k represent atoms of valence k.

In the preceding section, we have established the importance of the power series q(x), r(x), s(x), t(x) in combinatorics. Here we examine their analytical properties: radius of convergence, singularities on the circle of convergence, analytic continuation. We derive these characteristics from the functional equations whose solutions these series present. I start with a summary of the equations and some notations.

Pólya’s paper, translated here for the first time, was a landmark in the history of combinatorial analysis. It presented to mathematicians a unified technique for solving a wide class of combinatorial problems — a technique which is summarized in Pólya’s main theorem, the “Hauptsatz” of Section 16 of his paper, which will here be referred to as “Pólya’s Theorem”. This theorem can be explained and expounded in many different ways, and at many different levels, ranging from the down-to-earth to highly abstract. It will be convenient for future reference to review the essentials of Pólya’s Theorem, and to this end I offer the following, rather mundane, way of looking at the type of problem to which the theorem applies and the way that it provides a solution.