Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

[Tutorial] From Burnside to Polya: A Short Introduction to Group Theory

Revision en1, by Zhtluo, 2023-08-03 11:02:31

Consider this famous necklace counting problem:

Assume a necklace can be made with $$$n \ (1\le n\le 10^5) $$$ beads. Each bead can be painted with one of the $$$ k\ (1\le k\le 10^5) $$$ colors. We consider two necklaces the same if after rotating and flipping they look identical. How many different necklaces are there in total?

The solution to this problem is often represented in terms of group theory jargon. In this post we will try to explain and demystify the process.

Just wrote a short tutorial on Polya's Theorem as I tried to figure out how to explain it to people without background on group theory. I am not exactly a mathematician so there might be errors and inaccuracies. Any feedback and suggestion would be greatly appreciated. Enjoy :)

https://zhtluo.com/cp/from-burnside-to-polya-a-short-introduction-to-group-theory.html

Tags polya enumeration, maths, combinatorics, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Zhtluo 2023-08-03 11:02:31 1013 Initial revision (published)