␈↓␈↓ αdApplications of Artificial Intelligence for Chemical Inference XIII.
␈↓ ∧1Labelling Objects Having Symmetry␈↓#
1␈↓#␈↓#
,␈↓#␈↓#
2␈↓#

␈↓ ∧LLarry Masinter and N.S. Sridharan

␈↓ βVContribution from the Computer Science Department
␈↓ ¬&Stanford University
␈↓ ∧zStanford, California 94305








␈↓ α(ABSTRACT.␈αAn␈αalgorithm␈αfor␈αfinding␈αa␈αcomplete␈αset␈αof␈αnon-equivalent␈α
labellings

␈↓ α(of␈α∃a␈α∃symmetric␈α∃object␈α∃and␈α⊗applications␈α∃of␈α∃the␈α∃algorithm␈α∃to␈α⊗problems␈α∃in

␈↓ α(chemistry␈α
are␈α
presented.





















____________________________________
␈↓#
1␈↓#We␈α
gratefully␈αacknowledge␈α
the␈αsupport␈α
of␈αthis␈α
research␈αby␈α
the␈αNational␈α
Institutes␈α
of␈αHealth
(RR␈α
00612-03)␈α
and␈α
the␈α
Advanced␈α
Research␈α
Projects␈α
Agency␈α
(SD-183).

␈↓#
2␈↓#For␈α
part␈α
XII,␈α
see␈α
L.␈α
Masinter,␈α
N.␈α
S.␈α
Sridharan,␈α
J.␈α
Lederberg,␈α
and␈α
D.␈α
H.␈α
Smith,␈α
␈↓↓J.␈α∞Amer.␈α
Chem.
Soc.␈↓,␈α
␈↓α00␈↓,␈α
0000␈α
(0000).



The␈α⊂class␈α∂of␈α⊂combinatorial␈α∂problems␈α⊂dealing␈α∂with␈α⊂finding␈α∂a␈α⊂complete␈α∂set␈α⊂of␈α∂non-isomorphic

objects␈α∂under␈α⊂varying␈α∂constraints␈α⊂and␈α∂concepts␈α∂of␈α⊂isomorphism,␈α∂has␈α⊂wide␈α∂applications␈α⊂in␈α∂a

variety␈α∂of␈α∂fields.␈α∂The␈α∂problem␈α∂attacked␈α∂in␈α∂this␈α∂paper␈α∂is␈α∂one␈α∂of␈α∂finding␈α∂all␈α∂distinct␈α∂ways␈α∂to

assign␈αa␈αgiven␈αcollection␈αof␈αlabels␈αor␈αcolors␈αto␈αthe␈αparts␈αof␈αa␈αsymmetric␈αobject.␈α In␈αchemistry,

one␈αmanifestation␈αof␈αthis␈αproblem␈αis␈αto␈αmake␈αall␈αassignments␈αof␈αligands␈α(from␈αa␈αfixed␈αset)␈αto␈αa

given␈α∂carbocyclic␈α∂skeleton␈α∂␈↓#
2␈↓#.␈α∂Part␈α∂A␈α∂of␈α∂this␈α⊂paper␈α∂may␈α∂be␈α∂read␈α∂as␈α∂a␈α∂brief␈α∂tutorial␈α⊂on␈α∂the

nature␈α∀of␈α∀the␈α∪problem␈α∀and␈α∀an␈α∪introduction␈α∀to␈α∀the␈α∪terminology␈α∀found␈α∀in␈α∀more␈α∪technical

treatments.␈α
Part␈α
B␈α
is␈α
a␈α
textual␈α
description␈α
of␈αa␈α
method␈α
for␈α
the␈α
solution␈α
of␈α
this␈α
type␈αof␈α
problem.

Part␈α⊃C␈α⊃is␈α⊃a␈α⊃summary␈α⊂of␈α⊃the␈α⊃procedure␈α⊃in␈α⊃a␈α⊂more␈α⊃algorithmic␈α⊃form;␈α⊃an␈α⊃even␈α⊃more␈α⊂formal

description␈α∞and␈α∞a␈α∞proof␈α∞of␈α∞correctness␈α∂is␈α∞available␈α∞elsewhere␈↓#
3␈↓#.␈α∞ Part␈α∞D␈α∞gives␈α∂examples␈α∞and

applications␈α
of␈α
this␈α
algorithm␈α
in␈α
both␈α
organic␈α
and␈α
inorganic␈α
chemistry.



This␈αproblem␈αis␈αencountered␈αin␈αa␈αwide␈αrange␈αof␈αapplications␈αbeyond␈αchemistry--␈α
within␈αmany

areas␈αof␈α
graph␈αtheory␈αand␈α
combinatorics,␈αfor␈α
example.␈α It␈αhas␈α
been␈αknown␈α
how␈αto␈αcompute␈α
the

number␈α
of␈α
solutions␈↓#
4␈↓#␈↓#
,␈↓#␈↓#
5␈↓#,␈α
but␈α
an␈α
efficent␈αmethod␈α
of␈α
actually␈α
constructing␈α
the␈α
solutions␈α
has␈αnot

previously␈α
been␈α
published␈↓#
6␈↓#.









____________________________________
␈↓#
3␈↓#(a)␈αH.␈αBrown,␈αL.␈αMasinter,␈αand␈αL.␈αHjelemeland,␈α␈↓↓Discrete␈αMath.␈↓␈αin␈αpress;␈α(b)␈αStanford␈αComputer
Science␈α
Memo␈α
31B,␈α
Computer␈α
Science␈α
Department,␈α
Stanford␈α
University.

␈↓#
4␈↓#N.␈α
G.␈α
DeBruijn,␈α
␈↓↓Nedarl.␈α
Akad.␈α
Wentesh.␈α
Proc.␈α
Ser.␈α
A␈↓,␈α
␈↓α62␈↓,␈α
59␈α
(1959).

␈↓#
5␈↓#N.␈α
G.␈α
DeBruijn,␈α∞in␈α
"Applied␈α
Combinatorial␈α
Mathematics,"␈α∞E.␈α
Beckenbach,␈α
Ed.,␈α
John␈α∞Wiley,␈α
New
York,␈α
1964,␈α
p.␈α
144.

␈↓#
6␈↓#an␈α⊂alternative␈α∂algorithm␈α⊂has␈α∂been␈α⊂described␈α⊂to␈α∂us␈α⊂in␈α∂a␈α⊂private␈α∂communication␈α⊂from␈α⊂D.␈α∂M.
Perlman,␈α
University␈α
of␈α
California,␈α
San␈α
Diego,␈α
California.

␈↓ ε ␈↓ 
x␈↓ ε_1␈↓ 
x



␈↓ ¬≤␈↓αPART A: DEFINITIONS␈↓


␈↓αSYMMETRY AND ITS RELATIONSHIP TO LABELLING␈↓

Consider␈α
the␈α
special␈α
case␈α∞of␈α
the␈α
general␈α
problem:␈α
suppose␈α∞all␈α
of␈α
the␈α
labels␈α
are␈α∞distinct.␈α
For

example,␈αsuppose␈αthat␈α
one␈αwishes␈αto␈αnumber␈α
the␈αfaces␈αof␈α
a␈αcube␈αwith␈αthe␈α
numbers␈α{1,␈α2,␈α3,␈α
4,

5,␈α
6},␈α
or␈α
the␈α"nodes"␈α
(atom␈α
positions␈α
in␈αa␈α
graph)␈α
of␈α
the␈α
decalin␈αskeleton␈α
(␈↓α1␈↓)␈α
with␈α
numbers␈α{1,␈α
2,

3,␈α
4,␈α
5,␈α
6,␈α
7,␈α
8,␈α
9,␈α
10}.











There␈αare␈αn!␈α(n␈αfactorial)␈αways␈αof␈αlabelling␈αwhere␈αn␈αis␈αthe␈αnumber␈αof␈αparts.␈α If␈αthe␈αobject␈αhas

no␈αsymmetry␈αthen␈αeach␈αof␈αthese␈αn!␈αways␈αare␈αdistinct␈αfrom␈αthe␈αrest.␈α However␈αfor␈αthe␈αdecalin

skeleton␈α∪(where␈α∪n!␈α∀=␈α∪10!␈α∪=␈α∀3,628,800␈α∪ways)␈α∪there␈α∪is␈α∀some␈α∪symmetry.␈α∪First␈α∀one␈α∪picks,

arbitrarily,␈α
one␈α
of␈α
the␈α
numberings␈α
as␈α
a␈α
point␈α
of␈α
reference␈α
(e.g.␈α
␈↓α2a␈↓).













Some␈α
of␈αthe␈α
10!␈α
ways␈αmight␈α
be␈α
viewed␈αas␈α
different␈α
(e.g.␈α␈↓α2b␈↓);␈α
some␈α
of␈αthem␈α
might␈α
be␈αviewed␈α
as

the␈αsame␈α(e.g.␈α␈↓α2c␈↓).␈α
Intuitively,␈α␈↓α2a␈↓␈αand␈α␈↓α2c␈↓␈α
are␈αequivalent␈αbecause␈αone␈α
could␈αflip␈α␈↓α2a␈↓␈αover␈αthe␈α
3-8

axis␈α∂and␈α∂get␈α∂␈↓α2c␈↓.␈α∂ There␈α∂is␈α∂another␈α∂way␈α∂of␈α∂determining␈α∂the␈α∂"sameness"␈α∂of␈α∂such␈α∞numberings




␈↓ ε_2␈↓ 
x



which␈α∃is␈α⊗easier␈α∃in␈α∃more␈α⊗complicated␈α∃cases␈α⊗and␈α∃is␈α∃generally␈α⊗more␈α∃suited␈α⊗to␈α∃computer

application:

␈↓ α(␈↓αDEFINITION:␈↓␈α⊂Two␈α⊂numberings␈α⊂of␈α⊂the␈α⊂nodes␈α⊂of␈α⊂a␈α⊂graph␈α⊂are␈α⊂␈↓↓equivalent␈↓␈α⊃if␈α⊂the
␈↓ α(connection␈αtables␈αwith␈α
the␈αrespective␈αnumberings␈α
are␈αidentical␈αwhen␈α
the␈αnode
␈↓ α(numbers␈α⊃are␈α⊃written␈α⊃in␈α⊃ascending␈α⊃order␈α⊃and␈α⊃each␈α⊃"connected␈α⊃to"␈α⊃list␈α∩is␈α⊃in
␈↓ α(ascending␈α
order.



Table␈α∃I␈α∃contains␈α∃the␈α∃respective␈α⊗"connection␈α∃tables"␈α∃of␈α∃structures␈α∃␈↓α2a-c␈↓.␈α∃ Note␈α⊗that␈α∃the

connection␈α
table␈α
for␈α
␈↓α2c␈↓␈α
is␈α
identical␈α
to␈α
that␈α
of␈α
␈↓α2a␈↓;␈α
that␈α
of␈α
␈↓α2b␈↓␈α
is␈α
different.
␈↓β______________________________________________________________________

␈↓αTable I.␈↓β Connection Tables for Structures ␈↓α2a-c␈↓β.

             ␈↓α2a␈↓β               ␈↓α2b␈↓β               ␈↓α2c␈↓β
         node|connected | node|connected | node|connected
             |   to     |     |   to     |     |  to
                        |                |
           1    2,1O    |  1    8,9      |  1    2,1O
           2    1,3     |  2    3,7      |  2    1,3
           3    2,4,8   |  3    2,6      |  3    2,4,8
           4    3,5     |  4    6,8,1O   |  4    3,5
           5    4,6     |  5    9,1O     |  5    4,6
           6    5,7     |  6    3,4      |  6    5,7
           7    6,8     |  7    2,8      |  7    6,8
           8    3,7,9   |  8    1,4,7    |  8    3,7,9
           9    8,1O    |  9    1,5      |  9    8,1O
           1O   1,9     |  1O   4,5      |  1O   1,9
______________________________________________________________________



␈↓This␈α
definition␈α
means,␈α∞among␈α
other␈α
things,␈α∞that␈α
properties␈α
such␈α∞as␈α
valency␈α
are␈α∞preserved:␈α
If

two␈αnumberings␈αare␈αequivalent␈αand␈αin␈αthe␈αfirst,␈αnode␈α1␈αis␈αtrivalent,␈αthen␈αin␈αthe␈αsecond,␈αnode␈α
1

is␈αtrivalent.␈α If␈αthere␈αare␈αother␈αproperties␈αof␈αthe␈αnodes␈α(they␈αare␈αalready␈αcolored␈αor␈αlabelled,

for␈α∩example),␈α∪then␈α∩this␈α∪definition␈α∩can␈α∪be␈α∩extended␈α∪to␈α∩include␈α∪the␈α∩preservation␈α∪of␈α∩those

properties.␈α For␈αexample,␈αsuppose␈αthere␈αare␈αatom␈αnames␈αassociated␈αwith␈α(some␈αof)␈αthe␈αnodes

of␈α∞the␈α
graph.␈α∞ Then␈α∞one␈α
can␈α∞define␈α
equivalent␈α∞numberings␈α∞to␈α
be␈α∞those␈α
which␈α∞not␈α∞only␈α
have

identical␈αconnection␈αtables,␈α
but␈αalso␈αthe␈α
same␈αatom␈αnames␈α
for␈αthe␈αcorresponding␈α
nodes.␈αThen



␈↓ ε_3␈↓ 
x



␈↓α3a␈↓␈αwould␈αstill␈αbe␈αequivalent␈αto␈α␈↓α3c␈↓␈αbut␈αno␈αlonger␈αto␈α␈↓α3b␈↓␈αsince,␈αalthough␈αthe␈αconnection␈αtables␈αof

␈↓α3a␈↓␈α
and␈α
␈↓α3b␈↓␈α
are␈α
identical,␈α
node␈α
1␈α
in␈α
␈↓α3a␈↓␈α
is␈α
labelled␈α
with␈α
an␈α
"N"␈α
while␈α
in␈α
␈↓α3b␈↓␈α
it␈α
unlabelled.












␈↓αPERMUTATIONS AND PERMUTATION GROUPS␈↓

Given␈α∩a␈α∩numbering␈α∩of␈α∩a␈α∩graph,␈α∩one␈α∩can␈α∩use␈α∩a␈α∩condensed␈α∩notation␈α∩to␈α∩write␈α∩down␈α∩other

numberings␈α∞in␈α∞terms␈α∞of␈α∞the␈α∂first.␈α∞All␈α∞of␈α∞these␈α∞are␈α∂written␈α∞down␈α∞with␈α∞respect␈α∞to␈α∂an␈α∞original

"reference"␈α∞numbering.␈α∞ Using␈α
the␈α∞numbering␈α∞of␈α∞␈↓α2a␈↓␈α
as␈α∞the␈α∞reference␈α∞numbering,␈α
numberings

for␈α␈↓α2a-c␈↓␈αare␈α
given␈αin␈αTable␈αII.␈α
In␈αthe␈α2b␈αcase,␈α
the␈αrow␈αof␈αnumbers␈α
means␈αthat,␈αin␈αsequence,␈α
the

node␈α
numbered␈α∞1␈α
in␈α∞the␈α
reference␈α∞numbering␈α
of␈α∞␈↓α2a␈↓␈α
is␈α∞now␈α
numbered␈α∞2,␈α
the␈α∞node␈α
originally

numbered␈α
2␈α
is␈α
now␈α
numbered␈α
10,␈α
and␈α
so␈α
on.
␈↓β______________________________________________________________________

␈↓αTable II␈↓β  Condensed Notation for Numberings of ␈↓α2a-c␈↓β

          ␈↓α2a␈↓β numbers:  1  2  3  4  5  6  7  8  9 1O

          ␈↓α2b␈↓β numbers:  2  7  8  1  9  5 1O  4  6  3

          ␈↓α2c␈↓β numbers:  5  4  3  2  1 1O  9  8  7  6

______________________________________________________________________



␈↓One␈αcan␈αconceptualize␈αa␈αnumbering␈αas␈αa␈αtransformation␈αor␈αas␈αa␈αfunction:␈αThe␈αtransformation␈απ

for␈α␈↓α2c␈↓␈αis␈απ␈↓#v2␈↓#␈↓#vc␈↓#(1)=5,␈απ␈↓#v2␈↓#␈↓#vc␈↓#(2)=4,␈απ␈↓#v2␈↓#␈↓#vc␈↓#(3)=3,␈α...␈απ␈↓#v2␈↓#␈↓#vc␈↓#(10)=6.␈α These␈αtransformations␈αare␈α␈↓↓permutations␈↓:

one␈α∞to␈α∞one␈α∞mappings␈α∞from␈α∞the␈α∞integers␈α∞{1,2,...,n}␈α∞to␈α∞themselves.␈α∞ The␈α∞transformation␈α∞for␈α
the

"reference"␈α
numbering␈α
is␈α
the␈α
identity␈α
π␈↓#vi␈↓#(x)=x.␈α
It␈α
can␈α
be␈α
shown␈α
that␈α
whatever␈α
the␈α
graph,␈α
the␈α
set



␈↓ ε_4␈↓ 
x



of␈αtransformations␈αsatisfying␈αthe␈α"equivalency"␈αrequirement␈αabove␈αsatisfies␈αthe␈αproperty␈αof␈αa

group.␈α
 One␈α
may␈α
then␈α
say:

␈↓ α(The␈α∞␈↓↓symmetry␈α
group␈↓␈α∞of␈α∞a␈α
graph␈α∞is␈α
the␈α∞set␈α∞of␈α
all␈α∞transformations␈α∞which␈α
yield
␈↓ α(identical␈α∂connection␈α∂tables.␈α⊂ (If␈α∂there␈α∂are␈α⊂other␈α∂properties␈α∂to␈α⊂be␈α∂considered,
␈↓ α(one␈α
may␈α
include␈α
them␈α
as␈α
part␈α
of␈α
the␈α
connection␈α
table).

For␈α
the␈α
decalin␈α
skeleton␈α
there␈α
are␈α
4␈α
permutations␈α
in␈α
the␈α
symmetry␈α
group,␈α
given␈α
in␈α
Table␈α
III.
␈↓β______________________________________________________________________

␈↓αTable III.␈↓β The Symmetry Group of the Decalin Skeleton


                 π␈↓#vi␈↓#␈↓#
a␈↓#    1  2  3  4  5  6  7  8  9 1O
                 π␈↓#vv␈↓#     5  4  3  2  1 1O  9  8  7  6
                 π␈↓#vh␈↓#    1O  9  8  7  6  5  4  3  2  1
                 π␈↓#v18O␈↓#   6  7  8  9 1O  1  2  3  4  5

␈↓#
a␈↓# The reference numbering corresponds to that given for ␈↓α2a␈↓β.
______________________________________________________________________



␈↓These␈α⊃correspond␈α⊃directly␈α⊃to␈α∩the␈α⊃intuitive␈α⊃geometric␈α⊃symmetries␈α∩π␈↓#vi␈↓#=identity,␈α⊃π␈↓#vh␈↓#=reflection

about␈αhorizontal␈αaxis,␈απ␈↓#vv␈↓#=reflection␈αabout␈αvertical␈αaxis,␈απ␈↓#v180␈↓#␈α=␈αrotation␈αby␈α180␈αdegrees.␈α It␈αis

not␈α
too␈α
difficult␈α
for␈α
a␈αcomputer␈α
program␈α
to␈α
figure␈α
out␈α
the␈αsymmetry␈α
group␈α
of␈α
a␈α
graph␈αgiven␈α
its

connection␈α
table.



This␈α∞definition␈α∞deals␈α∞with␈α∞the␈α
symmetry␈α∞of␈α∞the␈α∞␈↓↓nodes␈↓␈α∞of␈α
a␈α∞graph.␈α∞ In␈α∞many␈α∞cases,␈α∞one␈α
might

wish␈α
to␈α
label␈αthe␈α
␈↓↓edges␈↓␈α
(interconnecting␈α
lines)␈αof␈α
a␈α
graph.␈α
 In␈αthis␈α
case,␈α
the␈α
symmetry␈αgroup␈α
on

the␈αedges␈αrather␈αthan␈αon␈αthe␈αnodes␈αis␈αrequired.␈α  It␈αis␈αvery␈αeasy␈αto␈αcalculate␈αthis␈αgroup␈αfrom

the␈αgroup␈αon␈αthe␈αnodes.␈αLet␈αthe␈αnumbering␈αfor␈αeach␈αedge␈αin␈αthe␈αgraph␈αbe␈αthe␈αunordered␈αpair

of␈αnumbers␈αof␈αthe␈αnodes␈αthat␈αform␈αthe␈αend-points.␈α Then␈αthe␈αcorresponding␈αpermutations␈αcan

be␈α
obtained␈α
as␈α
follows:

            π␈↓#vi␈↓#{n␈↓#v1␈↓#,n␈↓#v2␈↓#}={π␈↓#vi␈↓#(n␈↓#v1␈↓#),π␈↓#vi␈↓#(n␈↓#v2␈↓#)}

This␈α
is␈α
most␈α
easily␈α
shown␈α
by␈α
way␈α
of␈α
an␈α
example␈α
(Table␈α
IV).



␈↓ ε_5␈↓ 
x



␈↓β______________________________________________________________________

␈↓αTable IV.␈↓β Permutation Group of Decalin Skeleton Acting on the edges

  π␈↓#vi␈↓#␈↓#
a␈↓#    1-2   2-3  3-8  3-4  4-5  5-6  6-7  7-8  8-9  9-10 1-10

  π␈↓#vv␈↓#     4-5   3-4  3-8  2-3  1-2  1-10 9-10 8-9  7-8  6-7  5-6

  π␈↓#vh␈↓#     9-10  8-9  3-8  7-8  6-7  5-6  4-5  3-4  2-3  1-2  1-10

  π␈↓#v180␈↓#   6-7   7-8  3-8  8-9  9-10 1-10 1-2  2-3  3-4  4-5  5-6

␈↓#
a␈↓#The reference numbering corresponds to that given for ␈↓α2a␈↓β.
______________________________________________________________________



␈↓Finding␈α⊂the␈α⊂group␈α⊃of␈α⊂an␈α⊂object␈α⊂is␈α⊃a␈α⊂special␈α⊂kind␈α⊂of␈α⊃labelling␈α⊂problem.␈α⊂ Given␈α⊂one␈α⊃way␈α⊂of

numbering␈α∂(labelling␈α⊂with␈α∂distinct␈α⊂labels)␈α∂the␈α⊂parts␈α∂of␈α∂the␈α⊂object,␈α∂one␈α⊂finds␈α∂all␈α⊂other␈α∂ways

which␈αare␈αequivalent.␈α The␈αlabelling␈αproblem␈αattacked␈αin␈αthis␈αpaper␈αis␈αthe␈αconverse:␈α to␈αfind␈αa

maximal␈α∂list␈α∞of␈α∂labellings,␈α∂none␈α∞of␈α∂which␈α∞are␈α∂equivalent.␈α∂ In␈α∞general␈α∂the␈α∞set␈α∂of␈α∂all␈α∞posssible

labellings␈α
can␈α
be␈α
split␈α
into␈α
subsets,␈α
such␈α
that:

␈↓ α(1)␈α
If␈α
two␈α
labellings␈α
are␈α
in␈α
different␈α
subsets,␈α
they␈α
are␈α
not␈α
equivalent.

␈↓ α(2)␈α
 If␈α
two␈α
labellings␈α
are␈α
in␈α
the␈α
same␈α
subset,␈α
they␈α
are␈α
equivalent.



These␈αsubsets␈αare␈αcalled␈α␈↓↓equivalence␈αclasses␈↓␈αof␈αlabellings;␈αselection␈αof␈αone␈αlabelling␈αfrom␈αeach

equivalence␈α
class␈α
yields␈α
the␈α
maximal␈α
list␈α
of␈α
non-equivalent␈α
labellings.



The␈αrelationship␈αof␈αfinding␈αthe␈αgroup,␈αand␈αof␈αfinding␈αlabellings␈αwhen␈αall␈αthe␈αlabels␈αare␈αdistinct,

can␈αbe␈αseen␈α
as␈αfollows␈α(see␈α␈↓α4␈↓):␈α
view␈αthe␈αn!␈αpossible␈α
labellings␈αas␈αlaid␈αout␈α
in␈αa␈αmatrix␈αsuch␈α
that

each␈αrow␈α
contains␈αone␈α
equivalence␈αclass.␈α
It␈αcan␈αbe␈α
shown␈αthat␈α
in␈αthe␈α
special␈αcase␈α
where␈αthe

labels␈αare␈αdistinct,␈αall␈αof␈αthe␈αequivalence␈αclasses␈αare␈αof␈αthe␈αsame␈αsize.␈α To␈αfind␈αthe␈αgroup,␈αone

needs␈αto␈αfind␈αa␈αrow.␈α To␈αfind␈αthe␈αlabellings,␈αone␈αneeds␈αto␈αpick␈αone␈αelement␈αfrom␈αeach␈αrow␈α
(i.e.

find␈α
a␈α
column).


␈↓ ε_6␈↓ 
x























































␈↓ ε_7␈↓ 
x



␈↓ βr␈↓αPART B: SOLUTION TO THE LABELLING PROBLEM␈↓



An␈α
obvious␈α
method␈α
to␈α
find␈α
the␈α
distinct␈α
labellings␈αwould␈α
be␈α
to␈α
generate␈α
all␈α
n!␈α
of␈α
the␈αpossible

ones,␈αand␈αfor␈αeach␈α
one␈αto␈αcheck␈αif␈αan␈α
equivalent␈αone␈αwas␈αpreviously␈αgenerated.␈α
Unfortunately,

this␈αmethod␈αtakes␈αan␈α
exhorbitant␈αamount␈αof␈αcomputation␈α
(proportional␈αto␈αn!␈αsquared).␈α Below␈α
a

method␈α∞is␈α∞discussed␈α∞which␈α∂we␈α∞believe␈α∞takes␈α∞an␈α∞amount␈α∂of␈α∞time␈α∞roughly␈α∞proportional␈α∂to␈α∞the

number␈α∞of␈α∞solutions␈α∂(i.e.␈α∞the␈α∞number␈α∂of␈α∞equivalence␈α∞classes␈α∂of␈α∞labellings)␈α∞and␈α∂requires␈α∞only

knowledge␈αof␈αthe␈αsymmetry␈αgroup.␈αThus␈αit␈αis␈αuseful␈αfor␈αlabelling␈αobjects␈αusing␈αtheir␈αgeometric

symmetry␈α
␈↓#
2␈↓#␈α
as␈α
well␈α
as␈α
the␈α
topological␈α
symmetry␈α
defined␈α
above.



␈↓αSpecial␈α
case:␈α
distinguish␈α
1␈αnode.␈↓␈α
First␈α
consider␈α
the␈α
special␈αcase␈α
where␈α
there␈α
are␈α
only␈αtwo␈α
types

of␈α
labels␈α
such␈α
that␈α
there␈α
is␈α
one␈α
label␈α
of␈α
the␈α
first␈α
type␈α
and␈α
all␈α
the␈α
rest␈α
of␈α
the␈α
second␈α(e.g.,␈α
color

one␈α⊃red,␈α⊃and␈α⊃the␈α⊃rest␈α⊃green,␈α⊃or␈α⊃label␈α⊃one␈α⊃N␈α⊃and␈α⊃the␈α⊃rest␈α⊃C).␈α⊃Intuitively,␈α⊃for␈α⊃the␈α⊃decalin

skeleton,␈αone␈αcan␈αsee␈αthat␈αthere␈αare␈αthree␈αclasses␈αof␈αsymmetric␈αnodes,␈αor␈α␈↓↓orbits␈↓,␈αmarked␈αwith

"⊗",␈α"+"␈αand␈α
"&"␈αin␈α␈↓α5␈↓,␈αand␈α
that␈αeach␈αdistinct␈αlabelling␈α
corresponds␈αto␈αselecting␈αone␈α
node␈αfrom

each␈α
type␈α
(␈↓α6a␈↓,␈α
␈↓α6b␈↓,␈α
␈↓α6c␈↓).












Thus␈α∪there␈α∪are␈α∪three␈α∪distinct␈α∪labellings␈α∪(i.e.,␈α∪the␈α∪ten␈α∪possible␈α∪labellings␈α∪split␈α∪into␈α∩three

equivalalence␈α
classes).






␈↓ ε_8␈↓ 
x



In␈αgeneral,␈αthe␈αparts␈αof␈αa␈αsymmetric␈αobject␈αsplit␈αinto␈αdifferent␈αorbits␈α(sometimes␈αthere␈αis␈αonly

one␈αorbit,␈αas␈αin␈αthe␈αfaces␈αof␈αa␈αcube,␈αor␈αthe␈αnodes␈αof␈αthe␈αcyclohexane␈αskeleton).␈α To␈αlabel␈αthe

parts␈α(e.g.,␈αthe␈αfaces,␈αnodes,␈α
edges)␈αof␈αan␈αobject␈αsuch␈α
that␈αone␈αis␈αdistinguished,␈αit␈αis␈α
necessary

only␈αto␈αfind␈αthe␈αorbits␈αand␈αthen,␈αfor␈αeach␈αorbit,␈αpick␈αone␈αof␈αthe␈αparts␈αin␈αthat␈αorbit␈αarbitrarily.

Note␈α
that␈α
if␈α
the␈α
object␈α
has␈α
no␈α
symmetry␈α
each␈α
orbit␈α
has␈α
exactly␈α
one␈α
part␈α
in␈α
it.



␈↓αComputing␈αorbits.␈↓␈αIt␈αis␈αvery␈αsimple␈αto␈αfind␈αthe␈αdifferent␈αorbits␈αfrom␈αthe␈αtable␈αof␈αthe␈αsymmetry

group:␈α
if␈α
one␈α
writes␈α
out␈α
the␈αgroup,␈α
as␈α
in␈α
Table␈α
III,␈α
with␈αeach␈α
permutation␈α
as␈α
a␈α
row,␈α
then␈αthe

numbers␈αin␈αeach␈αcolumn,␈αtaken␈αas␈α
a␈αset,␈αform␈αan␈αorbit.␈αThe␈α
orbits␈αof␈αthe␈αgroup␈αin␈αTable␈αIII␈α
are:

{1,5,6,10},␈α
{2,4,7,9},␈α∞{3,8}.␈α
The␈α
nodes␈α∞in␈α
ech␈α
orbit␈α∞correspond␈α
to␈α
equivalent␈α∞nodes␈α
mentioned

above;␈α
compare␈α
␈↓α2a␈↓␈α
and␈α
␈↓α5␈↓.



After␈α∀finding␈α∪the␈α∀set␈α∪of␈α∀orbits,␈α∪one␈α∀then␈α∪can␈α∀do␈α∪the␈α∀special␈α∪labelling␈α∀described␈α∪above

(distinguishing␈αonly␈αone␈αnode):␈αthe␈αnumber␈α
of␈αdistinct␈αlabellings␈αis␈αthe␈αnumber␈αof␈α
orbits.␈αEach

corresponds␈α∂to␈α∂selecting␈α∂an␈α⊂element␈α∂from␈α∂a␈α∂corresponding␈α⊂orbit␈α∂and␈α∂labelling␈α∂it.␈α⊂ The␈α∂first

element␈α
of␈α
each␈α∞orbit␈α
is␈α
chosen␈α∞by␈α
convention␈α
(i.e.␈α∞the␈α
one␈α
with␈α∞the␈α
smallest␈α
number␈α∞in␈α
the

reference␈α
numbering).



␈↓αThe␈α∂reduced␈α∂symmetry␈α∂group.␈↓␈α∂Once␈α∂a␈α∂group␈α∂has␈α∂been␈α∂calculated␈α∂for␈α∂a␈α∂structure,␈α⊂often␈α∂one

wants␈α⊂to␈α∂know␈α⊂what␈α∂the␈α⊂group␈α∂is␈α⊂after␈α∂some␈α⊂labels␈α∂have␈α⊂been␈α∂attached.␈α⊂ The␈α∂group␈α⊂of␈α∂a

labelled␈αstructure␈α
is␈αalways␈α
a␈α␈↓↓subset␈↓␈α
of␈αthe␈α
group␈αof␈α
the␈αunlabelled␈α
structure.␈α Thus␈αone␈α
needs

to␈α∞know␈α∂which␈α∞permutations␈α∞in␈α∂the␈α∞group␈α∂must␈α∞be␈α∞thrown␈α∂out.␈α∞To␈α∞do␈α∂this,␈α∞write␈α∂the␈α∞labels

associated␈αwith␈αeach␈αnode␈αnext␈αto␈αthe␈αnode␈αnumber␈αin␈αthe␈αpermutation␈αtable␈α(e.g.␈αTable␈αIII).␈α If

in␈αany␈αcolumn,␈αthere␈αis␈αan␈αelement␈αwhich␈αhas␈αa␈αdifferent␈αlabel␈αthan␈αthe␈αlabel␈αin␈αthe␈αreference

numbering␈α∞(identity␈α∞permutation),␈α
then␈α∞that␈α∞row␈α
can␈α∞be␈α∞discarded.␈α
 That␈α∞is,␈α∞a␈α∞permutation␈α
is



␈↓ ε_9␈↓ 
x



valid␈α⊂if␈α⊂and␈α⊂only␈α⊂if␈α⊂identical␈α⊂connection␈α⊃tables,␈α⊂now␈α⊂in␈α⊂terms␈α⊂of␈α⊂node␈α⊂numbers␈α⊃␈↓↓and␈↓␈α⊂labels

associated␈αwith␈αeach␈α
node,␈αare␈αobtained␈α
by␈αthe␈αpermutation.␈α
 Only␈αpermutations␈αin␈αthe␈α
original

group␈α
can␈α
possibly␈αyield␈α
structures␈α
which␈αdo␈α
look␈α
the␈α
same.␈αHowever,␈α
because␈α
of␈αthe␈α
labelling,

some␈α⊃of␈α⊃these␈α⊃permutations␈α∩may␈α⊃yield␈α⊃non-equivalent␈α⊃structures␈α∩(non-identical␈α⊃connection

tables).␈α
 These␈α
permutations␈α
are␈α
the␈α
ones␈α
that␈α
must␈α
be␈α
discarded.



␈↓αReduction␈α
techniques.␈↓␈αIn␈α
the␈αgeneral␈α
labelling␈α
problem,␈αthere␈α
are␈αtwo␈α
important␈αtechniques␈α
used

to␈α
reduce␈α
the␈α
problem.␈α
 The␈α
first␈α
is␈α
called␈α
␈↓↓label␈α
recursion␈↓␈↓#
7␈↓#␈α
and␈α
the␈α
second␈α
␈↓↓orbit␈α
recursion␈↓.␈α
 The

idea␈α∂behind␈α∂label␈α∂recursion␈α∂is␈α∂that␈α∂one␈α∂can␈α∂do␈α∂one␈α∂label␈α∂at␈α∂a␈α∂time.␈α∂ The␈α∂idea␈α∂behind␈α∞orbit

recursion␈α
is␈α
that␈αone␈α
can␈α
label␈αone␈α
orbit␈α
at␈αa␈α
time.␈α
 These␈αreductions␈α
are␈α
discussed␈α
in␈αdetail

below.


␈↓αLABEL RECURSION␈↓

If␈α
one␈α
is␈α
given␈α
many␈α
(more␈α
than␈α
2)␈α
kinds␈α
of␈α
labels,␈α
say␈α
n␈↓#v1␈↓#␈α
of␈α
type␈α
1,␈α
n␈↓#v2␈↓#␈α
of␈α
type␈α
2,␈α
...␈α
n␈↓#vk␈↓#␈αof

type␈α
k,␈αone␈α
may␈αproceed␈α
as␈α
follows:␈αSolve␈α
the␈αlabelling␈α
problem␈α
for␈αn␈↓#v1␈↓#␈α
of␈αone␈α
type␈α
of␈αlabel

and␈αn␈↓#v2␈↓#+n␈↓#v3␈↓#+...+n␈↓#vk␈↓#␈α
of␈αanother␈α
type.␈α(Call␈α
the␈αsecond␈αtype␈α
of␈αlabel␈α
"blank").␈α  The␈α
result␈αwill␈αbe␈α
a

list␈αof␈α
partially␈αlabelled␈α
objects␈α(along␈α
with␈αtheir␈α
reduced␈αsymmetry␈α
groups).␈α Take␈α
each␈αof␈α
the

results␈αand␈αlabel␈αthe␈α"blank"␈αparts␈αwith␈αn␈↓#v2␈↓#␈αlabels␈αof␈αone␈αkind,␈αn␈↓#v3␈↓#␈αof␈αanother,␈α...␈α,n␈↓#vk␈↓#␈αof␈αanother.

It␈α∂has␈α∂been␈α∂proved␈α∂␈↓#
3␈↓#␈α∂that␈α∂the␈α∂results␈α∂will␈α∂be␈α∂a␈α∂list␈α∂of␈α∂all␈α∂distinct␈α∂solutions␈α∂to␈α∂the␈α∞original

problem.␈α
 For␈α
example,␈α
to␈α
label␈α
the␈α
decalin␈α
skeleton␈α
with␈α
one␈α
label␈α
␈↓↓N␈↓,␈α
one␈α
label␈α
␈↓↓B␈↓␈α
and␈αeight

labels␈α∞␈↓↓C␈↓␈α∞one␈α∞first␈α∞labels␈α∞with␈α∞one␈α∞N␈α∞and␈α∞nine␈α∞"blanks"␈α∞obtaining␈α∞the␈α∞three␈α∞partially␈α∞labelled

skeletons␈α
␈↓α7a1␈↓,␈α
␈↓α7a2␈↓,␈α
␈↓α7a3␈↓.




____________________________________
␈↓#
7␈↓#A␈α
␈↓↓recursive␈↓␈αtechnique␈α
is␈αone␈α
which␈α
is␈αdefined␈α
in␈αterms␈α
of␈α
itself.␈αIt␈α
is␈αonly␈α
necessary␈α
that␈αat
each␈αstep␈αthe␈αproblem␈αis␈αreduced,␈αand␈αthat␈αa␈αterminating␈αcondition␈αis␈αeventually␈αmet.␈αHere␈αthe
general␈α
solution␈α
of␈α
the␈α
labelling␈α
problem␈α
is␈α
described␈α
in␈α
terms␈α
of␈α
less␈α
complicated␈αlabellings.
Several␈α
special␈α
cases␈α
(terminating␈α
conditions)␈α
are␈α
also␈α
defined.

␈↓ ε⊂10␈↓ 
x


























There␈α∂are␈α∂now␈α∂three␈α∂new␈α∂problems:␈α∂to␈α∂label␈α∂the␈α∂"blanks"␈α∂of␈α∂␈↓α7a1-3␈↓␈α∂under␈α∂their␈α∂respective

reduced␈α
symmetry,␈α
with␈αone␈α
␈↓↓S␈↓␈α
and␈α
eight␈α␈↓↓C␈↓'s.␈α
 In␈α
␈↓α7a1␈↓␈αand␈α
␈↓α7a2␈↓,␈α
there␈α
is␈αno␈α
symmetry␈α
left␈αand␈α
so

each␈α∞of␈α
the␈α∞"blanks"␈α
has␈α∞its␈α
own␈α∞orbit;␈α∞thus␈α
there␈α∞are␈α
nine␈α∞distinct␈α
labellings␈α∞apiece.␈α∞In␈α
␈↓α7a3␈↓

there␈αare␈αfive␈α
orbits␈αunder␈αthe␈αreduced␈α
symmetry,␈αwhich␈αmay␈αbe␈α
verified␈αby␈αassignment␈αof␈α
an

␈↓↓N␈↓␈α⊂to␈α⊂node␈α⊂3,␈α⊂Table␈α⊂III.␈α⊂Thus␈α⊂five␈α⊂structures␈α⊂result␈α⊂(␈↓α7b1-5␈↓).␈α⊂Note␈α⊂that␈α⊂the␈α⊂problem␈α⊂is␈α⊂now

complete␈αas␈α
the␈αremaining␈αlabels␈α
(eight␈α␈↓↓C␈↓'s)␈α
can␈αbe␈αonly␈α
placed␈αin␈αone␈α
way␈αon␈α
each␈αskeleton

labeled␈α
with␈α
␈↓↓N␈↓␈α
and␈α
␈↓↓B␈↓.


␈↓αORBIT RECURSION␈↓

When␈αthere␈αis␈αmore␈αthan␈αone␈αlabel␈αof␈αa␈αgiven␈αtype,␈αa␈αmore␈αgeneral␈αform␈αof␈αorbit␈αrecursion␈αis

involved.␈α
There␈α∞are␈α
three␈α∞cases␈α
in␈α
the␈α∞problem␈α
of␈α∞labelling␈α
the␈α
decalin␈α∞skeleton␈α
with␈α∞one␈α
␈↓↓N␈↓

and␈α
nine␈α
␈↓↓C␈↓'s:
     (case 1) one N goes to orbit {1,5,6,10}.
     (case 2) one N goes to orbit {2,4,7,9},
     (case 3) one N goes to orbit {3,8}.




␈↓ ε⊂11␈↓ 
x



There␈α
is␈α
only␈α
one␈α
possibility␈α
in␈α
each␈αof␈α
these␈α
cases.␈α
 Suppose␈α
there␈α
were␈α
three␈α
␈↓↓N␈↓'s.␈αThere␈α
are

nine␈α
unique␈α
ways␈α
to␈α
partition␈α
the␈α
three␈α
␈↓↓N␈↓'s␈α
among␈α
the␈α
three␈α
orbits␈α
(Table␈α
IV).
␈↓β______________________________________________________________________

␈↓αTable IV.␈↓β Partitions of Three N's on Orbits of Decalin Skeleton.␈↓#
a␈↓#

                                # N's going to
    case        orbit                 orbit             orbit
    number    {1,5,6,10}            {2,4,7,9}           {3,8}

     1           3                     0                  0
     2           2                     1                  0
     3           2                     0                  1
     4           1                     2                  0
     5           1                     1                  1
     6           1                     0                  2
     7           0                     3                  0
     8           0                     2                  1
     9           0                     1                  2

␈↓#
a␈↓# Reference numbering is that given for ␈↓α2a␈↓β.
______________________________________________________________________



␈↓In␈α
some␈α
of␈α
these␈α
cases␈α
there␈α
is␈α
more␈α
than␈αone␈α
way␈α
of␈α
doing␈α
the␈α
labelling.␈α
 (cases␈α
2,␈α
3,␈α
4,␈α5␈α
and

8).␈α
 However,␈αevery␈α
labelling␈αfits␈α
into␈αone␈α
of␈αthese␈α
cases,␈αand␈α
labellings␈αfrom␈α
different␈αcases

cannot␈α
be␈αequivalent.␈α
 Thus,␈αeach␈α
of␈α
these␈αcases␈α
can␈αbe␈α
done␈αindependently,␈α
and␈α
the␈αresults

collected␈α⊂together.␈α⊂To␈α⊃do␈α⊂any␈α⊂one␈α⊂of␈α⊃the␈α⊂cases,␈α⊂the␈α⊂labellings␈α⊃of␈α⊂the␈α⊂orbits␈α⊂can␈α⊃be␈α⊂done

sequentially.␈α
That␈α
is,␈α
the␈α
rows␈α
of␈α
Table␈α
IV␈αcan␈α
be␈α
done␈α
independently,␈α
and␈α
for␈α
each␈α
row␈αthe

columns␈α
can␈α
be␈α
done␈α
from␈α
left␈α
to␈α
right.



Considering␈α
case␈α
5␈α(Table␈α
IV),␈α
one␈αcan␈α
first␈α
label␈α
one␈αof␈α
{1,5,6,10}␈α
with␈αone␈α
N,␈α
(and␈α
the␈αrest

"blanks").␈α
 Since␈α
{1,5,6,10}␈α
is␈α
an␈α
orbit,␈α
one␈α
can␈α
chose␈α
node␈α
1;␈α
the␈α
result␈α
is␈α
␈↓α8␈↓.









␈↓ ε⊂12␈↓ 
x















Second,␈αone␈αlabels␈α{2,4,7,9}␈αwith␈α1␈αN␈α(and␈α3␈αblanks).␈α Note␈αthat␈α{2,4,7,9}␈αis␈αno␈αlonger␈αan␈αorbit

under␈αthe␈αreduced␈αgroup.␈αafter␈αlabelling␈α{1,␈α5,␈α6,␈α10}.␈αIt␈αis␈αnecessary␈αto␈αfind␈α␈↓↓new␈↓␈αorbits␈αunder

the␈α
reduced␈α
group␈α
to␈α
label␈α
{2,4,7,9}.␈α
Since␈αthere␈α
is␈α
no␈α
symmetry␈α
left,␈α
{2,4,7,9}␈α
splits␈α
into␈αits

four␈αorbits.␈αThe␈α"special␈αcase"␈αdescribed␈αbelow␈αunder␈α"No␈αGroup"␈αcan␈αbe␈αused␈αdirectly␈αto␈αfind

the␈α
four␈α
solutions␈α
(␈↓α9a1-a4␈↓).















Then,␈α
for␈αeach␈α
of␈αthese␈α
solutions,␈α{3,8}␈α
(no␈α
longer␈αequivalent)␈α
must␈αbe␈α
labelled␈αwith␈α
one␈α␈↓↓N␈↓␈α
and

one␈αblank.␈α The␈α
final␈αresult␈αis␈α
eight␈αpossibilities␈αfor␈α
case␈α5,␈αnone␈α
of␈αwhich␈αhas␈α
any␈αremaining

symmetry␈α
(␈↓α9b1-8␈↓).


␈↓αSPECIAL CASES␈↓

There␈αare␈α
several␈αspecial␈α
cases␈αof␈α
labellings␈αin␈α
which␈αthe␈α
problem␈αcan␈α
be␈αreduced␈α
or␈αsolved

immediately.␈α∂Although␈α∂these␈α∂special␈α∂cases␈α∂may␈α∂be␈α∂amenable␈α∂to␈α∂the␈α∂more␈α∂general␈α∞algorithm,

their␈α
solution␈α
is␈α
computationally␈α
simpler.


␈↓ ε⊂13␈↓ 
x



␈↓αOnly␈αone␈αtype␈αof␈αlabel.␈↓␈αIf␈αthe␈αnumber␈αof␈αlabels␈α(of␈αa␈αgiven␈αtype)␈αis␈αthe␈αsame␈αas␈αthe␈αnumber␈αof

objects,␈α
then␈α
there␈α
is␈α
exactly␈α
one␈α
way␈α
of␈αdoing␈α
the␈α
labelling.␈α
This␈α
check␈α
for␈α
this␈α
special␈αcase␈α
is

necessary,␈αsince␈αin␈αorbit␈αrecursion,␈αoften␈αthe␈α
sub-problem␈αis␈αof␈αthis␈αform;␈αn␈↓#v1␈↓#=n,␈αand␈α
n␈↓#v2␈↓#=0␈αor

vice␈α
versa.



␈↓αOnly␈αone␈αof␈αa␈αgiven␈αlabel.␈↓␈αAlready␈αmentioned␈α
was␈αthe␈αcase␈αwhere␈αthere␈αwas␈αone␈αlabel␈α
of␈αone

kind␈α∞and␈α∞n-1␈α∂of␈α∞the␈α∞other;␈α∂it␈α∞was␈α∞only␈α∞necessary␈α∂to␈α∞find␈α∞the␈α∂orbits,␈α∞and␈α∞label␈α∂one␈α∞element

arbitrarily␈αfrom␈αeach␈αof␈αthe␈α
orbits.␈α One␈αmight␈αnote␈αhere␈α
that␈αthe␈αorder␈αin␈αwhich␈α
one␈αapplies

the␈α
labels␈α
in␈α
label␈α
recursion␈α
is␈α
arbitrary␈α
and␈α
thus␈α
if␈α
there␈α
is␈α
only␈α
one␈α
of␈α
␈↓↓any␈↓␈α
of␈α
the␈α
labels,␈α
then

this␈α
special␈α
case␈α
can␈α
be␈α
applied␈α
immediately.



␈↓αNo␈αgroup.␈↓␈αWhen␈αthere␈αis␈αno␈αsymmetry␈αleft␈αand␈αthere␈αare␈αtwo␈αlabel␈αtypes␈α(n␈↓#v1␈↓#␈αof␈αthe␈αfirst␈α
type,

n␈↓#v2␈↓#␈α
of␈αthe␈α
second,␈α
n␈↓#v1␈↓#+n␈↓#v2␈↓#=n,␈αthe␈α
number␈α
of␈αobjects␈α
to␈αbe␈α
labelled),␈α
the␈αlabelling␈α
reduces␈α
to␈αa

simple␈α
combinatorial␈α
problem:␈α
given␈α
n␈α
distinct␈α∞objects,␈α
find␈α
all␈α
ways␈α
of␈α
selecting␈α
n␈↓#v1␈↓#␈α∞of␈α
them.

This␈α
can␈α
be␈α
done␈α
by␈α
the␈α
following␈α
recursive␈α
algorithm:

To find all selections of k objects out of set S whose size is n:

  1) if k = 0 then there is only one selection, the empty set.

  2) if k > n then there are no possible selections.

  3) Otherwise, pick an element x from S.

       a)  Find all selections of k objects out of the set S-{x}.

       b)  Find all selections of k-1 objects out of the set S-{x};
            to each of these, add the element x.

       c) The result is the union of results from steps 3a and 3b.




A␈αsubset␈αof␈α
a␈αset␈αS␈α
with␈αk␈αelements␈αeither␈α
contains␈αan␈αelement␈α
x␈αor␈αnot.␈α
 In␈αcase␈α3a,␈αone␈α
finds



␈↓ ε⊂14␈↓ 
x



those␈α⊂selections␈α⊂which␈α⊂do␈α⊂not␈α⊂contain␈α⊂x.␈α⊃In␈α⊂case␈α⊂3b,␈α⊂one␈α⊂finds␈α⊂those␈α⊂selections␈α⊃which␈α⊂do.

However,␈αeach␈αof␈αthese␈αcases␈αare␈αsimpler␈αthan␈αthe␈αoriginal␈αselection␈αproblem;␈αthe␈αsize␈αof␈αthe

set␈αS␈α
reduces,␈αas␈α
well␈αas␈α
the␈αvalue␈αof␈α
k.␈αThe␈α
terminating␈αconditions,␈α
k=0,␈αor␈α
k␈αgreater␈αthan␈α
the

size␈α
of␈α
the␈α
set␈α
S,␈α
insure␈α
that␈α
the␈α
process␈α
will␈α
halt.


␈↓αFINAL TECHNIQUE␈↓

It␈α∞has␈α
been␈α∞now␈α∞shown␈α
that␈α∞every␈α∞problem␈α
can␈α∞be␈α
reduced␈α∞by␈α∞label␈α
and␈α∞orbit␈α∞recursion␈α
to

cases␈α⊃where␈α⊃there␈α⊃are␈α⊃only␈α⊃two␈α⊃types␈α⊃of␈α⊃labels,␈α⊃n␈↓#v1␈↓#␈α⊃of␈α⊃the␈α⊃first,␈α⊃and␈α⊃n␈↓#v2␈↓#␈α⊃of␈α⊃the␈α⊂second,

(n␈↓#v1␈↓#+n␈↓#v2␈↓#=n,␈α∞the␈α∞number␈α∞of␈α∞nodes␈α∞to␈α∞be␈α∞labelled),␈α∞both␈α∞n␈↓#v1␈↓#␈α∞and␈α∞n␈↓#v2␈↓#␈α∞>␈α∞1,␈α∞and␈α∞there␈α∞is␈α∞only␈α∞one

orbit.␈αNo␈αmore␈αsimple␈αreductions␈αare␈αleft.␈α One␈αsolution␈αis␈αas␈αfollows.␈α Pick␈αthe␈αfirst␈αnode␈αand

label␈αit,␈αcalculating␈αthe␈αreduced␈αsymmetry␈αgroup␈αand␈αnew␈αorbits.␈α Label␈αthe␈αrest␈αof␈αthe␈αnodes

(under␈αthe␈αreduced␈α
group)␈αwith␈αn␈↓#v1␈↓#-1␈αlabels␈α
of␈αtype␈α1␈α
and␈αn␈↓#v2␈↓#␈αlabels␈αof␈α
type␈α2.␈α The␈αresult␈α
will

contain␈α
a␈αrepresentative␈α
of␈α
each␈αequivalence␈α
class␈αof␈α
labellings;␈α
however,␈αif␈α
n␈↓#v1␈↓#>2␈α
then␈αthere

may␈α
be␈α
some␈α
duplicates␈α
(i.e.,␈α
two␈α
or␈α
more␈α
of␈α
the␈α
results␈α
may␈α
actually␈α
be␈α
equivalent).



For␈αexample,␈α
the␈αcyclohexane␈αskeleton␈α
has␈αa␈α
group␈αof␈αorder␈α
twelve␈α(has␈αtwelve␈α
permutations),

and␈α⊃there␈α⊃is␈α⊃only␈α⊃one␈α⊃orbit.␈α⊃ To␈α⊃label␈α⊃it␈α⊃with␈α⊃three␈α⊃␈↓↓N␈↓'s,␈α⊃one␈α⊃labels␈α⊃node␈α⊃one␈α⊃with␈α⊃a␈α⊂␈↓↓N␈↓,

calculates␈αthe␈αreduced␈αgroup␈αand␈αnew␈αorbits;␈αthen␈αfinds␈αthe␈αvarious␈αcases␈αfor␈αdistributing␈αthe

remaining␈α⊗two␈α∃␈↓↓N␈↓'s␈α⊗among␈α∃those␈α⊗orbits␈α∃(Table␈α⊗V.)␈α∃Then␈α⊗for␈α∃each␈α⊗case,␈α∃do␈α⊗each␈α∃orbit

sequentially.␈α
 Cases␈α1,␈α
3,␈α
4␈αand␈α
5␈α
are␈αfairly␈α
straightforward;␈α
  in␈αcase␈α
2,␈α
first␈αlabel␈α
{1,2}␈αwith␈α
1

N␈α
(see␈α
␈↓α10␈↓).












␈↓ ε⊂15␈↓ 
x



Now␈αthe␈αgroup␈α
reduces␈αeven␈αfurther,␈α
and␈αone␈αgets␈α
the␈αtwo␈αresults␈α
depicted␈αin␈α␈↓α10b␈↓.␈α Note␈α
that

cases␈α1␈αand␈α2a␈αare␈αequivalent␈αas␈αwell␈αas␈α2b,␈α3,␈αand␈α5.␈α  What␈αto␈αdo?␈α  Fortunately,␈αthere␈αis␈αa

good␈αway␈α
of␈αthrowing␈αout␈α
the␈αduplicates␈αwithout␈α
having␈αto␈αcheck␈α
each␈αof␈αthe␈α
results␈αagainst

each␈α
of␈α
the␈α
others␈α
for␈α
equivalency.␈α
 If␈α
there␈α
is␈α
a␈α
permutation␈α
π␈α
in␈α
the␈α
group,␈α
such␈α
that
                             π (labelled set) > labelled set

then␈αthe␈α
labelled␈αset␈α
is␈αa␈αa␈α
duplicate.␈αFurthermore,␈α
every␈αduplicate␈αis␈α
detected␈αthis␈α
way.␈α All

that␈αis␈αnecessary␈αis␈αto␈αbe␈αcareful␈αwhen␈αdoing␈αthese␈α"lower␈αlevel"␈αlabellings␈αto␈αpick␈αthe␈α"first"

element␈α∞of␈α∞each␈α∞orbit␈α∞to␈α∞label␈α∞(in␈α∞the␈α∞numerical␈α∞order␈α∞of␈α∞the␈α∞reference␈α∞numbering)␈α∞and␈α
the

"first␈α
orbit"␈α
when␈α
there␈α
are␈α
a␈α
choice␈α
of␈α
orbits.
␈↓β______________________________________________________________________
␈↓αTable V.␈↓β Unique ways of Distrubuting Two N's on {2,3,4,5,6} of
        Cyclohexane.

       case    {2,6}  {3,5}    {4}

        1       2       -       -
        2       1       1       -
        3       1       -       1
        4       -       2       -
        5       -       1       1
______________________________________________________________________



␈↓Fortunately,␈αthis␈αtechnique␈αis␈αrarely␈αnecessary␈α
--␈αusually␈αin␈αthe␈αcourse␈αof␈αa␈α
computation,␈αthe

"special␈αcases"␈αcatch␈αalmost␈αeverything.␈α For␈αexample,␈α
to␈αlabel␈αthe␈αdecalin␈αskeleton,␈αit␈αis␈α
never

needed␈α
since␈α
even␈α
when␈α
one␈α
is␈α
labelling␈α
say␈α
orbit␈α
{2,4,7,9},␈α
there␈α
is␈α
either␈α
1,␈α
2,␈α
n-1␈α
or␈αn-2

labels␈α
to␈αbe␈α
attached.␈α
 For␈αthe␈α
cyclohexane␈α
skeleton,␈αit␈α
is␈α
only␈αneeded␈α
if␈α
there␈αare␈α
3␈α
of␈αone

label␈αand␈α3␈αof␈αanother;␈αif␈αthere␈αwere␈α3,␈α2␈αand␈α1␈αof␈αthree␈αrespective␈αlabel␈αtypes␈αfor␈αexample,

just␈αdo␈αthe␈αsingle␈αlabel␈αfirst␈α--␈αthe␈αgroup␈αwill␈αthen␈αreduce␈αand␈αagain␈αthis␈α"final␈αtechnique"␈αwill

not␈αbe␈αnecessary.␈α  Only␈αin␈αcases␈αwhere␈αthere␈αis␈αan␈αorbit␈αwith␈αat␈αleast␈α6␈αelements␈α
and␈αthere

are␈α
at␈α
least␈α
3␈α
of␈α
each␈α
of␈α
the␈α
label␈α
types␈α
is␈α
this␈α
technique␈α
required.






␈↓ ε⊂16␈↓ 
x



␈↓ ∧≡␈↓αPART C: SUMMARY OF LABELLING STEPS␈↓

1)␈α
Calculate␈α
the␈α
group,␈α
if␈α
not␈α
previously␈α
calculated.

2)␈α
If␈α
there␈α∞are␈α
more␈α
than␈α
two␈α∞different␈α
node␈α
types,␈α
do␈α∞the␈α
entire␈α
labelling␈α∞process␈α
with
␈↓ ↓xone␈αof␈αthe␈αlabel␈αtypes,␈αand␈αthe␈αrest␈α"blanks";␈αthen␈αfor␈αeach␈αof␈αthe␈α
solutions␈αobtained,
␈↓ ↓xlabel␈α∞the␈α
"blanks"␈α∞with␈α
the␈α∞remaining␈α
label␈α∞types␈α
using␈α∞the␈α
reduced␈α∞symmetry␈α
group
␈↓ ↓xand␈α
collect␈α
the␈α
results.

3)␈α
Otherwise,␈α
(only␈α
two␈α
label␈α
types),

␈↓ ↓xa)␈α
Find␈α
the␈α
orbits.

␈↓ ↓xb)␈α
If␈α
more␈α
than␈α
one␈α
orbit,␈α
then

␈↓ α(1)␈α
Find␈α
the␈α
different␈α
"cases"␈α
--␈α
ways␈α
of␈α
distributing␈α
the␈α
labels␈α
among␈α
the
␈↓ αXorbits.

␈↓ α(2)␈α
For␈α
each␈α
case,

␈↓ αXa)␈α
Label␈α
the␈α
first␈α
orbit.

