perm filename ENUMER.PUB[DOC,LMM] blob sn#056028 filedate 1973-07-31 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00011 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .<< TITLE PAGE, INITIAL DECLARATIONS >> C00006 00003 .HD INTRODUCTION C00008 00004 Def. Given a set X, the ↓_symmetric group on X_↓, or S↓X, is defined C00009 00005 .HD STATEMENT OF PROBLEM C00010 00006 .HD Burnside lemma. C00011 00007 To apply the Bernside lemma to this problem, C00014 00008 This weight function satisfies our requirements: C00015 00009 Consider ↓[f=f%α]&[ ∃ ]w↓o(f) and the cycles of %α. C00017 00010 Our generating function is now ↓[n!]&↑[1 ]&[--]∂↓[αεS↓N]&[ ∃ ] V(α). C00019 00011 .comment << special chars %=chi, ∃=big sigma, #=script F, =circle, ↔ eqiv>> C00022 ENDMK C⊗; .<< TITLE PAGE, INITIAL DECLARATIONS >> .DEVICE TTY .FOOTSEP←"------------------"; .BEGIN CENTER ENUMERATION OF THE GRAPHS OF MOLECULES by Larry Masinter Stanford University Computer Science Department .END .GROUP SKIP 5 .BEGIN INDENT 6,6,6 ABSTRACT. Previously, enumerations of the number of equialence classes of graphs with a given partitions have been given (1,2). These results are extended to give enumerations for the number of equivalence classes of connected multigraphs. Connected multigraphs correspond directly with chemical molecules; thus the enumeration can be applied to count the number of chemical isomers constructable from a given set of atoms. Bounds may be placed on the multiplicity of each edge, corrsponding to restructions on multiple bonds in chemical structures. .END .MACRO HD (HEADING) ⊂ BEGIN TURNON "{"; .IF LINES<4 THEN SKIP TO COLUMN 1 ELSE SKIP 1;NOFILL;}HEADING{END;⊃ .TURNON "∪↑↓[]&_"; .TURNOFF "{}α%⊗#⊂⊃ε"; .EVERY HEADING(,ENUMERATION OF THE GRAPHS OF MOLECULES,{PAGE}); .MACRO TITL(TITLE)⊂BEGIN TURNON "{";SKIP 2;NOFILL;BREAK;CENTER;}TITLE{END;⊃ .AREA TEXT LINES 4 TO 45; .SKIP TO COLUMN 1; .HD INTRODUCTION .HD DEFINITIONS Def. A ↓_multi-graph_↓ of order n is the set N={1,...,n} (called the ∪nodes of the graph) together with a mapping f from the set E(n)={{i,j}|1≤i<j≤n} to the set of non-negative integers I+. Those eεE for which f(e)≠0 are said to be edges of the graph; the ∪multiplicity of e is f(e). Also, if e={i,j} then node i is said to be connected to node j with multiplicity f({i,j}). Multi-graphs may be restricted to those whose edges have maximum multiplicity k by restricting the range of f to be the set of integers {0,1,...,k}. A ↓_k-multigraph_↓ is thus an element of k↑[E(n)]. . break Def. The ∪degree of a node nεN is d(n)=↓[m≠n]&∃ f({n,m}). The degree is the total number of other nodes n is connected to, with each connection counted the appropriate multiplicity number of times. . break Def. The ∪degree ∪seqence of a graph f is defined to be the ordered list ds(f)=(o↓1,o↓2,...), where o↓1≤o↓2≤...≤o↓n, and |{j:o↓j=k}|=|{l:d(l)=k}|. It is the sorted list of the degrees of the nodes of f. . break Def. Given a set X, the ↓_symmetric group on X_↓, or S↓X, is defined to be the set of all automorphisms from X onto X. . break Def. Two graphs f, g of order n are said to be ∪isomorphic if there exists a permutation αεS↓N such that ∀i,jεN f({i,j})=g({α(i),α(j)}). This is written f↔g. . break Lemma. f↔g => ds(f) = ds(g). . break Def. Given a set F and an equivalence relation ↔ on F, we define the set of equivalence classes of F under ↔, F/↔, to be {{fεF:f↔g} | gεF}. . BREAK .HD STATEMENT OF PROBLEM Thus, the the problem is to find a generating function for the number of equivalence classes of k-multigraphs with a given degree sequence (o↓0,o↓1,o↓2,...) . break .HD Burnside lemma. Given a set E, and a group G, a mapping %:G→S↓E, a set B, and #=B↑E; and the equivalence relation for f,gε# f↔g if there exists αεG such that f=g⊗%(α). . break Given a weight function w:#→@, where @ is a field, such that f↔g => w(f)=w(g). . break For F an equivalence class in #/↔, define W(F) to be w(f) for any fεF. Then . begin nofill ↓[Fε#/↔]&[ ∃ ]W(F) = ↑[ 1 ]&↓[|G|]&--↓[αεG]&[ ∃ ]↓[f=f⊗%α]&[ ∃ ]w(f). . end To apply the Bernside lemma to this problem, it is necessary to devise a weight function such that two graphs with the same degree sequence have the same weight and graphs with different degree sequences have different weights. Further, to construct a generating function for the number of graphs with given degree sequences, the degree sequences should be reflected in the exponents of terms in the weight rather than in the coefficient. . break Thus, we define the weight function w↓o on k↑[E(n)] into the set of real polynomials in u↓1,u↓2,...,u↓n by: .begin nofill w↓o(f)=↓[1≤i<j≤n]&[ π ] (u↓iu↓j)↑[f({i,j})] .end The exponent of u↓i in w↓o(f) will be the degree of node i in the graph (N,f). Unfortunately, ds(f)=ds(g) (or even f↔g) does not imply w↓o(f)=w↓o(g); although f and g have the same degree sequence, the exponents may be permuted among the u↓i. It is necessary to apply a symmetrizing operator ∂: . break Def. For w a function in u↓1, u↓2, ... u↓n, define . begin nofill ∂(w)(u↓1,u↓2,...,u↓n)=↑[1 ]&↓[n!]&[--] ↓[αεS↓N]&[ ∃ ]w(u↓[α↓1],u↓[α↓2],...,u↓[α↓n]) Note: 1) ∂ is linear 2) if w is symmetric, then ∂w=w; specifically, ∂∂w=∂w for any w. The weight function w can now be defined by: for fεk↑E, w(f)=∂w↓o(f). . end This weight function satisfies our requirements: if the degree sequence of f is o↓1≤o↓2≤o↓3≤...o↓n, the weight of f will be: . begin nofill ∂u↓1&↑[o1]u↓2&↑[o2]...u↓n&↑[on] . end Then, using the definition of ↔ given earlier, with the representation of the group G=S↓N by: . break Def. %:S↓N→S↓E by %(β){i,j}={β(i),β(j)} . break we obtain: . begin nofill ↓[fε#/↔]&[ ∃ ]w(f)=↓[n!]&↑[1 ]&[--] ↓[αεS↓n]&[ ∃ ]↓[f=f⊗%α]&[ ∃ ]w(f) =↓[n!]&↑[1 ]&[--] ∂↓[αεS↓n]&[ ∃ ]↓[f=f⊗%α]&[ ∃ ] w↓o(f) . end Consider ↓[f=f⊗%α]&[ ∃ ]w↓o(f) and the cycles of %α. f=f⊗%α <=> f is constant on each cycle of %α. For a given α, let M↓α be the number of cycles of %α; for 1≤r≤M↓α, let C↓r&↑α be the set of edges (elements of E) in the r-th cycle of %α, and . begin nofill U↑α&↓r=↓[{l,p}εC↓r]&[ π ] u↓lu↓p Then for f=f⊗%α, w↓o(f)=↓[i,j]&[ π ](u↓iu↓j)↑[f({i,j})] =↓[r=1]&↑[ M ]&[ π] (U↓r&↑α)↑[f(cycle r)] . end Since each f=f⊗%α can be specified by its value on the cycles of %α, there is a 1-1 correspondence between such f and ∨ε{0,1,...,k}↑M, where k is the maximum multiplicity (can be ∞), by ∨(r)=f(cycle r). In particular, . begin nofill V(α) =↓[f=f⊗%α]&[ ∃ ] w↓o(f) =↓∨&∃ ↓[r=1]&↑[ Mα]&[ π ] ( U↓r&↑α )↑[∨(r)] .turnon "{"; = ↓[r=1]&↑[ Mα]&[ π ] ↑[1-(U↓r)↑k]&↓[1 - U↓r]&[-------] (or { }↓[r=1]&↑[ Mα]&[ π ] ↑[ 1 ]&↓[1-U↓r]&[-------] if k=∞) . end Our generating function is now ↓[n!]&↑[1 ]&[--]∂↓[αεS↓N]&[ ∃ ] V(α). We wish to group the summation by those permutations α with cycle index λ↓1+2λ↓2+...+nλ↓n=n (λ↓i is the number of i-cycles of α; note that this is different from the number of various cycles of %α). Let α↑⊗(λ↓1,λ↓2,...,λ↓n) be the permutation obtained by filling in the integers 1,...,n into the slots in . begin nofill (.)(.)...(.) (..)(..)(..) ... (.. ...) ---------- ---------- ----- λ↓1 1-cycles λ↓2 2-cycles ... λ↓n n-cycles . end For ∨εS↓N, ∨α↑⊗∨↑[-1] has the same cycle structure as α↑⊗; further, there are exactly Y(λ↓1,λ↓2,...,λ↓n)=↓[k=1]&↑[ n ]&[ π ] (k↑[↑λk]λ↓k!) such permutations. . BREAK Thus, . BREAK ↓[αεS↓N]&[ ∃ ] V(α) =↓[λ↓1+...+λ↓n=n]&[ ∃ ] ↓[Y(λ)]&↑[ 1 ]&[-----] ↓[∨εS↓N]&[ ∃ ] V(∨α↑⊗&↓λ∨↑[-1]) . BREAK .comment << special chars %=chi, ∃=big sigma, #=script F, ⊗=circle, ↔ eqiv>>; .comment << also @ is fancy f, ∂ is script O >> ;