␈↓ βTLABELLING OBJECTS HAVING SYMMETRY

␈↓␈↓ ∧'L. Masinter, N.S. Sridharan, D. H. Smith

␈↓ ∧kComputer Science Department
␈↓ ¬*Stanford University
␈↓ ¬*Stanford, California

␈↓ ¬←May, 1973






␈↓␈↓ α(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.



␈↓␈↓ ¬F␈↓αINTRODUCTION␈↓



␈↓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␈αnumber␈αof

labels␈αor␈αcolors␈αto␈αthe␈αparts␈αof␈αa␈αsymmetric␈αobject␈αwhen␈αit␈αis␈αalso␈αknown␈αhow␈αmany␈αparts␈αget␈α
each

of␈αthe␈αlabels␈αor␈αcolors.␈αIn␈αchemistry,␈αone␈αmanifestation␈αof␈αthis␈αproblem␈αis␈αto␈αmake␈αall␈αassignments

of␈αligands␈α(from␈αa␈αfixed␈αset)␈α
to␈αa␈αgiven␈αcarbocyclic␈αskeleton␈↓#
1␈↓#.␈α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␈↓#
2␈↓#.␈α∪ 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␈↓#
3␈↓#␈↓#
,␈↓#␈α
␈↓#
4␈↓#,␈α
but␈α
an␈α
efficent␈α
method␈αof␈α
actually␈α
constructing␈α
the␈α
solutions␈α
has␈α
not␈αpreviously␈α
been

␈↓published␈↓#
5␈↓#.
------------------
␈↓#
1␈↓#Masinter,␈αL.,␈α
Sridharan,␈αN.␈α
S.,␈αet.al.,␈α
Applications␈αof␈α
Artificial␈αIntelligence␈α
for␈αChemical␈α
Inference
-␈α
XII,␈α
submitted,␈α
1973,␈α
␈↓↓J.␈α
Amer.␈α
Chem.␈α
Soc.␈↓

␈↓#
2␈↓#Brown,␈α⊂H.,␈α⊂Masinter,␈α⊃L.,␈α⊂Hjelemeland,␈α⊂L.,␈α⊂Constructive␈α⊃Graph␈α⊂Labelling␈α⊂Using␈α⊃Double␈α⊂Cosets,
submitted,␈α∩1972,␈α∪␈↓↓Discrete␈α∩Mathematics␈↓;␈α∪also,␈α∩Stanford␈α∩Computer␈α∪Science␈α∩Memo␈α∪??,␈α∩Stanford
University.

␈↓#
3␈↓#De␈αBruijn,␈αN.␈αG.,␈αGeneralization␈αof␈αPolya's␈αFundamental␈αTheorem␈αin␈α
Enumerative␈αCombinatorial
Analysis,␈α
␈↓↓Nedarl.␈α
Akad.␈α
Wentesh.␈α
Proc.␈α
Ser.␈α
A,␈α
␈↓α62␈↓,␈α
(1959),␈α
59-69

␈↓#
4␈↓#De␈α
Bruijn,␈α
"Polya's␈α
Theory␈α
of␈α
Counting,"␈α
␈↓↓Applied␈α
Combinatorial␈α
Mathematics␈↓,␈α∞E.␈α
Beckenbach
(ed.),␈α
Wiley,␈α
New␈α
York,␈α
1964,␈α
pp␈α
144-184.

␈↓#
5␈↓#see,␈α∂however,␈α⊂Perlman,␈α∂D.␈α∂M.,␈α⊂Isomorph␈α∂Rejection␈α∂on␈α⊂Power␈α∂Sets,␈α∂(unpublished),␈α⊂University␈α∂of
California␈α
San␈α
Diego.

␈↓␈↓ ε_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.␈α This␈α
means

that,␈α
for␈αexample,␈α
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␈α
(Fig.␈α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␈α∞(Fig␈α∂2a).␈α∞ Some␈α∞of␈α∞the␈α∞10!␈α∂ways␈α∞are

different␈α
(Fig␈α
2b);␈α
some␈α
of␈α
them␈α
are␈α
essentially␈α
the␈α
same␈α
(Fig␈α
2c).
␈↓Fig. 1␈↓α␈↓ εi→→ Figure 1, The Decalin Skeleton ←←←←←␈↓
␈↓Fig. 2␈↓α␈↓ β`→→ Figure 2, Three of the 10! numberings of the Decalin Skeleton. ←←←←←␈↓



␈↓Intuitively,␈αFigs␈α2a␈αand␈α
2c␈αare␈αequivalent␈αbecause␈αone␈α
could␈αtake␈α2a,␈αflip␈α
it␈αover␈αthe␈α3-8␈αaxis,␈α
and

get␈α
2c.␈α There␈α
is␈α
another␈αway␈α
of␈αdetermining␈α
the␈α
"sameness"␈αof␈α
such␈α
numberings␈αwhich␈α
is␈αeasier␈α
in

the␈α
more␈α
complicated␈α
cases␈α
and␈α
is␈α
in␈α
general␈α
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␈α∂the␈α∂structures␈α∞in␈α∂Fig.␈α∞2.␈α∂ Note␈α∂that␈α∞the

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












␈↓ ε_2␈↓ 
x



␈↓β__________________________________________________________________

                            Table I.

          Structure (2a)   Structure (2b)  Structure (2c)

         node|connected | node|connected | node|connected
             |   to     |     |   to     |     |  to
                        |                |
           1    2,1O    |  1    8,9      |  1    2,1O
           2    1,3     |  2    7,3      |  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␈α
extened␈α
to␈α
include␈α
the␈α
preserving␈α
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␈αFig␈α3a␈αwould␈αstill␈αbe␈α
equivalent

to␈αFig␈α3c␈α
but␈αno␈αlonger␈αto␈α
Fig␈α3b␈αsince,␈αalthough␈α
the␈αconnection␈αtables␈αof␈α
3a␈αand␈α3b␈αare␈α
identical,

node␈α
1␈α
in␈α
Fig␈α
3a␈α
is␈α
labelled␈α
with␈α
an␈α
"N"␈α
while␈α
in␈α
3b␈α
it␈α
unlabelled.
Fig. 3␈↓α␈↓ ∧¬→→ Figure 3, Partially labelled graphs reduce the equivalencies. ←←←←←␈↓









␈↓ ε_3␈↓ 
x



␈↓␈↓αPERMUTATIONS AND PERMUTATION GROUPS␈↓
␈↓Given␈α∪a␈α∪numbering␈α∪of␈α∪a␈α∪structure,␈α∪one␈α∪can␈α∪use␈α∪a␈α∪condensed␈α∪notation␈α∪to␈α∪write␈α∪down␈α∪other

numberings␈α
in␈α∞terms␈α
of␈α
the␈α∞first␈α
(Table␈α
II).␈α∞In␈α
the␈α
2b␈α∞case,␈α
the␈α
row␈α∞of␈α
numbers␈α
means␈α∞that,␈α
in

sequence,␈α⊃the␈α⊂node␈α⊃numbered␈α⊃1␈α⊂in␈α⊃the␈α⊂reference␈α⊃numbering␈α⊃2a␈α⊂is␈α⊃now␈α⊂numbered␈α⊃2,␈α⊃the␈α⊂node

originally␈αnumbered␈α2␈αis␈αnow␈α
numbered␈α10,␈αand␈αso␈αon.␈α All␈α
of␈αthese␈αare␈αwritten␈αdown␈αwith␈α
respect

to␈α
the␈α
original␈α
"reference"␈α
numbering␈α
of␈α
figure␈α
2a.
␈↓β_________________________________________________________________

                             Table II
                 Condensed Notation for Numberings

             Figure 2a numbers:  1  2  3  4  5  6  7  8  9 10

             Figure 2b numbers:  2  7  8  1  9  5 10  4  6  3

             Figure 2c numbers:  5  4  3  2  1 10  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␈α⊗i(x)=x.␈α∃It␈α⊗can␈α∃be␈α⊗shown␈α⊗that␈α∃whatever␈α⊗the␈α∃graph,␈α⊗the␈α⊗set␈α∃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.











␈↓ ε_4␈↓ 
x



␈↓β_____________________________________________________________________

                             Table III
                          The Symmetry Group
                        of the Decalin Skeleton


                 π␈↓#vi␈↓#     1  2  3  4  5  6  7  8  9 10
                 π␈↓#vv␈↓#     5  4  3  2  1 10  9  8  7  6
                 π␈↓#vh␈↓#    10  9  8  7  6  5  4  3  2  1
                 π␈↓#v180␈↓#   6  7  8  9 10  1  2  3  4  5
␈↓β____________________________________________________________________



␈↓These␈α∞correspond␈α∞directly␈α∞to␈α∂the␈α∞intuitive␈α∞geometric␈α∞symmetries␈α∞π␈↓#vi␈↓#=identity,␈α∂π␈↓#vh␈↓#=reflection␈α∞about

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

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

connection␈α
table␈↓#
6␈↓#.



␈↓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).







------------------
␈↓#
6␈↓#this␈α
needs␈α
to␈α
be␈α
described

␈↓ ε_5␈↓ 
x



␈↓β__________________________________________________________________

                          Table IV
     Permutation Group of Decalin Skeleton acting on the edges

  π␈↓#vi␈↓#     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
____________________________________________________________________



␈↓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␈α
to␈αeach␈α
other.␈α 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.



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

can␈α
be␈αviewed␈α
as␈α
follows:␈αTake␈α
the␈αn!␈α
possible␈α
labellings␈αand␈α
lay␈αthem␈α
out␈α
in␈αa␈α
matrix:␈α
each␈αrow

will␈αcontain␈αone␈αequivalence␈αclass.␈α(It␈αcan␈αbe␈αshown␈αthat␈αin␈αthis␈αspecial␈αcases␈α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.
Fig. 4␈↓α␈↓ ∧[→→ Figure 4, Equivalence classes, Groups, and Labellings ←←←←←␈↓






␈↓ ε_6␈↓ 
x



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


␈↓␈↓αA Naive Method␈↓
␈↓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␈α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␈α∞␈↓#
1␈↓#␈α∞as␈α∞well␈α∂as␈α∞the

topological␈α
symmetry␈α
defined␈α
above.


␈↓αA Better Method␈↓
␈↓␈↓α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␈α
Fig.

5,␈α
and␈α
that␈α
each␈α
distinct␈α
labelling␈α
corresponds␈α
to␈α
selecting␈α
one␈α
node␈α
from␈α
each␈α
type␈α
(see␈α
Fig␈α
6.)



␈↓␈↓∧(CHECK␈α
TO␈α
MAKE␈α
SURE␈α
THAT␈α
SYMBOLS␈α
ARE␈α
APPROPRIATE␈α
TO␈α
FIGURE)␈↓
Fig. 5␈↓α␈↓ ¬}→→ Figure 5, Orbits in the Decalin Skeleton ←←←←←␈↓
␈↓Fig. 6␈↓α␈↓ ∧+→→ Figure 6, Three Labellings of Decalin with 1 N and 9 C's. ←←←←←␈↓



␈↓Thus␈α
there␈α∞are␈α
three␈α
distinct␈α∞labellings␈α
(the␈α∞ten␈α
possible␈α
labellings␈α∞split␈α
into␈α∞three␈α
equivalalence

classes).



␈↓αComputing␈αorbits.␈↓␈αIn␈αgeneral,␈αthe␈αparts␈αof␈αa␈αsymmetry␈αobject␈αsplit␈αinto␈αdifferent␈αorbits␈α(sometimes

there␈α
is␈α
only␈α
one␈α
type,␈α
as␈α∞in␈α
the␈α
faces␈α
of␈α
a␈α
cube,␈α∞or␈α
the␈α
nodes␈α
of␈α
the␈α
cyclohexane␈α∞skeleton).␈α
 To

label␈αthe␈αparts␈α
of␈αan␈αobject␈αsuch␈α
that␈αone␈αis␈α
distinguished,␈αit␈αis␈αnecessary␈α
only␈αto␈αfind␈α
the␈αorbits



␈↓ ε_7␈↓ 
x



and␈αthen,␈αfor␈α
each␈αtype,␈αpick␈α
one␈αof␈αthe␈α
parts␈αin␈αthat␈α
type␈αarbitrarily.␈α Note␈α
that␈αif␈αthe␈αobject␈α
has

␈↓no␈α
symmetry␈α
each␈α
type␈α
has␈α
exactly␈α
one␈α
part␈α
in␈α
it.



It␈αis␈αvery␈αsimple␈αto␈αfind␈αthe␈αdifferent␈αtypes␈α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}.



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.␈α⊂ For␈α⊃a␈α⊂convention,␈α⊃the␈α⊂first

element␈α∞of␈α∞each␈α∞orbit␈α∞should␈α∞be␈α∞chosen␈α∂(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,␈αmany␈α
times␈α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␈αas␈α
in␈α
Table␈α
II.␈α
 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␈αvalid␈αif␈αand␈α
only

if␈αthe␈αstructure␈α"looks␈αthe␈αsame"␈αafter␈αits␈αnode␈αnumbers␈αare␈αpermuted.␈α 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␈α
disimilar␈α
structures.␈α
These␈α
permutations␈α
are␈αthe

ones␈α
that␈α
must␈α
be␈α
discarded.





␈↓ ε_8␈↓ 
x



␈↓α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␈α␈↓#
2␈↓#␈αthat␈αthe␈αresults␈αwill␈αbe␈αa␈αlist␈αof␈αall␈αdistinct␈αsolutions␈αto␈αthe␈αoriginal␈αproblem.␈α For

example,␈α
to␈α
label␈α
the␈αdecalin␈α
skeleton␈α
with␈α
1␈α
label␈α"N",␈α
1␈α
label␈α
"S"␈α
and␈α8␈α
labels␈α
"C",␈α
one␈αfirst␈α
labels

with␈α1␈α"N"␈αand␈α9␈α"blanks"␈αobtaining␈αthe␈α3␈αresults␈αin␈αfigure␈α7a.␈α (Fig␈α7a1,␈α7a2,␈α7a3).␈α  There␈αare

now␈α∪3␈α∀new␈α∪problems:␈α∪to␈α∀label␈α∪the␈α∪"blanks"␈α∀of␈α∪Figs.␈α∪7a1-3␈α∀under␈α∪their␈α∀respective␈α∪reduced

symmetry,␈αwith␈α
1␈α"S"␈α
and␈α8␈α
"C"'s.␈α  In␈α
Figs␈α7a1␈α
and␈α7a2,␈α
there␈αis␈α
no␈αsymmetry␈α
left␈αand␈α
so␈αeach␈α
of

the␈α"blanks"␈α
has␈αits␈αown␈α
orbit;␈αthus␈α
there␈αare␈α9␈α
distinct␈αlabellings␈α
apiece.␈α In␈αFig.␈α
7a3␈αthere␈αare␈α
5

orbits␈α
under␈α
the␈α
reduced␈α
symmetry,␈α
and␈α
thus␈α
there␈α
are␈α
5␈α
additional␈α
possiblities␈α
(Fig␈α
7b).
␈↓Fig. 7␈↓α␈↓ ¬:→→ Figure 7, Labellings with 1 N, 1 S, and 8 C's. ←←←←←␈↓


␈↓␈↓αORBIT RECURSION␈↓
␈↓There␈α
are␈α
3␈α
cases␈α
in␈α
the␈α
problem␈α
of␈α
1␈α
N,␈α
9␈α
C␈α
on␈α
the␈α
decalin␈α
skeleton.

     (case 1) 1 N goes to orbit {1,5,6,10}.

     (case 2) 1 N goes to orbit {2,4,7,9},

     (case 3) 1 N goes to orbit {3,8}.


------------------
␈↓#
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.

␈↓ ε_9␈↓ 
x



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

␈↓be␈α
9␈α
cases.␈α
(Table␈α
IV).
␈↓β_________________________________________________________________

                             Table IV.
                        (3 N's on a Decalin)

                                # 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

_________________________________________________________________



␈↓In␈α
some␈αof␈α
these␈αcases␈α
there␈αare␈α
more␈αthan␈α
one␈αpossibility␈α
(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,␈α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␈α
Fig␈α
8.
Fig. 8␈↓α␈↓ εQ→→ Figure 8, 1 N to orbit {1,5,6,10} ←←←←←␈↓



␈↓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.␈α Stick␈α
to␈αthe␈αoriginal␈α
plan--␈αit␈αis␈α
necessary␈αto␈αfind␈α
␈↓↓new␈↓␈αorbits␈αunder␈α
the




␈↓ ε⊂10␈↓ 
x



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

␈↓own␈α
orbit.␈α
 The␈α
"special␈α
case"␈α
described␈α
below␈α
under␈α"No␈α
Group"␈α
can␈α
be␈α
used␈α
directly␈α
to␈α
find␈αthe␈α
4

solutions␈α
(Fig␈α
9).
Fig. 9␈↓α␈↓ εZ→→ Figure 9, Second step of case 5 ←←←←←␈↓



␈↓Then,␈α
for␈αeach␈α
of␈α
these␈αsolutions,␈α
{3,8}␈αmust␈α
be␈α
labelled␈αwith␈α
1␈αN␈α
(and␈α
1␈αblank).␈α
  The␈αfinal␈α
result

is␈α
8␈α
possibilities␈α
for␈α
case␈α
5,␈α
none␈α
of␈α
which␈α
has␈α
any␈α
remaining␈α
symmetry.


␈↓α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.



␈↓␈↓α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




␈↓ ε⊂11␈↓ 
x



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.



␈↓A␈αk-subset␈α
of␈αa␈αset␈α
S␈α(a␈αk-subset␈α
is␈αa␈αsubset␈α
with␈αk␈αelements)␈α
either␈αcontains␈αan␈α
element␈αx␈αor␈α
not.

In␈αcase␈α3a,␈αone␈αfinds␈α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␈α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,

however,␈α⊂is␈α∂another␈α⊂trick.␈α∂ 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).






␈↓ ε⊂12␈↓ 
x



␈↓␈↓αspecial kludges for fast programs by Larry Masinter␈↓
␈↓             (this section to be written?)
             (this section to be written?)
             (this section to be written?)
             (this section to be written?)
             (this section to be written?)
             (this section to be written?)
             (this section to be written?)



␈↓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␈α∞1␈α∞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.␈α
 (Figure␈α∞9).␈α∞ Now␈α∞the␈α
group

reduces␈αeven␈αfurther,␈αand␈αone␈αgets␈αthe␈αtwo␈αresults␈αdepicted␈αin␈αFigure␈α9b.␈α 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␈α
impostors␈α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␈αan␈α
impostor--␈αthrow␈αthe␈α
bum␈αout.␈αFurthermore,␈α
every␈αimpostor␈αis␈α
detected

this␈α
way.␈α
 All␈α
that␈α
is␈α
necessary␈α
is␈α
that␈α
when␈α
doing␈α
these␈α
"lower␈α
level"␈α
labellings,␈α
that␈α
one␈αis␈α
careful

to␈αpick␈αthe␈α"first"␈αelement␈αof␈αeach␈αorbit␈αto␈αlabel␈αand␈αthe␈α"first␈αorbit"␈αwhen␈αthere␈αare␈αa␈αchoice␈αof

orbits.
␈↓β____________________________________________________________
                Table V
           cases for 2 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
____________________________________________________________


␈↓ ε⊂13␈↓ 
x



␈↓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.


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

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

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

3)␈α
Otherwise,

␈↓ ↓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␈αof␈αone␈αof␈αthe␈αlabel␈α
types,␈αpick␈αthe␈α"first"␈αnode␈αand␈α
label
␈↓ αXit␈α
with␈α
that␈α
label␈α
type.␈α
 This␈α
is␈α
the␈α
only␈α
distinct␈α
possibility.

␈↓ α(2)␈α∞Otherwise␈α∞if␈α∞there␈α∞are␈α∞two␈α∞of␈α
one␈α∞of␈α∞the␈α∞label␈α∞types,␈α∞label␈α∞the␈α∞first␈α
node
␈↓ αXwith␈α
that␈α
label␈αtype,␈α
calculate␈α
the␈α
reduced␈αsymmetry␈α
group␈α
and␈αnew␈α
orbits,
␈↓ αXand␈α⊂from␈α⊂each␈α⊂of␈α⊂the␈α⊃new␈α⊂orbits,␈α⊂pick␈α⊂the␈α⊂"first"␈α⊂node.␈α⊃ The␈α⊂solutions
␈↓ αXconsist␈α
of␈α
those␈α
possibilities␈α
(one␈α
for␈α
each␈α
new␈α
orbit).

␈↓ ε⊂14␈↓ 
x



␈↓ α(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␈α
is
␈↓ αXevery␈α
such␈α
labelling␈α
that␈α
satisfies␈α
this␈α
property.


␈↓␈↓ ∧\␈↓α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␈αFigure␈α
10,

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).
␈↓Fig. 10␈↓α␈↓ εa→→ Figure 10, Diels-Alder reaction ←←←←←␈↓



␈↓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.
Fig. 11␈↓α␈↓ ¬D→→ Figure 11, Diagram of Method of Generation ←←←←←␈↓






------------------
␈↓#
8␈↓#proposed␈α≤by␈α≤Jan␈α≤Simek,␈α≤Chemistry␈α≤Department,␈α≤Stanford␈α≥University.Research␈α≤Proposal
(unpublished),␈α
February,␈α
1973.

␈↓ ε⊂15␈↓ 
x



␈↓␈↓αMETHOD  ␈↓(see Figure 11)
␈↓␈↓α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.



␈↓α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␈α⊂(Figure␈α⊂12).␈α⊃ The␈α⊂atoms

remaining␈α
to␈α
be␈α
assigned␈α
are␈α
C␈↓#v2␈↓#O␈↓#v2␈↓#␈α
and␈α
the␈α
ring␈α
positions␈α
are␈α
numbered␈α
1,2,3,4.
Fig. 12␈↓α␈↓ εB→→ Figure 12, Diels-Alder Example A ←←←←←␈↓



␈↓␈↓αVerification␈α∀by␈α∀Enumeration.␈↓␈α∃The␈α∀results␈α∀of␈α∃of␈α∀the␈α∀labelling␈α∃procedure␈α∀can␈α∀be␈α∃verified␈α∀by

combinatorial␈α⊂counting␈α⊂techniques␈α⊂␈↓#
4␈↓#␈↓#
,␈↓#␈α⊂␈↓#
3␈↓#.␈α⊂ The␈α∂following␈α⊂derivation␈α⊂follows␈α⊂closely␈α⊂from␈α⊂that␈α∂in

␈↓Liu␈↓#
9␈↓#.

␈↓βCycle Index of Group=PG = 1/2(y␈↓#
4␈↓#␈↓#+ y␈↓#
2␈↓#␈↓#)
                               ␈↓#v1   ␈↓#v1

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

     = 1/2 (x␈↓#
4␈↓#␈↓#+ x␈↓#
4␈↓#␈↓#+ 4x␈↓#
3␈↓#␈↓#x␈↓#v2␈↓#+ 6x␈↓#
2␈↓#␈↓#x␈↓#
2␈↓#␈↓#+4x␈↓#v1␈↓#x␈↓#
3␈↓#␈↓#)
             ␈↓#v1   ␈↓#v2    ␈↓#v1      ␈↓#v1 ␈↓#v1     ␈↓#v2
------------------
␈↓#
9␈↓#Liu,␈α
Introduction␈α
to␈α
Comb.␈α
Math,␈α
McGraw-Hill,␈α
1968

␈↓ ε⊂16␈↓ 
x



␈↓β         + (x␈↓#
4␈↓#␈↓#+ x␈↓#
4␈↓#␈↓#+ 2x␈↓#
2␈↓#␈↓#x␈↓#
2␈↓#␈↓#)
             ␈↓#v1   ␈↓#v2    ␈↓#v1 ␈↓#v2

     = 1/2 2x␈↓#
4␈↓#␈↓#+ 2x␈↓#
4␈↓#␈↓#+ 8x␈↓#
2␈↓#␈↓#x␈↓#
2␈↓#␈↓#+ 4x␈↓#
3␈↓#␈↓#x␈↓#v2␈↓#+ 4x␈↓#
3␈↓#␈↓#x␈↓#v1␈↓#
             ␈↓#v1    ␈↓#v2    ␈↓#v1 ␈↓#v2    ␈↓#v1      ␈↓#v2

     = x␈↓#v1␈↓#␈↓#+ x␈↓#v2␈↓#␈↓# + 4 x␈↓#v1␈↓#␈↓#x␈↓#v2␈↓#␈↓# + 2x␈↓#v1␈↓#␈↓#x␈↓#v2␈↓#+ 2x␈↓#v2␈↓#␈↓#x␈↓#v1␈↓#
        ␈↓#
4   ␈↓#
4      ␈↓#
2 ␈↓#
2     ␈↓#
3      ␈↓#
3

showing that there are precisely these number of labellings:

        labels         #labellings

       C C C C            1
       S S S S            1
       C C S S            4
       C S S S            2
       C C C S            2




␈↓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.

(Figure␈α
13).
␈↓Fig. 13␈↓α␈↓ ¬↑→→ Figure 13, Octahedral Skeletal Framework ←←←←←␈↓
␈↓_________________________________________________________________

            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:

␈↓ ε⊂17␈↓ 
x



    #     {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)
   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,??                            ???????? fill in
      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)


Fig. 14␈↓α␈↓ αH→→ Figure X, Four labellings of Octahedral Skeleton with Labels (A A A A B B) ←←←←←␈↓


␈↓Example with Labels  A B C D E F
Case 1.  A --> orbit {1 4}
         A --> 1

␈↓ ε⊂18␈↓ 
x



   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
            B --> 2
      new group i
      new orbits {3} {4} {5} {6}
      CDEF --> 3,4,5,6
            4! = 24 labelling generable with no further
                 involvement of permutation group.
   Case 1␈↓#v2␈↓#. 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
         new orbits {3} {5} {6}
            DEF --> 3 5 6   6 labellings

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
      new orbits {3} {4} {5} {6}
         CDEF --> 3 4 5 6
            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
         new orbits {3} {4} {6}
            DEF --> 3 4 6   6 labellings

      Case 2.2.2. C --> orbit BB2
                C --> 3
         new group i
         new orbit {1} {4} {6}

␈↓ ε⊂19␈↓ 
x



            DEF --> 1 4 6   6 labellings

␈↓   Case 2.3. B --> B3
            B --> 3
      new group i
      new orbit {1} {4} {5} {6}
         CDEF 1 4 5 6      24 labellings

90 unique labelings all together.

Verification:  When all labels are different the total number of
labellings

     (# labels)!                6!
   = --------------     =  ----  =  90 labellings
     (size of group)            8



␈↓␈↓ ¬_␈↓αACKNOWLEDGEMENTS␈↓



␈↓We␈α
gratefully␈α
acknowledge␈α
the␈α
contributions␈α
of␈α
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.






















␈↓ ε⊂20␈↓ 
x