Enumeration formulas

TucA74 Tucker, A. Polya s enumeration formula by example. Math. Mag. 47 (1974) 248-256. 

A paper in the same journal [PolG36b] elaborated on isomer enumeration and the corresponding asymptotic results. Here the functional equations for the generating functions for four kinds of rooted trees were presented without proof. They were, in a slightly different notation, formulae (8), (4), and (7) in the introduction to Polya s main paper, and one form of the functional equation for the generating function for rooted trees. From these results a number of asymptotic formulae were derived. These results were all incorporated into the main paper. 

Rather similar was the paper [PolG36a] which also derives asymptotic formulae for the number of several kinds of chemical compounds, for example the alcohols and benzene and naphthalene derivatives. Unlike the paper previously mentioned, this one gives proofs of the recursion formulae from which the asymptotic results are derived. A third paper on this topic [PolG36] covers the same sort of ground but ranges more broadly over the chemical compounds. Derivatives of anthracene, pyrene, phenanthrene, and thiophene are considered as well as primary, secondary, and tertiary alcohols, esters, and ketones. In this paper Polya addresses the question of enumerating stereoisomers -- a topic to which we shall return later. 

It was largely this chemical interpretation which led Cayley to enumerate various kinds of trees. He gave (without much of a proof) the formula for the number of trees on n labelled vertices [CayA89], and the equation... 

In the realm of chemical enumeration we note Polya s equation (4.4) which gives the generating function for stereoisomers of the alkyl radicals, or equivalently, alcohols — that is, equation (5.2) of this article. His equation (4.3) gives the corresponding result for the structural isomers of these compounds. His equations (4.2) and (4.5) correspond, respectively, to the cases of alcohols without any asymmetric carbon atoms and the number of embeddings in the plane of structural formulae for alcohols in general. The latter problem is not chemically very significant. 

