Theorem Polya

Biirmann-Lagrange theorem. Polya-Szegd, Problems and Theorems in Analysis, Vol. I, (1972) pp. 145-146. 

Polya 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 Polya s main theorem, the "Hauptsatz" of Section 16 of his paper, which will here be referred to as "Polya 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 Polya 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. 

We can now display Polya s Theorem in its one-variable form as follows. 

More generally the content of a figure will be a vector of nonnegative integers. Polya frequently used vectors of dimension 3. In that case the generating functions will be functions of three variables, and the statement of Polya s Theorem then gives... 

An earlier paper [PolG35] contained the essence of Polya s Theorem in its three-variable form, together with an informal proof of it. This paper also entered into the field of isomer enumeration by presenting a generating function for the substituted benzenes. 

To obtain Polya s Theorem from this we take the "weight" of a figure to be x where k is its content. (We should note here that the term "weight" is regarded by some authors as synonymous with "content" however, it is preferable to use them for the two different concepts just given.) Suppose that a configuration is invariant under... 

It used to be the case that almost any author who wrote a paper on some application of Polya s Theorem deemed it necessary to preface the application with an account, perhaps brief, perhaps comprehensive, of the theorem. Thus the number of expositions of the theorem in the early literature was almost equal to the number of publications. In this section we shall look only at some early expositions that were given of the theorem for its own sake, for the purpose of instruction, rather than as a means to an end. 

In 1967 Harary presented a proof of Polya s Theorem in Chapter 4 of his book [HarF67], and in the following chapter gave some applications. Four years later in Chapter 15 of "Graph Theory" [HarF71] he again gave an exposition of Polya s Theorem and some developments of it. 

Comtet s two-volume work on combinatorics [ComL70] appeared in 1970. It contained an account and proof of Polya s Theorem together with all the necessary preliminaries — definitions of cycle-index, Burnside s Lemma, and so on. Comtet illustrated Polya s Theorem by a single example, the coloring of the faces of a cube. 

By this time Polya s Theorem had become a familiar combinatorial tool, and it was no longer necessary to explain it whenever it was used. Despite that, expositions of the theorem have continued to proliferate, to the extent that it would be futile to attempt to trace them any further. I take space, however, to mention the unusual exposition by Merris [MerRSl], who analyzes in detail the 4-bead 3-color necklace problem, and interprets it in terms of symmetry classes of tensors — an interpretation that he has used to good effect elsewhere (see [MerRSO, 80a]). 

The use of Polya s Theorem in the enumeration of rooted trees is amply described in Polya s paper and needs little comment here. We shall note an important point in connection with the enumeration of alkyl radicals. A radical is a portion of a molecule that is regarded as a unit that is, it will be treated much the same as if it were a... 

To find the number of trees rooted at an edge we have merely to take the distinguished edge and add a rooted tree at each end. This is a Polya-type problem with two interchangeable boxes, and figure generating function T(x). Polya s Theorem thus gives... 

Polya s Theorem clearly showed the way to the general enumeration of all acyclic hydrocarbons, irrespective of how many double or triple bonds they might have but it was to be 35 years before this enumeration was carried out. In two papers [ReaR72,76] I obtained the solution to this general problem in both the structural isomer and stereoisomer cases, as generating functions in three variables. Of these variables, x marks the number of carbon atoms, y the number of double bonds, and z the number of triple bonds. The de- rivation of these generating functions was Polya theory all the way — a succession of applications of Polya s Theorem with occasional use of Otter s result. The derivation was really rather tedious, but the generating functions, once obtained, can be used to compute the... 

We have already noted that Polya s Theorem can be stated in the context of mappings from one set to another. Let D and R be two sets, and G a group of permutations of the elements of D, and consider the set of all mappings f D - R. If D is a set of boxes and R the set of figures, then each such mapping corresponds to a configuration. 

A theorem which, at first sight, does not seem to be very closely related to Polya s Theorem, but which in fact has much affinity with it, is the superposition theorem that appeared in my doctoral thesis [ReaR58] and later in [ReaR59,60]. The general problem to which it applies is the following. Consider an ordered set of k permutation groups of degree , say G. G. . and the set of all A -ads... 

It goes without saying that neither Polya s Theorem nor the superposition theorem is really needed to solve this simple problem — a... 

If the vertices are labelled with labels 1,2,. .., p then there are N = p p - 1) pairs of vertices, all distinct, and the problem of finding the number of such graphs with q edges is simply that of choosing q elements from a set of N elements. This number is, of course, (q). If the vertices are unlabelled, however, the problem is less easy and calls for the use of Polya s Theorem. 

We now need to know the appropriate group G. Since they are not labelled, we can permute the vertices in any way, that is, by any element of 5p, the symmetric group of degree p. Each permutation of the vertices will induce a permutation of the pairs of vertices, and these permutations form the group that we require. We can denote it by Polya s Theorem then gives the configuration... 

A series of four papers by G. W. Ford and others [ForG56,56a,56b, 57] amplified this work by using Polya s Theorem to enumerate a variety of graphs on both labelled and unlabelled vertices. These included connected graphs, stars (blocks) of given homeomorphic type, and star trees. In addition many asymptotic results were derived. The enumeration of series-parallel graphs followed in 1956 [CarL56], and in that and subsequent years Harary produced... 

---