Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that . One way to motivate a combinatorial proof is to [...]

Read Full Post »

GILA V: The Polya enumeration theorem and applications

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors (represented by variables [...]

Read Full Post »

GILA III: The orbit-counting lemma and baby Polya

The orbit-stabilizer theorem implies, very immediately, one of the most important counting results in group theory. The proof is easy enough to give in a paragraph now that we’ve set up the requisite machinery. Remember that we counted fixed points by looking at the size of the stabilizer subgroup. Let’s count them another way. Since [...]

Read Full Post »

GILA I: Group actions and equivalence relations

Sometimes I worry that I should be more consistent or more lenient about the background I expect of my readers. (Readers, I have to admit that I still don’t really know who you are!) Considering how important I think it is that mathematicians value communicating their ideas to non-specialists (what John Armstrong calls the Generally [...]

Read Full Post »