␈↓ αXb)␈α
Label␈α
the␈α
rest␈α
of␈α∞the␈α
orbits␈α
using␈α
the␈α
reduced␈α∞symmetry␈α
group
␈↓ βλobtained␈α
from␈α
a),␈α
and␈α
collect␈α
the␈α
results.

␈↓ ↓xc)␈α
Otherwise␈α
(only␈α
1␈α
orbit␈α
and␈α
2␈α
label␈α
types):

␈↓ α(1)␈α
If␈α
there␈α
is␈α
only␈α
one␈α
either␈α
label␈α
type,␈α
pick␈α
the␈α
"first"␈α
node␈α
and␈α
label␈αit
␈↓ αXwith␈α
that␈α
label␈α
type.␈α
 This␈α
is␈α
the␈α
only␈α
distinct␈α
possibility.

␈↓ α(2)␈α∞Otherwise␈α∞if␈α
there␈α∞are␈α∞exactly␈α
two␈α∞of␈α∞either␈α
label␈α∞type,␈α∞label␈α∞the␈α
first
␈↓ αXnode␈α∞with␈α∞that␈α∞label␈α∞type,␈α∞calculate␈α∞the␈α∞reduced␈α∞symmetry␈α∂group␈α∞and
␈↓ αXnew␈αorbits,␈αand␈αfrom␈αeach␈αof␈αthe␈αnew␈αorbits,␈αpick␈αthe␈α"first"␈αnode.␈α The
␈↓ αXsolutions␈α
consist␈α
of␈α
those␈α
possibilities␈α
(one␈α
for␈α
each␈α
new␈α
orbit).

