perm filename ENUMMR.PUB[DOC,LMM]2 blob sn#058034 filedate 1973-08-12 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .<< pub macros, declarations >> C00027 ENDMK C⊗; .<< pub macros, declarations >> .DEVICE XGP . .PAGE FRAME 53 HIGH 75 WIDE .AREA TEXT LINES 4 TO 54 ; .TITLE AREA HEADING LINES 1 TO 3 ; .TITLE AREA FOOTING LINE 56 ; . .TURN ON "≡" FOR "α"; . .FONT 1 "BDR25.FNT[DOC,LMM]"; FONT 2 "BDI25"; .FONT 3 "NGB25"; FONT 4 "FIX25Z.FNT[DOC,LMM]"; .FONT 5 "CTL25"; FONT 6 "GRK25"; .AT "β" ⊂ TURN ON "{", "\" FOR "%" }\1{TURN OFF⊃; .AT "λ" ⊂ TURN ON "{", "\" FOR "%" }\2{TURN OFF⊃; .AT "∞" ⊂ TURN ON "{", "\" FOR "%" }\3{TURN OFF⊃; . .AT "α" ⊂ TURN ON "{", "\" FOR "%" }\5{TURN OFF⊃; .AT "∧" ⊂ TURN ON "{", "\" FOR "%" }\6{TURN OFF⊃; .comment << special chars %=chi, ∃=big sigma, #=script F, ⊗=circle, ↔ eqiv>>; .comment << also @ is fancy f, ∂ is script O , ∨ is little sigma >> ; .<< MAKE THESE ALWAYS COME FROM FIX25Z ... SO CAN BE INCLUDED >> .AT "∃"⊂TURN ON "{", "\" FOR "%"}\6≡S\*{TURN OFF⊃ .AT "%"⊂TURN ON "{", "\" FOR "%"}\4≡%\*{TURN OFF⊃ .AT "#"⊂TURN ON "{", "\" FOR "%"}\4≡#\*{TURN OFF⊃ .AT "⊗"⊂TURN ON "{", "\" FOR "%"}\4≡⊗\*{TURN OFF⊃ .AT "↔"⊂TURN ON "{", "\" FOR "%"}\4≡↔\*{TURN OFF⊃ .AT "@"⊂TURN ON "{", "\" FOR "%"}\4≡@\*{TURN OFF⊃ .AT "∂"⊂TURN ON "{", "\" FOR "%"}\4≡∂\*{TURN OFF⊃ .AT "π"⊂TURN ON "{", "\" FOR "%"}\6≡P\*{TURN OFF⊃ .AT "∨"⊂TURN ON "{", "\" FOR "%"}\6≡s\*{TURN OFF⊃ .<< footnote macros >> .FOOTSEP←"------------------"; .COUNT REFERENCE INLINE PRINTING "↑1" .AT "<<" LABEL ":" TEXT ">" ⊂ .LABEL: NEXT REFERENCE!;!; .SEND FOOT ⊂ .PREFACE 1; SPREAD←1; INDENT 0,0; TURNON "{"; {REFERENCE! LABEL}TEXT .TURNOFF .BREAK ⊃ ⊃ . .<<label macros >> .MACRO HD (HEADING) ⊂ .BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; NOFILL; ∞HEADINGβ .END; ONCE PREFACE 1;⊃ . .MACRO TITL (TITLE) ⊂ .BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; CENTER; ∞TITLEβ .END;⊃ . .MACRO GRAF (HDNG) ⊂ BREAK ∞HDNG.β .⊃ . .MACRO I6 ⊂ INDENT 6,6,6; SPREAD←1; PREFACE 1; ⊃ .MACRO SPACE1 ⊂ SPREAD←1; PREFACE 2; BREAK; ⊃ .MACRO SPACE2 ⊂ SPREAD←2; PREFACE 3; BREAK; ⊃ . .TURNON "↑↓[]&"; .<< Title page >> .BEGIN CENTER ENUMERATION OF THE GRAPHS OF MOLECULES Larry Masinter Computer Science Department Stanford University Stanford, California May, 1973 .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<<PARTHA: PARTHASARATHY PAPER>↑,<<OTHER: OTHER REFERENCE>. 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 restrictions on multiple bonds in chemical structures. .END . .EVERY FOOTING(,{PAGE},) . .SKIP TO COLUMN 1 .SPACE2; .HD INTRODUCTION 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})β. Multigraphs 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+1↑[E(n)]β. 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. 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β. Given a set αXβ, the λsymmetry groupβ on αXβ, or αS↓Xβ, is defined to be the set of all automorphisms from αXβ onto αXβ. 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β. .GRAF Lemma αf↔g => ds(f) = ds(g).β 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}β. .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,...)β. .GRAF Burnside lemma Let αEβ be a set, αGβ a finite group with a mapping α%:G→S↓Eβ. Let αBβ be a finite set, and α#=B↑Eβ. Define the equivalence relation ↔ for αf,gε#β, such that αf↔gβ if there exists α≡αεGβ such that αf=g⊗%(≡α)β. Let αwβ be a mapping αw:#→@β, where @ is a field, such that αf↔g => w(f)=w(g)β. We call αwβ the weight function. 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. 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: αw↓o(f)=π↓[↓[1≤i<j≤n]](u↓iu↓j)↑[f({i,j})]β 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 ∂: .GRAF Definition 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 α%(G), where α%:S↓N→S↓E by %(≡β){i,j}={≡β(i),≡β(j)}β 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})] =π↓[1≤r≤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) =∃↓[↓∨] π↓[↓[1≤r≤M≡α]] (U↓r↑[≡α])↑[(r)] =π↓[↓[1≤r≤M≡α]]↑[↑[1-(U↓r)↑k]]&↓[↓[1 - U↓r]]&[-------] (or π↓[↓[1≤rM≡α]]↑[↑[ 1 ]]&↓[↓[1-U↓r]]&[-------] if k=≡∞)β . end Our generating function is now .begin nofill α↓[n!]&↑[1 ]&[--]∂∃↓[≡αεS↓N]V(≡α).β .end continue 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 .BEGIN NOFILL αY(≡λ↓1,≡λ↓2,...,≡λ↓n)=π↓[1≤k≤n] (k↑[↑[≡λ]k]≡λ↓k!)β .END CONTINUE such permutations. Thus, .BEGIN NOFILL α∃↓[≡αεS↓N]V(≡α) =∃↓[≡λ↓1+...+≡λ↓n=n]↓[Y(λ)]&↑[ 1 ]&[-----] ∃↓[↓[∨εS↓N]]V(∨⊗≡α↓[≡λ]⊗∨↑[-1])β .END