Other Enumerations

5 Other Enumerations. - Evaluations of permanents have been pursued by Cash (such permanents being involved in several different enumerations, including that of Kekule structures as mentioned in Section 2.5). He finds efficient means for their evaluation for matrices of up to 80 rows and columns, at least if the matrices have some sparsity. 

Tasi et make an enumeration of conformers of normal-alkane chains. 

Such does not require use of Polya-theoretic machinery and has been considered several times previously over the years. A difference in the present enumeration (using relatively straightforward mathematics to give a largely analytic enumera- 

Nitta considers some polymer statistical results for the variety of chains of branched acyclic molecules (such as alkanes). 

Xu and Johnson consider the classification of molecules into equivalence classes identified by substructures associated with molecular pseudographs . Here the pseudographs represent homeomorphism classes of graphs (wherein degree-2 vertices are deleted), and again the Morgan extended neighbor idea is utiUzed. 

---

Among other things, Redfield s paper led to a heightened awareness of something that was already beginning to be realized, namely the interrelationship between Polya s Theorem (and other enumeration theorems) on the one hand, and the theory of symmetric functions, -functions, and group characters on the other it helped to show the way to the use of cycle index sums in the solution of hitherto intractable problems and in a more nebulous way it provided a refreshing new outlook on combinatorial problems. 

It also happens that new researchers are being attracted to the field of polyhex enumerations. E. C. Kirby (Resource Use Institute, Pitlochry, Scotland, UK) may be reckoned as one of them, although his latest contributions [141,143] were preceded by some other enumeration-oriented works [85,153]. His latest work [141] makes a significant contribution to our understanding of all-benzenoids. Another name, which has recently entered the arena, is William C. Herndon (University of Texas at El Paso, Texas, USA). His enumerations [138], based on a computerized coding system for polyhexes [154], is particularly chemistry-oriented inasmuch as it takes stereoisomerism into account. 

Other Enumerations. - In this section, we present combinatorial enumerations that do not fit in any of the above sections, though some are related to discussions above or in our previous Reports.1,2... 

Other enumeration algorithms were developed [98,99,132,309,310,320]. There are also interesting applications of Polya s enumeration theorem [ 198,338]. The theorem was, e.g., applied [321,324,330,331] to enumerations of isomers for various substituted fullerenes. 

A number of physical chemistry relationships, not enumerated in other sections see Index), will be discussed in this section. 

Several other chemical reactions are also widely used for the synthesis of these polymers. This list enumerates some of the possibilities and Table 5.3 illustrates these reactions by schematic chemical equations ... 

Theorem 5. The transpose of is a complete B-matrrx of equation 13. It is advantageous if the dependent variables or the variables that can be regulated each occur in only one dimensionless product, so that a functional relationship among these dimensionless products may be most easily determined (8). For example, if a velocity is easily varied experimentally, then the velocity should occur in only one of the independent dimensionless variables (products). In other words, it is sometimes desirable to have certain specified variables, each of which occurs in one and only one of the B-vectors. The following theorem gives a necessary and sufficient condition for the existence of such a complete B-matrix. This result can be used to enumerate such a B-matrix without the necessity of exhausting all possibilities by linear combinations. 

The various types of localised corrosion have been enumerated in Table 1.2 in Section 1.1, and many of them are dealt with in some detail in other sections of this volume. For this reason this section will be confined to a consideration of the factors that give rise to crevice corrosion, filiform corrosion, pitting, selective leaching and erosion-corrosion and of the mechanisms of these forms of localised attack. 

This illustrates an important distinction in chemical enumeration that between the enumeration of "structural" isomers, in which only the connections between the atoms are considered, and that of stereoisomers, in which the situation of a molecule in space is important, so that as above we can have right- and left-hand forms of a molecule. This distinction will occur, for example, when a carbon atom is bonded to four distinct substituents (it can occur in many other ways). Such a carbon atom is said to be asymmetrical. 

In addition to these main results some others can be found in Polya s paper, notably the enumeration of doubly and multiply substituted alkanes. 

A question which chemical enumerators should not ignore is that of the extent to which their results are realistic in the physical world. Thus in [BlaCSla] it is stated that the number of alkanes (paraffins) with 40 carbon atoms is 62,491,178,805,831. Can we really be sure that all these compounds can exist or could it be that factors not catered for in the enumeration render some of them chemically infeasible In this connection we should note the paper [KleD81], in which it is shown jthat because of such factors the chemical tree enumerations by Polya and others give numbers that are consistently higher than the number of compounds that are in fact chemically possible. This does not detract from the mathematical value of these results it merely shows that care is needed in relating them to problems of real life. 

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... 

The use of Polya s Theorem in a specialized context such as the above, has led to the extension of the theorem along certain useful lines. One such derivation pertains to the situation where the boxes are not all filled from the same store of figures. More specifically, the boxes are partitioned into a number of subsets, and there is a store of figures peculiar to each subset. To make sense of this we must assume that no two boxes in different subsets are in the same orbit of the group in question. A simple extension of Polya s Theorem enables us to tackle problems of this type. Instead of the cycle index being a function of a single family of variables, the 5j, we have other families of variables, one for each subset. An example from chemical enumeration will make this clear. 

When there are many carbon atoms which might be asymmetrical, the solution is more complicated. Nevertheless, by methods that basically rely on Polya s Theorem, enumeration of compounds taking chirality into account can be carried out. For alkanes and mono-substituted alkanes see the paper [BalA76] for the chiral alkanes with some restrictions see [QuiL77,79]. See also [HarF75], [PalE77], and [WorNSl] for other problems in which chirality appears. 

To conclude this section, we note quickly a few other asymptotic enumerations. In [PalE70] Palmer found an asymptotic estimate for the number of self-complementary graphs and digraphs. Robinson [RobR76] and Stanley [StaR73] enumerated acyclic digraphs, and obtained the asymptotic estimate... 

The two specific areas of research in which Polya s Theorem has been most extensively applied are graphical and chemical enumeration, a fact which Polya clearly foresaw in his choice of title. Applications in other fields are far from rare, however, and it is fitting to give a brief account of a few such uses of the theorem. 

---