image/svg+xml
Math3012AppliedCombinatorics
Goal:How do we countwhen symmetries arecomplicated?
How many wayscan Buzz decoratethis hexagon?
samesamesamedifferent
Permutation Groups
have all compositionshave all inverses
Groups can act on sets
Burnside's Lemma
If group G acts on X then
The number of distinct decorations is the average number of decorations fixed by group members.
(012)(3)(45)
0
3
4
5
Polya's cycle index
(012)(3)(45)
(0)(12)(34)(5)
G=Symmetries of
Polya's Enumeration
If G acts on n then the numberof inequivalent functions n→mmodulo G has generating function
Counting Isomers
Counting Isomorphism Classesof Graphs
xylenol
Every permutation can be written uniquely as the product of disjoint cyclic permutations
2
1
(0)(1)(2)(3)(4)(5)
(012345)
(024)(135)
(03)(14)(25)
(042)(153)
(054321)
(0)(15)(24)(3)
(01)(25)(34)
(02)(1)(35)(4)
(03)(12)(45)
(04)(13)(2)(5)
(05)(14)(23)
Dihedral Group Order 12Symmetries of the Hexagon