If you want to count the number of tiles in your floor, you probably will not count each one individually, but be lazy and look for a short cut. For instance, if the room is rectangular and walking part of its perimeter you discover there are 8 tiles along the north wall
and 6 tiles along the west wall, you expect 48 tiles total. This short cut employs the power of symmetry. (And a bit of algebra.)
In this talk, I'll discuss a powerful counting method that is often referred to as Burnside's Lemma, although it goes back to Frobenius (1887) and Cauchy (1845). This method uses symmetry and a bit more algebra. I will illustrate the lemma by counting necklaces strung with colored beads. Other applications include counting: isomers of a given molecule; crystal structures; chords in a twelve-tone musical scale; Latin squares; finite automata .
Attachment | Size |
---|---|
Vazirani 3.pdf | 1.83 MB |