Lattice animals: Supplementation of perimeter polynomial data by graph-theoretic methods

Application of graph-theoretic methods to new perimeter polynomials for connected clusters on a lattice yields extra data on the total number of clusters and for the coefficients in the series expansion for the mean size of clusters at low densities. The lattices studied are the square, the square with next nearest neighbors, the triangular, and the simple cubic.     

First-passage times in a critical stochastic model

Average first-passage times for a single-variable stochastic model with a critical fixed point at the origin are computed by exact enumeration. The numerical measurements show excellent agreement with analytical results. The scaling function approaches the predicted asymptotic dependence.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

Zero-temperature properties of randomly self-interacting polymers

We study the zero-temperature behavior of several simple models for randomly self-interacting polymers in one and 1+1 dimensions. Results are based on exact enumeration and closed-form expressions.     

Symmetry specified enumeration of substituted derivatives: an easy solution to the complex problem

Several sophisticated methods to solution of symmetry specified enumeration problems are available in the modern literature. In this paper we propose a simple technique that allows one to manually compute the exact numbers of fixed-symmetry derivatives for a given structure either with inclusion or ignoring the substitution patterns. The basic idea of the method suggested consists in the derivation of Pólya-like cycle indices for the automorphism groups of specially constructed orbit partition graphs; the expansion of these indices and subsequent simple calculations result in the desired numbers of substituted derivatives with achiral substituents. Limitations of the new technique (and a method suggested earlier) depend on the relevance of the orbit partitions for particular subgroups of the point symmetry group. For illustration purposes, the results obtained for the prismane (D _3h ) and adamantane (T _d ) structures are discussed. In the former case the numbers of substituted derivatives can be found for all subgroups of the D _3h group, whereas in the latter case these numbers can be determined for eight out of eleven subgroups of the T _d point symmetry group. This work is based on the text of the lecture presented by the authors at the 5th All-Russia Conference on Molecular Modeling (Moscow, April 2007). The paper deals with the methodology and detailed treatment of applied aspects related to solution of enumeration problems for substituted derivatives with prescribed symmetry groups. Unlike the known methods of symmetry specified enumeration, the technique suggested is simple enough and may be regarded as generalization of the Pólya methodology, which is widely used by chemists. Published in Russian in Izvestiya Akademii Nauk. Seriya Khimicheskaya, No. 2, pp. 227–245, February, 2008.     

Zhang–Zhang Polynomials of Multiple Zigzag Chains Revisited: A Connection with the John–Sachs Theorem

Multiple zigzag chains Zm,n of length n and width m constitute an important class of regular graphene flakes of rectangular shape. The physical and chemical properties of these basic pericondensed benzenoids can be related to their various topological invariants, conveniently encoded as the coefficients of a combinatorial polynomial, usually referred to as the ZZ polynomial of multiple zigzag chains Zm,n. The current study reports a novel method for determination of these ZZ polynomials based on a hypothesized extension to John–Sachs theorem, used previously to enumerate Kekulé structures of various benzenoid hydrocarbons. We show that the ZZ polynomial of the Zm,n multiple zigzag chain can be conveniently expressed as a determinant of a Toeplitz (or almost Toeplitz) matrix of size m2×m2 consisting of simple hypergeometric polynomials. The presented analysis can be extended to generalized multiple zigzag chains Zkm,n, i.e., derivatives of Zm,n with a single attached polyacene chain of length k. All presented formulas are accompanied by formal proofs. The developed theoretical machinery is applied for predicting aromaticity distribution patterns in large and infinite multiple zigzag chains Zm,n and for computing the distribution of spin densities in biradical states of finite multiple zigzag chains Zm,n.     

Enumeration of the isomers of phenylenes

Summary The [h]phenylene C_6h H_2h+4 isomers are enumerated up toh=12. The numbers are compared with old and new data for C _n H₅ isomers of benzenoids, fluoranthenoids and biphenylenoids.

---

Anzahl möglicher Isomerer von Phenylenen

Zusammenfassung Die Anzahl der [h]Phenylen-Isomeren C_6h H_2h+4 wurde bish=12 ausgewertet. Die Zahlen wurden mit alten und neuen Daten für C _n H _s -Isomere von Benzenoiden, Fluoranthenoiden und Biphenyloiden verglichen.

     

N叉树上的离散时间量子随机行走

通过离散时间量子随机行走的框架,我们研究了在N叉树上的离散时间量子随机行走,该框架不需要硬币空间,仅仅只需要选择一个除了酉性再无其它限制的演化算子,并且包含了使用再生结构的轨道枚举和z变换.作为结果,我们在封闭形式中计算了在根处的振幅的生成函数.     

The permutational power of a priority queue

A priority queue transforms an input permutation of some set of sizen into an output permutation. It is shown that the number of such pairs (, ) is (n + 1) ^n–1. Some related enumerative and algorithmic questions are also considered.Supported by the National Science and Engineering Research Council of Canada under Grant A4219.     

Graphs to chemical structures. 4: Combinatorial enumeration of planted three-dimensional trees as stereochemical models of monosubstituted alkanes

Planted three-dimensional (3D) trees, which are defined as a 3D version of planted trees, are enumerated by means of Fujita’s proligand method formulated in Parts 1–3 of this series [Fujita in Theor Chem Acc 113:73–79, 80–86, 2005; Fujita in Theor Chem Acc 115:37–53, 2006]. By starting from the concepts of proligand and promolecule introduced previously [Fujita in Tetrahedron 47:31–46, 1991], a planted promolecule is defined as a 3D object in which the substitution positions of a given 3D skeleton are occupied by a root and proligands. Then, such planted promolecules are introduced as models of planted 3D-trees. Because each of the proligands in a given planted promolecule is regarded as another intermediate planted promolecule in a nested fashion, the given planted promolecule is recursively constructed by a set of such intermediates planted promolecules. The recursive nature of such intermediate planted promolecules is used to derive generating functions for enumerating planted promolecules or planted 3D-trees. The generating functions are based on cycle indices with chirality fittingness (CI-CFs), which are composed of three kinds of sphericity indices (SIs), i.e., a _d for homospheric cycles, c _d for enantiospheric cycles, and b _d for hemispheric cycles. For the purpose of evaluating c _d recursively, the concept of diploid is proposed, where the nested nature of c _d is demonstrated clearly. The SIs are applied to derive functional equations for recursive calculations, i.e., a(x), c(x ²), and b(x). Thereby, planted 3D-trees or equivalently monosubstituted alkanes as stereoisomers are enumerated recursively by counting planted promolecules. The resulting values are collected up to 20 carbon content in a tabular form. Now, the enumeration problem initiated by mathematician Cayley [Philos Mag 47(4):444–446, 1874] has been solved in such a systematic and integrated manner as satisfying both mathematical and chemical requirements.