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