Summer of Math Exposition

Presented by 3Blue1Brown 3blue1brown

Pólya's enumeration theorem

Audience:

Tags: combinatoricsalgebraenumerative-combinatoricsgroup-theorygenerating-functionspermutationsymmetryfinite-group-theory

How many ways can you colour an 8x8 grid using two colours, considering two colourings as the same if one can be obtained from the other by a rotation or reflection of the grid? In this essay, I present Pólya’s enumeration theorem, which provides a systematic method for answering such questions. I wrote it as part of my university coursework so it is aimed at undergraduate students familiar with basic group theory and combinatorics. In particular, in Example 2.2, I present a new solution to a slight variant of an interesting enumeration problem studied by 3Blue1Brown in his 'Olympiad Level Counting' video: namely how many subsets of {1, 2, ..., 2025} have sum divisible by 5?


Analytics

2.75 Overall score*
77 Rank
4 Votes
2 Comments

Comments

2

We should be careful with the terminology. Double counting is used in several ways in both the concept of counting an object twice, as well as two different methodologies to count a set which are different and may cause confusion. I think in introducing the problem, using the example of a graph in a straight line is a simple demonstration and can be added with a simple triangular graph to illustrate why it’s slightly different that we might want to consider additional structure and why it could be useful in this instance.

The text and arguments are also slightly too complex for an undergraduate to read through easily as they would need to very familiar with group theory and would be more suited for a beginner graduate level and this might not click very easily in terms of new connections to a person who is not too familiar with the subject in terms of introducing a new field. In this instance, we may sacrifice some mathematical rigour to try to communicate the ideas of the proof forwards to the reader.

3.5

Pretty difficult to read. Feels like one of those handouts by a professor. A student can power through it if needed, but I can’t see those students gaining much interest in the subject.