␈↓ α(3)␈αOtherwise,␈α(3␈αor␈αmore␈αof␈αeach␈αlabel␈αtype,␈αand␈αone␈αorbit)␈αlabel␈αthe␈α"first"
␈↓ αXnode,␈α
calculate␈α
the␈α
reduced␈α
symmetry␈α
group,␈α
label␈α
the␈α
rest␈α
of␈α
the␈α
nodes
␈↓ αXunder␈α
the␈α
reduced␈α
group,␈α
and␈α
for␈α
each␈α
of␈α
the␈α
results,␈α
check␈α
if␈α
for␈α
every
␈↓ αXpermutation␈α
π␈α
in␈α
the␈α
original␈α
group␈α
that
␈↓ α(                π(labelled set)≥labelled set
␈↓ αXIf␈αthis␈αis␈αnot␈αtrue␈αof␈αa␈αlabelled␈αset,␈αdiscard␈αit␈αas␈αa␈αsolution.␈α  The␈αresult
␈↓ αXis␈α
every␈α
such␈α
labelling␈α
that␈α
satisfies␈α
this␈α
property.










␈↓ ε⊂17␈↓ 
x



␈↓ ∧\␈↓αPART D:  EXTENDED EXAMPLES␈↓


␈↓αStudy of Diels-Alder Rings␈↓␈↓#
8␈↓#␈↓α

␈↓The␈α
labelling␈αalgorithm␈α
has␈αbeen␈α
used␈α
to␈αdefine␈α
the␈αscope␈α
and␈αboundaries␈α
of␈α
the␈αDiels-Alder

reaction,␈α∞a␈α
well-known␈α∞and␈α
commonly␈α∞used␈α
synthetic␈α∞reaction.␈α
 The␈α∞reaction␈α
is␈α∞shown␈α∞in␈α
␈↓α11␈↓,

and␈αis␈αdefined␈αas␈αthe␈α4+2␈αcycloaddition␈αof␈αan␈αolefin,␈αtermed␈αthe␈αdienophile,␈αwith␈αa␈αconjugated

diene,␈α
leading␈α
to␈α
the␈α
formation␈α
of␈α
a␈α
cyclohexene-type␈α
of␈α
ring␈α
system␈α
(Diels-Alder␈α
Ring).








The␈α
method␈αused␈α
by␈αthe␈α
program␈α
to␈αgenerate␈α
Diels␈αAlder␈α
Rings␈αis␈α
described␈α
below,␈αfollowed

by␈α∂an␈α∂example␈α∂of␈α∂the␈α∂labelling␈α∂procedure.␈α∂ The␈α∂program␈α∂generated␈α∂1176␈α⊂Diels-Alder␈α∂Rings

using␈αany␈αcombination␈αof␈αC,␈αN,␈αO␈αand␈αS.␈α Other␈αatoms␈αsuch␈αas␈αP␈αcould␈αhave␈αbeen␈αincluded␈αbut

were␈α∞deemed␈α∂not␈α∞interesting␈α∞to␈α∂us.␈α∞ A␈α∞comparison␈α∂of␈α∞the␈α∞computer␈α∂print-out␈α∞with␈α∂the␈α∞Ring

Index␈α(which␈αcovers␈αthe␈αliterature␈αthrough␈α1963)␈αrevealed␈αthat␈αonly␈α224␈α(about␈α19%␈αof␈α1176)

are␈α
"known"␈αsystems.␈α
 A␈αring␈α
system␈αwas␈α
said␈αto␈α
be␈αknown␈α
if␈αthe␈α
same␈αsequence␈α
of␈αatoms␈α
had

been␈αreported␈αregardless␈αof␈αnumber␈αor␈αposition␈αof␈αunsaturations.␈α The␈αcomplete␈αlist␈αof␈αDiels-

Alder␈α⊂Rings␈α⊂is␈α⊂richly␈α⊂suggestive␈α⊂to␈α⊃the␈α⊂synthetic␈α⊂chemists␈α⊂and␈α⊂may␈α⊂serve␈α⊂to␈α⊃increase␈α⊂the

information␈α
on␈α
the␈α
scope␈α
of␈α
the␈α
Diels-Alder␈α
reaction.











____________________________________
␈↓#
8␈↓#proposed␈α≤by␈α≤Jan␈α≤Simek,␈α≤Chemistry␈α≤Department,␈α≤Stanford␈α≤UniversityResearch␈α≤Proposal
(unpublished),␈α
February,␈α
1973.

␈↓ ε⊂18␈↓ 
x

























␈↓αMETHOD  ␈↓(see ␈↓α12␈↓)␈↓α

␈↓␈↓αStep␈α
1.␈↓␈αThe␈α
initial␈αpot␈α
of␈αatoms␈α
consisted␈αof␈α
C␈↓#v6␈↓#N␈↓#v6␈↓#O␈↓#v4␈↓#S␈↓#v4␈↓#.␈α The␈α
number␈αof␈α
oxygens␈α
and␈αsulfurs

was␈αlimited␈αto␈αfour,␈αbecause␈αno␈αDiels-Alder␈α
ring␈αcan␈αbe␈αmade␈αwith␈αfive␈αor␈αsix␈α
bivalent␈αatoms,

owing␈αto␈αvalence␈αrestrictions.␈α A␈αlist␈αof␈αall␈αpossible␈α76␈αcompositions␈αof␈α6␈αatoms␈αwas␈αproduced

using␈α
a␈α
purely␈α
combinatorial␈α
procedure.



␈↓αStep␈α2.␈↓␈αEleven␈αof␈αthe␈α76␈αcompositions␈αwere␈αeliminated,␈αagain␈αowing␈αto␈αvalence␈αlimitations.␈α An

example␈α
of␈α
the␈α
eleven␈α
compositions␈α
eliminated␈α
is␈α
O␈↓#v3␈↓#S␈↓#v3␈↓#.



␈↓αStep␈α3.␈↓␈αFor␈αeach␈αof␈αthe␈α65␈αremaining␈αcompositions,␈αthe␈αDiels-Alder␈αring␈αskeleton␈αwas␈αlabelled

with␈α
the␈α
atoms,␈α
while␈α
ensuring␈α
valence␈α
constraints␈α
were␈α
satisfied.



␈↓αStep␈α⊃4.␈↓␈α⊃The␈α⊃results␈α⊃from␈α⊃all␈α⊃labelling␈α⊂steps␈α⊃were␈α⊃collected,␈α⊃without␈α⊃needing␈α⊃to␈α⊃check␈α⊂for

duplicates.␈α
 The␈α
labelling␈α
algorithm␈α
guarantees␈α
that␈α
the␈α
lists␈α
were␈α
irredundant.



␈↓ ε⊂19␈↓ 
x



␈↓αExample␈αof␈αlabelling.␈↓␈αAn␈αexample␈αof␈αa␈αvalid␈αcomposition␈αis␈αC␈↓#v4␈↓#O␈↓#v2␈↓#.␈α Diels-Alder␈αrings␈αformed␈α
with

this␈α∂composition␈α∂can␈α∂only␈α∞have␈α∂carbons␈α∂double␈α∂bonded␈α∂to␈α∞each␈α∂other␈α∂(see␈α∂␈↓α13␈↓).␈α∂ The␈α∞atoms

remaining␈α
to␈α
be␈α
assigned␈α
are␈α
C␈↓#v2␈↓#O␈↓#v2␈↓#␈α
and␈α
the␈α
ring␈α
positions␈α
are␈α
numbered␈α
1,2,3,4.


















␈↓αVerification by Enumeration␈↓

The␈αresults␈αof␈αof␈αthe␈αlabelling␈αprocedure␈αcan␈αbe␈αverified␈αby␈αcombinatorial␈αcounting␈αtechniques

␈↓#
4␈↓#␈↓#
,␈↓#␈α␈↓#
5␈↓#.␈α The␈αfollowing␈αderivation␈αfollows␈αclosely␈αfrom␈αthat␈αin␈αLiu␈↓#
9␈↓#.␈α The␈αgenerating␈αfunction␈↓#
10␈↓#␈αof

the␈α
number␈α
of␈α
labellings␈α
with␈α
two␈α
types␈α
of␈α
labels␈α
can␈α
be␈α
calculated␈α
with␈α
the
␈↓βCycle Index of Group=PG = 1/2(y␈↓#
4␈↓#␈↓#+ y␈↓#
2␈↓#␈↓#)
                               ␈↓#v1   ␈↓#v1

␈↓and␈α
the
␈↓βPattern Inventory is 1/2 (x␈↓#
1␈↓#␈↓#+ x␈↓#
1␈↓#␈↓#)␈↓#
4␈↓#+ (x␈↓#
2␈↓#␈↓#+ x␈↓#
2␈↓#␈↓#)␈↓#
2␈↓#
                           ␈↓#v1   ␈↓#v2      ␈↓#v1   ␈↓#v2

␈↓showing␈α
that␈α
there␈α
are␈α
precisely␈α
these␈α
number␈α
of␈α
labellings:
␈↓β        labels         #labellings

       C␈↓#v4␈↓#                 1
       S␈↓#v4␈↓#                 1
       C␈↓#v2␈↓#S␈↓#v2␈↓#               4
       CS␈↓#v3␈↓#                2
       C␈↓#v3␈↓#S                2




____________________________________
␈↓#
9␈↓#␈↓α␈↓Liu,␈α
Introduction␈α
to␈α
Comb.␈α
Math,␈α
McGraw-Hill,␈α
1968

␈↓#
10␈↓#generate␈α
a␈α
reference␈α
for␈α
generating␈α
functions

␈↓ ε⊂20␈↓ 
x



␈↓The␈α
third␈α
entry␈α
in␈α
the␈α
table␈α
verifies␈α
our␈α
labelling␈α
with␈α
C␈↓#v2␈↓#S␈↓#v2␈↓#␈α
in␈α
four␈α
ways.


␈↓αLabellings on the Octahedral Skeletal Framework.␈↓

This␈αexample␈αis␈αconcerned␈αwith␈αthe␈αgeometric␈αisomers␈αof␈αstructures␈αwith␈αoctahedral␈αsymmetry

(see␈α
␈↓α14␈↓).










␈↓β______________________________________________________________________␈↓

            Labellings on Octahedral Skeletal Framework
Group is:

          i      (1 2 3 4 5 6)
          r␈↓#v1␈↓#    (1 3 5 4 6 2)
          r␈↓#v2␈↓#    (1 5 6 4 2 3)
          r␈↓#v3␈↓#    (1 6 2 4 3 5)
          v␈↓#v1␈↓#    (4 5 3 1 2 6)
          v␈↓#v2␈↓#    (4 2 6 1 5 3)
          v␈↓#v3␈↓#    (4 3 2 1 6 5)
          v␈↓#v4␈↓#    (4 6 5 1 3 2)

Orbits:  {1,4}, {2,3,5,6}.

Example with labels (A A A A B B)
   Number of labels A = 4
   Number of labels B = 2


Partitioning Labels into Orbits:

   Case   number of A's assigned to orbit:
    #     {1 4}     {2 3 5 6}

    1       2           0
    2       1           1
    3       0           2

Case 1.  To map A A --> {1,4}
            and A A B B --> {2,3,5,6}
   Map A A --> {1,4} (trivial case)

␈↓ ε⊂21␈↓ 
x



   New group   i, r␈↓#v1␈↓#, r␈↓#v2␈↓#, r␈↓#v3␈↓#, v␈↓#v1␈↓#, v␈↓#v2␈↓#, v␈↓#v3␈↓#, v␈↓#v4␈↓#
   New orbits {2 3 5 6}
   To map A A B B --> {2 3 5 6}

   Case 1.1.  Assign A --> 2
      New group i,r␈↓#v2␈↓#
      New orbits {5},{3,6}

      Case 1.1.1.  Assign A --> 5
         Remaining B B --> {3,6}
                                1 labelling (A A B A A B)

      Case 1.1.2.  Assign A --> 3
         Remaining B B --> {5,6}
                                1 labelling (A A A A B B)

Case 2.  To map A B --> {1,4}
            and A A A B --> {2,3,5,6}
         Assign A --> 1 and B --> 4
         New group i, r␈↓#v1␈↓#, r␈↓#v2␈↓#, r␈↓#v3␈↓#
         New orbits {2 3 5 6}
         To map A A A B --> {2 3 5 6}

  Case 2.1. Assign B --> 2
         To map A A A --> {3 5 6}
                                 1 labelling (A B A B A A)

Case 3.  To map B B --> {1 4}
            and A A A A --> {2 3 5 6}
         Assign B --> and B --> 4
         New group  i, r␈↓#v1␈↓#, r␈↓#v2␈↓#, r␈↓#v3␈↓#, v␈↓#v1␈↓#, v␈↓#v2␈↓#, v␈↓#v3␈↓#, v␈↓#v4␈↓#
         New orbit {2 3 5 6}
         To map A A A A --> {2 3 5 6}
                              1 labelling (B A A B A A)









Example with Labels  A B C D E F
Case 1.  A --> orbit {1 4}
         A --> 1
   new group  i, r␈↓#v1␈↓#, r␈↓#v2␈↓#, r␈↓#v3␈↓#
      new orbits A1 = {2 3 5 6}
                 A2 = {4}
   Assign label B
   Case 1.1. B --> orbit A1

␈↓ ε⊂22␈↓ 
x



            B --> 2
      new group i; special case No Group

   Case 1.2. B --> orbit A2
            B --> 4
      new group  i, r1, r2, r3
      new orbits AA1 = {2 3 5 6}
      Case 1.2.1  C --> orbit AB1
                C --> 2
         new group i; special case No group

Case 2. A --> orbit {2 3 5 6}
        A --> 2
   new group i,                 ???
   new orbits B1 = {1 4}
              B2 = {5}
              B3 = {3 6}

   Case 2.1. B --> orbit B1
            B --> 1
      new group i; special case No Group; 24 labellings

   Case 2.2. B --> orbit B2
            B --> 5
      new group i,?                             ???? fill in
      new orbits BB1 = {1 4}
                 BB2 = {3 6}

      Case 2.2.1. C --> orbit BB1
                C --> 1
         new group i; special case No Group; 6 labellings

      Case 2.2.2. C --> orbit BB2
                C --> 3
         new group i ; special case No group ; 6 labellings

   Case 2.3. B --> B3
            B --> 3
      new group i ; special case No Group; 24 labellings

90 unique labelings all together.

Verification:  When all labels are different the total number of
labellings
=␈↓#
(# labels)!␈↓#    ␈↓#  ␈↓#
6!␈↓#
 ␈↓#v(size of group)  ␈↓#v8␈↓#
 -------------- = ---=90 labellings







␈↓ ε⊂23␈↓ 
x



␈↓ ¬_␈↓αACKNOWLEDGEMENTS␈↓



We␈α
gratefully␈α∞acknowledge␈α
the␈α
contributions␈α∞of␈α
D.␈α
H.␈α∞Smith,␈α
whose␈α
aid␈α∞in␈α
the␈α∞preparation␈α
of

this␈α
paper␈α
was␈αinvaluable,␈α
Jan␈α
Simek,␈αwho␈α
proposed␈α
the␈α
application␈αin␈α
Part␈α
D,␈αLarry␈α
Hjelmeland

who␈α∞formulized␈α∞the␈α∞initial␈α∞problem,␈α∞Professor␈α∞Harold␈α∞Brown,␈α∞who␈α∞proved␈α∞the␈α∂correctness␈α∞of

the␈α∩original␈α∩algorithms,␈α∩and␈α∩Professor␈α∩Joshua␈α∩Lederburg,␈α∩whose␈α∩advice␈α∩and␈α∩guidance␈α⊃has

always␈α
been␈α
an␈α
inspiration.







































␈↓ ε⊂24␈↓ 
x