§ Weighted Burnside Lemma
- I'm learning the weighted burnside lemma as a preamble to polya enumeration.
- Define for a set with a group action , a weight function on the orbits . Said differently, we have a weight function such that for all and .
- We wish to count the orbits of weighted by the weight function (where is a commutative ring). So we wish to find .
- Recall that Burnside tells us that:
- We replace cardinality with weight, giving us the statement:
- In english, this reads: for each orbit in , pick an equivalence class representative . The sum of weights of the representatives equals the average over of the fixpoint-weights.
- We begin by considering the LHS:
- We switch the order of summation to get where is the Iverson bracket --- it evaluates to 1 if and if .
- We pull the constant out to get .
- We see that is the cardinality of the stabilizer of , written as . So we write this as .
- By orbit stabilizer, we use . Thus, we get .
- Since the set of orbits partitions , we write the above as
- Since is the orbit of , we replace with , giving .
- Since the weight is constant on orbits, we replace by giving .
- We pull the inner terms out giving .
- Since , we get which simplies to .
- We are done, since we have shown that .
§ Example, Unweighted
- Suppose we squares acted on by rotations . It takes the square:
to the squares:
e r r^2 r^3
1 2 | 4 1 | 4 2 | 4 3
3 4 | 3 2 | 3 1 | 1 2