It was found [9,49] that all the postulates enumerated above are satisfied by the autoclave method for the reduction of technetious acid in concentrated hydrogen halide solutions by molecular hydrogen under a pressure of 3-5 MPa at 140-220 °C. A series of experiments showed that the final product of the reduction of H [TcOJ under these conditions is a mixture of outwardly similar crystalline substances with similar physico-chemical properties. The composition of the mixture can be described by the general overall formula [TcXi,s o.3 m(H20, OH , H30+)] , where X = I or Br and n > 2.8... 

Using Assertion 8, it is not difficult to derive the following formulas for generating solutions of the Yang-Mills equations by the transformation groups enumerated above [33] ... 

If these conjectures are accepted the quantity /ne should tend to a limit as n - oo, and an estimate of this limit can be derived from the exact enumerations. Consequently an asymptotic formula can be put forward for the behavior of as a function of n, and this can be compared with Monte Carlo values for much longer walks. Such a comparison with walks of up to 600 steps on the tetrahedral and square lattices is reproduced in Table II, and the percentage deviations are recorded. An error of order 2% or 3% seems reasonable for a sample of about 1000 walks and the constanty of sign of eror may well be due to the enrichment 9 procedure introduced by Wall and Erpenbeck so as to overcome attrition. 

Comparison between asymptotic formulas based on direct enumeration and Monte Carlo estimates. Tetrahedral and square lattices. (Wall and Erpenbeck9). 

All the remaining enumeration is done with Formula 9.2 and exhaustive analysis of local configurations. ... 

For the parent compound of the menthane-type (Type A) monocyclic terpene hydrocarbons, the name menthane, its well-established fixed numbering of the carbon skeleton, and extension of nomenclature rules to apply to double bonds outside the ring have been recommended (for the p-form, see Formula 6, Chart 5, p. 19). These recommendations and the extension of nomenclature practices to apply to points of attachment outside the ring are basic to the rules for forming the names of menthane-type monocyclic radicals. Since the enumeration of the parent compound is fixed, the position number of a point of attachment in radicals derived from it is predetermined and will not always be numbered as 1. 

By merging our prior aufbau concept with the Formula Periodic Table for Benzenoid Hydrocarbons (Table PAH6), the enumeration process itself will have a... 

The enumeration of Kekule structures for rectangle-shaped benzenoids is treated. Combinatorial formulas for K (the Kekule structure count) are derived by several methods. The oblate rectangles, Rj(m, n), with fixed values of m are treated most extensively and used to exemplify different procedures based on the method of fragmentation (chopping, summation), a fully computerized method (fitting of polynominal coefficients), application of the John-Sachs theorem, and the transfer-matrix method. For Rj(m, n) with fixed values of n the relevant recurrence relations are accounted for, and general explicit combinatorial K formulas are reported. Finally a class of multiple coronoids, the perforated oblate rectangles, is considered in order to exemplify a perfectly explicit combinatorial K formula, an expression for arbitraty values of the parameters m and n. 

The manner in which chemical structure is described depends upon the concept applied. A chemical can variously be considered as a microscopic ensemble of nuclei and electrons and so may be described with energy functions. Alternatively, it can be regarded as a macroscopic collection of molecules and characterized with physicochemical properties. The term chemical structure is also related to the molecular formula (i.e., the atoms of which the molecule is composed, and the way in which those atoms are connected). According to Kier and Hall (2001), the structure is the count of each atom, identified as its element, along with a description, enumeration, or characterization... 

The loctions of the posints and lines enumerated above, and related formulae for their computation, are summarized in Table I. 

The enumeration of all-benzenoids was foreshadowed by Dias [121-123], who discussed 2-factorable benzenoids in the frame of the enumeration of benzenoid isomers (according to the chemical formulas C HS). In these works Dias depicted some all-benzenoids as examples. It was Knop et al. [91] who presented the first list of the numbers of all-benzenoids according to the number of hexagons (h) see Table 40. In later works, Dias [25, 124, 125] enumerated some all-benzenoid... 

Benzenoid (chemical) isomers are, in a strict sense, the benzenoid systems compatible with a formula C HS. Several invariants, including the Dias parameter, are treated and relations between them are given. Many of the relations involve upper and lower bounds. The periodic table for benzenoid hydrocarbons is revisited and new aspects of it are pointed out. In this connection some new classes of benzenoids are defined extreme-left, protrusive and circular. Extensive tables of enumeration data for benzenoid isomers are presented. Some of their forms are displayed in figures. 

In the light of these long traditions, extensive enumerations of the isomers of benzenoid hydrocarbons is a very new area. A systematic investigation can be dated to 1982 with the first paper of Dias [7] (but see also below). He published an article series in ten parts [7-16] entitled A Periodic Table for Polycyclic Aromatic Hydrocarbons and more recent works [17, 18]. With the invention of the periodic table, Dias created orderness in the chaotic myriads of chemical formulas for benzenoid hydrocarbons, which may be written. He has also written a monograph [19] with relevance to this topic and some other reviews [20-22], Two years before Dias, Elk [23] published a paper on benzenoids, which contains explicitly the enumeration of isomers up to h = 5. It seems that the work of Elk has largely been overlooked in the context of benzenoid isomer enumeration. 

In the present chapter the studies of benzenoid isomers, or benzenoid systems compatible with a formula C Hj, are reviewed. On one hand the emphasis is laid on precise definitions and relations. Some of the relations, especially for certain upper and lower bounds, have not been published before. On the other hand a comprehensive collection of enumeration data with documentations is presented. 

One of the classical problems in the enumeration of chemical isomers was posed more than a hundred years ago [1, 2] — How many alkanes with the formula CjvH2N+2 can be constructed It is a well-known fact in organic chemistry that there is one methane (N = 1), one ethane (N = 2), one propane (N = 3), but two butanes (N = 4) and three pentanes (N = 5). These isomers can be symbolized in the simplest way as ... 

In Fig. 2 is an attempt to give a general idea of how far the enumerations of benzenoid isomers have been advanced up to now. The position of a formula C HS in the dot-diagram representation of the periodic table is marked by an asterisk if the corresponding numbers of isomers are known (at least) for the Kekulean and non-Kekulean systems separately. 

The full-drawn staircase line in Fig. 2 indicates the limit for the significant enumerations of Stojmenovic et al. [17]. In that work the separate numbers for Kekulean and non-Kekulean systems were not determined. However, it was taken into account, when the asterisks were distributed, that odd-carbon atom formulas (C HS with n and s odd) pertain to non-Kekuleans only, while even-carbon atom... 

---